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

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

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

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

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

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

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

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

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

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

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

Видно сразу — не все клетки алгоритм обошёл, что говорит о его эффективности. Если увеличить количество просматриваемых клеток до 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;
}

// Получаем сообщение из основного потока

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);	
}

//прогоняем точки

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 клеточную реализацию волнового алгоритма.

Gamedev suffering

Блог о разработке игр и серверных технологиях

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

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

HTML5, Canvas и Web Workers