Просчет маршрута движения «точки»

Question

[Андрей]

Добрый день всем!
Сижу ломаю голову как сделать движение точки по лабиринту, причем из одной его точки в другую… Пусть «лабиринт» простой, никаких тупиковых и запутанных ходов нет, представляет собой поле из клеток 175х175, точка, соответственно, 1 клетку.
Проблема в том, что на поле будет множество точек, разные маршруты и «конкуренция» за дорожку, по которой идти, поэтому простой обход препятствий не подходит, надо прокладывать оптимальные маршруты в зависимости от ситуации…
Изложение, скорее сумбурное, но прошу меня простить)
pix.am/z9r5/
Синей точке надо пройти к зеленой следуя между серых линий. Она знает координаты себя и координаты зеленой точки.
Спасибо!
upd. Для задачи можно дать знание точке, что рядом с ней забор, так же она может касаться забора этого, да и координаты, разве они не дополняют картины? Точка знает координаты себя в любой момент времени.
upd.2 Все частицы имеют одинаковый размер, пропускная способность тоннеля не меняется, может в дальнейшем только ширина меняться может меняться, и то, с перезапуском системы.

Answer 1

[Vlad911]

Если все проходы между серыми линиями имеют незначительную ширину, имеет смысл преобразовать эту карту в граф. А дальше Алгоритм А-стар (A*), где эвристика будет как раз функцией ситуации.

Comments

[Vlad911]

Имею ввиду, что ширина прохода не существенна в сравнении с длиной коридора и тогда возможный путь заменить, к примеру линией, грубо говоря проходящей по середине туннеля.

В противном случае, необходимо геометрию привести к тайлам и использовать алгоритм заливки.

[Андрей]

Про линию я уже думал, но тогда выйдет так, что по ней сможет двигаться только одна точка, а нужно множество, причем в режиме конкуренции ( они запускаются в параллельных потоках )
Можно сделать, конечно, задачу наоборот, разрешить им двигаться только по маршруту определенного «цвета», тогда задача упростится, в принципе. Под мою задачу, наверно, подойдет) Из всего этого должно выйти «метро», вернее его станция…

[Vlad911]

Может адаптировать муравьиный алгоритм? Только вот с распараллеливанием пока не очень ясно. Может быть в личку? скайпонуться было бы интересно.

[Vlad911]

а частицы, например, имеют разный размер или одинаковый? нельзя ли тут принцип неопределенности использовать если имеют разный. Иными словами разная ли пропускная способность туннеля для разного типа частиц, допустим?

[Виталий Желтяков]

Я тоже за алгоритм А*. Это очень простой алгоритм, который справиться с вашей задачей.

Вообще не понимаю, когда вместо давно известных алгоритмов придумывают свои велосипеды с квадратными колёсами.

[Андрей]

Когда знаешь куда копать, конечно, будешь использовать уже известные алгоритмы. Вы можете составить запрос в гугл, который выдаст ссылку на алгоритм?

[Sergey Lerg]

www.google.ru/search?q=A*+pathfinding

[AlexanderG]

Pathfinding+algorithm на английском.
Алгоритм поиска пути на русском. Первая ссылка ведет на статью в Википедии, в которой есть список алгоритмов, чтобы копать дальше.

Answer 2

[Sergey Lerg]

Если есть движущиеся препятствия, то либо на каждом шаге вычисляют A*, либо используют D*.

Comments

[Vlad911]

вы говорите о вычислении эвристической функции.

Answer 3

[EndUser]

В пресловутом колоботе есть задачка на проезд между заборами.
Но там, простите, есть нормальное объектное окружение.
В данном случае функция radar(), которая возвращает расстояние и тип ближайшего объекта.

Ситуация, которую вы нагородили… Если без радара, то наверное решать модификацией алгоритма Dijkstra — а именно заливка восьмисвязной области краской из ведра.

Answer 4

[Zigmar]

Посмотрите как это реализовано в игрушке Liquid War. По-моему там решается задача похожая на вашу — тысячи точек (которые не могут проходить сквозь друг друга) ищут кратчайший путь на карте со сложной топологией.

Answer 5

[crazylammer]

Crowd motion planning. Возможно, найдется что-нибудь подходящее.