In my effort to update this blog more often, I want to make a quick update of what I have going on.
I’ve been working on shader-based texture decompression for a bit; I’m planning to write a series of what I’ve done thus far. I’ve worked out three ways for decompression, two with my own written compressors and one that supports DXT1 textures. It’s not really a problem that anyone has but it caught my attention long enough that I wanted to see some results.
Right now, I’ve been reminiscing quite a bit about id software games and how I’ve played them my entire life. They’re kind of the reason I’m into this stuff and always wondered how they work when I was younger. I’m decent enough to know now and went ahead to look into the first id software game I’ve played: Wolfenstein 3D.
One thing lead to another and eventually I made myself believe that I’ll learn things a lot better if I just rewrite Wolfenstein 3D in C#. So that’s what I’m doing.
Out of the jail cell
I’m mostly following along the iPhone source code (and using all of the iPhone version of the assets, though I’m planning to implement full support for the original data later), though the ray casting was a little messy and confusing. Even though the iPhone version was rendered using OpenGL ES, it still used ray casting to determine which ’tiles’ were visible from the camera. Ray casting is actually not very expensive for Wolfenstein; it’s mostly the matter of iterating through the horizontal and vertical intercepts of the grid by using offsets. To see if the ray hit anything, you just check the tile position of the current iteration if it’s within a wall.
I’ve rewritten the ray casting part in the way that I understood it (with the absence of Cos, Sin and Tan tables since they’re mostly superfluous now), which took a little doing since I’m prone to making dumb mistakes. I’ve finally gotten to the point where it’s rendering levels correctly, though.
As you can tell in the window title, I’m writing it in Playstation Mobile, but I’m writing the code in mind to be very portable. I’ve abstracted away the renderers and platform system functions so people would be able to just fill in the stuff needed to get it running on some different set of graphics APIs and such. After I’ve gotten the game feature complete, I’m planning to port it to XNA very quickly to see if I’ve done a decent job.
My philosophy with this rewrite is to keep it true to the original, but also architect it in a way that I’d write games today. In other words, same damage and movement models, but based on an entity framework.
The other part of this rewrite is the rendering systems, which I’m quite proud of. I’ve abstracted enough of the rendering system away, yes, but it’s all written in mind to only make a single draw call for the world rendering (two draw calls if you include UI). Doesn’t sound too great at first glance, developers batch quads for sprites and particles all the time to make that single draw call. Well, the other part of this, at least for Wolf3D, is that all the textures are not atlas’ed. I could process atlas textures offline, but that wouldn’t fit well with my goal of eventually supporting the original Wolf3D files. Instead, at level load, I automagically create an atlas texture for the level (which includes all the sprites and wall textures the level would use, even enemy sprites). Since any level in Wolf3D would never go beyond a 2048×2048 atlas texture, it makes it all done in a single draw call.
For now, all I have is level rendering of only the walls. From there, I’m going render doors and decorative sprites. After than, I’ll get started on the game, then polish up on the UI to emulate the original PC UI as possible.
This probably won’t be going on PSM and rather just reside only on my Vita so I can play Wolf3D where ever (unless id software would like to release it on PSM! That’d be cool!). Regardless of what happens, I’m hoping to open source it once I get it to a state where all the original features are implemented.
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.
This got bug fixes/improvements on mostly the end game (final run back to starting room), and added the boost dodge mechanic I was originally supposed to have. I’ve also staggered enemy spawns so they don’t all spawn at once.
This is mostly going to be a game development blog; talking about stuff I’m doing as I do them. Hopefully by the time any person sees this, it’ll have more than the default template images and design provided by WordPress, though chances are that you will.
Right now I’m gearing up for a competition in July held in the SomethingAwful game forums. I think I’ve got a solid idea for a game and mostly been experimenting with code before I get started when July gets around, though I should be focusing on some design so I can have a clearer path for the month.
I’ll be talking about the game probably in my next post and go over some programy/engineery things in posts afterwards. Probably some bits on game design as well, though I’m not as well versed as I’d be in anything involving code.