Blog Comments

Originally Posted by copeg

A space partitioning tree might be an alternative to look into. Partition the space in some manner (say by halves) and represent each space as a node (children of a node are subsets of that space). The partitioning stops for a given node when the space it represents contains a single object (thus, each leaf represents a given space with one object - no need for determining how small to partition as you terminate when each partition contains a single element, and it avoids unnecessary partitioning). When an object moves, get the leaf node that represents its surrounding space, update the tree by ascending up to the parent(s) and relocating the node in the tree appropriately - collisions can be checked when you update the tree and find the node you are repositioning to 'collide' with another leaf node (you can do precise collision checking at this point). Then re-partition the tree (if no collisions exist) or update the two objects position based upon the collision as appropriate and recursively reposition the nodes within the tree.

I have given quad-trees a try before, but I found that their performance over a 2D grid with a moderate number of objects isn't that great. It may have been the implementation I chose, though. Perhaps a k-d tree would work better... in any case, this grid mechanism works extremely well for a medium number of objects with larger objects tending to be stationary and smaller ones doing the moving. I think I should save the data in each grid as a set, though... the current 2-D arraylist implementation works but is very inefficient

A space partitioning tree might be an alternative to look into. Partition the space in some manner (say by halves) and represent each space as a node (children of a node are subsets of that space). The partitioning stops for a given node when the space it represents contains a single object (thus, each leaf represents a given space with one object - no need for determining how small to partition as you terminate when each partition contains a single element, and it avoids unnecessary partitioning). When an object moves, get the leaf node that represents its surrounding space, update the tree by ascending up to the parent(s) and relocating the node in the tree appropriately - collisions can be checked when you update the tree and find the node you are repositioning to 'collide' with another leaf node (you can do precise collision checking at this point). Then re-partition the tree (if no collisions exist) or update the two objects position based upon the collision as appropriate and recursively reposition the nodes within the tree.

Great blog post as usual I enjoy reading your posts.

Great tip! I can think of many situations in my current projects where this would come in handy.

Nice post! Haven't had a chance to fully digest the material but this definitely has lubed up the bearings and gotten those wheels turning. Definitely like the nicely documented code, and how CMWC takes advantage of Random by extending it.

I changed the first line from frequently asked to foolishly asked (if anyone else hasn't picked up on the hint yet )

LOL I was reading this thinking someone must of hijacked your account! Let's hope no one takes this information seriousally and reads all the way to the bottom
I forgot it was April fools day today. I've already been tricked into eating sweets that were so hot I've been crying for an hour. I did wonder why everyone started laughing when I put it in my mouth.. haha