Hi folks! I''m trying to come up with a good pathfinding scheme on a 3d terrain, drawn using a quadtree. What i want to simulate is this: the "character" can walk on the whole terrain, except on "water" areas. The terrain is based on a height map, and id assum that heights go from 0 - 255. heights from 0-10 are water areas. The character is free to walk elsewhere, but the "optimal" path for this special case is this -it should go from point A to B with minimum height changes - it should avoid climbing or going down hills, and try to go a way around. I''d use the A*, but I couldn''t come up with some ideia to use the quadtree structure instead of the heightmap to use as wayponits. Using the heightmap in big meshes would have a high cost, and the quadtree reduces a lot the number of points where to look for a path, and would be very good to take advantage over this data structure for the path planning. But there''s not many directions to choose from one quad tree point to another. Consider the following scenario: x x B x x o o x x x x C x x x x o o xA x x x I want to go from A to B, and C is the center of the quadtree. The "o''s" are the quads centers, and "x''s" their edges. See the problem??? The points can be actually "outside"the qtree structure... Does anyone knows an algorith fro pathfinding that actually uses and qtree scheme, or have any ideas on how to solve this? I look forward for your ideas! many thx in advance! Luiz

Seems that the spaces where trimmed.. now "_"= spaces =P

x_xBx_x
_o___o_
x_x_x_x
___C___
x_x_x_x
_o___o_
xAx_x_x

I''ve got an article on my desk in my office that provides the solution you need. It covers 3D pathfinding using tree structures. I''ll be back in my office sometime this week so I''ll post the reference in this thread when I have it.

Cheers,

Timkin

THX!!!