Jump to content
  • Advertisement
Sign in to follow this  
Anand Baumunk

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

This topic is 1264 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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
Advertisement

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

My units are smaller than the tiles I'm pathing on, so I can't really use the pathing approach. That's why I am looking for some kind of steering method.

Edited by gnomgrol

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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!