Как настроить алгоритм поиска пути поиска A * для обработки различных значений движения местности?

8

Я создаю 2D-игру на основе карт с дизайном, похожим на Diablo II. Другими словами, игрок щелкает по карте, чтобы переместить своего игрока. Я только что закончил движение игрока и перехожу к поиску пути.

В игре враги должны заряжать персонажа игрока. Есть также пять различных типов местности, которые дают разные бонусы движения. Я хочу, чтобы ИИ использовал эти бонусы на местности, когда они пытались добраться до игрока.

Мне сказали проверить алгоритм поиска A * (http://en.wikipedia.org/wiki/A*_search_algorithm). Я делаю эту игру на HTML5 и JavaScript, и нашел версию на JavaScript: http://www.briangrinstead.com/blog/astar-search-algorithm-in-javascript Я пытаюсь выяснить, как настроить ее хоть.

Ниже приведены мои идеи о том, что мне нужно изменить. О чем еще мне нужно беспокоиться?

  • Когда я создаю график, мне нужно будет инициализировать переданный мной 2D-массив с обходом карты, соответствующей различным типам местности.
  • в graph.js: определение «GraphNodeType» необходимо изменить для обработки 5 типов местности. Там не будет стен.
  • в astar.js: оценку g и h нужно будет изменить. Как мне это сделать?
  • в astar.js: isWall (), вероятно, следует удалить. У моей игры нет стен.
  • в astar.js: я не уверен, что это такое. Я думаю, что это указывает на узел, который недопустим для обработки. Когда же это произойдет?
  • На высоком уровне, как я могу изменить этот алгоритм с "о, там стена?" на "эта местность приведет меня к игроку быстрее, чем местность вокруг меня?"

Из-за времени я также обсуждаю повторное использование моего алгоритма Брезенхэма для врагов. К сожалению, ИИ не будет использовать различные бонусы за движение по местности, что сделает игру отстойной. : / Я бы очень хотел иметь это для прототипа, но я не разработчик по профессии, и я не ученый. : D

Если вы знаете какой-либо код, который делает то, что я ищу, пожалуйста, поделитесь!

Советы по проверке работоспособности также приветствуются.

user422318
источник
Эй, автор библиотеки здесь. Используете ли вы последнюю версию от GitHub? github.com/bgrins/javascript-astar/blob/master/astar.js . Это намного быстрее, чем старая реализация на основе списка.
Брайан Гринстед

Ответы:

7

Вам нужно обратить внимание на очень специфическую строку в алгоритме:

// g score is the shortest distance from start to current node, we need to check if
//   the path we have arrived at this neighbor is the shortest one we have seen yet
var gScore = currentNode.g + 1; // 1 is the distance from a node to it's neighbor

Это стоимость этого конкретного узла. Вы хотели бы изменить его на что-то вроде

var gScore = currentNode.g + currentNode.cost

Это заставит путь избегать дорогой местности и предпочитать дешевую местность; Вы несете ответственность за то, чтобы currentNode.cost возвращал что-то подходящее для вашей местности. Это тот факт, что не вся местность имеет стоимость 1, на которую вы обращаете внимание ... одна местность дешевле, чем другая. Есть и другие соображения, но этот конкретный момент в коде должен быть в центре вашего внимания.

Мирддин Эмрис
источник
Спасибо за это. Я изменил свой код так, чтобы каждый узел просматривал пиксель в своих координатах и ​​сохранял его как стоимость. К сожалению, я проверил поиск пути между двумя точками на моей сетке 800x500, и мой браузер завис. : / В этом есть несколько факторов: астрарный код может нуждаться в оптимизации; размер моего холста огромен; возможно, моя инициализация графа неверна; и возможно цвета на аватарах персонажей портят вещи. Что мне делать? :(
user422318
Когда вы говорите «хранит пиксель», вы имеете в виду, что он хранит стоимость местности пикселя, да? Потому что какое-то значение RGB вряд ли будет соответствовать реальной стоимости этого участка местности. Вы, вероятно, должны хранить что-то между 1 и 10 (1 - дорога, 10 - болото), хотя точные значения, конечно, зависят от вашей конкретной игры.
Мирддин Эмрис
1
Эй, автор библиотеки здесь. Используете ли вы последнюю версию от GitHub? github.com/bgrins/javascript-astar/blob/master/astar.js . Это намного быстрее, чем старая реализация на основе списка.
Брайан Гринстед
2
@ Брайан Вы должны поставить этот комментарий к вопросу, а не к моему ответу, чтобы человек, фактически использующий библиотеку, получал уведомление по электронной почте, а не я.
Myrddin Emrys
2

Это именно то, для чего предназначен A *. Все, что вам нужно сделать, это назначить вершины между затратами узлов на основе типов местности. (Похоже, в ваших примерах используется график, где все вершины имеют стоимость 1.)

хаос
источник
0

Эта реализация немного специфична для включения / выключения прямо сейчас. Как говорит Myrddin Emrys, вам нужно будет изменить оценку g на основе стоимости (а не только на 1). Об этом шла дискуссия здесь: https://github.com/bgrins/javascript-astar/issues/3 .

Я бы хотел перенести это решение обратно в основную библиотеку, если оно будет работать!

Брайан Гринстед
источник