Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

Dijkstra and A* are all nice and popular but what kind of algorithm was used in Warcraft 1 for pathfinding?

I remember that the enemy could get trapped in bowl-like caverns which means there were (most probably) no full-path calculations from "start to end". If I recall correctly, the algorithm could be something like this:

A) Move towards enemy until success or hitting a wall

B) If blocked by a wall, follow the wall until you can move towards the enemy without being blocked and then do A)

But I'd like to know, if someone knows :-)

[edit] As explained to Byte56, I'm searching for a low cpu/mem/mem-bandwidth algo and wanted to know if Warcraft had some special secrets to deliver (never seen that kind of pathfinding elsewhere), I hope that that is more concordant with the stackexchange rules.

share|improve this question
2  
I don't think it used A* at all. A 33MHz CPU doing all the raster and in-game calculations? There was probably no room to do any kind of intelligent pathfinding at all. –  bobobobo Sep 14 '12 at 12:44
2  
I don't see how this is more than just trivia. Can you explain how it's useful? –  Byte56 Sep 14 '12 at 16:44
3  
1  
@Byte56 I'm searching a pathfinding algo that doesn't use neither a lot of cpu nor a lot of memory (especially memory bandwidth) and this seems to be it. –  Valmond Sep 14 '12 at 17:24
1  
@Valmond Then you should ask for one. Don't ask how a specific game does A, ask how you can do A. You're bound to get better answers and it wouldn't be off topic (like this question is). –  Byte56 Sep 14 '12 at 17:26
show 6 more comments

2 Answers

up vote 10 down vote accepted

Actually this turned out to be a more interesting question than I thought.

Video

I forgot about the "right hand rule" for pathfinding, but it appears that the game uses it.

Say you're lost in a basement and it's dark. The easiest way to find an exit (if there is one!) is to place your hand on the nearest wall and "follow the wall", following all it's turns and going through it's crevices, until you find an exit. The only time this doesn't work is if you happen to grab a pole ("island") in the basement, then you'll be walking around that pole forever.

I think the game uses some variation of this "follow the wall" rule until the unit can find a beeline to the destination point.

enter image description here

share|improve this answer
3  
From the video you linked, it looked like the orc followed the wall until it got back to the original blocked line. –  tugs Sep 14 '12 at 18:45
1  
Yeah, it looks like it! I jumped the gun on beelining. –  bobobobo Sep 14 '12 at 18:46
    
Very nice video +1 thanks for that! Your image (images and videos should get at least +2 at vote-up!) seems, for me at least, to be like the pseudo-algorithm I described in the original post, right? –  Valmond Sep 14 '12 at 21:07
add comment

I don't think "how did X game accomplish Y?" is technically in the scope of this stack, but I'll hazard a guess as to why some pathfinding algorithms get stuck in a bowl: They run something like A*, but only up to a certain depth. This limits the amount of processing time spent pathfinding, but doesn't guarantee exhaustive search [which might be a good thing, Starcraft had that issue where dragoons would wander to the other side of the map trying to find a path]

Illustration of two orcs navigating bowl-shaped walls

In the top scenario, the top orc's search radius is too small. The "best" visible point is marked A, the "best" navigable point is on the closer side of the wall across from A.

In the bottom scenario, point A is now navigable, but point B should be the "best" navigable point, and that would be the path a constrained A* would take.

share|improve this answer
1  
Thanks for the answer but I doubt A* was used, you can get Dijkstra to run much faster in small 'maps' if you got direct memory access (ie. C/C++ / asm). –  Valmond Sep 14 '12 at 17:28
    
thanks for the edit but I think the algo works as I explained, otherwise the orc wouldn't move along the wall (and for my example to 'fail' then the bowl have to be rounder, like a circle with a small opening in it, your example would work I think). I'd love to know for sure though :-) –  Valmond Sep 14 '12 at 17:34
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.