Перемещение / избегание препятствий

12

Я хотел бы написать «игру», в которой вы можете разместить препятствие (красное), а затем черная точка пытается избежать его и добраться до зеленой цели.
Я использую очень простой способ избежать этого: если черная точка близка к красной, она меняет свое направление и некоторое время движется, затем она движется вперед к зеленой точке.
«Нереальный» путь

Как я могу создать «гладкий» путь для «игрока», управляемого компьютером?
Изменить: не гладкость является основным пунктом, но чтобы избежать красной блокирующей "стены" и не врезаться в нее, а затем избегать ее.

Как я могу реализовать какой-то алгоритм поиска пути, если у меня всего 3 точки?
(И что могло бы сделать вещи намного сложнее, если бы вы могли разместить несколько препятствий?)
Гладкий путь

ai path-finding пользователь
источник

Ответы:

9

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

Эта ссылка помогла мне начать с понимания и реализации алгоритма A *.

Редактировать :

Более простая мысль, которая приходит мне в голову, - это ... как только у вас будет мир в ячейках сетки. Всегда, чтобы черная точка следовала за манхэттенским расстоянием до зеленой точки. Затем вы можете назначить веса для каждой ячейки. Препятствия могут иметь большой вес в ячейке сетки, а свободные для перемещения могут иметь (скажем, 0) вес. По мере продвижения по манхэттенскому расстоянию для каждого хода проверяйте, не превышает ли вес следующей ячейки вес текущей ячейки. Если оно выше, проверьте вес соседней ячейки и затем двигайтесь дальше.

Надеюсь это поможет

brainydexter
источник
Эта статья об алгоритме * кажется мне тем, что я искал, но, к сожалению, я до сих пор не знаю, как разделить мой «мир» на сетки: S
пользователь
Это действительно зависит. Мысль: разделите ваш мир на сетку размером 32 х 32, которая будет представлять позиции в двумерном массиве. Например, в вашем случае: красная точка на 120, 120 пикселей (или 120/32 x 120/32: 3,75 x 3,75) 3,75 x 3,75 представляет позицию в вашей сетке мира (или 2D-массиве). Поскольку массивы индексируются целыми числами, вам нужна только целая часть. Таким образом, красная точка будет в 3 х 3. Надеюсь, это поможет
Brainydexter
18

Поведение рулевого управления предназначено для решения именно этой проблемы.

http://www.red3d.com/cwr/steer/

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

тетрада
источник
Поведение рулевого управления идеально подходит для этого.
Tennn
2

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

Пауло Пинто
источник