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

## 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 on other sites

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 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 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

1. 1
Rutin
29
2. 2
3. 3
4. 4
5. 5

• 13
• 13
• 11
• 10
• 13
• ### Forum Statistics

• Total Topics
632960
• Total Posts
3009475
• ### Who's Online (See full list)

There are no registered users currently online

×

## Important Information

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!