http://www.ai-blog.net/archives/000091.html

I am wondering how do I identify which node is walkable.

Say when I first break up a tile which covers the whole scene into 4 divisions.

And there are heaps of obstacles in the leaf node, how can I tell the obstacles are located in there

I am using DX9, D3DX....

Update:

BTW, how do I use AStar or TimeAStar with QuadTrees?

Thanks

Jack

http://mathieuturcotte.ca/textes/quadtree/quadtree.html

When I compiled this code with Visual Studio 2013 community, I am getting these results after running it...

assert failed at line 992 in test_5x5_quadtree: q02->distance(q22) == 2.0
assert failed at line 993 in test_5x5_quadtree: q22->distance(q02) == 2.0
assert failed at line 995 in test_5x5_quadtree: floor(q02->distance(q20)) == 2
assert failed at line 996 in test_5x5_quadtree: ceil(q02->distance(q20)) == 3
assert failed at line 997 in test_5x5_quadtree: floor(q20->distance(q02)) == 2
assert failed at line 998 in test_5x5_quadtree: ceil(q20->distance(q02)) == 3

Would anyone like to test this code as well on their side?

Pathfinding algorithm is completely separate from node storage.

Afaik a quad tree is just another form of node storage. Assuming the quadtree uses position as key, it's just another form of storing the world.

You give it a coordinate, and it returns a node to you, just like "node[pos]" in a grid-like structure, except the "[]" operation is a bit more complicated.

The pathfinding algorithm generates positions that you need to inspect. Based on the content of the queried position, you decide walkable/non-walkable, etc.

I don't know what TimeAStar does, but I assume it wants some extra information. If you can derive that information from the node contents (or from more queries of other positions), then yeah, you can use TimeAStar too.

Sorry, I have no time to try that code right now.

Would anyone like to test this code as well on their side?

I tried it, and it works at my Linux 64 bit system.

Edit: With a few warnings about reordening the order of initialization