3D game: is a spatial index necessary?

Marco Giancotti
  • 3D game: is a spatial index necessary? Marco Giancotti

    I'm working on a 3D space simulation game in C++.

    I've read that in many cases games use spatial indexing (hashing) that allows to quickly detect collisions, find out what entities to draw and so forth.

    Is this really necessary for my game, considering that collisions between entities can happen, but are very rare? Is there any viable (and simpler) alternative?

  • No, you don't have to. Remember that spatial subdivision is an optimisation. That means it isn't necessary until you've proven that there is no way your game can run fast enough without it. And optimisations are always prioritisable; what could be optimised with an octree, you might be able to optimise at a lower level, or in another way, so that no spatial subdivision is required. Prematurely optimising is a bad thing. If you've never written a game that required octrees before, chances are you won't have a sense of at what level they actually become a necessity.

    Broadly speaking, you're not going to be capable of the same level of processing (read: number of entities in your world) without it, if only for physics purposes. Literally, because of the recursive nature of quad- and octrees, they improve performance by (an) order(s) of magnitude. So you'll probably have to be happy with a relatively simpler world as a result in the meantime (or per se).

    Really, spatial subdivision is not such a tough concept to grasp. If you take quadtrees (2D) as a simple example, you can write very basic demo to get familiar with them, using a typical "balls bouncing around screen" type demo as a basis for learning how quadtrees work, and how to apportion collisions using them. You can then directly transfer your knowledge to octrees (3D). That would be my recommended path to a beginner in these.

    Anyway, for now, just keep going using a uniform grid, and if things begin to grind, and you've already optimised a good amount in other areas, then look into spatial hashing.

  • The fact that collisions are rare is mostly irrelevant - it's how often you need to check for them that matters. The optimisation is to reduce the number of object-to-object checks you have to make, not to reduce the cost of each check.

    I totally agree with Nick Wiggill and would stress that spatial hashing is an optimisation, nothing more. Don't do it until you need it. However, I also agree with him that it's not such a tough concept to grasp, and you can go a long way simply with a uniform grid. eg. grid_x = universe_x % GRID_WIDTH, repeat for all dimensions. This partitions the space into several cubes, and it's easy to keep a list of ships inside each cube of space. Then, when checking collisions, you only need to check a ship against other ships in that cube and the ones in adjacent cubes. (Providing ships can all fit entirely inside a cube - if not, start with bigger cubes.)

Tags
c++ architecture design-patterns
Related questions and answers
  • language, in my case Lua. On the other hand I want to use a component based design for my entities, and here starts my questions: 1) Should I define my componentes in C++? If I do this in C++ won't I...) Where should I place the messaging system for my game engine? Lua? C++? I'm tempted to just have C++ object to behave as servers, offering services to lua business logic. Things like physics system...I have a 2D basic editor written in Qt, and I'm in the process of adding entities. I want the editor to be able to receive RTTI information from entities to change properties, create some logic being

  • I am trying to create a 2D platformer (Mario-type) game and I am some having some issues with handling collisions properly. I am writing this game in C++, using SDL for input, image loading, font... I need to start with. What I need is an easy way to both detect which side the collision occurred on and handle the collisions properly. So, basically, if the player collides with the top... be crucial, let me know and I'll provide the necessary information. Finally, for anyone who can help, providing code would be very helpful and much appreciated. Thank you again for your help! Edit: I

  • I would like to any tips/articles/tutorials on how to write collision detection using OpenGL and C++ in 3D mainly just simple box collisions etc but also if there are any advanced resources that would be great to. i also don't wont to use any external library`s if possible. thanks

  • I am a 2D Game Programmer.Some programming languages which I am good at are C,Java ,C#. I also know Actionscript 2.0,3.0 and some javascript. I'm interested in learning 3D Game programming. So far from the research I have accumulated by googling and reading different game development forums and articles. I've noticed that most programmers tend to prefer C++.Also in an online game programming... for 3d game programming. Also include links to good 3d game programming articles for the already 2d game programmer. P.S : IMHO , I also find C++ to be cryptic.

  • I dont know much about finite state machine in AI or other game behaviors in game, except this quick tutorial with a Miner: http://www.ai-junkie.com/architecture/state_driven/tut_state1.html which is object oriented. I don't really know if this tutorial describes the State pattern or not, what do you think ? I'm not speaking about other more arithmetic-oriented stuff like steering or physics or path-finding or collisions, but rather about game logics, state-driven AI, and things that involves a lot of simultaneous states and ifs and/or switches What are the pro/cons of using either a State

  • Hi I'm new to 3D games developing, I can a little c++, C#, VB.Net, 3D Max, ArchiCad ..etc. my problem is where to get started, which tools I need to start a own 3D game like GTA, I have tried some tools like : 'Unity3D' (crashes on start), '3D Rad' (uses only built-in items), 'Game Maker A7' (only 2D games can be made there).. could you help me to find the tools of making a 3D game..plz I'm using Windows XP SP 2, I don't have pixel shader 1.1 into my video card

  • I'm writing a shooter (like 1942, classic 2D graphics) and I'd like to use a component based approch. So far I thought about the following design: Each game element (airship, projectile, powerup... C++ application. Entities can be defined in an XML file (the IA part in a lua or python file). The main loop doesn't care a lot about entities: it only manages components. The software design should... remove_component(C* c) { components.at<C>() = 0; } void serialize(filestream, op) { /* Serialize all componets*/ } ... }; std::list<Entity*> entity_list; With this design I can get #1

  • Say I develop a game for mobile platform running OpenGL ES 2.0. I have done 2D part, and now I wish to import some 3D objects. The imported 3D objects must contain the following: Vertices... 3D authoring application (3ds Max, Maya, Softimage) into the game. However, doing so from scratch is going to be really be a lot of work. Therefore, is there any available solution/middleware, that will let me import 3d meshes into my game, ready to use? The solution/middleware should be: easy to use easy to port efficient not consuming too much memory with unnecessary things containing all

  • After careful consideration to use middleware, I have decided on creating my own 3d file format format to export meshes from 3D authoring application (Softimage) into my game. I will need to export the following: Vertices Indices Normals UVs Material Information Animation information (no clue, how to import it) Collision mesh Game Properties defined within 3D authoring tool (object... of wasting it on incorrect approaches. I use Softimage as my 3D authoring tool. Target platform is OpenGL ES 2.0 running on mobile devices (iOS, Android). Programming language: C++.

Data information