Sign in to follow this  

[.net] QuadTree in C#

This topic is 4381 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

Hi everyone! I just have a question.. Can anyone help me to find a nice guide to write a QuadTree in C# Managed DirectX.. I have done a QuadTree in C++ but i think is't a little more difficult to write it in C# there the most syntax and the pointers are gone.. or just to difficult to understand. I'd be glad fore any kind of help.. //Esperanza

Share this post


Link to post
Share on other sites
I thought that to that it will be easy to port from C++ to C# but i'm a NOOB in the C# area.. i have only worked with it a couple of weeks.. but do you have some links or do you know any tutorials that might help?
I need help with the entire quadtree.. i know how to the boxes and stuff like that.. but it's the the code that generates the quadtree that is the mayor problem..

//Esperanza

Share this post


Link to post
Share on other sites
I'm not sure if you have trouble understanding how a quadtree is constructed? If that's so, I suggest you read up on quadtrees.
There is a QT tutorial here at gamedev:
http://www.gamedev.net/reference/articles/article1303.asp

If C# is the problem, then I guess you should be able to find a ton of tutorials on the net.

I also found this at "The ZBuffer" (www.thezbuffer.com):
http://www.eteractions.com/
I haven't checked it out, but it's supposed to contain a C# implementation of a QT.

Hope this gets you started...

Share this post


Link to post
Share on other sites
No i'm not having trouble with understanding how a quadtree works and how it's constructet.. is just the C# i have problems with..
I have search the net for C# tutorials for QT but i havn't found any yet..
But i will check out the links that you posted..
Thanks..



Share this post


Link to post
Share on other sites
one thing to remember with C# is that object reference more closely resemble C++'s object pointers. Yes, they are syntactically different, just imagine as if all the dereferencing is being done for you.

An example of what I mean


class Bar{
//...
}

void Foo(Bar c)
{
//more ...
}



disregarding the lack of semicolon on the end of the class, if these two constructs were replicated in C# and C++ they would act fundamentally differently. In C#, calling Foo with an instantiated Bar value will not make a copy of the Bar instance, but will make a copy of the Bar reference to the instance. In C++, the Bar instance itself will be copied and passed to the function.

So, these two classes are essentially equivalent.

class CSharpFoo{
private CSharpFoo a, b, c, d;
}

class CPPFoo{
private:
CSharpFoo *a, *b, *c, *d;
};




Java is similar to C# in this regard. However, C# offers a few keywords over Java to make it behave more like C++, namely the out and ref keywords.

Share this post


Link to post
Share on other sites
The Game Engine Design in C# book that's out has a chapter on the rendering pipeline with Source Code, etc. There is a whole section on not only understanding the quadtree but actual implementation that he did. You can get source of the engine (a basic engine) at APRESS.com. Otherwise, the book is pretty good. Goes over a lot of good elements for an engine but doesn't deliver the entire implementation, just overviews good design.

Good luck and I hope this helps!

Share this post


Link to post
Share on other sites
This is something I'm just typing into Firefox, but it ought to be close enough:


namespace foo {
class QTreeNode {
public QTreeNode topleft;
public QTreeNode topright;
public QTreeNode botleft;
public QTreeNode botright;
public System.Collection.ArrayList nodeData;
};

class QTree {
QTreeNode root;
int width;
int height;
int maxDepth;

QTree() { maxDepth = 10; width = 8192; height = 8192; }

public void Insert( object o, int x, int y ) {
InsertAtDepth( maxDepth, ref root, o, x, y, 0, 0, width, height );
}

public void InsertAtDepth( int md, ref QTreeNode n, object o, int x, int y, mx, my, tx, ty ) {
if( n == null ) n = new QTreeNode();
if( md > 0 ) {
int midx = (tx+mx)/2;
int midy = (ty+my)/2;
if( x >= midx ) {
if( y >= midy ) {
InsertAtDepth( md-1, n.botright, o, x, y, midx, midy, tx, ty );
}
else {
InsertAtDepth( md-1, n.topright, o, x, y, midx, my, tx, midy );
}
}
else {
if( y >= midy ) {
InsertAtDepth( md-1, n.botleft, o, x, y, mx, midy, midx, ty );
}
else {
InsertAtDepth( md-1, n.topleft, o, x, y, mx, my, tx, ty );
}
}
return;
}
if( n.nodeData == null ) n.nodeData = new System.Collections.ArrayList();
n.nodeData.add( o );
}
}
}



You do querying and removal in much the same way. Yes, it can be optimized with block allocators and all that jazz, but this shows how to do a quadtree in C#.

Share this post


Link to post
Share on other sites

This topic is 4381 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