# (2D) Handling large number of game objects, no quadtree

This topic is 827 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I was searching for a simple way to handle a high number of objects (say enemies, obstacles, collectables, platforms...) in a 2D platformer-style game, without having to run through the whole set every frame. After a lot of seaches, surprisingly I only found the QuadTree method, so I wondered what simpler algorithms the old school games like Sonic used.

By looking at Sonic 2's commented disassembly https://github.com/sonicretro/s2disasm_git/archive/ObjectMacros.zip , i (approximately) understood how it works, let me explain :

The objects are stored in rom in a simple list (1D array) for each level, sorted by their X position. An object entry = X coord + Y coord + object type

At the beginning of the level, the code walks through this array, ignoring elements until it finds some object past the camera's left bound X. It loads every object, until it finds one which X position greater than the camera right bound, then it stops here. We've loaded all we need for the first screen. The clever trick happens now : we saved in memory the index of the first object found in the camera bounds and the last one. Instead of reading again the array from the beginning when the player moves, we only read the objects close to those indexes depending on the player movement :

- if the player is walking forward : read from last object index (camera right border) and stop when an object is found at X > (last object index + xPlayerAcc),

- if the player is moving backward, read at the first object index (camera left border) and stop when object found at X < (first object index - xPlayerAcc)

When an object becomes too far from the screen, it's purely destroyed from RAM. It won't reload the next time the player comes if it has an entry in a special array called the "respawn table". It avoids collectables/enemies to pop again.

What do you think about this method ? The flaws are, it's very optimized for horizontal levels but it's quite less effective for vertical ones, or the objects would need to be sorted by their Y position instead of X.

What sort of optimization algorithms did you used in your games ? I'm curious, since i can't manage to find a lot about that on the net...
Edited by isbinil

##### Share on other sites

Simple methods are perfectly fine -- yes, maybe a quad-tree or some such is the optimal algorithm, but its also a rather generalized one; oftentimes a simpler solution will do when it fits your own needs better, and sometimes its just as fast--or faster--than the optimal general solution. What Sonic did is a neat trick for exactly that kind of game, its an excellent example of looking at your needs and constraints, and coming up with a solution that does what it needs and no more.

That said, nothing on the genesis or contemporary systems would have approached "large numbers" of enemies by computational-complexity standards. In 3D space, or with a great number of objects to consider (especially if you have to test whether they interact, as in an n-bodies simulation) you probably do need a way to easily partition the objects that might interact. In 2D, with relatively few objects to consider, its often sufficient to simply check whether an object is potentially on-screen before blitting it, or within a slightly larger rectangle to "activate" autonomous entities ahead of time, just so that it doesn't seem like life suddenly springs into being right at the screen's edge.

In a 2D overhead RPG I wrote in my early days, that's exactly what I did -- NPCs activated half-a-screen outside the visible area in every direction, so even if the player stood still, nearby NPCs would come on-screen, leave, and come back at will. If they wandered too far they'd suspend and remain near where the player would have expected them to be. This all lent to a more immersive kind of feel, without spending resources to calculate all the NPCs in the entire town.

##### Share on other sites

One way is to make bigger rectangles over your playing field, and store the objects in those rectangles based on their location.

From the displayed screen, figure out which rectangles are visible, and only search those for objects to display.

##### Share on other sites

A grid is a tried and true very simple method. Whatever sized your world is, split it into evenly spaced grid cells and then based on where the viewer is in the world, it's super trivial to calculate the min and max bounding extents of the grid to isolate the small subset of objects that are relevant to where the camera is looking.

1. 1
2. 2
Rutin
21
3. 3
4. 4
A4L
15
5. 5
khawk
14

• 13
• 26
• 10
• 11
• 44
• ### Forum Statistics

• Total Topics
633742
• Total Posts
3013631
×