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

Добрый день всем!
Сижу ломаю голову как сделать движение точки по лабиринту, причем из одной его точки в другую… Пусть «лабиринт» простой, никаких тупиковых и запутанных ходов нет, представляет собой поле из клеток 175х175, точка, соответственно, 1 клетку.
Проблема в том, что на поле будет множество точек, разные маршруты и «конкуренция» за дорожку, по которой идти, поэтому простой обход препятствий не подходит, надо прокладывать оптимальные маршруты в зависимости от ситуации…
Изложение, скорее сумбурное, но прошу меня простить)
pix.am/z9r5/
Синей точке надо пройти к зеленой следуя между серых линий. Она знает координаты себя и координаты зеленой точки.
Спасибо!
upd. Для задачи можно дать знание точке, что рядом с ней забор, так же она может касаться забора этого, да и координаты, разве они не дополняют картины? Точка знает координаты себя в любой момент времени.
upd.2 Все частицы имеют одинаковый размер, пропускная способность тоннеля не меняется, может в дальнейшем только ширина меняться может меняться, и то, с перезапуском системы.
  • Вопрос задан
  • 2984 просмотра
Пригласить эксперта
Ответы на вопрос 5
Vlad911
@Vlad911
Если все проходы между серыми линиями имеют незначительную ширину, имеет смысл преобразовать эту карту в граф. А дальше Алгоритм А-стар (A*), где эвристика будет как раз функцией ситуации.
Ответ написан
Lerg
@Lerg
Defold, Corona, Lua, GameDev
Если есть движущиеся препятствия, то либо на каждом шаге вычисляют A*, либо используют D*.
Ответ написан
EndUser
@EndUser
В пресловутом колоботе есть задачка на проезд между заборами.
Но там, простите, есть нормальное объектное окружение.
В данном случае функция radar(), которая возвращает расстояние и тип ближайшего объекта.

Ситуация, которую вы нагородили… Если без радара, то наверное решать модификацией алгоритма Dijkstra — а именно заливка восьмисвязной области краской из ведра.
Ответ написан
Комментировать
Zigmar
@Zigmar
Посмотрите как это реализовано в игрушке Liquid War. По-моему там решается задача похожая на вашу — тысячи точек (которые не могут проходить сквозь друг друга) ищут кратчайший путь на карте со сложной топологией.
Ответ написан
Комментировать
@crazylammer
Crowd motion planning. Возможно, найдется что-нибудь подходящее.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы