Sign in to follow this  

About Quadtree (spatial partitioning)

This topic is 831 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Edited by lucky6969b

Share this post


Link to post
Share on other sites

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?

Edited by lucky6969b

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites
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

Edited by Alberth

Share this post


Link to post
Share on other sites

This topic is 831 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this