Разгоняем А*

Темы, связанные с проектированием и программированием roguelike-игр

Модераторы: Sanja, Максим Кич

Ответить
keyj
Сообщения: 3
Зарегистрирован: 22 авг 2007, 13:25

Разгоняем А*

Сообщение keyj » 22 авг 2007, 14:02

Можно ли ускорить поиск с помощью алгоритма A* ?
Можно если применить более качественную эвристическую функцию.

Рассмотрим поиск пути в лабиринте, где любой узел S задается координатами (x, y) и перемещение разрешено только по горизонтали или вертикали.

Обозначим:
s0 - начальный узел,
g - целевой узел,
h - эвристическая функция.

Определим эвристическую функцию h для произвольного узла s как:
h(s) = |s.x - g.x| + |s.y - g.y|, где g - целевой узел.

Данная эвристическая функция позволяет алгоритму A* находить оптимальное решение. Но h(s) недооценивает стоимость пути, если приходиться обходить препятствия. Как следствие при поиске открывается большее количество узлов.

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

Обозначим:
m - ориентирный узел,
d(s, m) - кратчайшее расстояние от узла s до ориентирного узла m.

Определим функцию dg для произвольного узла s как:
dg(s, m) = |d(s, m) - d(g, m)|, где m - ориентирный узел, g - целевой узел.

Определим новую эвристическую функцию h-new для произвольного узла s как:
h-new(s) = max{h(s), dg(s, m1), ... , dg(s, mN)}, где m1, ... , mN - ориентирные узлы.

Качество эвристической функции h-new(s) зависит от выбора ориентирных узлов. Имеет смысл располагать ориентирные узлы по периметру лабиринта.

Посмотрим как это работает на практике:

..............
.2xxxxxx....3.
.01....x.G....
..xxxxxx......
..............

x - непроходимый пункт
0 - начальный пункт
G - целевой пункт
3 - ориентирный пункт

Необходимо определить какой пункт предпочтительнее 1 или 2. Стандартная эвристическая функция даст нам оценку: h(1) = 7, h(2) = 9. Из чего следует что выбрать надо пункт 1.

Рассчитаем h-new(1) и h-new(2):

dg(1, 3) = |d(1, 3) - d(G, 3)| = |15 - 4| = 11
dg(2, 3) = |d(2, 3) - d(G, 3)| = |13 - 4| = 9

h-new(1) = max{h(1), dg(1, 3)} = max{7, 11} = 11
h-new(2) = max{h(2), dg(2, 3)} = max{9, 9} = 9

Видно, что эвристическая функция h-new(s) дает лучшую оценку, чем h(s).

Более подробно вопрос рассмотрен здесь:
http://research.microsoft.com/research/ ... ort&id=986

ADB

Сообщение ADB » 22 авг 2007, 21:26

А работающий пример выложить можешь?

Аватара пользователя
Maelstrom
Мастер
Сообщения: 2062
Зарегистрирован: 26 ноя 2006, 14:19
Откуда: г. Усть-Кирдык
Контактная информация:

Сообщение Maelstrom » 23 авг 2007, 04:55

А я вообще забыл что такое A*...
Айв кнгенгах Йог-Сотот

ADB

Сообщение ADB » 23 авг 2007, 07:51

"А-звезду" частенько используют в современных компьютерных играх, когда нужен быстрый и несложный поиск пути.
keyj, а пример кода не выложишь?

darhark
Сообщения: 57
Зарегистрирован: 02 май 2007, 23:18

Сообщение darhark » 23 авг 2007, 07:59

Опля! Ценно. Пасибки.

v0l0sat1y
Сообщения: 59
Зарегистрирован: 11 мар 2007, 13:21
Откуда: Беларусь, Минск
Контактная информация:

Сообщение v0l0sat1y » 23 авг 2007, 21:46

Епт, многа букав, ниасилил.
А вообще есть очень хороший совет: оптимизируйте то, что работает медленнее всего и ДЕЙСТВИТЕЛЬНО замедляет программу. Поэтому меня и прикалывают попытки зафигачить какой-нибудь новомодный оптимизированный алгоритм в рогалик. Хотя потом можно лихо понтануццо где-нибудь. Типа "я представил лабиринт в виде графа и сча юзаю Дейкстру для поиска пути и все это счастье работает за NlogN". Вопрос: нахера? Или вам надо, чтобы оно летало на первом Pentium'e?
So far, so good... So what?

MazeCrawl roguelike
http://mazecrawl.com

Аватара пользователя
Maelstrom
Мастер
Сообщения: 2062
Зарегистрирован: 26 ноя 2006, 14:19
Откуда: г. Усть-Кирдык
Контактная информация:

Сообщение Maelstrom » 24 авг 2007, 05:28

Вопрос: нахера? Или вам надо, чтобы оно летало на первом Pentium'e?
Просто есть те, которые делают игры, а есть те, которые понтуются кодом :)
Айв кнгенгах Йог-Сотот

Аватара пользователя
Максим Кич
Администратор
Сообщения: 1642
Зарегистрирован: 03 дек 2006, 20:17
Откуда: Витебск, Беларусь
Контактная информация:

Сообщение Максим Кич » 24 авг 2007, 08:14

v0l0sat1y писал(а):Епт, многа букав, ниасилил.
А вообще есть очень хороший совет: оптимизируйте то, что работает медленнее всего и ДЕЙСТВИТЕЛЬНО замедляет программу. Поэтому меня и прикалывают попытки зафигачить какой-нибудь новомодный оптимизированный алгоритм в рогалик. Хотя потом можно лихо понтануццо где-нибудь. Типа "я представил лабиринт в виде графа и сча юзаю Дейкстру для поиска пути и все это счастье работает за NlogN". Вопрос: нахера? Или вам надо, чтобы оно летало на первом Pentium'e?
Оптимизация действительно имеет смысл только тогда, когда в ней появляется необходимость. К примеру лось, скачущий по Брезенхему, вполне нормально пашет, когда он один. А пересчитай полсотни таких лосей на кадр хотя бы при 50 fps и уже как-то кажется, что не такое это резвое животное. И надо как-то чистить алгоритм, чтобы не делать лишних итераций.

Скорость нахождения пути в рогаликах вообще особенно не должна смущать. Тут интереснее будет найти какие-нибудь весовые коэффициенты, чтобы монстры могли более адекватно оценивать ситуацию и бежать не туда, где ближе, а туда где больше шансов сделать своё грязное дело.

С другой стороны, нерациональные решения имеют кумулятивный эффект и в момент икс, когда вдруг окажется, что всё это тормозит на двухъядерном монстре, будет весьма проблематично распутывать клубок из собственных недочётов, чтобы выдрать необходимую скорость.

А уровень в виде графа в принципе полезно представлять. Но не все могут себе это позволить :)
Dump the screen? [y/n]

keyj
Сообщения: 3
Зарегистрирован: 22 авг 2007, 13:25

Сообщение keyj » 24 авг 2007, 08:45

v0l0sat1y
Про оптимизацию согласен на 100%. Но когда прижмет и потребуется что-то лучшее, часто начинаешь изобретать велосипед с нуля из-за отсутствия информации о других решениях.

ADB
Примером пока не смогу порадовать. Если руки дойдут, выложу обязательно.

Ответить

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и 37 гостей