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!"

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