# Q 'bout games with LARGE levels

## Recommended Posts

Say I have a quite large 2d game world with LOTS of entities. All at different positions of course. Now I have the camera follow one of these entities thus I want to draw other entities if they are close enough and also perform collision detection and other stuff. This would get quite tough for the CPU if it has to do this for ALL entities (even if I first check if the object is close enough I think..). So my question is: how do most games do this? Do they simply store all entities in an array or linked list and do some kind of comparision whether to check for collisions etc on the object, or do they use some kind of data tree?? I was thinking that'd be a nice solution, but there is one problem with that: if I was to store everything by its x-position, then I would end up with ALL entities with an x-position within a given range no matter what Y-POS they have. Thank you

##### Share on other sites
Most use a tree with 2^(number of dimensions) children per node. Quadtree in 2D, Octtree in 3D.
(<=,<=),(<=,>),(>,<=),(>,>) for 2d

##### Share on other sites
A tree structure is good because you only have to do actual collision testing on objects that are close together.

Quick Approximation of 2D Collision Detection

I hope that is enough information to get you into it.

Good luck.

##### Share on other sites
Quote:
 Original post by moussen15Say I have a quite large 2d game world with LOTS of entities. [...] how do most games do [collision detection]?

The keyword phrase you want to google for is "spatial partitioning".

The basic idea is to partition space into regions in some manner, with the regions being larger than the objects you have. Clearly, if two objects reside in two regions that are far from each other, they do not need to be tested for collision against each other. In other words, for a given object A you only need to test for collisions amongst the objects in the region R of A (and regions neighboring R, if objects are allowed to straddle regions).

Grids are a very effective spatial partitioning method. Trees, such as k-d trees, quadtrees, and octrees are also good spatial partitioning methods. There's lots of information available on the net about all of these.

##### Share on other sites
You may often find (it depends on the type of game you are making) that in a large world, it's the world entities that are many, not the actual moving objects (characters). Calculating the collisions etc for moving objects is actually much easier since there are usually only a few.

As for drawing too, usually most people use a quadtree or grid or some similar structure. However, i've come up with an idea for non-tilebased static world objects i call a Cell Wrapper. Because all your objects will have some kind of Draw() or Update() function, what you do is create an object with those functions whose only job is to update other objects. However a cell wrapper keeps track of the furthest X and Y coords of the objects it contains. When it gets called with Draw() or similar, it first checks if the total bounding rectangle of all the objects it contains (like a rubber band) intersects the rectangle made by the screen, then draw the objects. So we do this:

// create a cell wrapperCellWrapper cw;cw.AddObject( some_object_1 );cw.AddObject( some_object_2 );cw.AddObject( some_object_3 );// cw now understands the bounding volumes of the objects it contains// now the engine iterates over all the objects when drawing including......cw.Draw();...// Inside, the cell wrapper does this:void CellWrapper::Draw() {   if ( my_bounding_rectangle intersects screen_rectangle ) {      foreach object contained { object->Draw(); }      }   }

... and so if the cell wrapper volume intersects the screen, it then procedes to draw all of the objects contained by it. You could further reduce overdraw by putting individual bounding checks on each object if you wanted, but that might bog things down a bit.

It's not a foolproof method, but it's easy to slap together and works good very static world objects. You can change how big you want the wrappers by varying what you put in them. If you keep them small you have more Draw() called but less overdraw. If they are bigger and contain many objects, you call Draw() less times but may waste a lot of drawing.

##### Share on other sites
You might also want to consider not doing collision detection on things more than X metres away. It's common in games that entities only exist where yuor are looking and close by - for instance in a city the traffic will be generated around you rather than modelling every car in the city. If you have to have the entities as persistent for some reason, collision detection is almost certainly something you can avoid for out-of-screen entities in amost all cases.

##### Share on other sites
For each moving object which changes its velocity and/or direction.
Check every object with every other object on the same grid and calculate which one the moving object is going to collide with and when if it keeps its present cource.
Add the time of collision and the objects to the que
next

Keep a que, of items in crhonoligical order.

Per frame, check the first item to see if the objects will be colliding within the next frame.

If they are, then do collision responce,
and add any more collisions to the list. Every collision move the time forward to the collision every time your responding to it.

From,
Nice coder

##### Share on other sites
One thing I didn't see mentioned above is that most games don't have LARGE levels or LOTS of entities - if you can walk in a straight line for a long time, you're probably changing maps without knowing it (because they are loaded while you walk around instead of when you hit the seam) and entities are loaded/unloaded just like levels.
I can't give any actual numbers, though. The above combined with even the crudest of spatial partitioning algorithms changes a billion collision checks(from 10000 entities in the world) each update to maybe a few hundred.

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628383
• Total Posts
2982378

• 10
• 9
• 15
• 24
• 11