Jump to content
  • Advertisement
Sign in to follow this  
isbinil

(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.

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement

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 this post


Link to post
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 this post


Link to post
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!