Sign in to follow this  
Anand Baumunk

Advanced unit steering (e.g minion movement in moba games)

Recommended Posts

Hello there!
 
While trying to finish movement for my game, I got stuck with the steering.
I have done a lot of reading on popular steering algorithms, but I could not find one that results in the behaviour I'm looking for.
 
Take a look at my scribble:
OHiAep9.png
 
 
Red box is a wall, Green dots are my units, Orange line is the path for the new unit (from A*) and pink dots the way I need the new unit to go.
The unit in the middle on the path is the one to be steered.
(It is fine to first walk to the wall and then switch the direction).
 
The units which are currently not moving (in this example all besides the one to steer) can not be moved at all.
Also, the speed of the steering unit has to stay constant.
Movement should not look extremly jittery while steering if at all possible.
 
The most promising things I found were boids and flowfield pathingfinding.
Flowfield pathfind looks great in the examples, but is a pretty big overkill. A* is fine for the pathing itself.
Boids can't really be applied, since not all units are moving all the time. One can always suddenly stop and become unmoveable.
Speed does not stay constant with boids and my units are not supposed to group.
I tried to only implement the parts of boids that seperates units, but unit speed still decreases.
 
There are also very advanced things like ClearPath, but those look like a big overkill. They usually are used to prevent moving-moving collisions in advance, which is not needed.
 
I don't really know where to go from here.
A good example for what I am looking for is the behaviour of minions in popular moba games - look at Dota2, LoL or Heros of the storm.
 
If you could point me towards some kind of algorithm or tell me how the big titles (most likely) did it, that would be insanly helpful!
As always, any kind of help is appreciated!
 
Have a nice day and thank you for your time!
-gnomgrol
Edited by gnomgrol

Share this post


Link to post
Share on other sites

You already have working A* algorithm, and it takes the red wall into account. Can't you just provide information about other units to this algorithm in the same way you provide information about the wall?

Share this post


Link to post
Share on other sites

golergka's advice is sound, though it can be kind of fiddly to constantly be updating which tiles are blocked not blocked.  Or are you using a navmesh?  Much more of a pain to update that, though it's doable, I wouldn't suggest it unless those units are immobile for a great deal of time, like deployable turrets.  The steering algorithm should work, it's probably just an implementation issue that your units don't have constant speed after using it.

Share this post


Link to post
Share on other sites

I am using A* on a classic grid, but taking all units into account would mean repathing all units when one unit moves. Units are usualy only immobile for a very brief time, so thats not happening.

 

When using classic steering, a unit will get stuck between two stationary units which are sitting next to each other. Imagine two circles touching each other - the 3rd unit will get stuck right between the two, because the repulsing forces cancel each other out. Can post a picture when I'm home.

Share this post


Link to post
Share on other sites

I am using A* on a classic grid, but taking all units into account would mean repathing all units when one unit moves. Units are usualy only immobile for a very brief time, so thats not happening.

 

When using classic steering, a unit will get stuck between two stationary units which are sitting next to each other. Imagine two circles touching each other - the 3rd unit will get stuck right between the two, because the repulsing forces cancel each other out. Can post a picture when I'm home.

 

I believe the old tile based games just had units calculate new paths every x milliseconds, sometimes only if they are blocked and unable to move.  It's not great, but for a MOBA should work fine, as they tend to have very low unit counts, and players tend to click madly all over the place repathing their own character anyway.  (You could even have different re-pathing rates for mobs/creeps and players)

 

Steering, yeah, there will always be cases that are hard to fix, you can search around to see different attempts at fixing those kind of issues.

Share this post


Link to post
Share on other sites

I'm a beginner at pathfinding, so take these thoughts with a grain of salt:

 

I am using A* on a classic grid, but taking all units into account would mean repathing all units when one unit moves. Units are usualy only immobile for a very brief time, so thats not happening.

 

How about you don't take units into account, doing the regular A* you are currently doing, and if an entity is blocked by another entity and they are within a small range of each other (i.e. "10 ft"), then, preserving your existing A*, run a smaller local A* only taking into account the nearest tiles (the tiles within 20ft) with a "goal" of getting back on the "real" path from the original A*. Take into account other units only in the smaller A*.

If the entity can't find a way around, then just let him walk through the other entity (perhaps having each entity visually step to the side to pass around each other).

To prevent both entities from trying to move around each other at the same time, have the first entity "tell" the second entity not to bother changing its path.

 

Your entity normal pathfinding is gameplay-related. But the entities moving around each other - is that just visual polish, or gameplay-critical? You could just have them walk through each other and "sidestep" (each automatically moves a half-tile to their left if another entity is also on the same tile).

Share this post


Link to post
Share on other sites

You mention that you are looking for an alternative steering mechanic, but without considering the path the steering will follow you will just end up with the same issue of pathway collisions.  No matter what steering mechanic you use, either you need to consider what else is on the pathway or you will suffer from congestion when the next immediate step is blocked.  An alternative steering does not solve the problem.

 

 

Adding to the many good options listed above:

 

* Pause, retry, repath.  If a friendly unit is blocked by another friendly unit, first pause the movement. Perhaps a brief animation, perhaps just pause their simulator. In either event, spend just a moment doing something different to allow the barrier to be removed.  After that brief pause, attempt to continue the movement.  If it succeeds, then the problem is solved.  If it fails and the unit is still blocked, queue the repath.

 

* Consider bidirectional paths when establishing flow and motion.  It takes a little more resources, but in a few games I've worked on we established flow paths. Objects always flowed on the chosen side. This happens in real life, where those using stairs or pathways or roads always stick to the same side. Those going up the stairs stay on their right, those going down the stairs stay on their right, and everybody flows through nicely even though they are traveling the same narrow stairwell.   This works especially well in tight paths like doorways and stairwells that can be marked in advance as bottlenecks needing flow control.

 

* Consider more steps than the immediately-next motion.  Many key areas of the map are frequently traveled by many objects, leading to high traffic and a high risk of congestion. Paths tend to be both verified and recalculated fairly often.  That means that even a slightly compute-expensive path prediction routine is less expensive than frequent collisions and repaths. In some games I've worked on the immediate path before the unit, perhaps 5-10 steps, is tested every time the object moves forward.  If the way is clear those steps are marked as reserved with a path avoidance that includes the unit's direction and estimated number of frames before they enter and leave.  If the way is not clear those steps are tested for the same path avoidance marks, if the other object will not be there when you are planning to arrive, your unit adds its own path avoidance markers to the same trail.  This way a long parade can follow the same path without the other units triggering a repath. 

Share this post


Link to post
Share on other sites

No matter what steering mechanic you use, either you need to consider what else is on the pathway or you will suffer from congestion when the next immediate step is blocked.

 

MOBA minions are supposed to pile up on one another if the path is completely blocked, aren't they? At least that's what I remember from LoL.

Share this post


Link to post
Share on other sites

Thank you for all your answers.

I had implemented what Khatharr suggested before I wrote my post, but that didn't result in what I need.

 

But what frob and servant suggest sounds fine to mine - I'll go with that.

 

Thank you all!

Edited by gnomgrol

Share this post


Link to post
Share on other sites
I dont understand the objection to just rerunning a* once (or twice) every simulation tick (typically less than fps) to compute flow fields.

Use A* with jump point search to go faster.

Use hierarchial tile subdivision to handle smaller obstacle sizes without exploding costs.

You can either run a* every simulation tick, to maintain game pace.. Or you can't, in which case there are problems whenever you are forced to do this.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this