🔒 Locked

Adjacent Nodes

Started by NightWraith Oct 31, 2000 at 10:42 AM 1 replies 350+ views

Original Post

Oct 31, 2000 at 10:42 AM

I''m not exactly sure where I should be posting this one, so I''m putting it here... I have a basic 2D map which, in order to speed up my path-finding algorithm, I''m dividing up into larger sections (groups of tiles) using a binary tree (each node of the tree is either blocked (i.e has something(s) in it) or empty). Each node of the tree contains the co-ordinates of the center of that node (the center is assumed to be the top left of the specified) map tile (besides the pointers to child nodes). The plan is the instead of planning a route on a square-by-square basis the AI will consider it on a node-by-node basis. The problem I have is this... How do I find all the adjacent nodes (an adjacent node in this case is one where the EDGES touch if only the corners touch then they are not adjacent) quickly (i.e. using the tree and not visiting every node)

Yanroy

Oct 31, 2000 at 12:22 PM

I have never done anything like this before, but here''s my $0.02. You are probably using a quadtree to divide the map into four quadrants, then those into four quadrants, and again and again... until you get to just one tile. If I was doing this, I would base it off of an artificial neural net (maybe this is standard practice) so that the top of the parent node will report the average status of its child nodes... which report the average status of their child nodes... All you need to find the adjacent nodes is the lowest level of the tree you are starting at. Travel backwards through the tree until you find the node that encompasses the quadrants around your location. Precisely how to do that is tickling the back of my brain, but I think I would need to spend several hours unconscious before it came to me.

--------------------

You are not a real programmer until you end all your sentences with semicolons; (c) 2000 ROAD Programming

You are unique. Just like everybody else.

Yanroy@usa.com

Visit the ROAD Programming Website for more programming help.

NightWraith

Nov 1, 2000 at 2:50 AM

Thats not quite the method I''m using...

Firstly I''m using a binary tree as this leads to a smaller number of sectors than a quadtree. The problem with a quadtree is that if only the bottom quater of a square is "full" then the square gets split into 4 rather than the 3 a binary tree would make of it (I''ve tried a fer experiments and have found that on average a Binary tree gives 3/4 the number of sectors as a quadtree, (on a 16x16 grid thats about 25 sectors saved.. and since I''m going to running maps 256x256 thats a lot of saving))

Secondly I''m not splitting every node of the tree all the way down to the single square level.. if I did that it would make the tree pointless! as I already have a grid of single squares. I am only splitting each node if it is not 100% empty or 100% full (down to a minimum sector size of "1 square")

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.