Как лучше всего организовать поиск пути?

Question

[Zimaell]

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

Comments

[GavriKos]

Так это, в юнити вроде был пасфайндинг же. Чем не устроил?

[Zimaell]

GavriKos, https://assetstore.unity.com/packages/tools/ai/pat... - этот что ли?
Не думаю что в моем случае стоит прибегать к каким-то дополнения (покупать тем более) или библиотекам, мне всего-то нужно найти путь грубо говоря в 2х мерной плоскости...

[GavriKos]

Zimaell, нет, вот этот: https://docs.unity3d.com/Manual/Navigation.html

[xmoonlight]

GavriKos, "Документация?! Нет, не слышал." :)

[Zimaell]

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

[GavriKos]

Zimaell, и почему не подойдет? Метод, возвращающий путь, есть - https://docs.unity3d.com/ScriptReference/AI.NavMes...

[Zimaell]

GavriKos, есть такое, сейчас поковыряюсь в плане в свою среду это прикрутить...

[GavriKos]

Zimaell, скажем так - оно реально может не подойти - это факт, но нужно понимать почему и от этого уже искать другую систему. Ну или руками реализуйте, как xmoonlight посоветовал

[xmoonlight]

Zimaell,

допустим дорога постоянно генерируется новая, на каждый тест

далее оба смотрят как юнит идет по вычисленному маршруту

это тотализатор "тараканьи бега"?)

[Zimaell]

xmoonlight, да нет :D
Генерируется карта, в том числе дорога по которой будут идти юниты , далее идет расчет кратчайшего пути к цели...

[xmoonlight]

Zimaell, а у юнитов разная скорость или они будут ходить только колонной?
Если они будут идти хаотично, но к одной дальней цели - нужно, чтобы задние всегда шли именно за впереди идущим, а не все к дальней цели. А уже самый первый - к той самой дальней цели.
Иначе, крайне затратно каждому по волне на весь левел раздавать)

[Zimaell]

xmoonlight, так просчет то один раз будет при старте, а дальше какая разница у кого какая скорость, главное что у каждого будут чекпоинты по которым они будут ориентироваться куда идти...

[xmoonlight]

Zimaell, если у них след.шаг одна и та же клетка: они будут или ждать пока кто-то первый пройдёт (это доп.время), или должны будут накладываться друг на друга (т.е., без коллизий к друг другу).

А в моём варианте - они всегда будут стараться искать путь так, чтобы не мешать друг другу.
Просчёт - только для самого ближнего к цели. Остальные - по ближним юнитам к друг другу, и которые чуть впереди идут.

[Zimaell]

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

spoiler

void Start(){
  waypoints = GameObject.Find("WayPoints").transform;
  NextWaypoint();
  }
	
void Update(){
  Vector3 dir = waypoint.transform.position - transform.position;
  dir.y = 0;
  float _speed = Time.deltaTime * speed;
  transform.Translate(dir.normalized * _speed);
  if(dir.magnitude < _speed) NextWaypoint();
  }
	
void NextWaypoint(){
  ++waypointIndex;
  if(waypointIndex >= waypoints.childCount){
    Object.Destroy(gameObject);
    return;
    }
  waypoint = waypoints.GetChild(waypointIndex);
  }

как-то так...

[xmoonlight]

Zimaell, с чекпоинтами - это уже не так правдоподобно, но проще, да.

[Zimaell]

xmoonlight, почему не правдоподобно?
игра в стиле TD, как не крути у юнитов есть конкретная тропинка по которой они идут к цели (или игрок выбирает им маршрут), конечно можно заморочиться чтобы они не проходили сквозь друг друга а обходили (если быстрее идет), но это уже такое...

[xmoonlight]

Zimaell, а-а.. Т.е. они проходят насквозь - тогда один просчёт и без вэйпоинтов)

[xmoonlight]

Zimaell, TD - не знаю, знаю TTD, где всю индустрию и города нужно развивать.

[Zimaell]

xmoonlight, TD - Tower Defence, но в общем песочница TTD, но сам бой происходит именно в режиме TD, то есть сидишь себе развиваешь экономику, строишь оборону, здания, флот для нападения, а тут бах и нападает противник, вся экономика на время боя замирает и работают только оборонительные системы, в тоже время противник пытается нахапать все что "неправильно" лежит на складе :D

[xmoonlight]

Zimaell, забавно должно получиться! Особенно рандомный прорыв)))

Answer 1

[xmoonlight]

Волновой алгоритм Ли (как раз для стратегических игр)