Im building an advanced 2D side-scrolling game, and it seems that I need to handle more than a couple hundred moving objects, which pretty much kills my "check one object to every other object" algorithm. Ive heard that octrees are fast, but I cant seem to find any sources on the net that are AT ALL useful in explaining this concept. Could anybody help point me to a good tutorial, or perhaps contribute a minimal understanding of what an octree actually is, or how it could be used to handle collisions? My game is really fun to build, if I could only get this taken care of, I can continue moving forward! thnx

Erm, as far as I know you would only use Octree''s for 3d games.

A couple of things you might want to think about are this:

Do you really need to have all the offscreen things moving around and check them for collisions every frame?

Only check things against other things that are nearby each other also. if object a is 5 inches long, then you don''t need to check it against anything that''s coords are farther than 5 inches away.

Try to optimize your routines so that they don''t do any unnecessary calculations.

Also, don''t forget, today''s processers are plenty fast. You should be able to do tons of calculations before you get a significant slowdown.

Actually, what you want is a QuadTree, since your game is 2D.
OctTree is the analogous structure for 3D.

Here is a nice article right here at GameDev that
explains QuadTrees.


~~~~
Kami no Itte ga ore ni zettai naru!

quote:

---

Original post by tangentz
Actually, what you want is a QuadTree, since your game is 2D.
OctTree is the analogous structure for 3D.

Here is a nice article right here at GameDev that
explains QuadTrees.


~~~~
Kami no Itte ga ore ni zettai naru!

---

The only thing is, i''m not sure if that is what he/she/it is really looking for.

You could use the heirarchical mesh techniques described in, among other places, Game Programming Gems (v1).

Timkin