Click here for an overview of Oh God Why.
Click here to see how the tile map itself is generated.
Box2D is a 2D physics system which uses rigid bodies to represent objects. Normally you'd have one body per sprite, such as for the player (which is really just a rectangle). But having one body for each tile is hugely inefficient and causes the physics system to slow down considerably (I tried that first; start out simple). There's another problem with doing it the brute-force way: due to the way Box2D works it's possible to collide with the edge between two adjacent bodies, even if they line up perfectly and there's no gap between them. This meant that as much as possible I had to have a single body represent each continuous surface in its entirety.
If you look at a screenshot example of the tile map we're trying to cover, such as the sample room I used in the previous post:
Pseudocode
Here's what I did:
- Tiles are stored in an array of pointers, with a NULL pointer meaning a space.
- There is a similarly sized array of booleans for whether each tile has a body representing it. Every boolean starts off false and those which correspond to NULL pointers in the tile array do not matter. All booleans which correspond to non-NULL pointers (i.e. actual tiles) should be true by the end of the algorithm.
- Start in the top left corner of the tile array, working left to right and top to bottom. Find the first non-NULL pointer.
- Make a new Box2D body which is sized and positioned to cover just that tile, and set the corresponding boolean to true.
- Check the next tile over.
- If the tile exists and doesn't already have a body, increase the width of the previously made body and move it over to cover both tiles. Set that tile's boolean to true.
- Repeat until the edge of the map is hit or the next tile over either doesn't exist or already has a body.
- If all of the tiles exist and none of them already have a body, increase the height of the previously made body and move it down to cover both rows of tiles. Update all of the corresponding booleans to true.
- Repeat until the bottom of the map is hit, one or more of the tiles below doesn't exist, or one or more of the tiles below already has a body.*
*There's actually one additional check performed when the body is expanding vertically. As well as checking that all of the tiles directly below the current ones exist, it also checks that the tiles to either side of that don't. This stops the body from expanding vertically over tiles which would've been expanded over horizontally later. This is part of the horizontal prioritization, resulting in the two bodies shown here on the left rather than the three on the right:
Phase 2: Complete
There is another caveat to this system too. Since each room is generated individually, the problem of having perfectly aligned but distinct bodies still applies when transitioning from one room to another. The easiest fix for this would be to have each room generate a section of a single large tile map for the entire level, then run this algorithm on the resulting array. Not only would it fix the transition issue, it would also generate far fewer bodies overall.
Next time I'll finish explaining Oh God Why's level generation by detailing phases 3 and 4: populating the level with enemies and collectibles.