How to detec Collisions in open world games?

Newbie & Debugging Questions
#1

Hello.

I used Quad / Oct trees to detect collisions so far.
But what if I have an open world game, for example an mmorpg,
where a / the world is… huge… ? Is there an simple quad / oct tree the right way to go,
or are there better approaches?

Thank you!

#2

http://c2.com/cgi/wiki?PrematureOptimization

#3

Since you obviously shouldn’t check your collision box(es) with every other collision box in the entire game, I would consider something like this:

  1. Build all your collision boxes in the game (however you do it)
  2. Have a range detection like this that goes through all your collision boxes that are loaded:
    [icode]if ((Math.abs(youX-objectsX) < distanceX) && (Math.abs(youY-objectsY) < distanceY) && (Math.abs(youZ-objectsZ) < distanceZ))[/icode]
  3. Stick whatever objects pass the statement into an ArrayList;
  4. Now, you can just loop through the arraylist you collected and only check for collisions nearby instead of map-wide.

Pseudocode for 3D checks, remove [icode] && (Math.abs(youZ-objectsZ) < distanceZ)[/icode] if this is for 2D:


// distanceX, Y and Z are the distance you want to check around the player.
// objectArray is the assumed collections you keep all this in.
// youX and objectX are the positions of you and the objects being checked.

//Create a new array list to store things in.
ArrayList<Objects> tempObjectArray = new ArrayList<Objects>();

//Loop through whatever collections you have for all the game objects loaded.
for (int i = 0; i < objectArray.size(); i++){
     Object object = objectArray.get(i);
     if ((Math.abs(youX-object.getObjectsX()) < distanceX)
        && (Math.abs(youY-object.getObjectsY()) < distanceY) 
        && (Math.abs(youZ-object.getObjectsZ()) < distanceZ)){
           tempObjectArray.add(objectArray.get(i));
     }
}

//Now check collision only with the objects in the tempObjectArray
for (int i = 0; i < tempObjectArray.size(); i++){
     checkCollision(tempObjectArray.get(i));
}

It’s just a concept, I use it often in RPC but mainly for range detection. RPC doesn’t actually have any collision detection, but the concept should work just as well unless you have absolutely massive amounts of collision objects loaded. If you do, I would suggest a chunking system where you only fetch certain areas. Like breakup the map into smaller pieces and detect what piece the player is in, then do the above only in that area to narrow it down to around the player.

there’s a bazillion ways to do this, but this way seems to be the most straightforward if you just want to fetch everything around the player and only check against them instead.

#4

I just divide my worlds into areas. Collision tests are done with objects in the current area and the 8 neighbors. (Assuming objects can stretch at most over 2 areas). The rest of the world is not considered.

This is a simplification of the tree concept. An 8-neighbors-tree searched 1-deep. Usually this is good enough.

You can still use Quadtrees (or Octtrees) in the areas.