Я создаю 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
Если вы знаете какой-либо код, который делает то, что я ищу, пожалуйста, поделитесь!
Советы по проверке работоспособности также приветствуются.
источник
Ответы:
Вам нужно обратить внимание на очень специфическую строку в алгоритме:
Это стоимость этого конкретного узла. Вы хотели бы изменить его на что-то вроде
Это заставит путь избегать дорогой местности и предпочитать дешевую местность; Вы несете ответственность за то, чтобы currentNode.cost возвращал что-то подходящее для вашей местности. Это тот факт, что не вся местность имеет стоимость 1, на которую вы обращаете внимание ... одна местность дешевле, чем другая. Есть и другие соображения, но этот конкретный момент в коде должен быть в центре вашего внимания.
источник
Это именно то, для чего предназначен A *. Все, что вам нужно сделать, это назначить вершины между затратами узлов на основе типов местности. (Похоже, в ваших примерах используется график, где все вершины имеют стоимость 1.)
источник
Эта реализация немного специфична для включения / выключения прямо сейчас. Как говорит Myrddin Emrys, вам нужно будет изменить оценку g на основе стоимости (а не только на 1). Об этом шла дискуссия здесь: https://github.com/bgrins/javascript-astar/issues/3 .
Я бы хотел перенести это решение обратно в основную библиотеку, если оно будет работать!
источник