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.
Making Hexatron was a bit more challenging that what I originally thought it was going to be, so I haven’t had the chance to make many posts about it. I want to try to make up for it via a post mortem series and whats the future is going to be like, though.
Regardless, despite some hang ups, I’ve actually finished making the game. Check it out!
For the SA GameDev compo, which its theme is BALLS, seemed a little bit abstract. Right before the theme was announced, I was playing AirMech for a little while. For those that are not familiar, the game is pretty similar to Herzog Zwei, with some DOTA elements like creeps added into the mix. I wanted to take Herzog Zwei and combine it with Galcon Fusion, where you could jump from planet to planet with a fleet of buddies and start some shit. Made me think about Dynasty Warriors, while for all intents of purposes in love with its idea, usually just shut off within the first minute. Having something of a galactic map, showing what fronts you’re working with and swooping in on planets that are getting very contentious with your almighty supership has been really fun to think about. Unfortunately, it probably wouldn’t have been possible to do, given that I only have July to make it. I’ve never really worked on any kind of AI past state machines and wouldn’t know how to tell a computer to think strategically as I’m pretty awful at that myself.
I went to think about other games that have planets, namely Super Stardust. I’ve bought a Vita at launch as I’m a little too addicted and excited about powerful handheld game consoles, but also for Sony’s exciting Playstation Suite (now Playstation Mobile) initiative. Unfortunately Playstation Mobile hasn’t lived up to my expectations (which was something like Microsoft’s Indie Games), but that is a post for another time. One of the first games I got for the Vita was Super Stardust Delta, which was my first Super Stardust game. Needless to say, it’s a pretty dang good game.
I’ve figured, I could probably pull off making Super Stardust pretty easily. Probably need to try to make a very basic clone of it in Unity to confirm my suspicions, since there are often unforeseen circumstances. Given that, it wouldn’t be good enough to just rip it off. I’ve seen a post in the compo thread that was providing tips on what kind of game idea you should make based on goon tastes; one of them suggested that goons love Metroidvanias. Thing is, I do too! So I’ve figured… some Super Stardust-like game, with the planet’s surface covered with interconnected rooms that you would fly through. Another thing I would like to sprinkle over are some RPG elements, like leveling up your health meter and having some sort of skill tree for each weapon type, though details of such I would try and worry about later. So here I got a game that’s like Super Stardust with some RPG elements, having the player explore rooms on top a surface of a planet, moving from one area to another to eventually get to some final boss (sounds a little like a top-down Descent). How many levels could I possibly make in a month, though? One? Two? If anything, I’d like to give it some unique gameplay at every game the player starts.
So, I’ve figured I’d make it a roguelike. At least in the sense of level design, if not various RPG stuff like loot drops. Here comes the more technical bits; I needed to think about some base unit structure that I can extend out from the planet. So, I’m looking for some sort of sphere made up of the same polygons, of roughly the same size. The polygon used to make the sphere, I’d use to create rooms and levels with. My first idea was triangles, since all meshes are made up of triangles, in one way or another! I couldn’t use the bread and butter sphere mesh, though. You know, the one made up of horizontal and vertical slices, making longitude and latitude lines?
Imagine every square polygon made up of two triangles from the above picture. I could try to generate random structures and rooms, based on the triangles on the surface, but not every triangle would be of the same size or shape. I would have to add even more rules to my level generation based on how close to the poles the rooms would be; even then, rooms will tend to look skewed compared to rooms around the equator. I needed the triangles to be of roughly uniform size and shape. So I decided to look into an Ico Sphere.
The basic concept of an ico sphere is based on the icosahedron; a 20-sided polyhedron that many would recognize as your favorite 20-sided die. The steps involved to make this more of a sphere is to subdivided each of the 20 triangles to some desired amount of polygons, then from the center of the polyhedron, project through each vertex of the subdivided mesh of some uniform length; this is meant to be an act of projecting each vertex at the surface of some perfect imaginary sphere that surrounds this shape. What would result is this:
This method of making spheres usually yields better results than the longitude and latitude sphere above with fewer polygons (though it is usually called a UV Sphere for a reason!). Not what I’m interested in, though. From here, you can see it creates much more uniform triangles in size and shape, but not completely. There are some groups of triangles that look to be pinching in within each other; these triangles are the ones closest to the corners of the original subdivided triangle. When projecting lines through these, they are much closer together once on the sphere, than the subdivided triangles that are closer to the center of the original triangle face. Still, a much better starting point than the above UV Sphere.
After I’ve been looking in this for a while, I’ve begun to doubt the viability of using triangles as a building block for level generation. Given enough time and work, I’m pretty it’d be possible to create amazing looking level designs with some few parameters. Problem is, I don’t have enough time to experiment and try to create great randomized rooms, especially since I’ve never dealt with any form of procedural generation before. I’ve begun to notice a certain polygon in the above mess of triangles, though. Hexagons! That’d be a pretty neat build unit for level generation. Awesome thing is, before I even begun to research and experiment with this, I’ve found an great demo of the exact thing I’m looking for; HexPlanet!
The mesh it generates is still an icosphere, but I’ve been able to take the code and create a sphere completely made up of triangulated-hexagons (with the odd 12 pentagons) within the same demo:
With this, I can generate rooms based on hexagons, connected to other rooms and so forth with an easy enough to develop algorithm (I’ll get more into level generation in my next few posts). I know I’ve talked quite a bit about this aspect but for me I feel this is the glue that would hold the game together. I’m hoping that it’ll be fun enough for people to want to play new games over and over again.
As a bonus, here is a terrible concept sketch I’ve made on how the game would “play”:
The center mess of triangles would be the player, flying around these rooms (remember, the movement is not based on the hexes, they are only used for level generation), playing like some dual stick shooter like Geometry Wars/Super Stardust with some RPG elements. There are, of course, some more minute details to go over and additional gameplay elements, but that’ll be a post for another time! This one is long enough as it is.
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.