Monthly Archives: January 2014

QuadTree

Got all fired up to do collision detection for some reason, so I wrote a QuadTree implementation in Lua. Performs pretty well, especially when tuned right – it handles 256 objects bouncing around a 3×3 screen area at around 75% of one core on my desktop, and doesn’t start even dropping frames until I drop in 512 objects. In the scenario above (256 objects, 32x32px in size, bouncing around an area 960x720px in size), the engine is doing between 600 and 1000 collision checks per cycle; for comparison, brute-force checking for that many objects would require around 33,000 (and when I try it, the framerate drops from 60 to around 4).

Working with Tiled maps got me experimenting with XML formatting for my object definitions, too. I’ve already worked out a document style which encapsulates the animation and some basic logic, giving me a nice, compact way to sketch out player and enemy behavior. Next up: terrain collisions and physics.

Backgrounds revisited

A while back, I mentioned that Bits & Bots performs pretty poorly: at the title screen, with just two parallax scrolling backgrounds and nothing much else going on, it was using a HUGE amount of CPU time. I had tracked it down to my brute-force background rendering, and I finally got around to implementing the background buffering that I used for my NDS project (one of the few things I did right).

Basically, the background library creates a canvas twice the dimensions of the viewport and renders a chunk of the map to it; as the camera scrolls around this area, a viewport-sized chunk of the canvas is rendered to the active window. When the camera breaks the boundaries of the canvas, the background library renders another chunk of map, centered on the camera. Instead of looking up and rendering every visible tile each frame, it does one simple operation most frames, and only actually renders the background from raw tiles when it’s absolutely needed. Between that and the efficiency of Love2D for everything else, I’m down to only 3% of one core, which I’m pretty happy with.

As an added bonus, thanks to the direction of Ghoulsblade and Co. and the excellent documentation on the Lua Wiki, I built in Tiled map support at the same time. It’s an elegant suite with a lot of cool features, and a hell of a lot easier than trying to constantly fix LIV every time Firefox breaks it.