Jump to content
  • Advertisement
Sign in to follow this  
lucky6969b

About Quadtree (spatial partitioning)

This topic is 1049 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
Advertisement

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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!