• What is your GameDev Story?

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

Recommended Posts

Well after a month of off and on work trying to figure out how to find the adjacents of a chunk in a Quad-Tree. I've been able to get it to kinda work but it's so confusing... Here is what I did. 1. I create a array which checks 4 chunks to see if they need to be spit. 2. I create a array that contains the adjacents of each one of the 4 chunks and I pack this data into 1 byte per chunk. 3. I look at the data from step #1 and if it does not need to be spit I render the chunk. If it does need to be spit I tell it to do this function over with the values of that chunk. Here is the source code:
void DrawPanel(D3DXMATRIX worldmatrix, D3DXMATRIX offsetmatrix, float radius, int layer, int maxlayer, byte adjacents, ID3DXEffect* effect)
{
byte d[4];
D3DXMATRIX tempmatrix;
//Step #1
for(int i=0;i<4;i++)
{
tempmatrix = (ChunkMatrices * offsetmatrix);
//memcpy(tempmatrix.m[3], normalize(tempmatrix.m[3]),12);
float td = distance(D3DXVECTOR3(0,0,0) ,(tempmatrix * worldmatrix).m[3]);
if((td > radius) || (layer == maxlayer))
d=0;
else
d=1;
}
//Step #2
//Step #3
for(int i=0;i<4;i++)
if(!d)
{
tempmatrix = (ChunkMatrices * offsetmatrix);
effect->SetMatrix( "WorldOffset", &tempmatrix );
effect->Begin( 0, 0 );
effect->BeginPass( 0 );
effect->EndPass();
effect->End();
}
else
DrawPanel(worldmatrix, (ChunkMatrices * offsetmatrix), radius / 2, layer + 1, maxlayer, sadjacents, effect);
}


Now the only problem I'm having is figuring out what values need to be in step #2 I got it to work on some of the edges but it's making my head feel like it's going to explode from the complexity. [Edited by - EmptyVoid on June 9, 2008 3:16:35 AM]

Share on other sites
Yesterday, I was trying to create a quad-tree for some path-finding code and I needed the adjacents, so I used this paper as a guide:

http://citeseer.ist.psu.edu/660001.html

There's even some code at the bottom.

What it'll furnish you with (you'll have to expand the two example edge-neighbor functions so you get all four) is edge neighbors of the same size or larger - if you get neighbors that have children, just recurse down and get the neighbors closest to that edge. For instance, if it returns the northern neighbor that has children, you check it's South-West and South-East child for children and keep doing that until you get to the leaf-nodes (i.e. no children), then add them to your neighborhood. It'll even give you corners.

If you hit any snags, feel free to PM me and I'll see what I can do.

Share on other sites
Quote:
 Original post by HexiDaveYesterday, I was trying to create a quad-tree for some path-finding code and I needed the adjacents, so I used this paper as a guide:http://citeseer.ist.psu.edu/660001.htmlThere's even some code at the bottom. What it'll furnish you with (you'll have to expand the two example edge-neighbor functions so you get all four) is edge neighbors of the same size or larger - if you get neighbors that have children, just recurse down and get the neighbors closest to that edge. For instance, if it returns the northern neighbor that has children, you check it's South-West and South-East child for children and keep doing that until you get to the leaf-nodes (i.e. no children), then add them to your neighborhood. It'll even give you corners.If you hit any snags, feel free to PM me and I'll see what I can do.

I can't figure out where the article that your talking about is on that site? I think the site may be down at the moment...

Share on other sites

Click for PDF

Give it a second, though - it does seem to be a bit slow today.

Share on other sites
Quote:
 Original post by HexiDaveUp in the top-right corner are the downloads for the papers:Click for PDFGive it a second, though - it does seem to be a bit slow today.

I think it was down when I tried. Going to read it but I'm not sure if it's quite what I'm looking for.

Share on other sites
When you construct a node in the tree, it not only needs to know its parent, but also its position relative to the parent (top left, top right, bottom left, bottom right)

Then, in the constructor build an array of neighbours.

For example, if the node is the topleft, and you want the left neighbour:
this->leftNeighbour = this->parent->leftNeighbour->topRightChild

If you are in the bottom left, and you want the right neighbour
this->rightNeighbour = this->parent->bottomRightChild

You should be able to work the rest out from there. Of course when you split a node, you would want to inform neighbours of it so they can relink etc.

Share on other sites
Quote:
 Original post by ExorcistFor example, if the node is the topleft, and you want the left neighbour:this->leftNeighbour = this->parent->leftNeighbour->topRightChild

Good suggestion, but remember that the neighbours do not always share the same parent. You might have to visit the grandparents, great-grandparents etc, in some cases (it helps to draw it on paper). It depends of course on the depth of the tree.

Share on other sites
The problem is I am passing the adjacent data for each node down to the next node correctly but after a few layers in to the quadtree it just stops working right...

[Edited by - EmptyVoid on June 11, 2008 3:57:25 AM]

• What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 27
• 16
• 10
• 10
• 11
• Forum Statistics

• Total Topics
634100
• Total Posts
3015527
×