Манипулирование картами

Question

Учитывая набор поэтажных планов (в Autocad, SVG или любом другом формате, который должен быть ...), я хотел бы программно генерировать направления из точки А в точку Б. В основном я хотел бы сказать: «Как мне получить из комнаты 101 в комнату 143? (или для тройных бонусных баллов, из комнаты 101 в комнату 323). У кого-нибудь есть идеи, как это сделать? На данный момент я довольно независим от языка, хотя лучше всего знаю C (++), Erlang, PHP и Python. Я понимаю, что это высокий заказ.

Спасибо!

Answer 1

Общий термин для этого: pathfinding . Задача широко изучена для двумерных диаграмм. Я бы разбил проблему на следующие разделы:

1. Преобразование CAD модели пола в простую модель комнат, дверей, прихожих.
2. Запуск алгоритма поиска пути на этом этаже от источника к месту назначения с ограничениями для движения человека.
3. Преобразуйте результаты в текстовые указания (поверните направо, идите прямо и т. Д.). Может быть полезным добавление ориентиров

Для нескольких этажей вы можете просто использовать одноэтажную реализацию и перейти от (например, 104) к лестнице 1-го этажа, к лестнице 3-го этажа - к 311. Преобразование чертежа САПР в семантически полезный формат кажется наиболее сложным. шаг ко мне.

Answer 2

Я знаю, что вы хотите использовать php, но я рекомендую python и networkx.Вы должны преобразовать свое здание в набор (источник, пункт назначения, стоимость), а затем запустить либо TSP (как упоминалось до сих пор), либо A * или Dijkstra

Answer 3

читайте об алгоритме коммивояжера Существует бесконечное количество путей из точки А в точку Б. Вы ищете самый короткий?какое у вас транспортное средство?ты умеешь летать или тебя заставляют ходить или водить?это факторы, определяющие решение.