I've been mucking about with XNA a bit recently. Anyway.
I thought I'd share some of the things I've learnt, and a bit about an algorithm I'm implementing.
One thing I found is that the performance of the base GameComponent isn't all that hot. My guess is that each frame, they sort the components by the DrawOrder, or UpdateOrder (depending on the op). Yet the default for both of these is zero, so by default, they are sorting a list of zeros. Assuming they are using Array.Sort(), this probably means quicksort, so probably means O(N^2).
But ignoring that...
I've also been mucking about with my own xna-like base classes. I'm wondering if there is any interest out there, if any of you want them? etc
The best one I have so far is a space partitioning class.
In the past I've done various implementations. Usually octree (for no particular reason).
What this one does is pretty much the same. It's a binary tree, dividing an axis at a time. So first divide is X axis, next is Y axis, next Z axis. Always at midpoints.
I know it sounds simple, but it has a catch. It can call Update() on all the items stored within, and shift them around in the tree afterwards. It expands/contracts and culls itself, so provided your dataset is fairly good, it keeps itself fairly well balanced. Of course stick 1000 objects within 1mm and another 1000 10km away and it won't be so balanced. But it works, and is fast. It does no runtime allocation.
Currently it's (as far as I can tell) cache limited. All nodes/leaves are currently classes (for simplicity) but I'm moving it to structs and 16bit or 32bit indexing. This will really help the CF GC on the 360 too (in theory).
I'm monitoring how much time I keep a thread busy when updating at 60hz. At 15,000 items it's ~%2 but fluctuates a lot, at 18,000 it's 100%, and 20k can't keep up - so I'm pretty sure it's a cache issue. Moving to structs should help this a lot (maybe down as low as 10byte node,~50byte leaf).
The actual implementation is a damn sight more complex than it seems on the surface (duh!
). I've done it all before, but it's amazing how I keep forgetting the little catches . Keeping track of what items have had Update() called for the current sweep - for when they get rearranged - has been frustrating Especially without using lists/allocation.
Anyway the plan is to eventually put it out there for anyone. XNA, MDX, maybe even a C++ port. Ideally I'll be looking at the entire thing having a constant allocation overhead (less than 10 allocations).
Currently jazzing it up with per-item bounding box support.
Anyway here is a pic.
5000 boxes, around 1800 nodes / 1800 leaves (leaves store a max of 5 items). The cpu hit for the Update sweep is less than 1% as far as I can tell...
Ideally I want to be able to comfortably put 30k+ items in it at 60hz updating.
I'm thinking a good test case would be a space battle with 5,000 ships.
I'm interested in opinion. Space partitioning ain't exactly easy, but I'm not deluded in thinking it's rocket science - yet at the same time it's not exactly a glamour feature, so I don't have much to compare/learn from. I'm thinking something robust, small and efficient would be really, really useful for the xna community. And I think I'm getting there on most counts
I thought I'd share some of the things I've learnt, and a bit about an algorithm I'm implementing.
One thing I found is that the performance of the base GameComponent isn't all that hot. My guess is that each frame, they sort the components by the DrawOrder, or UpdateOrder (depending on the op). Yet the default for both of these is zero, so by default, they are sorting a list of zeros. Assuming they are using Array.Sort(), this probably means quicksort, so probably means O(N^2).
But ignoring that...
I've also been mucking about with my own xna-like base classes. I'm wondering if there is any interest out there, if any of you want them? etc
The best one I have so far is a space partitioning class.
In the past I've done various implementations. Usually octree (for no particular reason).
What this one does is pretty much the same. It's a binary tree, dividing an axis at a time. So first divide is X axis, next is Y axis, next Z axis. Always at midpoints.
I know it sounds simple, but it has a catch. It can call Update() on all the items stored within, and shift them around in the tree afterwards. It expands/contracts and culls itself, so provided your dataset is fairly good, it keeps itself fairly well balanced. Of course stick 1000 objects within 1mm and another 1000 10km away and it won't be so balanced. But it works, and is fast. It does no runtime allocation.
Currently it's (as far as I can tell) cache limited. All nodes/leaves are currently classes (for simplicity) but I'm moving it to structs and 16bit or 32bit indexing. This will really help the CF GC on the 360 too (in theory).
I'm monitoring how much time I keep a thread busy when updating at 60hz. At 15,000 items it's ~%2 but fluctuates a lot, at 18,000 it's 100%, and 20k can't keep up - so I'm pretty sure it's a cache issue. Moving to structs should help this a lot (maybe down as low as 10byte node,~50byte leaf).
The actual implementation is a damn sight more complex than it seems on the surface (duh!
). I've done it all before, but it's amazing how I keep forgetting the little catches . Keeping track of what items have had Update() called for the current sweep - for when they get rearranged - has been frustrating Especially without using lists/allocation.Anyway the plan is to eventually put it out there for anyone. XNA, MDX, maybe even a C++ port. Ideally I'll be looking at the entire thing having a constant allocation overhead (less than 10 allocations).
Currently jazzing it up with per-item bounding box support.
Anyway here is a pic.
5000 boxes, around 1800 nodes / 1800 leaves (leaves store a max of 5 items). The cpu hit for the Update sweep is less than 1% as far as I can tell
...
Ideally I want to be able to comfortably put 30k+ items in it at 60hz updating.
I'm thinking a good test case would be a space battle with 5,000 ships.
I'm interested in opinion. Space partitioning ain't exactly easy, but I'm not deluded in thinking it's rocket science - yet at the same time it's not exactly a glamour feature, so I don't have much to compare/learn from. I'm thinking something robust, small and efficient would be really, really useful for the xna community. And I think I'm getting there on most counts
Last edited by a moderator:
