-Tentus
Hey all,let's talk about culling in a 2d environment for a bit.
First off, some terminology. For the purposes of this rant, culling means "not dealing with," as opposed to "removing from a group." Think of it as "removing this thing from stuff we have to work with," if you insist on verbose clarity. Also, by 2d environment we mean a layered series of images that are output to a 2d plane: a video game render. Yes, this is a rant about the inner workings of a video game.
So what are we culling anyhow? What's the point of culling? How do you even do it?
What we're culling is individual elements in a video game, in their entirety. So, if we use the old Mario games as an example, we don't need to think about blocks or goombas that we can't see right now. They're off screen, so there's no need to draw them each frame, or run their logic every time we update. To avoid this extra work, we cull them.
The point of culling, as you can probably guess from the previous paragraph, is to avoid unnecessary work. What we can't see we don't need to worry about, most of the time. I say most of the time, because there are a few occasions that you do want to update an object, even if it's off screen. For example, once you see an enemy once, the AI for it should probably run constantly from then on, even if we can't see the enemy. That way if we backtrack to a place where we saw an enemy before, it's not exactly where we left it. That would be both really unrealistic (destroying any immersion we might have built up) and also has lots of room for bad gameplay: imagine leaving a room with an enemy hot on your heels. An hour later you reenter the room, to find the enemy you left behind staring at the door, probably either actively shooting or charging at you. No fun.
This raises the questions of how culling works. Because of the reasons mentioned above, culling for AI and culling for rendering is often done separately and quite differently. That's part of why the definition is "not dealing with" rather than "removing from a group:" if we removed an object from drawing, but still need to update it's AI, then we'd be in trouble. Instead we just ignore things that have been culled.
Culling AI logic is usually the simpler of the two. The object usually has a variable that says if it's "sleeping." If it is sleeping, then this update of the game will just skip this object and keep going. We set sleeping to false (wake the object up) once we see it, even a little bit. So wakeup is often tied to rendering, though going back to sleep is where we differ. In some games wakeup happens when we get within a certain range, but remember that we're talking about 2d here: we're not talking about the most sophisticated setups.
Putting an object to back to sleep often happens one of these ways: The AI gets killed. Simple enough. The AI "looses sight" of the player and after doing a short routine it returns to its starting state (and often starting position). The player gets far enough away that the engine decides that to stop worrying about that AI. This is more common in 3d games. The distance is usually totally arbitrary, based purely on the decisions of the programmer. The engine has enough other stuff going on that it decides to start culling the oldest AIs. This is an unusual method because it's kind of risky, if the AI position is irrelevant to age, but it works ok for stuff like bullets. The AI has a timer that starts when it wakes up, which is reset by certain events in the AI logic. If the timer goes longer than a certain number, the AI goes back to sleep. This is often combined with the loosing sight system.
Culling what is rendered is harder to implement, so there are fewer variations of it. A lot of people think that if a pixel is off screen, it isn't rendered. Without going into a lot of detail, that's simply not the case. It's a lot easier to think about big objects (a player, an enemy, a block of the environment) and render their entirety than to try and think about each pixel of each object and just render the ones on screen. This means that if even a single pixel of a sprite is on screen, the whole thing has to get drawn, but that's how the cookie crumbles.
The main method used is a simple X-Y test, with consideration to the width and height. If the top left corner of an object is the X and Y origin, then each edge and corner of the object can be determined by adding the width and/or height as appropriate. We can say the same thing about the screen itself, treating it as a big object. If the two objects overlap, then render the object. Otherwise, cull it from the list of everything in the level.
Here is some example code, written in pseudo-Lua for readability. "Self" refers to the object we are checking to be culled, while "screen" refers to the render area.
if (self.x > screen.x and self.x < screen.x + screen.width) or (self.x + self.width > screen.x and self.x + self.width < screen.x + screen.width) then
if (self.y > screen.y and self.y < screen.y + screen.height) or (self.y + self.height > screen.y and self.y + self.height < screen.y + screen.height) then
render()
end
end
Now, there are a number of problems with this code. First, it's quite verbose. Second, it's only checking to see if the edges of the object are onscreen. This works great for most things, but what if there's a really big object (like an image of a castle or something). Then the object could actually eclipse the screen, causing it to disappear. Yikes! Third, this only works with rectangles that are rotationally locked. A circle or tilted rectangle would break this method like a child with crayons.
There are other methods, obviously, but because most games are based on rectangular images, this one is surprisingly common. I will expand on this article later as I fully wrap my head around other methods and clarify my own thoughts. I hope this has given you something to think about!
-Tentus