Which spatial partitioning method suitable for my game?
Author
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.
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.
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.
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.
Author
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!
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!
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.
Author
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...
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...
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
