5
\$\begingroup\$

I currently have two armies (smaller scale) crashing into each other. They will usually form a line of units fighting. I have no idea how to handle a unit coming from behind the line to properly go around its allies to reach the enemies. Like in this position, where a new unit approaching from the green army needs to navigate around the battle front to reach the red enemies:

Diagram of green unit approaching a battle front

StarCraft 2 handles this beautifully, as seen here:

Units swarming in SC2

I've read that SC2 uses steering for local avoidance and A* and some other methods to plan out the paths. Which all is perfectly clear, but I haven't found anywhere any details on engaging the enemy.

This is what I have, it's been a month and I still haven't solved this specific issue.

Units failing to surround

How is it possible to do continuous checks of possible destinations before engaging the enemy, wouldn't it be too costly? To clarify, in the video of the Zerglings vs Zealots, they first engage each other and form a line, all the other units that come after them will go around the line, but, if space opens in the line they will immediately go towards it. This kind of arrival behaviour is briefly explained in their GDC talk, they have a cone of vision in which they do checks. The only ideas I had was

  1. Have a cone of vectors (in the direction of Velocity) and do checks for each vector to see if it could provide a favorable position to move to

    issue: Cannot figure out the math to create offsetted (by an angle) vectors, but it seems like a pretty decent solution

  2. Have a spatial query in a rectangle to where the unit is moving

    issue: How do I check for an empty space? I can get all entities in that rectangle but how can I check for empty places and score them (how favorable are they)? Are they even reachable, I'd still need some kind of raycast like with the first option

I have circlular collision shapes, seperation and goal following in place. I somewhat have introduced a goal system that should further spread the units, but as it stands I still lack the arrival behaviour described in the GDC talk.

\$\endgroup\$
9
  • 4
    \$\begingroup\$ Please do not keep deleting and re-posting variants of the same question. If your previous versions were not getting the answers you wanted, edit them. \$\endgroup\$
    – DMGregory
    Apr 29, 2021 at 17:33
  • 1
    \$\begingroup\$ @DMGregory First question was related to a previous approach I mentioned in this post so it isn't relevant anymore. Previous question was edited incorrectly and didn't reflect my question properly. This should convey my question more properly. I also waited a couple of days in between them. \$\endgroup\$ Apr 29, 2021 at 17:37
  • 2
    \$\begingroup\$ @Nikola-Milovic If it was edited incorrectly, you should rollback the edit, preferably with comments summarizing why the edits made by others made the post worse. Edits are almost always well intentioned; if they don't reflect your question it may mean that your question hasn't been explained sufficiently to be understood by someone else. \$\endgroup\$
    – Pikalek
    Apr 29, 2021 at 18:39
  • 1
    \$\begingroup\$ @Nikola-Milovic Questions can be sorted by "active" or "newest"; editing affects the order of the first, but not the other. Edits just to bump may be considered misuse; better alternatives are given here. \$\endgroup\$
    – Pikalek
    Apr 30, 2021 at 14:19
  • 1
    \$\begingroup\$ Also, as written, you've asked about how SC2 tackled this problem. However, it might be more useful to ask how you can better solve the problem. Explain / show your code for the pathing / steering & walk us through one or more specific examples of how your units are getting stuck. We can see the results in the image clip, but unless you share how your engine works, at best we can only guess as to why you get those results & how to fix them. Given the differences between the two, it might be better to ask that as a new question. \$\endgroup\$
    – Pikalek
    Apr 30, 2021 at 14:27

2 Answers 2

2
\$\begingroup\$

Your main diagram illustrates the lowest green unit not knowing which way to go. When I initially came to this problem I found standard avoidance would make the unit yo-yo between friendly units. So, instead I force the unit to pick a direction to move around friendlies and stick to that avoidance direction. This could lead to the unit moving the slower way round to the right in your example image but that's probably not something that matters much in an RTS. It doesn't have to be perfect - just not too stupid.

Which all is perfectly clear, but I haven't found anywhere any details on engaging the enemy.

Steering can be used when engaging the enemy in the same way. But the steering rules do get quite a bit more complex.

How is it possible to do continuous checks of possible destinations before engaging the enemy, wouldn't it be too costly?

If you store the unit positions in some sort of spatial partitioning data structure then finding out which units are at a particular area isn't too costly.

I've written a little more & put some diagrams on the spatial partitioning & boids avoidance behaviours similar to SC2 here: boids avoidance for surrounding groups

With accompanying youtube vid here which demonstrates tweaking the behaviours to get the desired effect: video of advanced boid avoidance & surrounding

I stress that verbose visual debugging of steering forces becomes essential (as they mentioned in the SC2 talk) if you want to get complex interactions working and understand what's going on. You can see I took the debug visualisations quite far in the video.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ I've been reading this over and over again and it's amazing. After weeks of researching this topic, this was an amazing find. I've checked out your other videos and posts and they are all superb. Can't wait to see more of it! I'd love to see a followup post that goes a bit more into the surround behaviour and the spread of targets. \$\endgroup\$ May 19, 2021 at 5:58
  • \$\begingroup\$ Thanks, glad to hear it's helpful. I will be posting more RTS AI related content in the future. \$\endgroup\$
    – jdtec
    May 22, 2021 at 13:54
2
\$\begingroup\$

The GDC multi-game session AI Navigation: It's Not a Solved Problem - Yet includes an explanation of how Star Craft 2 handles navigation. The SC2 content is presented in the first 20 minutes of the talk. There's a joint question and answer portion at about the 54 minute mark with a number of question pitched to SC2.

While a complete transcript of the material is outside the scope of an answer, here's an overview with some key portions that apply to your question as posted.

The pathing in SC2 occurs in three steps: planning, steering, collision.

Planning

The planning is done using A* & funnel algorithms on a constrained Delaunay triangulation. A sparse regular grid is used to locate units within the triangulation. From your post, it sounds like you've focused on grid-based solutions. If you're interested in an SC2 style solution, you should explore a navmesh style model.

The planning step does account for the attack range of the unit, but it does not include any mobile units (they are dealt with via steering & collision). Note: mobile units in this context seems to mean any units capable of moving as the can potentially be nudged out of the way (as discussed under collisions). Units only store the next two steps of their pathing plan; the assumption is that by the time a unit gets further than that, things have probably changed enough to require re-planning anyway.

Steering

Compared to pathing & planning, steering required the most work in SC2. Most of the steering behaviors are based the Boids work pioneered by Criag Reyonlds.

The high level steering behaviors identified are:

  • Following
  • Flocking
  • Grouping
  • Separation
  • Avoidance
  • Arrival

Of these, the avoidance step required many iterations to find a solution that worked well. In the end they settled on the following approach:

  • figure out what you can ignore
  • plot obstacles
  • don't turn if the center path is clear, otherwise aim for the closest gap
  • don't path into walls
  • check the steering intent of on coming traffic to avoid the "hallway dance"; that is to say: if an oncoming unit has decided to steer to the north to go around you, you shouldn't also steer north as you'll collide with their intended course correction

The arrival step is discussed during the Q&A session. While a group may to collective pathing, each individual unit gets its own destination point. Furthermore, the system never allows two units to path to the same location.

Collisions

SC2 units are allowed to push other units using a limited physics model. The overall rule set is complex but here are some of the basics:

  • conceptually all mobile units are modelled as circles
  • idle friendly units get pushed out of the way
  • faster units get pushed out of the way more than slower units
  • typically opposing units push each other out of the way equally
  • units being told to hold a position don't get pushed
  • attacking units don't get pushed (mentioned during the Q&A)
  • the simulation is limited in the number of "rounds" required to find an outcome

In the animation clip you linked, it looks as if the units that arrive later either don't realize that an allied unit has stopped in front of them or are failing to take appropriate action. Connecting it back to the SC2 presentation, that seems like a problem with either collision detection or avoidance. It's also possible the problem stems from the arrival steering behavior - that is to say, the late units are attempting to move to the location that their engaged ally has stopped at.

\$\endgroup\$
2
  • \$\begingroup\$ how does the arrival behaviour work? They mention using a field of vision infront of the unit. Either with a fan of vectors or checking every single free position in a rectangle in front of the unit? I have circle collision shapes like SC but currently stuck on this step. Other steps are somewhat clear but this one is puzzling, as I am not sure about the math for the vectors (fan of vectors in front of the unit) or checking every single position could be kinda costly depending on how its done. From the videos it seems that they have some kind of a quick clever check \$\endgroup\$ Apr 30, 2021 at 17:44
  • \$\begingroup\$ Gather the nearby obstacles with a close-range query. Project those circles (expanded by a multiple of your own radius for clearance) into your local heading space: each one maps to an interval, so you can manipulate them easily as a start angle and an end angle. Take the union of those intervals, then find the gap closest to zero (dead ahead) \$\endgroup\$
    – DMGregory
    May 1, 2021 at 12:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .