How can I create the arriving/ engaging in combat movement like in StarCraft 2?

Question

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:

StarCraft 2 handles this beautifully, as seen here:

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.

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.

Answer 1

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.

Answer 2

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.