2Д Игра Долгая дорога домой: Поиск пути

[intmain]

Написал программу которая рисует шарики разного цвета в 2д.
Эти шарики элементы карты размером 40 на 30 шаров.
Один шарик имеет размер 16 на 16 точек, поэтому вся карта видна в одном окне.
Есть шарик S - start начало пути от куда нужно двигаться , есть шарик E - End конец пути куда нужно прийти. Зеленый шарик - свободный проход. Красный - преграда. Желтый шарик – для прорисовки пути.

Ну и вопрос на засыпку как мне теперь все это заставить работать как задумано? С чего начать писать алгоритм поиска пути ?

[BDA]

http://ru.wikipedia.org/wiki/Волновой_алгоритм
Пример работы
(путь из одной точки в другую по нарисованной карте, с ходьбой только по вертикали или горизонтали)

[intmain]

BDA, спасибо.
Теперь придется голову поломать как его написать.

[s-andriano]

Я бы рекомендовал определиться, какими свойствами должен обладать алгоритм поиска пути.
В играх в основном используются два варианта:
- если нужно быстро, то A*,
- если нужно наверняка - алгоритм Дейкстры.
Частный случай алгоритма Дейкстры, когда цена шага везде, где проходимо, одинакова, называется волновым алгоритмом.

[intmain]

быстрым да. предрасчитанная карта перемещений на этапе загрузки из любого в любой квадрат.

[s-andriano]

Сообщение от intmain

быстрым да. предрасчитанная карта перемещений на этапе загрузки из любого в любой квадрат.

"предрасчитанная карта перемещений из любого в любой квадрат" - это сильно.
Но абсолютно не нужно.
Если карта не очень велика, расчет в реальном времени не займет много времени, а если велика, то результаты "предрасчета" все равно не поместятся в оперативную память (а, возможно, и на диск).

Арифметику в школе проходили?
Тогда считаем.
Помнится, когда делал свою реализацию алгоритма Дейкстры (тогда я еще не знал, что Дейкстра, оказывается, изобрел этот алгоритм еще до меня) на процессоре 166-Мгц он обсчитывал карту (находил пути из одной точки до всех остальных) за 0.03 с. Это было на карте 256х256 клеток.
На современных процессорах это будет порядка 0.002-0.0025 с. Если принять, что допустимым временем расчета является 1 с, то можно в реальном времени обсчитывать карту примерно 6000х6000.
Пар клеток: 36000000.
Среднюю длину пути берем равной 3000.
В каждой точке пути записываются 2 координаты, пусть по 2 байта.
Итого 36 000 000 х 3 000 х 2 х 2 = 432 000 000 000 байт или 432 Гбайта.
На современный жесткий диск это, конечно, поместиться, но вот за 1 с прочитать это с него абсолютно нереально.

Т.е. вывод: считать всегда быстрее, чем считывать с диска предрассчитанное.

[Arigato]

Есть пример оптимизированного классического рекурсивного поиска пути, вот что выдала программа для рандомного лабиринта:

labirint.PNG

Оптимизация касается двух аспектов:
1. Всегда стремимся двигаться в сторону выхода.
2. Если расстояние до выхода больше, чем уже найденное расстояние, то прерываем поиск.

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

Пример на Делфи в аттаче.

[s-andriano]

В этом оптимизированном алгоритме непонятно, откуда взялись шаги с номерами от 36 до 52, если найденное расстояние равно 35.

2. Вообще-то так работает любой алгоритм, а не только оптимизированный. Но, судя по рисунку, почему-то, как раз "оптимизированный" работает не так.

[Arigato]

Сообщение от s-andriano

В этом оптимизированном алгоритме непонятно, откуда взялись шаги с номерами от 36 до 52, если найденное расстояние равно 35.

Видимо, где-то не туда свернул и пришел к финишу за 53 шага, потом пришел по другому пути уже за 34 шага.
Запустил еще раз, получил такое:

labirint.PNG

Тут как повезет, если выход находится, скажем, внизу слева, то пойдя вниз можно долго плутать и попасть в тупик или прийти к выходу длинным путем, тогда надо проверять путь влево. Знать заранее, куда идти выгоднее, невозможно.

Сообщение от s-andriano

Вообще-то так работает любой алгоритм, а не только оптимизированный. Но, судя по рисунку, почему-то, как раз "оптимизированный" работает не так.

Классический вариант рекурсивного поиска пути вообще ничего не отсекает, он проходит по всем доступным клеткам.

[intmain]

это сильно.

Это была шутка. Понятно что я сохранять такое количество данных не буду.
У меня слишком убогая игра чтобы таскать такой багаж с сохраненными путями )

Есть пример оптимизированного классического рекурсивного поиска пути, вот что выдала программа для рандомного лабиринта:
Пример на Делфи в аттаче.

Сяб, покурю и его тоже. Но пока на Альфа Центавру смотрю, курю.