2D нахождение пути - поиск гладких путей

10

Я пытался реализовать простой поиск пути, но результат был менее удовлетворительным, чем то, что я намеревался достичь. Дело в том, что юниты в таких играх, как Starcraft 2, движутся во всех направлениях, тогда как юниты в моем случае движутся не более чем в 8 направлениях (стиль Warcraft 1), так как эти 8 направлений направлены к следующим доступным узлам (они перемещаются из одной плитки в следующую соседнюю плитку) , Что мне нужно сделать, чтобы добиться результата как в Starcraft 2? Уменьшить размер плитки?

http://i.stack.imgur.com/lr19c.jpg

На картинке вы видите горизонтальную линию каменных плиток, являющихся препятствиями, а найденный путь отмечен зелеными плитками. Красная линия - это путь, которого я хочу достичь.

game-design game-mechanics path-finding Кои Нам Нг
источник
Я большой поклонник поиска точек перехода, хотя пока не нашел времени для его реализации. Но документация была интересной и имеет хорошие показатели.
2
Вы уверены, что это ваш путь? Единицы, использующие его, будут частично проходить сквозь стены. Я сделал это более заметным в другом примере: i.imgur.com/eh4ZR.png И вот что вы, вероятно, действительно хотите достичь: i.imgur.com/vFQg4.png
Маркус фон Броади
Вы правы. Мой путь был ошибочным, но это было больше для иллюстрации. Спасибо за то, что указали лучший способ разобраться.
Kooi Nam Ng
Вам нужно будет иметь дробные координаты внутри плитки, чтобы получить то, что вы хотите. Никакой возможный путь без этого не сработает - перенос фракций, но не их отображение, заставит ваш юнит двигаться прямо / по диагонали / прямо / по диагонали.
Лорен Печтел
@LorenPechtel вы не правы, вы можете сгладить путь после его поиска. Это довольно просто, поскольку вы создаете две линии на основе размеров объекта и проверяете, пересекаются ли они с плитками между tile0 и tileN, где tile1-tile (N-1) - это плитки, которые вы хотите удалить из пути.
Маркус фон Броади

Ответы:

8

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

Вы можете сгенерировать «график видимости» (какие другие точки видны из каждой точки) из вершин и затем выполнить A * на графике. Это работает, потому что кратчайший путь всегда будет лежать на графике видимости.

Сократить размер плитки может помочь вам.

Ресурсы

Дальнейшее чтение

РЕДАКТИРОВАТЬ: Мне нравится комментарий @ MarkusvonBroady.

«На самом деле речь идет о сглаживании, а не о поиске. Найденный путь на картинке выглядит нормально».

Ресурсы

От @MarkusvonBroady

Я сделал поиск, найти следующие (которые могут вам помочь)

Г-н Махбубур Рахман
источник
1
отличные ссылки, +1 от меня
lhk
2
@MarkusvonBroady, спасибо за -1. Я учился у вас. Я не хочу, чтобы точка, скорее я готов учиться и поделиться правильным. Я считаю, что, обсуждая, мы можем найти правильный. :)
Md Mahbubur Rahman
@MarkusvonBroady, не могли бы вы поделиться несколькими ресурсами алгоритма сглаживания пути?
Md Mahbubur Rahman
На самом деле, я думаю, что этот ответ помогает ОП. Я не думаю, что ОП требовал фактического сглаживания (сплайн-интерполяция и т. П.), А скорее, что его алгоритм в настоящее время находит ужасно неоптимальный путь и должен быть «сглажен» в более прямую линию. Какой A *, естественно, нашел бы для него без какого-либо дополнительного сглаживания.
Шон Мидлдич
Я использовал A * и думаю, что нашел оптимальный путь.
Kooi Nam Ng
0

Начиная с одного конца исходного пути, скажем path[0], вы можете удалить , path[1]если сегмент образуется путем объединения точек path[0]и path[2]не пересекается с любой стене. Пройдя дальше, пока последний сегмент не предоставит более простой путь.

Это не только сгладит путь, но и удалит некоторые бесполезные точки, например, огонь, 3 последовательных отрезка прямой линии.

arainone
источник