So when it came time to write a collision system to represent level geometry for Replica Island, tiles seemed like a natural choice. I already had a tool for editing tiles and tile maps, as well as runtime code for loading tile sets and maps, so using tiles for collision meant I could leverage a lot of existing infrastructure. Also, maintaining a 2D array of collision tiles in memory was appealing because it's very fast to query the contents of any particular tile; while many collision systems organize their data in trees, doing so requires that the tree be traversed for every collision test. A 2D array, on the other hand, can be indexed directly into, which is very fast (the down side is that these arrays are generally sparse, so there is a lot of runtime memory wasted; however, for the size of the levels I was considering and the available ram on Android devices, the memory required of an array to describe the level is trivially small).
Tile-Based Line Segment Collision? Huh?The problem with using tiles for collision is that they are basically square. The simplest implementation is to simply consider the collision world a 2D grid of booleans, set to true in grid cells that are "solid" and false to cells that are "empty." Using this method you can calcuate the location of a collision cell in game space and then check to see if it is solid or not before deciding if, for example, your player can move forward. While that's a very simple approach (and I shipped a few games that worked that way back in the day), it's not really going to scale to the types of interesting level designs that modern players expect. At the very least you want to be able to support a sloped surface so you can make hills and valleys, and ideally you should be able to express bumps, spikes, curves, and other shapes that are much more complicated than a simple solid cube.
So, for Replica Island, I decided to implement a collision system based on arbitrary line segments, stored as shapes in tiles and laid out in the world as a tile map. The idea is pretty straightforward: within a 32x32 collision tile I can define any number of line segments, which can have arbitrary angles and normals. I can use my tile editor tools to lay the collision tiles out and at runtime I can leverage the speed of a 2D array (direct index into the current tile) to find a set of potentially-intersecting line segments. The nice thing about line segments is that they can contain both a slope and a normal, which allows for all kinds of interesting physics calculations without a lot of code (for example, to make a ball bounce convincingly off an angled surface you can simply reflect the ball's velocity about the normal of the surface). I've used similar systems (though never stored as tiles) on a lot of other games and, at least for 2D collision worlds, I'm quite happy with the approach.
Data GenerationOnce I had settled on the line-segments-in-tiles approach, the problem became actually generating the line segment data for each tile. Genki, the artist behind Replica Island, generated a set of collision tiles that would serve as the basic building blocks of our levels, but now I needed a way to represent that same data as line segments. I've had success with edge-tracing algorithms in the past but my experience with them also suggested that they require a bit of tuning to get right. And since collision detection and response is so closely tied into core game play, I wanted a way to hand-modify individual segments. When I worked in games development full time we would just sit down and write an editor tool for this kind of thing, but one of my goals with Replica Island is to see how simply (read: cheaply) I can get it finished, so writing a dedicated tool was a little out of scope. So I decided to piggyback on some existing tool to generate the data that I needed. After thinking about it for a bit, I settled on Photoshop.
Querying Collision at RuntimeSo, now I have two different sets of data: I have a single collision tile set, which maps collision tile indicies to collections of line segments, and a bunch of collision tile maps (one for each level) that place individual collision tiles in space to describe level geometry. I can load the collision tile set once and keep it around; each level that I load brings with it its own collision tile map. At runtime, to check to see if a region of space in the game world is blocked or not, I can cast a ray through the tile map (using one of my favorite algorithms: the Bresenham line algorithm) and check it against the collision tiles that it touches. The actual line segment vs line segment test is pretty simple (here's a useful reference), and it produces an exact intersection point. As soon as an intersection is detected the ray test can be aborted and the results returned (note that it's necessary to test the ray against all segments in a particular tile, though; you always want the intersection point closest to the origin of the ray, so all segments within a given tile must be tested and only the closest intersection returned). It's also possible to test a collision volume against the world by simply visiting each cell that intersects the volume and doing a volume vs line test, but in Replica Island this sort of test did not end up being necessary. The game play is described using ray casts alone.
So, given a collection of collision tiles, each containing a collision of line segments, and a map of those tiles laid out on a 2D grid, I was able to make a pretty expressive 2D collision system without a whole lot of effort. The next tricky bit, which I'll cover in a subsequent post, was what sort of tests, and what sort of response, are actually the best for game play. And this system only deals with intersections between entities and the background; in the future I'll write about the system I used to detect collisions between individual entities.