Войти
ПрограммированиеФорумОбщее

RTS: перемещение юнитов по карте через узкие проходы, в которых стоят другие юниты

Страницы: 1 2 Следующая »
#0
(Правка: 0:14) 0:11, 3 июня 2021

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

Нужен какой-то простейший алгоритм резолвинга их коллизий. Карта реализована сеткой тайлов, один юнит может занимать минимум одну клетку (или сразу несколько, если большой). В одной клетке не больше одного юнита.

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

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


Возможно ли реализовать подобное относительно простыми способами? Какие существуют подходы к решению данной задачи?


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


Хочу получить нечто подобное в итоге:

Запустить видео по клику - Как делать игрыЗапустить видео по клику - Как делать игры

#1
0:30, 3 июня 2021

Robotex
> Какие существуют подходы к решению данной задачи?

Steering Behaviors. В частности в составе формаций.

#2
0:53, 3 июня 2021

имхо не нужно усложнять.
для прохода разных типов клеток ставим разную цену(дорога 1 болото 3 вода 5 и тд и тп)
если юнит занимает клетку то цена этой клетки ставится скажем 3-4
в итоге если возле юнита будет пустая клетка то другой унит будет его обходить иначе он будет с замедлением просачиваться через своего юнита.
врагов естественно ставим как непреодолимое препятствие.
подобным же образом можно сделать  свои здания проницаемыми для своих юнитов-просто добавлем цену за проход...

#3
1:25, 3 июня 2021

uss
> если юнит занимает клетку то цена этой клетки ставится скажем 3-4
угу, юнит давно ушел с этой клетки, а путь так и лежит в обход. Я так уже делал, не нравится.

#4
(Правка: 2:18) 1:33, 3 июня 2021

написал не правильное решение.
нужно подумать как оптимизировать но на ум приходят только монструозные решения в виде графов или обновлять траекторию каждый тик :(

#5
(Правка: 3:02) 2:56, 3 июня 2021

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

Robotex
> б) две группы друг навстречу другу через узкий проход. При столкновении групп
> одна из них должна выйти из прохода, пропустить вторую, а потом пройти
это уже требует дополнительной информации о карте.
есть некая территория "мост" (с двумя точками входа/выхода), на которой группы не могут разминутся, в принципе.

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

Этакая критическая секция :)
Задача решается постоянно в Transport Tycoon Deluxe. (c семафорами на ж/д).

Задача становится ещё интереснее, если "мосты" соединены "островами" на которых может поместиться только N юнитов. а группы, которые хотят пройти имеют размер N+M.

Robotex
> в) юнит должны пройти в комнату, в дверях которой стоит другой юнит. Внутри
> комнаты у них нет места, чтобы разминуться, значит тот юнит, что стоит в
> дверях, должен не входить внутрь комнаты, пропуская входящего, а выйти из
> комнаты, пропустить юнита, а затем вернуться обратно в дверной проем
усложню задачу, что если стоит не один юнит, а группа юнитов. И чтобы им "уступить" дорогу нужно выйти достаточно далеко.

причём часть "охранников" может зайти внутрь, а часть выйти. Опять же в завимисоти от того "как далеко нужно идти"

#6
(Правка: 3:05) 3:02, 3 июня 2021

uss

или обновлять траекторию каждый тик :(

А что? Если не больше сотни-две юнитов вроде шустро получается.
https://disk.yandex.ru/d/EM2apiK4OPIJ0g
Поясню:
Это эмуляция терминала и бегают полноценные картинки через OpenGL.
Карта тоже меняется каждый тик случайным образом во многих местах...
Возможно это не корректная проба, но на первый взгляд подвоха не вижу.
#7
3:05, 3 июня 2021

skalogryz
> то если одна группа достигла точку входа на "мост", то должна проверить не
> занят ли мост в данный момент.
Можно попробовать попроще: пусть одна группа пятится назад, пока не освободится проход для второй. И каждой группе приоритет расставить кто кому уступает

#8
(Правка: 3:13) 3:08, 3 июня 2021

Robotex
> Можно попробовать попроще: пусть одна группа пятится назад, пока не освободится
> проход для второй. И каждой группе приоритет расставить кто кому уступает
а если там три группы будет?

A-> Б <-В
Б пятится и пятит с собой группу А или В?
подход с критической секцией лучше.

Конечно, если режим у юнитов будет вроде "бежать в панике за подкреплением", то можно затолкаться на мост, где свои!

Хотя я так понимаю, ты не хочешь усложнять ИИ теми случаями, когда на мост идут две группы в одном направлении:

A-> Б->  <-В

?
т.е. в этом случае А и Б могут идти одновременно, а В должна ждать двоих.

#9
8:28, 3 июня 2021

А, может, разрешить дружественным юнитам ходить друг сквозь друга. Хотя бы иногда?

#10
12:41, 3 июня 2021

skalogryz
> а если там три группы будет?

В узких местах надо ставить семафор с очередью.

#11
15:54, 3 июня 2021

Нашел сорцы к приведенному выше видео: https://github.com/Sandruski/RTS-Group-Movement

Можно попробовать использовать что-то оттуда.

Правда у нее две группы в узком проходе застревают наглухо.

#12
(Правка: 15:59) 15:59, 3 июня 2021

skalogryz
> Б пятится и пятит с собой группу А или В?
B, у нее приоритет ниже

skalogryz
> т.е. в этом случае А и Б могут идти одновременно, а В должна ждать двоих.
ну да, так и будет. Но если А и Б начнут конфликтовать за клетки, то A будут пропускаться вперед

а вот в таком случае хз как быть

-———————————--—————————————————
| *       Б     <-        A
-———————————--—————————————————

звездочка это куда А хочет попасть

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

#13
19:59, 3 июня 2021

Robotex
Cooperative pathfinding
https://arongranberg.com/2015/06/cooperative-pathfinding-experiments/
В каждую клетку ставится время через которое клетка станет доступна. И мы можем заходить в эту клетку при поиске пути только если текущее время больше чем время в ней. Также при поиске должны учитывать время через которое мы дойдем до клетки.

#14
(Правка: 20:36) 20:35, 3 июня 2021

AlexeyLarin
Так на момент, когда юнит подойдет к этой клетке, она уже может быть доступна, но на момент поиска ее отбросили


Вот здесь https://robotex.itch.io/redalertnes я активировал Steering Behavior. Работает Cohesion, Separation и Alignment.

Не очень нравится мне такое поведение: когда юниты доходят до точки, они начинают бродить вокруг нее, движимые Separation. Также стоячего юнита могут выпихать с карты. А еще они почему-то иногда сильно расталкиваются при движении, на большее расстояние чем BoundingRadius.

Код:

#---------------------------- Separation --------------------------------
#
# this calculates a force repelling from the other neighbors
#------------------------------------------------------------------------  
func Separation(flocking_neighbors : Array) -> Vector2:
  if not agent:
    return Vector2()

  # iterate through all the neighbors and calculate the vector from the
  var SteeringForce : Vector2
  var neighborsCounted : int = 0

  for neighbor in flocking_neighbors:
    # make sure this agent isn't included in the calculations and that
    # the agent being examined is close enough. ***also make sure it doesn't
    # include the evade target ***
    if neighbor == agent or neighbor == evadeTargetAgent:
      continue

    if not neighbor:
      continue
      
    var ToAgent : Vector2 = agent.global_position - neighbor.global_position

    SteeringForce += ToAgent / agent.boundingRadius()

    neighborsCounted += 1

  if neighborsCounted > 0:
    SteeringForce /= neighborsCounted

  return SteeringForce

#---------------------------- Alignment --------------------------------
#
# this calculates a force to set one heading with neighbors
#------------------------------------------------------------------------
func Alignment(neighbors : Array) -> Vector2:
  if not agent:
    return Vector2()

  # iterate through all the neighbors and calculate the average heading vector
  var averageHeading : Vector2
  var neighborsCounted : int = 0

  for neighbor in neighbors:
    if not neighbor:
      continue
      
    if neighbor == agent or neighbor == evadeTargetAgent:
      continue
    
    var neighborVelocity : Vector2 = neighbor.velocity

    if neighborVelocity.length() > 0:
      averageHeading += neighborVelocity.normalized()
      neighborsCounted += 1

  var force : Vector2
  if neighborsCounted > 0:
    averageHeading /= neighborsCounted

    # Steer towards that heading
    var desired : Vector2 = averageHeading * agent.maxSpeed
    force = desired - agent.velocity
    force *= (agent.maxForce / agent.maxSpeed)

  return force

#---------------------------- Separation --------------------------------
#
# this calculates a force repelling from the other neighbors
#------------------------------------------------------------------------
func Cohesion(neighbors : Array) -> Vector2:
  if not agent:
    return Vector2()

  # Start with just our position
  var centerOfMass : Vector2 = agent.global_position
  var neighborsCounted : int = 1

  for neighbor in neighbors:
    if not neighbor:
      continue
      
    if neighbor == agent or neighbor == evadeTargetAgent:
      continue
      
    centerOfMass += neighbor.global_position

    neighborsCounted += 1

  var SteeringForce : Vector2

  if neighborsCounted > 1:
    centerOfMass /= neighborsCounted

    SteeringForce = Seek(centerOfMass)

  return SteeringForce
Страницы: 1 2 Следующая »
ПрограммированиеФорумОбщее