Обход препятствий: волновой алгоритм (Алгоритм Ли)

Волновой алгоритм (Алгоритм Ли)

Волновой алгоритм (Алгоритм Ли)

Тема нахождения пути на карте волнует многих программистов (в основном занимающихся разработкой игр). Заинтересовался этими алгоритмами. Решил для начала самый простой рассмотреть – волновой алгоритм (алгоритм Ли) .

Волновой алгоритм (Алгоритм Ли)

Волновой алгоритм один из самых уникальных алгоритмов трассировки. Он позволяет построить путь между двумя элементами в любом лабиринте. Сам процесс можно разделить на 2 этапа.

1. Из начального элемента распространяется в 4-х направлениях волна (см. рисунок сверху). Элемент в который пришла волна образует фронт волны. На рисунках цифрами обозначены номера фронтов волны.

Каждый элемент первого фронта волны является источником вторичной волны. Элементы второго фронта волны генерируют волну третьего фронта и т.д. Процесс продолжается до тех пор пока не будет достигнут конечный элемент. Ну, или пока не станет ясно, что его не достигнуть.

2. Строится сама трасса. Её построение осуществляется от конечного элемента к начальному.

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

Существует два способа определения количества соседних клеток: считать соседними клетки, доступные через обще грани (их 4) и считать соседними клетки, доступные через общие грани и общие углы (таких клеток будет 8). Я реализовал пока более простой вариант, используя 4 клетки. Ну, сразу видны минусы. Вместо того, чтобы идти по диагонали, алгоритм идёт по прямой. Известно, что сторона треугольника меньше суммы двух других сторон. Так что, для более лучшего поиска, лучше использовать 8 клеток.

Посмотреть как это работает можно ниже.







HTML5 нид, мэн

Видно сразу – не все клетки алгоритм обошёл, что говорит о его эффективности. Если увеличить количество просматриваемых клеток до 8, то ещё более эффективно станет.

HTML5, Canvas и Web Workers

Реализовано это дело на HTML5, просто ради фана, да и для наглядности. Решил заодно потестить и потоки (Web Workers) в js. У потока на входе точка, окружение которой необходимо просмотреть, и массив.

    // Получаем сообщение из основного потока 
    onmessage = function(e) {
	
	var obj = e.data;
	var y =obj.i;
	var x =obj.j;
	mas = obj.m;
	//чтоб за границы точка не уходила
	if(y<0 || x< 0 || y>=mas.length ||x>=mas[0].length)
	postMessage('lim');
	
	var res = Array();
	//чекаем точки на выпадение за границы
	if(checkPoint(x+1,y,mas))
	//чекаем на то пуста ли клетка
	if(mas[y][x+1] ==0 )
		res[res.length] = {i :y, j:x+1, v: mas[y][x]+1};
		
	if(checkPoint(x-1,y,mas))
	if(mas[y][x-1] ==0 )
	res[res.length] = {i :y, j:x-1, v: mas[y][x]+1};
		
	if(checkPoint(x,y+1,mas))
	if(mas[y+1][x] ==0 )
	res[res.length] = {i :y+1, j:x, v: mas[y][x]+1};
		
	if(checkPoint(x,y-1,mas))
	if(mas[y-1][x] ==0 )
	res[res.length] = {i :y-1, j:x, v: mas[y][x]+1};

	postMessage(res);



};

this.checkPoint = function(j,i,mas)
{
    return(i<0 || j< 0 || i>=mas.length ||j>=mas[0].length) ? false : true;
}

Как уже сказал, проверяются лишь соседние 4 клетки. В основному потоке ждём сообщения от дочерних. Когда будут выполнены потоки с проверками для всех клеток волны, то для всех новых точек пускаем новую волну. Потоки мы никогда не завершаем (только в конце), чтобы не тратиться на создание контекста потока и т.д. Поэтому в старые уже созданные потоки просто посылаем новое сообщение. Если потоков не хватает, только тогда создаём новые. Как-то так:

...
//прогоняем точки
for(i=0;i<pCount;++i)
{
   var obj = {m: mas, i: points[i].i, j:points[i].j };
   if(i<workers.length)
      workers[i].w.postMessage(obj);
   else
      self.createWorker(obj);	
}
...

Тут и возникла забавная ситуация. В Хроме всё работает нормально. Но в Фаере, к примеру, когда количество созданных потоков превышает определённое число, то стопорится всё. Поэтому ввёл ограничение на максимальное количество создаваемых потоков. Если сделать больше 15, то стопорится. Оптимальным оказалось 10.

Кому интересно, может поковырять файлы: сам алгоритм и файл, выполняющийся в потоке

UPD: сделал 8 клеточную реализацию волнового алгоритма.

  • Pingback: Обход препятствий: волновой алгоритм (Алгоритм Ли) 8 клеточный | Suvitruf's Blog()

  • http://ufo.net.ru/ Алексей

    Здравствуйте, не могли бы вы выложить отдельно в архиве все нужные для работы скрипта файлы, пытаюсь выдернуть прямо от сюда всю страницу, но при этом скрипт почему-то не работает, при запуске теста, меняются только точки A и B, а трасса не прокладывается, как и не отображается вес ячеек при пуске волны.
    P.S. подобный алгоритм ещё называют “Волновой алгоритм с ортогональным направлением (т.е. волны от начальной точки идут в стороны c углом в 90 градусов) “

    • http://suvitruf.ru Suvitruf

      Для работы два файла js используются. Я их приложил внизу статьи же =/

      Для запуска вызвать метод на странице initLee("идентификатор вашего canvas", сколько клеток по ширине,сколько клеток по высоте);

  • Иван

    Здравствуйте.
    Можно ли использовать волновой алгоритм для заполнения неравномерной по высоте области, высота которой меньше заданной точки?
    Спасибо.

    • http://suvitruf.ru Suvitruf

      Можно поподробнее? )

  • Надежда

    Здравствуйте. А можно сделать эту же программу в EXE формате, чтобы возможно было запустить его для нерезбирающихся в программировании? Хочется побаловать детишек на уроках.