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

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

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

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

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

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

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

Волновой алгоритм 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 (дин под другим) без фона (прозрачные). Вот и вся магия (:

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





Показывать волны


HTML5 нид, мэн
HTML5 нид, мэн

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

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

  Категории: html, html5, JavaScript, Коддинг
  • Pingback: Обход препятствий: волновой алгоритм (Алгоритм Ли) | Suvitruf's Blog()

  • Сергей

    Не ясно , почему диагональ всё таки 1.6 , ведь , корень из двух ~1.4 . В таком деле нужно считать точно диагональ , т.к. ошибка (в данном случае 0.2) будет копиться очень быстро и в один прекрасный момент 5 реальных клеток по диагонали дадут 6 ошибочную клетку клетку (соответственно если диагональ 500 клеток , то добавиться 100 ненужных клеток (вес пути) )

    • http://suvitruf.ru Suvitruf

      Я ж об этом написал)
      Если положение/размер клетки – единственный критерий выбора пути, то да, нужно ~1.4. Я это к тому, что в играх, зачастую, есть ещё доп. факторы: проходимость клетки и т.д. То есть, даже если фактический путь 1.4, то при расчётах может быть число 2. Это число отображает больше проходимость, чем точную длину.

  • http://all-docs.ru Саша

    Спасибо… Хороший сайт.

  • Max

    Как можно подправить, если последний шаг можно сделать по-диагонали, чтоб он его все-таки делал, а не заходил сбоку. Пример:
    http://s019.radikal.ru/i640/1211/c9/a8e9ea532129.jpg

    • http://suvitruf.ru Suvitruf

      Вместо
      if(bEnd) this.findWay();

      Написать:
      if(bEnd) {
      mas[begPoint.i][begPoint.j] = 0.1;
      this.findWay();
      }

      • Max

        Спасибо. Уже разобрался:)
        Переписывал твой код на С

  • Arsiah

    Добрый день, возник вопросы
    1)в какой части происходит генерирование карты и расстановка препятствий, запуск поиска?
    2)как сделать чтоб карту можно было не произвольно генерировать а например нарисовать и указав точки начала и конца пути рассчитать кратчайший путь?

    • http://suvitruf.ru Suvitruf

      1) В this.generatePoints = function() точки начала и конца генерируются. В this.generateObstacle = function() препятствия генерируются.
      2) Обработку нажатий по канве сделать и при клике в эту точку ставить препятствие.

      • Arsiah

        спасибо,теперь вот такой вопрос а для чего используется вот этот код
        endPoint = {i:Math.round(Math.random()*(vCount-1)+0), j:Math.round(Math.random()*(hCount-1)+0)};
        в скрипте?

        • http://suvitruf.ru Suvitruf

          Случайным образом задаём точку, в которую необходимо попасть.

          • Arsiah

            Извините, а можно попросить Вас помочь с реализацией ручной прорисовки карты?
            Просто я начинающий программист и еще очень много чего не умею…

            • http://suvitruf.ru Suvitruf

              Если время будет, то возможно сделаю.

              • Arsiah

                Спасибо

  • Arsiah

    Добрый вечер, подскажите пожалуйста, где и как нужно исправить чтоб при выборе варианта конечной точки из списка устанавливалась конечная точка на карте и прокладывался путь до этой точки?