Войти
ПрограммированиеФорумИгровая логика и ИИ

Прохождение лабиринта с пустотами?

#0
7:22, 30 июня 2015

Добрый день!

Есть лабиринт с толстыми стенами. В лабиринте могут быть пустоты.
Есть персонаж, который двигается произвольным образом, а не только по клеточкам. У персонажа есть размер, поэтому срезать углы персонаж не может. Искомый путь для кусочка лабиринта в приложенном файле.
Лабиринт | Прохождение лабиринта с пустотами?


Подскажите в какую сторону копать для решения задачи?

Заранее спасибо!


#1
9:25, 30 июня 2015

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

#2
10:56, 30 июня 2015

A* же

#3
11:26, 30 июня 2015

Vowik
Попробуй алгоритм Дейкстры https://ru.wikipedia.org/wiki/Алгоритм_Дейкстры .

#4
12:58, 30 июня 2015

Vowik
> У персонажа есть размер, поэтому срезать углы персонаж не может.
Делается карта проходимости уже с учётом размера. То есть, если персонаж радиуса R, то все стены отодвигаются на R. После чего делается обычный поиск пути.

#5
16:40, 30 июня 2015

разбиваешь лабиринт не по клеточкам а по комнатам. граф для нахождения пути строишь по точкам выхода из коридора/внутреним углам в комнате
т.е. как-то так
когда надо найти путь - добиваешь в граф две точки в комнате и связываешь из со всеми точками в ней. далее обычной дейкстрой/а* ищешь путь по графу.
Изображение

для общего случая - гугли Navigation Mesh

#6
10:24, 13 июля 2015

Я думаю, решение нужно простое, и быстрое (в смысле программирования, а не эффективности работы). Я пользуюсь просто "матрицей расстояний" (как её ещё назвать???). Т.е. в точке, где находится персонаж я начинаю "двигаться во все стороны", записывая каждый шаг (1-вверх, 2-вправо, 3-вниз, 4-влево для Вашего случая). Как только "достигнута" конечная точка из неё проводите "обратный маршрут".

#7
12:01, 13 июля 2015

A*

#8
12:46, 13 июля 2015

на хабре появилась неплохая статья о пачфайдинге с использованием потенциальных полей

#9
14:53, 13 июля 2015

Зачем потенциальные поля-то?
Тут обычная оптимизация найденного пути.
Сам писал алгоритм сглаживания, но там не A*, а Дийкстра, потому как нужно все доступные траектории было учитывать при "брезенхемизации".

Получилось вот такое:

Изображение
#10
9:18, 26 июля 2015

Тупой и дешёвый способ:

1. Находишь путь к выходу по правилу правой руки (как робо-пылесос, например, делает). Или ещё как.
2. Превращаешь найденный путь в кружочки диаметром с ищущего путь NPC, связанные упругими связями (бусы на резиночке)
3. Выполняешь N итераций сокращения этой резиночки, где кружочки жёстко отталкиваюются от стен, притягиваются к соседним и мягко отталкиваются от следующего соседа.
4. Получаешь вменяемо выглядящую траекторию, да ещё и огранически сглаженную, для персонажа который передвигается не только по клеточкам.

В реале живые существа не паярятся всякими A*, им лениво напрягать мосК! Они примерно так и оптимизируют. Находят приближённый маршрут, а потом по мере движения сглаживают его.

ПрограммированиеФорумИгровая логика и ИИ

Тема в архиве.