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

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

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

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

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