Волновой алгоритм 8 клеточный (Алгоритм Ли)

В прошлой статье описывал как обходить препятствия, используя волновой алгоритм (Алгоритм Ли). Но там лишь 4 клеточная реализация была. Теперь же сделал, проверяя все 8 клеток, ну и оптимизировал немного.

Волновой алгоритм (Алгоритм Ли), использующий 8 клеток

Добавить проверки ещё 4 клеток, по сути, не так сложно. После этого ещё необходимо рассмотреть нюанс с диагональными путями.

Волновой алгоритм 8 клеточный (Алгоритм Ли) - неправильный путь

Очевидно, что на самом деле невозможно пройти из 2.6 в 4.2, хотя этот путь и короче с точки зрения алгоритма. Необходимо ещё добавить проверку на препятствия смежных клеток при движении по диагонали.

Если эту проверку сделать, то путь будет 2.6 -> 3.6 -> 4.2. К слову, диагональный путь у меня имеет длину 1.6. С точки зрения математики то он будет корень из 2. По факту же, числа можно любые ставить в клетки. К примеру, если проходимость у них разная, алгоритм будет выбирать клетки, с более лучшей.

Дёрганья персонажа в сложной ситуации

Кто играл в StarCraft, в курсе, что это значит. Когда вы кардинально маршрут меняете, то юниты дёргаются. Это является следствием одного нелостатка алгоритма (в то же время и плюса).

Чтобы использовать алгоритм, необходимо карту поделить на клетки. И необходимо отдавать себе отчёт, что слишком большие клетки не прокатят, так же как и слишком мелкие. В том же StarCraft’e клетки по ширине поболее 50 пикселей. Поэтому то и возникают дёрганья. Если бы клетки были размером 1 px, то было бы плавно, но тогда бы увеличилось время на просчёт маршрутов. И вы учтите, что считает то он не только, когда вы кликнули на область и послали юнитов. Сам компьютер для ИИ постоянно пути просчитывает.

В StarCraft самая большая карта имеет размер 200×200 клеток. Если проверить мой алгоритм при таком размере, то вычисления занимают 0.03 секунды. То есть, если вы неустанно кликаете, что-то типо 5 нажатий в минуту, то только на расчёт путей для вас занимает 0.15 сек. Это без учёта маршрутов ИИ. Естественно на C++ будет быстрее, чем на js, и там разные методы оптимизации. Быть может запоминаются пройденные уже пути…не знаю.

Волновой алгоритм (Алгоритм Ли), использующий 8 клеток на JavaScript

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

this.checkPoints= function(p)
{	
  var count = p.length;
  points = new Array();
  //если закончен расчёт, тикаем
  if(count==0 || bEnd) return;
    //обходим точки
    for(i=0;i<count;++i
    {
      //если достигли конца, то тикаем
      if(p[i].i == endPoint.i && p[i].j == endPoint.j)
      {
	bEnd = true;
	return;
      }
      //var x = 0;
      //var y = 0;
      //проверяем окружные 8 клеток
      for( y=-1;y<=1;++y)
	for( x=-1;x<=1;++x)
	  if(!(x==0&&y==0))
	    //проверка на выход за пределы поля
	    if(checkPointLimit(p[i].i+y,p[i].j+x))
	      if(mas[p[i].i+y][p[i].j+x] ==0)
		//проверка на препятствия
	        if(checkPointObstacle(p[i].i+y, p[i].j+x,p[i].i, p[i].j))
		  //проверка значения
		  if(checkPointValue (p[i].i+y,p[i].j+x,  mas[p[i].i][p[i].j]+((Math.abs(x)==Math.abs(y))?1.6:1), points))
                    //если надо, рисуем волны
		    if(showPriority && typeOfDrawing == 1) 
		    {
			var ar = new Array();
			ar[0]={i:p[i].i+y, j:p[i].j+x};
			delay+=10;
			timer = setTimeout( function(ar ) {return function(){self.drawPointsAsynchron(ar)}}(ar), delay);
		    }
    }
    //повторяем для новых клеток
    this.checkPoints(points);
}

HTML5, Canvas, слои

При каждом клике, необходимо canvas перерисовывать. То есть, либо полностью, либо только те клетки, что были изменены. Первый вариант сразу отпадает, так как, к примеру, при размере 200×200 клеток, на отрисовку будет тратиться намного больше времени, чем на вычисления.

Второй вариант тоже не очень, ибо сложно и муторно следить за клетками, которые изменились. По этому, лучший вариант — использовать слои. В нижнем слое будет фон, то есть неизменная часть, а волны и пути будут в верхнем слое. Поэтому при клике, стираем этой верхний слой и рисуем лишь путь. Тогда время на прорисовку соизмеримо со временем вычисления. В сущности же, при большом поле (более 300×300 клеток) время затраченное на вычисления уже больше, чем время на прорисовку.

То есть, у нас есть два canvas (дин под другим) без фона (прозрачные). Вот и вся магия (:

Как это всё выглядит, можно увидеть ниже. Кликаем на нужную клетку, алгоритм находит оптимальный путь.

Если выбрать оптимальный размер клеток, скажем как в том же StarCraft, то можно запоминать уже найденные пути. Это одномерный массив, на C++ для этого удобно было бы использовать стек. Память это жрать будет не так много, выборка из стека довольно быстро осуществляется. Так что, по сути, ближе к концу игры практически не надо будет считать пути, а брать из кеша уже просчитанные. Всё упирается тогда в память. По сути, можно при загрузке карты просчитать пути для каждой точки и это дерево хранить в памяти 0___0. Ну, это конечно, ооочень не оптимально)

Кому интересно, можете покопаться в исходнике.