   Questions about pathfinding in Diablo-esque games...
  AS A FIRST QUESTION:I am working on an isometric Diablo-style game, where movement is controlled in a manner similar to Diablo--ie, you click, you move.Clicking and holding on the ground or on an enemy "captures" either the mouse cursor or the enemy, and Player->Update() will update the destination location that the player will walk towards every frame, to account for either the mouse cursor or the enemy moving.  This causes the player to track toward the goal as it moves.In a situation like this, how important is it, in your opinion, to have 100% accurate pathfinding to maneuver through terrain?  Given that, in moving, the player has total frame-to-frame control and continuous updating of the goal, is it best to implement a pathfinder that eats precious frame cycles in generating a 100% accurate path, a path that might be completely invalidated at the next move of the mouse; or would it be best to implement a "best-guess" pather that will operate much faster, but cause the occasional choke, where the player can see that there is obviously a path to the goal, but the pather is not able to find it?I know that I have been irritated when my schmuck in Diablo does not go exactly where I wanted him to, but the irritation is generally mild as it usually only takes a single mouse click to resolve, and being a coder, I am aware of the sacrifices that must be made in the interest of performance.Part of my question, then, is asking your opinions on how you think I should best handle this, and how patient you believe the player will be for an imperfect pathfinder in this style of game.(I know that in other styles of games, RTS in particular, it is more critical to have a perfect or nearly-perfect pathfinder, but I''m not entirely convinced it''s necessary in this style.)AS A SECOND QUESTION:I have been experimenting with a couple of ways of "imperfect" pathfinding: raycasting,limited-length A*, and potential field pathing.I''ve noticed that all three brands have their bonuses, and their annoying little quirks.  I''ve constructed prototypes of all three.In the raycast, I cast out an initial ray toward the destination and check it for blockage.  If it is blocked, I generate a length based on the distance to the blockage, and create a set of rays of this length, at angular increments from the initial ray, proceding around the circle in positive and negative directions from the initial ray, testing the most-adjacent rays first.  If one of these rays succeeds, I find it''s end point and use that as a new starting point to feed recursively to the initial ray caster, basically recursively casting rays and generating waypoints as needed.I specify a Depth at which the raycaster will back out, and if this depth is reached, and a ray at that depth succeeds (regardless of whether or not it has reached the destination) I return TRUE, and at the top level, I use the ray whose tree returned the TRUE value as the ray to use for taking a step, as it seems to be the "best guess".If the ultimate destination is reached, I return TRUE, and the ultimate parent of that ray tree is used as the "best guess"--in this case, a guess that is actually correct.This method works in some cases, and fails miserably in other cases which seem almost idiot-obvious. Sometimes, this failure is represented by vainly trying to walk through an obstacle; other times, it results in the player wandering off like a drug-crazed maniac in a seemingly random direction. Most often, this failure is in closely-packed terrain, where the angular-offset sub-rays can not find a waypoint that makes sense, due to being blocked by other nearby obstacles.For the potential field pathfinder, I basically follow the method outlined in the Potential Field article here at GD.net Motion Planning Using Potential Fields, in the final section where a "field" is generated around each blocking obstacle. When checking for the Next Step to take, I check the potential field weights of each candidate step, and "fudge" these based on the distance to the final destination.This method seems to work very well in many situations, but of course it, too, breaks down in an irritating fashion. Most of the break-downs seem to be in the same areas that throw A* performance into the toilet-- U-shaped or even L-shaped areas that act as "sinks", drawing the player in, then refusing him a way out. In areas of relatively small, globular obstacles, the path tends to stick quite nicely to the "path of least resistance" between those obstacles.I''m rather steering clear of A* at this point, though I have experimented with a maximum path length - limited A* pathfinder, which will return it''s own "best guess" if a certain maximum path length is reached. After all of the path smoothing necessary to ensure that the path generated doesn''t follow your typical 8-directions zig-zag, and given the length-limitation, it doesn''t seem to perform noticeably better than the other two methods in either path accuracy or performance. It breaks down in many of the same situations that the Potential Field pathfinder does, due to path-length limit, and seems to operate with worse performance than the fairly zippy potential field planner.My second question is actually a few questions.Has anyone had experience in implementing one of these techniques in their own project? Can you point me to any research or articles you feel were beneficial? Do you have any ideas for hybrid techniques that might potentially decrease the failure rate for either of these techniques?  Basically, what have I missed? Vague questions, I know, but I''m running out of Google''ed/GDnet/Gamasutra/Flipcode/Amit/Stout/etc.. resources, and I still haven''t got my head entirely wrapped around this thing.I''m leaning more toward the Potential Fields algorithm currently, as it performs more elegantly in simple situations that horribly confuse the raycaster, but before I start optimizing, refining, and installing in-game, I''d like to gather a little more research and input from the masters (you guys).If I seem bizarrely incoherent or completely idiotic in this post, please ignore/forgive me. Thank you   Joshvertexnormal AT email DOT comCheck out Golem at:My cheapass website
  1) I dont usually click very far ahaed when I play Diablo. I expect my guy to be able to dodge a tree or boulder, but thats about it.2) When it comes to perfection in pathfinding, I say YANGI - You ain''t gonna need it. Use the best algorithm that looks decent (not absurdly stupid) and maintains speed. I would rather have a high framerate than my guy take a 1 tile longer way around a tree.But most importantly- send me a demo of your game! It looks pretty awesome.  Brian JDL Vacuum - A media file organizer I made | Mumbling Miles - A band I was the guitarist/vocalist for ;  It seems like with a single character, or even just a few characters, A* wouldn''t be very slow.  In RTS games you have 100s of units using the pathfinder (not necessarily all at once, but...), it seems like if you only have one character doing it, even if you do end up having to find new paths every frame or every other frame it will still be pretty fast. You could do some kind of hiearchical A* and only do high resolution pathing for a small area around the character.  First you''d search find a low res path (maybe with 10x10 or 5x5 map) and then do high res path finding within the current larger node to find a path into the next node in the low res path.    ;quote:Original post by Impossible  You could do some kind of hiearchical A* and only do high resolution pathing for a small area around the character.  First you''d search find a low res path (maybe with 10x10 or 5x5 map) and then do high res path finding within the current larger node to find a path into the next node in the low res path. This is what I was thinking about too: If you have alot of wide open spaces then you can have relatively few nodes and nodes connecting the trouble spots; ie the niche in the L or U is accessible through only one open, grassy node adjacent to it.  If the nodes cover large areas then most of the time it will only be a matter of casting a ray within a node and A* between the nodes (or an adjacency matrix).  Of course in tighter confines, like a dungeon, would be much more difficult.  I haven''t coded this, but my A* that used a 60x60 tile map (32x32 pixels) ran plenty fast on this p3.