Hexatron post-mortem; level generation

In case you guys haven’t played Hexatron, go check it out!

Be prepared; this post will not introduce any new/revolutionary/interesting ideas on procedural generated levels. Maybe it’ll be useful as some tale that emphasizes on the idea that its okay to have a simple enough algorithm to make playable levels for you. Then again, that might be just something I tell myself every night for not coming up with something like cellular automata.

In some post I’ve written before, the planet is largely based on the excellent HexPlanet demo by Joel Davis. Given the code I’ve ported over, I now have some map of hexes with their normals, vertices for all six corners of the hex shape and all its neighbors. This is all the information I’ve utilized, meaning I’d have no sense of locality beyond the neighbors for each hex. What I mean by this is I couldn’t tell where hex 5 is in relation to hex 19. Obviously there is a pattern to what HexPlanet spits out, but I’ve figured trying to put it in a context of a flat map would need too much time to look into, so I’ve made the assumption in my code that I had no idea what the neighbors are given some hex, but I would have pointers to them. This will be something I’m going to touch on in a moment; first, the general idea of level generation.

Early on I was also planning on symmetric room generation but cut out early to avoid any complexities it may raise due to its random nature. Provided a bigger time budget, I would have definitely pursued this and probably still will. Here’s a little demo I’ve written before the competition for a certain type of room generator I had in mind. Use the W/S keys to increase line budget, space to generate the room. The line of purple hexes are a path I’ve generated connecting two tips of the spokes together in order to create rooms that all just don’t comprise of spokes coming out of the center.

I’ve decided on five basic room types for the level generation, which all range from a single hex to five hexes. There would’ve been a final type of hex room with 6 hexes for a boss battle room, but that idea was cut later on in the interest of time for a Descent style escape sequence.

The basic structure for the level that I’ve wanted would be similar to the idea of a Metroid level; meaning, having rooms grouped into several areas, where there is only a single door to an area between areas. For now, I’ve made the idea even simpler and decided on having only three areas, each being connected only by their neighboring areas in the order they’ve been generated (first area <-> second area <-> third area, first area does not connect to third, etc). Given that restriction, I’ve also opted for single hex rooms for the beginning and ending rooms, each only accessible by the first and last areas, respectively.

So, based on this idea, I would have to guarantee some path that would take you from the starting room to the ending room. The solution is simple; create a number of rooms that would connect the previous to the next until they reach the ending room, then add any miscellaneous rooms connecting to them. To make things a little bit evened out for the level structure, we’ll determine some number of rooms (let’s say three) per area that will be part of the main path from beginning to end. After we have created the nine interconnecting rooms, we will then add the ending room connected to the last room.

First, we pick some random hex as the starting room, whilst marking all neighboring hexes as that room’s expansion fronts. References to these front hexes will be stored in this room’s area’s data structure as well as the room data structure (since it is a starting room, it doesn’t particularly belong to any area at first). To add the next room, randomly pick some expansion front hex:

With this picked hex, we start to try to insert random room types starting at this particular hex. The room insertion algorithm reads through the ‘blueprint’ of the room it tries to insert and follows the general building path as defined. If it fails in one direction, it will try again to apply the blueprint in all possible orientations. If it’s successful, it will mark all the hexes it traversed as active room hexes. Otherwise, we will pick another room type and try again until we get one that fits.

When we get a successful room placement, we store all the room hexes in a new room data structure, as well as mark new expansion front hexes, storing them inside both the room’s and area’s data structure. We mark the side of both rooms we connected them as doors. We start again by picking another expansion front hex from the new room data structure.

We try to fit in another room, get a new room structure, mark expansion fronts, and so forth. From the above picture, the darker teal looking hexes are expansion front hexes belonging to that first red room. I make this distinction as while these hexes are part of the area’s total collection of expansion front hexes, these specifically belong to this room. In this phase of level generation, we’re only interested in the last room’s set of frontier hexes, which are the brighter teal colored ones as shown. We continue this until we have a single path of interconnecting rooms that go from the starting room to the ending room:

The three different colors (with exception to the grey rooms) indicate they are part of area 1, area 2 and area 3. Each area have their own set of expansion front hexes that touch rooms belonging to their respective area. Given this layout, we can now just fill the hex world as much as possible with miscellaneous rooms. The process is largely the same as before, except this time we use the pool of expansion front hexes from the area structure itself, instead of any particular room. We loop through the three areas over and over, adding a single room to the area at each iteration. If we cannot add anymore rooms to some area, we take that area out of the loop and keep going until we can’t add anymore rooms. This is to try to provide an even distribution of rooms in each area, though sometimes you’ll get levels with varying numbers of rooms per area. We should now have something like this:

Since we’ve only used expansion fronts for the particular area when we were adding rooms, we have a setup that still only has one way to get to the next and previous areas. This structure can be helped to emphasize a Metroidvania vibe of exploring some area before you move on to the next, just to finish some task that would allow access to the aforementioned next area. Unfortunately, this particular mechanic wasn’t implemented due to the little time I had left.

We give the level one more pass by marking all possible doors in each area between its various rooms. When we have this list, we will randomly pick some number of these marked doors and add them to the level. Checks are placed to make sure the doors will be connecting rooms of the same area, to guarantee the single doorway to the next area.

There we have it, the final layout of the level. It’ll get post processed a bit more from the game logic to assign various spawn groups to each room, as well as rewards that will be left behind for each room that’ll be cleared. Details of such will probably be covered in another post.

The meshes of the rooms are actually generated at load time. Given the collection of room hexes that are used to describe the room, we use a simple algorithm to create a chain of points that describe the perimeter of the room on top of a unit sphere’s surface. To get the base vertices of the rooms (vertices along the bottom of the walls), we simply multiply these points by the radius of the planet we’re on. Next, to get the top vertices of the walls, we multiply the same points by the radius once more, plus the desired wall height. After that, it’s a simple matter of triangulating polygons out of these vertices, as well as texture UVs for the slice texture that I use for the dissolve shader. I run another post processing step that snaps any nearby vertices together, in case if rooms didn’t line up exactly. I’ve had this problem, but it was due to the rooms having the rigidbody component that made them shift a bit, even though they were marked as kinematic. In retrospect, the vertex snapping processing probably wasn’t needed, but the code is there, so it’ll have some use.

I think that’s about for how I’ve done level generation. As I said, its pretty simplistic in of itself; the ‘hard’ part was designing the algorithms in a way that didn’t assume what the neighboring hexes were, only having access to them. The difficulty was mostly prevalent on room placement, which I would figure would be more difficult if I incorporated randomized rooms.

As for the future, it’d probably need a bit of refactoring, as well as some offline processing for hex planets at various subdivision levels. Given all that, I can attempt to fit in randomized rooms in level generation, maybe do some experimentation with the general shape of the room so they won’t look like they were comprised of only hexagons. Then again, I think that’s part of their charm. I’d also would like to put in more obstacles like short walls and such to make the movement more interesting, but that’d be mostly the gameplay post processing step of level generation.

If you’ve made it this far, thanks for reading! Any questions and comments are always welcome.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>