Game Development Reference
In-Depth Information
Dealing With Thousands Of Game Objects
Gosu is blazing fast when it comes to drawing, but there are more things going on. Namely,
we use
ObjectPool#nearby
quite often to loop through thousands of objects 60 times
per second to measure distances among them. This slows everything down when object pool
grows.
To demonstrate the effect, we will generate 1500 trees, 30 tanks, ~100 boxes and leave 1000
damage trails from explosions. It was enough to drop FPS below 30:
Running slow with thousands of game objects
Spatial Partitioning
There is a solution for this particular problem is “Spatial Partitioning”, and the essence of
it is that you have to use a tree-like data structure that divides space into regions, places
objects there and lets you query itself in
logarithmic time
,
omitting objects that fall out of
query region. Spatial Partitioning is explained well in
Game Programming Patterns
.
Wikipedia, “quadtrees are most often used to partition a two-dimensional space by
recursively subdividing it into four quadrants or regions.” Here is how it looks like:
