A short while ago I was approached to write a book on terrain generation using dedicated tools for a variety of game engines. There's a lot more to game content than just terrains. Josh's recent blogs on CSG got me thinking about one of my favourite games and had me itching to re-visit the genre.
This series is an exploration of topics I don't normally exercise but are fun to do. Leadwerks is a fun engine that's ideal for prototyping ideas. So throw out your terrain system, we're going to make a game all about claustrophobia. We're going DOWN into the tunnels to blow stuff up Leadwerks style using a mix of old-school gaming know how and modern day 3D.
Our goal: create a simple six degrees of freedom shooter set in a procedurally generated network of rooms and corridors. You can use this as the basis for a number of different games but as I'm a fan of the old classic shooter "Descent" and it's easy to create a physics controller to fly around in Leadwerks. Also it can be re-worked using Leadwerks3Ds CSG functions when it's available.
Procedural Map Generation
Dungeoneering is back in gaming news with Legend of Grimrock, a take on Dungeon Master grid based geometry. Many games are based on grids, they are easy to work with and often form the basis of AI routines. They are also easy to generate geometry for. There have already been numerous articles and blogs on creating such levels, you'll find links at the bottom of this article.
But before we look at some LUA code to create geometry we'll first have a taster of different techniques used in creating random level geometry. After that we'll kick things up by adding more vertical elements for our demo game. I warn you in advance, I'm not a LUA expert and nor am I a big fan but I'm sure you good folks can make it better and LUA brings the examples to the widest possible audience.
Node based grid
Our goal is to create a collection of rooms connected by corridors through which we can explore. A simple approach is to seed a random number of nodes (rooms) and connect them up. There are other methods, such as a corridor based approach which adds rooms in a second pass, such a method is used in the classic DOS game HACK (aka NETHACK).
For our examples we'll stick to a 40 x 40 grid to keep it simple. Each grid square could equate 100 world units or 10 in Leadwerks, it doesn't matter as long as we use a consistent scale. We'll stick to 100 units (1 unit = 1 meter) per grid square for this example meaning our potential map is 400x400 units.
Here each node represents a room of random size. We can restrict the size of the room to fit within its parent grid to make it easier to deal with problem of overlapping rooms as illustrated in the figure below. Eventually we'll construct the geometry to build these irregular shaped rooms so they merge as a single entity.
You can see that choosing the size of rooms will impact on how much corridor space you're going to end up with per map. This is something you can set in code easily giving control over how open or closed your level will feel.
If we stick to the grid arrangement connecting them by corridors becomes an easy process. The difficult part is constructing the vertices and triangles to fit together nicely but we'll get to that. By far the easiest way of joining rooms together is by joining them at the cardinal points of the room. While this makes logic easy it also makes for a pretty boring layout. What's more, there's no reason why a corridor has to be of fixed width...or height.
A room typically connects to a room in a neighbouring grid using the straightest link possible and we'll dog leg corridors as required. To add some interest we'll create a 'route' through the grid and randomly connect to neighbours.
Again there are many ways you can do this and I encourage you to try your own variations. Our rule-set will have a random chance of connecting to a neighbour if that room. That chance will degrade if that room overlaps and on the number of existing corridor links. Hopefully our final 2D layout will approximate the figure below.
Then each room can add its own flavour by adding columns, point lights, props, whatever fits your game.
Once we've got a class to generate the map we can then move on to generating the required geometry (surfaces) so we end up with something looking like...
Things get even more exciting when we'll extend these maps into 3D, with vertically offset rooms and corridors. Eventually we'll have a complete base generated by a single random seed you can fly, shoot, leap, run through with a basic controller.
Once we make the logic for generating rooms 'furniture' props can be parented to the room mesh to take advantage of culling. I'm not going to add much in the way of occlusion, instead Leadwerks can take the stain and should do a good job with no effort on our part.
In part 2 we'll start with some code to generate the above with geometry directly in the Leadwerks editor and we'll be using Vertex and Surface commands to create rooms which look like the screen-shot below.
Random room generation in LUA, corridors coming shortly for part 2
Everyone is welcome to contribute.