Archived

This topic is now archived and is closed to further replies.

wolfbane

AI pathing in something like Diablo

Recommended Posts

I am writting an rpg an was wonering what would be the best method of doing ai pathing? the rpg does not use an isometric grid. A good example of what im talking about is Diablo or Starcraft. Can anyone tell me the type of AI pathing those games used?

Share this post


Link to post
Share on other sites
Both Diablo and Starcraft used an isometric grid.

Diablo used A* I''m guessing, and SC seems to use some weird pathfinding where units move in random directions and crash into each toher until they get stuck, or get to their destination.

I know in Starcraft they had to save cycles by not using a full A* pathfinding scheme, but sometimes the pathfinding really is pathetic. Especially when your units have to go down a ramp or something.

Share this post


Link to post
Share on other sites
How small do you thing the grid was in Starcraft? was the size of the units like the zerglings or marines? I took a look at the movement and saw that the units do travel in an isometric fashion.

Share this post


Link to post
Share on other sites
I don''t know what the minimum size was in SC, but I believe they used a system where they parse the map down from larger grids to smaller ones where possible so the grid sizes can actually vary.

Dave Mark - President and Lead Designer
Intrinsic Algorithm -
"Reducing the world to mathematical equations!"

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
>>and SC seems to use some weird pathfinding where units move in random directions and crash into each toher until they get stuck, or get to their destination

LOL! I remember shelling units to shreds while they just went back and forth in my fire zone.

Share this post


Link to post
Share on other sites
I was wondering the same, and I played around with a few different methods--ray-casting, potential fields, and a limited A*. I got the best/least-stupid results from the A* with path smoothing; it actually seems to work fairly well, though I haven''t stress-tested it with more than about 15 monsters + the player yet.

The way I do it is this:

First, my map is organized in tiles, which are themselves subdivided into smaller grids of 4x4 subtiles for pathing.

Initially, I check to see if pathing is even necessary; if not, a straight shot is calculated. Straight shots are calculated for other situations, such as if the destination location is in the middle of a wall, or some other situation where pathing would propagate to it''s maximum depth and needlessly waste CPU cycles.

If the initial test indicates that we need to path, then I run an A* search on a small (64x64 subtiles) subset of the map, centered between the start and endpoints of the path. Sometimes, the path sneaks outside this area, so I return a failure, and default to a straight shot. Sometimes, the pather searches to near maximum depth (ouch) without a path being found; again, I default to a straight shot.

In the event that a path is found, I iterate backwards through the just-built path, checking at each step to see if I have a straight shot to the location of that step from where I now stand. As soon as I have a straight vector, I return it, and feed it to my movement logic.

Monster pathing is significantly more limited, presently to a search area of 16x16--enough to path around a tree or boulder if the player is nearby, but not so much as to overly tax the system.

I am pleased with the results so far; it runs smoothly, finds paths in most of the situations where it seems logical to find a path, and doesn''t act obviously stupid in most other situations. I initially hated the idea of doing a full A* search, constructing an elaborate path only to return a single vector, in effect throwing the rest of that hard work away; but as movement tracks the mouse, I could not think of a method for avoiding needless recomputations of a similar path over and over each update cycle--at least not one that didn''t introduce greater complexity than I am currently equipped to deal with. Given the fact that I maintain framerate even with the current (soon to change) system of performing a full Update() on every entity in the map every frame, as well as a path search for the player at each frame, I am no longer so concerned with any possible performance hits from pathing in the final product.

This method could easily be adapted to a rectangular environment (with even less occasional wierdness, even, than in an isometric, I think).

It seems to me that the pathing in Diablo might be even more limited than this in some respects, as you can occasionally see your character fail to find a path around seemingly trivial objects; more akin to the wierd failures I got in my Potential Fields experiments, where pathing ended up in "neutral sinks" of potential, going nowhere.


And I seem to remember reading somewhere that StarCraft actually used a rectangular grid, and "faked" the isometric appearance. I could be wrong, here, though...Stranger things have happened...


Josh
vertexnormal AT email DOT com

Check out Golem at:
My cheapass website

Share this post


Link to post
Share on other sites