Rambler's Top100
  Навигация :
Оглавление
Новости (Архив)
Об этом проекте
О программе GM
Скачать
Документация
Русский Help
Обучение
Примеры
Ресурсы
Ссылки
Прямая связь
  Статьи:
Platform
Platform v4.2
Maze
  Статистика :




Волновой алгоритм (GM 6.1)


Автор © 18.12.2005 Виталий Дружин (Vit)

Поиск пути

Сразу оговорюсь что эта статья не претендует на "правильность", это просто рассказ о том как я делал поиск пути.
Так же буду стараться приводить ключевые куски кода.
В GM существует неплохой встроенный A алгоритм поиска пути, но мне захотелось сделать свой подобный из простого интереса :)

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

Теперь вкратце обьясню методы работы подобных алгоритмов.
Создаётся поле n на m числовых элементов :

11111222111
11111121111
11111121111
11011111111
11111111171
11111111111

Которое представляется как двумерный массив, в нашем случае сетка.
В котором какие то числа (1) обозначают проходимые поля, какие то (2) препятствия, какие то (7) позицию персонажа, и какие то (0) позицию куда ему надо прийти обходя препятствия (числа могут быть любые).
От позиции куда надо прийти (цели), мы "рапространяем волну", т.е. в те соседние с позицией целью ячейки массива где нет препятствия мы ставим значения на 1 больше чем в ячейке позии цели, т.е. если там 0, то во всех соседних будет 1.
Следующим шагом мы просматриваем те ячейки в которых находится 1, ставим в соседние к этим ячейкам значения ещё на единицу большее т.е. 2. И так до тех пор пока не встретится ячейка с числом персонажа.
Существует два варианта распространения волны, первый - просматриваются все элементы массива (построчно), если обнаружилось в ячейке число равное значению счётчика интераций (сначала волна ищет 1 потом 2 потом 3 и т.д.), то в соседние ставим на 1 больше.
Второй вариант - все элементы массива не просматриваются, а запоминаются те ячейки массива на которые накатила "волна" в последнем шаге, и следующая волна распространяется уже из этих ячеек.

Второй вариант мне показался более привлекательным, но более сложным, тем не менее делаем именно его :)

Для начала я создал сетку, присвоил всем её элементам значение, и заставил рисовать эти значения :

Create Event:
setka=ds_grid_create(20,20)
ds_grid_clear(setka,-1)

Draw Event:
//Рисуем значения сетки
for (i=0; i<ds_grid_width(setka); i+=1)
{
    for (j=0; j<ds_grid_height(setka); j+=1)
    {
      draw_text((i*30),(j*30),ds_grid_get(setka,i,j))
    }
}

(Файл 1.gm6)

После проверки работоспособности присвоил элементам позиции персонажа и позиции-цели значения 999 и 1 соответственно.
ds_grid_set(setka,0,1,999)  //Начальная позиция
ds_grid_set(setka,6,6,1)  //Точка назначения

Потом сделал две очереди для хранения позиций X и Y элементов конца волны.
И попробовал присвоить соседним с целью ячейкам другие значения:

//Две очереди для хранения позиций старта
och_x=ds_queue_create()
ds_queue_enqueue(och_x,8)

och_y=ds_queue_create()
ds_queue_enqueue(och_y,8)

//Назначаем соседним с точкой назначения позициям другую величину
//Передаём значения переменной и удаляем позиции очереди
temp_x=ds_queue_dequeue(och_x) //Присваиваем переменной значение из очереди и его удаляем оттуда
temp_y=ds_queue_dequeue(och_y)

sh1=1
if(temp_x>0) //Ограниения выхода за пределы сетки
{
  if(ds_grid_get(setka,temp_x-1,temp_y)==0)
    {
      ds_grid_set(setka,temp_x-1,temp_y,sh1)
    }
}

if(temp_y>0)
{
  if(ds_grid_get(setka,temp_x,temp_y-1)==0)
    {
      ds_grid_set(setka,temp_x,temp_y-1,sh1)
    }
}

if(temp_x<ds_grid_width(setka)-1)
{
  if(ds_grid_get(setka,temp_x+1,temp_y)==0)
    {
      ds_grid_set(setka,temp_x+1,temp_y,sh1)
    }
}

if(temp_x<ds_grid_height(setka)-1)
{
  if(ds_grid_get(setka,temp_x,temp_y+1)==0)
    {
      ds_grid_set(setka,temp_x,temp_y+1,sh1)
    }
}

Впоследствии сетку и очереди я сделал глобальными.
К сожалению я не могу описывать как я создал событие "create" и т.п., статья расчитана на более менее подготовленных людей... :)

Теперь самый главный момент.
Нам надо сделать цикл, который собственно и будет распространять волну.
Вышенапечатанный код помещаем в скрипт, с некоторыми дополнениями:

//Назначаем соседним с точкой назначения позициям другую величину
//Передаём значения переменным и удаляем позиции очереди
temp_x=ds_queue_dequeue(och_x)
temp_y=ds_queue_dequeue(och_y)

if(temp_x>0) //Ограниения выхода за пределы сетки
{
 if(ds_grid_get(setka,temp_x-1,temp_y)==-1)
    {
      ds_grid_set(setka,temp_x-1,temp_y,ds_grid_get(setka,temp_x,temp_y)+1)
      ds_queue_enqueue(och_x,temp_x-1) //Добавляем точку старта в очередь
      ds_queue_enqueue(och_y,temp_y)
    }
 else if(ds_grid_get(setka,temp_x-1,temp_y)==998){konec=true;break} //Нашли персонажа
}

if(temp_y>0)
{
  if(ds_grid_get(setka,temp_x,temp_y-1)==-1)
    {
      ds_grid_set(setka,temp_x,temp_y-1,ds_grid_get(setka,temp_x,temp_y)+1)
      ds_queue_enqueue(och_x,temp_x)
      ds_queue_enqueue(och_y,temp_y-1)
    }
  else if(ds_grid_get(setka,temp_x,temp_y-1)==998){konec=true;break}
}

if(temp_x<ds_grid_width(setka)-1)
{
  if(ds_grid_get(setka,temp_x+1,temp_y)==-1)
    {
      ds_grid_set(setka,temp_x+1,temp_y,ds_grid_get(setka,temp_x,temp_y)+1)
      ds_queue_enqueue(och_x,temp_x+1)
      ds_queue_enqueue(och_y,temp_y)
    }
  else if(ds_grid_get(setka,temp_x+1,temp_y)==998){konec=true;break}
}

if(temp_x<ds_grid_height(setka)-1)
{
  if(ds_grid_get(setka,temp_x,temp_y+1)==-1)
    {
      ds_grid_set(setka,temp_x,temp_y+1,ds_grid_get(setka,temp_x,temp_y)+1)
      ds_queue_enqueue(och_x,temp_x)
      ds_queue_enqueue(och_y,temp_y+1)
    }
  else if(ds_grid_get(setka,temp_x,temp_y+1)==998){konec=true;break}
}

Главной фишкой является то что мы сразу же записываем в очереди только что "оцифрованную" клетку.
Делаем событие нажатия кнопы, куда помещаем цикл:

konec=false
while(konec==false)
{
   script_execute(d)
}

(Файл 10.gm6)

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

if(ds_queue_empty(och_x)){konec=true;break}

Многие решают этот момент через счётчик повторений, т.е. если цикл прокрутился болле допустим 300 раз, и не нашёл пути, тады выход из него нафиг :) Но вышеописанное решение на мой взгляд гораздо лучше.

(Файл 14.gm6)

Впринципе всё ...
Нам остаётся только заставить персонажа идти в соседнюю клетку которая имеет наименьшее значение...
Это может реализоваться различными способами, я сделал так:
(Файл 20.gm6)

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

if (abs(клетка_волны.x - клетка цели.x) - abs(клетка_НАЧАЛА_волны.x - клетка цели.x) > 7)
{прекращаем волну в этом направлении}

7 зависит от размера обходимых препятствий.

Ну вобщем то подходить к концу статья и третья бутыль пыва :)

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

Так или иначе - что непонятно, какие баги, мнения, улучшения, отзывы хотелось бы услышать на форуме. Не штисняйтесь выкладывать ваши интересные наработки.

P.S. В инете много статей по поиску пути, например эта:
http://delphigfx.mastak.ru/doc/path/path.htm#detour.



Скачать урок и все примеры к нему (ZIP формат).



Если у вас появится желание предложить на всеобщее обозрение свои уроки или просто интересную информацию по созданию игр при помощи GameMaker, то милости просим - присылайте свои работы по адресу gamemaker [at] e1.ru, с указанием темы 'Уроки по GM' или непосредственным указанием на предмет урока.

Присланные вами материалы мы с радостью разместим на страницах нашего сайта, с обязательным указанием автора!


[ Вернуться в основной раздел ]

© 2006 Simple Life & World