Yay, view frustum culling!

[MP6767]

I typed this up in about 5 minutes on my phone. It determines whether to draw something based on its x and y position, as well as the bounds defined by h and w.

Code: Select all

function Frustum(posx,posy,h,w)
  if posx > w or posx < 0 or posy > h or posy < 0 then
     return false
  end
  return true
end

This is useful for overall optimization when theres a large amount of drawn objects or things changing position and moving in/out of view. Have fun!

[scutheotaku]

Yeah, this is pretty simple, but nice job nonetheless.
That being said, I think it'd be more useful if you took into account the width and height of what you are deciding whether to draw. As it is now, if you have a 32x32 rectangle whose origin is (0,0) and its x position is -1, it would return false even though 31/32 of its pixels are inside the box.

EDIT:
I would go with something like this:

Code: Select all

function CheckIfRectanglesIntersect( aX, aY, aWidth, aHeight, bX, bY, bWidth, bHeight )
	--returns true if rectangles intersect

	return (
		( aX <= bX + bWidth ) and
		( bX <= aX + aWidth ) and
		( aY <= bY + bHeight ) and
		( bY <= aY + aHeight )
	)
end

For an example of how to use that (for you, or anyone from Internet-land who may come across this), see the attached .love file and attached main.lua file

[T-Bone]

Also, instead of calculating for each object if it should be drawn or not, you can place all objects in a data stricture designed in such a way that you directly have access to the objects near the screen. That uses more memory but saves cpu power, which is in most cases worth it.

[severedskullz]

Also, instead of calculating for each object if it should be drawn or not, you can place all objects in a data stricture designed in such a way that you directly have access to the objects near the screen. That uses more memory but saves cpu power, which is in most cases worth it.

I keep seeing people mention data structures like this but wouldn't even know where to begin to figure out how to implement it.
I am also suspicious regarding "saving cpu power" because wouldn't it be just as expensive to update the data structure than it is to use a linear algorithm to just loop through N items? You are already updating at N time in the update function, so I don't really see how any improvement can be done for drawing... The only thing I could see this as a use for is static entities and calls that don't ever update their position, but rather their position is determined by the position of the camera.

[spectralcanine]

I keep seeing people mention data structures like this but wouldn't even know where to begin to figure out how to implement it.
I am also suspicious regarding "saving cpu power" because wouldn't it be just as expensive to update the data structure than it is to use a linear algorithm to just loop through N items? You are already updating at N time in the update function, so I don't really see how any improvement can be done for drawing... The only thing I could see this as a use for is static entities and calls that don't ever update their position, but rather their position is determined by the position of the camera.

The surmise is that updating the data structure and then using it to cull will be faster than the otherwise O(n) loop.
If this isn't true, don't bother.

Using such data structures (e.g. Quadtree, Octree) is more obvious in 3D scenes, where each game object might be quite complex and take a lot of processing power.
Another very important use is in physics engines (either 2D or 3D), where without reducing the number of checks your code will be quite slow once you have many objects in the scene.

Depending on your game, there might be more specialized ways that evade this completely, for example with a uniform tile map you can know exactly what can be seen with a few math operations.

And of course, as a general advice, don't bother with optimizations like this until you actually know you need them.

[seanmd]

And of course, as a general advice, don't bother with optimizations like this until you actually know you need them.

this, this, a thousand times this!

A quadtree would help you figure out in general what you're looking at, but their most popular use is in collision detection. The idea is to partition your space out regularly, and to a level of granularity at which is a balance between the structure itself being useful and your computer running out of memory/cpu. To do that, usually you cut the play area (or screen) into quadrants, then each of those quadrants into quadrants, storing off each of your drawables into its own box as you get more and more specific. You can then query the contents of any subdivision you want to tell if it matches a certain criteria, or query each of its elements to see if you need to resolve any collisions without fear of comparing one thing on one end of the play field to one that is nowhere near it.

There are tons of examples of implementations of quadtrees all around the net, but my advice would be to skip it until you need it (or feel particularly inclined to shave that specific yak.)

[T-Bone]

It really depends on what kind of game and objects we're talking about. For all static objects that don't move at all, it's a very obvious advantage to place them in data structures. For moving objects it really depends on the amount of objects you have. If they're not too many, I just put all of them in a list for convinience. In another project, I have hundreds or even thousands of robots running around in a pretty large world. There, you really need to find a more efficient solution. In my case, I have a second thread that, among other things, keep calculating which robots are within the drawn world chunks, and sends any new robots to the main thread for it to draw. The ones that are within the drawn area are kept in a simple list too. After trying a couple of different approaches, this one worked by far the best.

In this second thread, each chunk simply has a list of all objects within it. When it is updated, it does a check to see if any objects have left the chunk, and if so, move it to the correct chunk. The good thing about this approach is that the frequency of the updates can vary. I make sure that the chunks that are close to the screen are updated more often than the chunks that are further away. This makes a lot of sense when the world gets large, and is more or less impossible to implement without some sort of data structure.

Of course, you should never optimize until you need it. My point is that you sometimes do.