Sorry about the length of this post but I couldn''t describe it any shorter. I''m new to this forum and I wish I''d found it sooner. I''ve been working on a game for the last 9 months and I''ve constantly been getting hung up on the pathfinding ai. Hopefully this forum can ease my woes. It''s the first time I''ve developed a 3D game of this scale and with pathfinding. I''m developing a 3rd person perspective game which involves hand to hand combat fighting and magic. I''m using the Wildtangent 3D engine with java. I''ll probably get a lot of guffaws for saying that. No it''s not as fast as c but it''s still capable of producing a good game. Anyway, the game engine is quite developed at the moment but one point I''m having trouble with is the pathfinding ai. I''ll just explain how I''m doing and hopefully someone who''s done it before can offer some helpful tips and maybe some people might even get some ideas from it. A level is split up into a whole bunch of connecting 3D sectors. Each sector being connected to one or more other sectors at entry and exit points. Each sector contains a grid which tells if a cell is passable or not as well as other things. I''m using A* but with graphs instead of a grid. ie. certain cells are set as nodes and these are placed around obstacles. All these nodes are connected either directly or via another node and all distances between these nodes are precalculated. So from any point on the grid, you can work out the shortest path to any other point via these nodes. The reason I use these instead of doing a grid based A* search is that I want straight line movement, not cell by cell movement and I''ve got guaranteed process time for a best path search and it''s also so much faster than grid based that I can do frame by frame checks which is better suited to the style of game it is. The downside to it, (there''s always a downside) is that while it can be used to navigate a level, it can''t be used to navigate around moveable obstacles, like npcs. For that though, I figured I can just use a simple path search when the player hits an npc. Below represents a simple grid and the nodes are set up like so. O = empty space, X = blocked space P = NPC T = target and N = node 0 0 O 0 0 0 O 0 0 0 0 T 0 N 0 0 0 N 0 0 0 0 0 0 0 X X X 0 0 0 0 0 0 0 0 X X X 0 0 0 0 0 0 0 0 X X X 0 0 0 P 0 0 0 0 X X X 0 0 0 0 0 0 0 N 0 0 0 N 0 0 0 0 0 0 O 0 0 0 O 0 0 0 0 Each node in this example can see two other nodes. The pathfinding cycle is like so for when P wants to get to T: It performs a cell based Bresenhams line check from P to T. If it hits nothing, it''ll return T as a waypoint to head to. If it hits a blocked cell, which it will in this case, it performs the A* search. First it does the line check to all of the nodes in this grid and any it can see go into its node group. Two in this case. (this can be sideskipped if you pre-calc node groups for each cell so the cell already knows what nodes it can see). Same happens for T. Then A* is performed with this information to find the shortest path and returns the first node as the waypoint to head to. So at the end of it, the npc simply gets a waypoint to head to. On top of that, it needs to then do object collision detection and if necessary find a way around the object. It performs this every frame so as soon as it can see the target, it will start heading towards it. The problems I''ve got are with space management and characters that are larger than the size of a grid cell which are sort of the same problem. Because I''m using straight line movement, an npc may occupy 4 cells if it''s sitting in an intersection line on the grid. Because all these 4 cells can only be occupied by the one npc, it''s about 75% wasted space. I''ve thought of doing, when an npc hits another npc, calculate the distance needed to move to the side of it instead of moving via cells. This gets very complicated though if there''s another npc to the side of it or slightly offset and even more complicated and expensive trying to find a route around them. This difficulty is partly due to the fact that each npc is updated per frame instead of having a calculated path so a point that is available one frame might not be in the next one. I guess I''m going to have to use a calculated path to get around this problem. Maybe when an npc hits another npc, switch to grid based movement and designate cells to move to. I''m also not sure how to manage sprites larger than a single cell when it comes to finding a path through a level. If I''ve got a sprite whose size is 4 grid cells, how do I know if it can pass through a particular area. I''m not sure how you''d do this even with grid based A*. One idea I had is that instead of using a single cell as a node point, break the grid up into a series of rectangles and each one of these will be a node. That way when performing A*, I can check if the npc can fit through a rectangle based on its width and height which are the number of cells wide and high. This has the problem in that I then have to calculate the best entry and exit point on a rectangle and the distance between them. It''ll still probably be faster than a grid based search though. I''ll leave it at that for the moment. If anyone read this far, thanks, and any feedback would be greatly appreciated as this is the first time I''ve done this and I''ve no idea if I''m missing a much simpler or better way. Thanks, Jules.

If you''re looking for alternative nodal algorithms, try this:

http://www.geocities.com/bpj1138/shortest_path.html

as far as your "NPC too big to pass through" thing, well, you could store the maximum size of the NPC that can pass through a node, then when doing the path finding, if the NPC is too big, you can "artificially" increase the "cost" of that node in the path, so if NPC.radius > node.maxRadius then node.cost = infinity.

hope that helps..

Thanks bpj1138,
I thought of adding a size value to the nodes and it seems like the best deal at the moment. It would need a value per node connection and I guess I''ll just factor that into the heuristic.
Thanks for the link too, it had some helpful ideas.
Jules.