Sign in to follow this  

Which spatial partitioning method suitable for my game?

This topic is 3631 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 guys, I'm coding a homebrew 3D racer (a Wipeout clone for the Nintendo DS) and used to have an octree to partition the level before I started recoding everything. I'm now reconsidering the method I should use: there seems to be a general opinion that kd-trees are the be-all-and-end-all but I'm questioning it's suitability for my game. The racer will almost always be on the track, but I don't want to split the level into a linked chain as I want users to be able to build tracks with shortcuts and multiple paths e.t.c. Kd-trees seem to be ideal for splitting geometry from empty space, however this seems good for a raytracer but maybe not for my game. As the racer will almost always be colliding with the track every frame, splitting empty space from geometry won't benefit me much I don't think as I won't be avoiding collisiosn, unless for a kd-tree I use a different heuristic than the SAH. However, I'll be using really short segments and spheres to test against the tree, but maybe down the line I'll add some raytracing for AI or something. Any thoughts? The following image is an example of what the level geometry will look like, remember the racer will be colliding every frame so I have no need to avoid collisions by separating empty space. P.S. As it's for the Nintendo DS, I'd also like the method to be memory efficient, although without any compression as processor efficiency is much more important. Free Image Hosting at www.ImageShack.us

Share this post


Link to post
Share on other sites
I'm not an expert on spatial subdivision, could you explain why you think an octree is not efficient?
From what I understand is that octrees are divided uniformly. That combined with the fixed polys per frame for the DS, and I would guess relatively short zfar ,might give octrees more optimal results than kd trees, where subdivision dimensions are not uniform.
Am I missing something here?

It sure sounds like a cool concept. Reminds me of the 386 days of Stunts. Building tracks was usually more fun than racing hehe.

Share this post


Link to post
Share on other sites
Is this for collision or rendering purposes, or both? If collision only then I'd be tempted to go for something race-track specific, like storing a graph of track sections (like your linked list idea, but allowing for multiple exits/entrances from each segment). If you need it for rendering as well then perhaps a quad or oct tree is going to be more useful. If your camera is reasonably fixed then you could precalculate which octtree nodes are visible from each track segment and save yourself some runtime calculations.

Share this post


Link to post
Share on other sites
Thanks for the replies guys. Wow I totally forgot about rendering, which is another reason why I'd use it. I guess an octree would be more useful if I only want one tree structure. I could have 2 trees, an octree for rendering and a linked tree for collisions, with the octree I could also store a precalculated table of nodes to draw for each node.

If going just with the octree, how efficient would an adjacency table be for storing nodes surrounding the current node? This way if not in the current node, I could just check nodes around it, the player would probably be within one of these nodes.

Also, could you elaborate more on the graph of track sections? I'm not sure what the graph part means, but I'd like to know!

Share this post


Link to post
Share on other sites
Quote:
Original post by Rajveer
If going just with the octree, how efficient would an adjacency table be for storing nodes surrounding the current node? This way if not in the current node, I could just check nodes around it, the player would probably be within one of these nodes.

I'm not sure that's a good idea - depending on the size of your objects and their position a player may be very close to you in distance but not be in an adjacent tree node. I'd just stick to doing a proper recursive search, unless your tree is very deep there shouldn't be any real difference and it'll be more robust.

Quote:
Also, could you elaborate more on the graph of track sections? I'm not sure what the graph part means, but I'd like to know!

By graph I just mean a structure of linked nodes. A linked chain you mention would have each node (a track section) store a link/pointer to the previous section and the next section. It's fairly trivial to change that to allow multiple "next" sections and multiple "prev" sections and you've got a graph structure capable of handling tracks with shortcuts, pit lanes, etc. etc.

Like most problems you've got to decide on your tradeoffs. A quad or oct tree is probably going to be the most general and flexible. On the other hand something written to take advantage of the nature of your race track (ie. limited player and camera movement, constant forward progression instead of free roaming) could be faster at runtime at the expense of flexibility. If this were for pc I'd say just use the octtree method, but with the DS's limited CPU you may have to go the other route.

Share this post


Link to post
Share on other sites
I guess the best way to know which is best is to test them both. Octrees seem to work well at the moment but a linked node structure would most likely work better. One key difference however is the creation of the tracks: with octrees the tree can be created at level load but with a linked node system I guess the user would have to create the tree manually, and since I'm aiming for the simplest level creation this would be a pretty big disadvantage unless I can somehow find a way to automate it. In the end I want any user to be able to knock-up a few track models and use them in-game!

Hmm, about the linked-node, I'm using splines and progress quads (quads which the user has to pass though to progress) so maybe I could use these to automate it...

Share this post


Link to post
Share on other sites

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