I am thinking about making a simulator type game that will involve having lots of small objects in a 3D space. What is the typical solution for handling these objects? The first thing that comes to mind is a 3D Array, but I can't help but think there is a more efficient solution. Another idea that comes to mind is objects having possession of smaller items. For example a House possesses a Table which possesses a Cup and Bowl.

The final way I can think of handling this is just having an array of "objects" that each have an x, y, z value. While this would make storing them easy I do not understand how you would detect collisions without just looking at every possible object and checking to see if it is in the way.

Are there other ways of holding onto these objects that is more efficient?

Edit: Following up with the comments below, are there typical thread-safe ways of implementing these structures in Java?

  • \$\begingroup\$ The term of the technique for what you are looking for is called a Scene Graph and its a way of storing data logically for fast access for things like collision and rendering. \$\endgroup\$ – James Dec 1 '11 at 0:56
  • \$\begingroup\$ Also look for octrees -- they're a data structure very commonly used by scenegraphs. \$\endgroup\$ – sam hocevar Dec 1 '11 at 18:19
  • \$\begingroup\$ In regard to your edit, I don't think so (or at least I haven't seen anything). Typically your scene graph would be mutated that much by another thread (read: simple locking will suffice) - only the values for each node (read: simply locking will probably work here too). Make it lock synchronized; and then if there is a performance problem investigate lock-free structures. \$\endgroup\$ – Jonathan Dickinson Dec 1 '11 at 23:07
  • \$\begingroup\$ Regarding your edit: I don't know of a "typical" thread-safe way. I started with something real simple, but I had a lot of objects and a lot of threads and got forced into going whole hog with a thread-safe octree. It's now on a commercial site, but you can get the source for personal use for free. A good look at the code will no doubt convince you avoid multi-threading, but if not it should give you some ideas. \$\endgroup\$ – RalphChapin Jan 19 '12 at 15:25

You could use a scene graph, or just a list of objects with some sort of spatial hash to speed up collision checks.

But even just sorting objects by one of the coordinates and using that knowledge to limit the comparisons is a good enough optimisation for most simple applications, and your application fits the bill. Imagine you took the solar system and flattened it down onto 1 dimension - how many objects would overlap? Hardly any (except perhaps a few asteroids). That would mean that for each object, you only need to check a couple of other adjacent objects to see if a collision has happened.

As for thread-safety, what 'safe' means depends on what you're trying to achieve. The term "thread-safe" refers more to algorithms than to data structures. (A data structure may be thread-safe, but that doesn't mean your use of the data is correct with regards to multiple threads.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.