Я работаю в последние недели в многопользовательской игре HTML5, используя nodejs
и websockets
.
Я немного застрял в этой проблеме. Представьте, что у меня есть эта карта плитки, реализованная с массивом (как показано ниже).
1 или коричневые плитки - на пути есть препятствие, и игрок не может пройти через него.
0 или зеленые плитки - это бесплатные пути, где игроку разрешено перемещаться.
Доступ к любому фрагменту на карте, вызвав:
array[x][y]
Я хотел бы создать самый быстрый алгоритм, чтобы узнать самый короткий маршрут (если есть) между двумя точками карты. Как вы подходите к этой проблеме? Я знаю, что это обычная проблема.
Пример:
Игрок в позиции (1,7) стреляет пулей с некоторым ИИ, который будет направлен против вражеского игрока в позицию (6,0). Bullet должен рассчитать кратчайший маршрут между двумя игроками, и если он не будет просто взорваться от стены.
Вопрос:
Как эффективно найти кратчайший маршрут между двумя точками?