Warcraft 2 grid-based pathfinding with dynamic objects

[BennyTheDog]

Hello everyone,
As the title of thread says I'm trying to figure out what kind of pathfinding is used in the mentioned game. I've been observing the pathfinding for some time and it must be my lack of experience in programming but I cannot conclude how's pathfinding with dynamic obstacles implemented there. I'm torn between couple of ideas but I cannot be sure about it. I'm just asking for someone who has little bit of time to try me to explain how the avoidance works in there?

 

[Pixelated_Pope]

I mean, without talking to a Blizzard employee you probably won't get an exact answer, but I imagine something like A* would work fine. The built in mp_grid functionality is basically A* but missing some pretty key features like heuristics and, most importantly in your case, influence maps.

Influence maps are a concept in A* to change the cost of specific nodes in your pathfinding grid temporarily. In this manner, each unit can consider the position of each other unit when generating a new path. In my own implementation, this can produce some... sketchy results but that could be because of the way my AI is forced to move along the desired path.

 

[BennyTheDog]

Thanks a lot for replying! I will consider your idea with the cost change and try to implement it. I'd never think of it and it does make a lot of sense.
Let me ask you one more thing.. Imagine an NPC unit is moving slightly slower than a player and its movement is pretty fluid. How to decide which tile to take for cost manipulation when NPC's location is right on the edge of two different tiles.

 

[Pixelated_Pope]

First off, there's no such thing as "between" tiles in programming. You do the math and you'll be on one or the other.

Second, your objects don't need to influence a "single" tile only. My objects have a gradient of influence around them. The influence is strongest right next to them, but every tile up to 3 tiles away is also influenced, but with diminishing impact. So there's like a soft "circle" of influence around each object.

 

[BennyTheDog]

I'm so grateful for your answer, Mr. Pope! I'll try to work on it right now! Thanks a lot!

 

[NightFrost]

Influence maps are a concept in A* to change the cost of specific nodes in your pathfinding grid temporarily. In this manner, each unit can consider the position of each other unit when generating a new path. In my own implementation, this can produce some... sketchy results but that could be because of the way my AI is forced to move along the desired path.

That's an interesting idea, but yeah I can see where it can lead to problems, like when the increased pathing cost caused by a unit does not work to be enough to make a roundabout clear path cheaper, leading to the unit walking through the occupied grid anyway (as can be seen happening in the vid); or when the pathing unit is inhabiting the same grid square as the blocking unit, which nullifies the effect of increased cost (since it is the starting square) and visually appears to walk through it.

 

[BennyTheDog]

That's an interesting idea, but yeah I can see where it can lead to problems, like when the increased pathing cost caused by a unit does not work to be enough to make a roundabout clear path cheaper, leading to the unit walking through the occupied grid anyway (as can be seen happening in the vid); or when the pathing unit is inhabiting the same grid square as the blocking unit, which nullifies the effect of increased cost (since it is the starting square) and visually appears to walk through it.

So NightFrost, do you have any better idea? I'm willing to hear everyone's opinion.

I've noticed units actually end their pathing for a while until they "feel" comfortable to proceed (especially when obstacle is located near).

Either of units which are about to encounter can stop for a moment. I'm not sure what's behind the pick but that's irrelevant to me now.

 

[NightFrost]

Dynamic obstacles that themselves are not grid cell-sized are bit problematic. I haven't found a grid-based solution that works at acceptable speeds (that is, supports a goodly number of pathfinding agents). The only thing that's worked well enough has been an alternative approach using steering behaviors. You could look into those, though take note that they are a vector math-based solution; GML doesn't do vectors (GMS2: yet?) so you have to write your own vector scripts or use someone's solution.

 

[BennyTheDog]

In both my game and WC2 object instances (or sprite size) are over tile height, but it shouldn't cause any problem. When overlapping is happening over any object instances (when a tile above (Y-1) is taken) right depth adjustment solves the issue. The one object instances appears to be behind the other and it looks really good like that. What concerns me is right tile distribution while moving. Even when you distribute a 2x2 to a moving object, sometimes overlapping happens and only reason why it's happening is that the moving object takes a different tile than it suppose to take.

 

[GoatSkulls]

Hello everyone,
As the title of thread says I'm trying to figure out what kind of pathfinding is used in the mentioned game. I've been observing the pathfinding for some time and it must be my lack of experience in programming but I cannot conclude how's pathfinding with dynamic obstacles implemented there. I'm torn between couple of ideas but I cannot be sure about it. I'm just asking for someone who has little bit of time to try me to explain how the avoidance works in there?

Hey! Here to chime in what I know on the subject, hope something in here is useful to ya.

The lead programmer on WC1 whose systems were improved upon for WC2 (Patrick Wyatt, lead programmer on the former, producer and all around program helper on the latter) has written a tiny bit about the basic pathing. Based upon his blog (Code of Honor), an informal conversation with him, and looking at documentation / code from bits of projects using the open-source reverse-engineered Wargus engine, there is less going on than you would think. What follows is what I have been able to figure out so far, and might not be completely accurate, but it is certainly an educated series of guesses (i.e. take it with a grain of salt). If anyone has better info / corrections, please post:

Units have what amounts to a 'move' state and a 'wait' state. Instead of considering other units in whatever pre-planned pathing they make, they use a local avoidance that is more readily viewable, flaws and all, in WC1: sort of like mp_potential, but grid-based, not purely a rotary motion like in GM. When they reach a dynamic obstacle along their path, they try local pathing around it, and if not possible, they wait until there is a gap next to them. They have fairly low tolerance though. Try sending several units in WC2 all at once through a funnel shape. Some on the edge might tool around confused, while those in the middle will wait, as they have no direction to rotate/check in. When peasants/peons are harvesting gold in great numbers, watch them carefully. They will path straight to their destination, only rotating/moving around stuff in their way in a basic manner, or if they are prevented from doing so, or are blocked in a certain way, they enter the temporary 'wait' state then continue on once the timer on that is up (this is fairly easy to do in GM using ids, as you can tell units to wait if their id is less than the unit occupying a nearby tile, or whatever). Try finding an area or island that you can access through a small gap, that you could walk/sail around that is not too large. If you plug that gap, most units simply stop and give up. The pathfinding they have does not extend very far by necessity of efficiency.

The A* or similar pre-planned pathfinding going on (EDIT: confirmed it is A*) is only used for a portion of any given units' movement (probably for larger divisions of space, i.e. regions, but not traversing tile-to-tile), and it only considers static entities. In a medium to large size map, try sending units from one corner to the other. They will stop on fairly basic obstacles after a set distance, as their local pathing or something similarly simple kicks in after a short distance. On most maps this is perfectly fine, as there are enough open areas and obstacles conducive to unit-flow (map design is a big part of this illusion of virtual intelligence), but as stated, it doesn't take that complex of an obstacle to confound them (side note: the first time I noticed this was on the Dun Modr human map. Sending units from your base across the river usually ends in them getting stuck in silly places on the river bank, which is why the enemy-producing active barracks is placed in the way it is across the water-- look at other maps with this in mind). This makes perfect sense, as running larger spaces through any sort of pathfinding would be prohibitively expensive, especially considering you have potentially 800 units all doing it,whether in a custom map or online multiplayer! I have played more than a few scenario maps that have had the computer grind to a halt and stop everything because they happened to plug a gap on one side of an island / trees, or something of the sort. Doesn't crop up too often, but it is certainly noticeable.

Try studying it with some of this in mind and I think you will find that it is far simpler than it seems at first glance. I will edit this as additional thoughts come about.

 

[BennyTheDog]

Thanks, man! You've been so detailed about everything, this will help for sure!

 

[GoatSkulls]

Thanks, man! You've been so detailed about everything, this will help for sure!

Of course! Glad to be of service. Make sure to post any progress you make, as I (and many others, I am sure) would be very interested to see it.