Алгоритм A*

Я не буду рассказывать про суть этого алгоритма, т.к. существует множество статей о нём рассказывающих. К тому же о нём хорошо рассказывает эта картинка:

Однажды в рамках курса английского языка в ВУЗе я делал перевод нескольких статей на тему поиска пути. Начал я с традиционного описания алгоритма на матрице из квадратных ячеек. И почему-то многие разработчики считают это потолком возможностей А*

Алгоритм А* является эвристическим, а это значит — можно наворачивать его различными условиями по выбору следующей клетки. Введение ограничений позволит решать при помощи этого алгоритма много разнообразныз задач. Пример?

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

Задача в целом не тривиальная, т.к. 3Д карту тяжело разделить на клетки и я думал что авторы будут выдумывать что-то экстраординарное. Ан нет! Всё это выглядело очень примитивно — по карте расставляются точки с радиусом области который говорит что объект в ней находится. Таким образом, первоочередная задача объекта — добежать до ближайшей точки.

Второй этап — посик пути как раз алгоритмом А*, но не по матрице, а по графу. В целом, ничего не изменилось кроме того что мы проверяем не четыре соседние клетки, а все смежные вершины.

И вот что я подумал… Особенно после вопроса Цифр о том как сделать поиск пути в платформере. Ведь ту же идею можно использовать, только дуги должны параметры иметь, например высоту прыжка, или свойство среды через которую нужно пробраться, телепорты те же самые! Тогда имея такой граф можно будет искать пути для разных типов объектов. И даже более того, если объект способен менять форму — можно оценивать эффективность использования той или иной формы для достижения цели. Ещё как вариант можно ввести дополнительный параметр «здоровье», который затрачивается на каждый шаг, и расставив  в графе места пополнения этого здоровья, можно рассчитать оптимальный путь с учётом сохранения здоровья или же с учётом поддержания максимального значения здоровья. Всё завсиит от алгоритма.

Но важно помнить, что А* даёт только оптимальный путь и использовать его нужно как инструмент формирования псевдо-ИИ. Общая логика поведения объектов и применение А* зависит только от фантазии разработчика.

Похожие статьи

18 комментариев
Xitilon

Звучит немного слишком академично, но вдохновлляюще. Отталкиваясь от этих мыслей, представляю себе систему разработки, которая не только позволяет делать карты из взаимосвязанных локаций, но и валидирует переходы между ними с учётом способностей (форм) игрока. Хорошо бы такое получить в распоряжение в один прекрасный день, но думаю день этот наступит нескоро.

Вторая схема крутая, точнее даже — сам способ формирования такого графа.
Hrenzerg
Академично — это потому что я его должен был запостить год назад, когда я ещё учился в универе и корпел над своим дипломом. Точнее над статьями для диплома.
Xitilon
Так чё ж не запостил? Хотя, не то чтобы оно сильно устарело за это время. Ещё небось лет 10 пройдёт пока такой софт сделают, или по крайней мере сделают адекватно.
buntarsky
Xitilon

В очередной раз посмотрев на стены кода, я смог сформулировать, почему такое преимущество свободного софта как «можно модифицировать под свои нужды» практически бесполезно на практике. Исходный код этой штуки не сильно отличается от ассемблера по уровню сложности разбора и проникновения в суть вещей — каким навыком программирования нужно вообще обладать, чтобы что-то подобное подпилить? Можно разве что какие-то очевидные баги править типа нехватающего или перепутанного знака. А для остального нужна высшая квалификация, и видение всей архитектуры проекта — когда этим заниматься-то? Тут даже подключить это всё к игре — нужно провозиться хорошие два полных дня.

Ну и ещё оно трёхмерное. Воксели, мэши, зачем же так сразу.

buntarsky
Все с нуля писать, конечно, проще и быстрее. Жизнь-то длинная. Тем более, в чужих библиотеках — баги, непонятный код, а я пишу безашыбачна, как бох.
Xitilon
Про баги и про свой код я как раз ничего не говорил.
buntarsky
модифицировать подпилить править

наталкивают именно на такую мысль. А если ничего исправлять не нужно, тогда что мешает просто пользоваться, не разбираясь в коде? Опенсорс же ни к чему не обязывает, лишь предоставляет возможности. Для тех, кто готов разбираться в архитектуре и повышать квалификацию. Так что

преимущество свободного софта как «можно модифицировать под свои нужды» практически бесполезно на практике

ложное утверждение.

Xitilon

Мне не нужно 3Д, мне нужно такое же, но 2Д, поэтому мне нужно «просто» вырезать лишнее измерение. Но даже это слишком сложно. О чём речь? Конечный вывод - всё равно, открытый или закрытый исходник, если ты занимаешься игрой, а не движком и неравным боем с кривой IDE.

Мне — бесполезно на практике. Я за всех не говорю, это ИМХО про меня. Впрочем, если поменять «практически бесполезно» на «выстреливает намного реже, чем это кажется по громким словам о самой концепции таковой разработки софта», то это для меня уже и не похоже на ложное утверждение.

Мурка
Я не понял, геометрию кубиков упростили до геометрии шара?
Hrenzerg
Геометрию сетки расширили до геометрии графа.
Мурка
А как это работает? Напиши нормально, одного абзаца мало.
Hrenzerg
Что конкретно? А*, пострение графа, поиск пути по графу?
DarkDes
Как подбирается радиус? И по сути это получается NavMesh или нет?
Hrenzerg

Авторы статьим пишут что радиусы подибраются изначально после триангуляции по длинам сторон, а вообще вручную. Ну и вообще вручную такой граф строить — значит сделать более качественный поиск. Да это и есть NavMesh. Я же ссылку в посте даже привёл на оригниал: http://www.gamedev.net/page/resources/_/technical/artificial-intelligence/navigation-graph-generation-r2805

 

DarkDes
Когда всё руками, то да — качественнее получится.

Ссылку как-то проглядел, да.
MekaGem

Напомнило вот эту статью:

http://www.gamasutra.com/blogs/YoannPignole/20150427/241995/The_Hobbyist_Coder_3__2D_platformers_pathfinding__part_12.php

Понятно, что зачастую в платформерах монстров даже лучше делать глупо двигающимися туда-сюда, чем умными-разумными. Но вообще, всегда, когда всплывает тема поиска пути в 2d, меня беспокоит один момент — а что если не статика? Что если платформы двигаются? Что если игрок и враги могут стены ломать? Это же звучит дико интересно, пусть и не очень понятно, зачем в платформере такой мощный ИИ.

buntarsky
Поиск пути — это и так, практически всегда, динамика. Даже если не меняется окружение, меняют положение другие объекты (юниты, враги, NPC и т.п.). Поэтому его постоянно приходится пересчитывать. Поэтому к нему такие высокие требования по скорости.
Автор статьи запретил добавлять комментарии