Jump to content

Let's Make a Game - Procedual Content Creation (part 02)



blog-0329348001336644600.jpgAbout: This is a short series for the Leadwerks community on the process of creating a simple game using procedural content.


In part 01 we looked at one theory of generating random maps in the style of old school dungeon crawlers. This week we'll put that into practice to generate map data, room geometry and mesh colliders. The easy part was adding a flying physics based camera to act as our first-person flown "spaceship".



Again I want to flag I'm not a LUA expert, this is not a LUA tutorial but like most languages they are a syntax away from common functionality. It includes examples and explanations of some LUA code to relate why I did something a certain way. What you see is what you get. All code is freely available for use and modification however you see fit.



How to use the code and run any examples in this series


After working on the code a short time I found using the
Leadwerks ScriptEditor.exe
better for the process rather than attempting to run and debug it as an editor script. And one last note before we get on with it, 99% of the assets are included the Leadwerks SDK media folder so please edit the "MediaDir" in the LUA source. Any other required media will be included as a download.


Pre-amble over with. Lets get to it.



Map Data to 3D Geometry - first experiment


The focus for this tutorial is generating map data then creating 3D geometry from it. The latter raised several questions about what would work for a tutorial and flexibility for use in different kinds of games. So I've focused more on this side for part 02. (Also I had to re-write it meaning less time to work on the map data code).


My first room generator working prototype created "shoe boxes" as pictured below. With lighting, ambient sounds and the physics on a controller to fly your 'ship' around in first-person view it was a passable bit of code.




figure 2.2 - "ShoeBox" room and corridor structure


"ShoeBox" was efficient in that it was a collection of flipped volumes with light sources, individually painted surfaces (6 materials) and would be good for a simple iPhone adventure.


When it came to merging volumes for more complex rooms I realised there would be a lot of code needed to split up geometry and re-build it. Rather than turn it into an exploration of CSG, triangulation and mesh simplification (which is not trivial) I ditched it for another simpler approach.


Going back to how 2D games work, room geometry became a collection of grids (figure 2.2) that can be thought of in terms of traditional 'tiles'.



figure 2.2 - tiled room (aka a regular mesh)


Looking more like a terrain mesh with walls and roof, the grid structure makes it easier to merge volumes, add doors, corridors and holes traps or vertical shafts. And by increasing the mesh density and adding vertex noise you can turn rooms into caves with bumpy walls. I felt justified in presenting this method as it allows more possibilities and simplifies geometry construction.


In appearance it's quite like old-school cells and tiles, similar to existing 2D dungeon map generators. In my working prototype you can't individually paint a tile but it might be possible to modify the code to allow for UV painting and save out this data. Each room can have it's own unique set of materials.



LUA code-time. Geometry Construction


Leadwerks like other engines provides tools to create solid shapes entirely in code. First you need to create a Mesh object then a Surface object attached to that Mesh.


local room = {}
room.mesh = CreateMesh()
room.surface = CreateSurface(room.mesh)


Note: For clarity this is using ONE surface, this will be expanded to use a six surfaces for each side of the room. The important part is that you add geometry to surfaces, you paint surfaces with materials, you create colliders with surfaces. It's all about the surfaces baby.


All room elements such as walls, floor, lights, props etc. are parented to the room.mesh which is positioned in world space. Moving the room is as simple as calling Map:Room[id].SetPosition(x,y,z)


Really evil dungeon masters might want to re-position a room with players inside. Well you can do that, even rotate it. Parent the room to the whole map (which has a pivot) and you can roll the entire map around for a marble game. All walls are solid but as they are one sided you can see right through them when viewing from outside.



Patch Maker


Let's look at a LUA code snippet for creating the roof and floor mesh, I want to draw attention to one of the cute things LUA can do and if you've not come across it before it can be confusing. So I draw your attention to it now. The assignment of (nameless) functions to a table and indexing them by string.


Depending on what part of the room we are building we take care vertices are wound the correct way and the vertex normals are perpendicular. So I put the AddVertex() and AddTriangle() calls into a table and for ease of identification indexed them by string such as "roof", "floor", "north_wall" (walls not included here for clarity).


addvert["floor"] = function (s,x,y,height,xsize,ysize) return s:AddVertex ( Vec3( x-(xsize * 0.5), height , y-(ysize *0.5) ) , Vec3( 0 ,  1 ,  0 ) , Vec2(x / (ysize*0.1), 1.0- y/(xsize*0.1)) ) end
addvert["roof"]  = function (s,x,y,height,xsize,ysize) return s:AddVertex ( Vec3( x-(xsize * 0.5), height , y-(ysize *0.5) ) , Vec3( 0 , -1 ,  0 ) , Vec2(x / (ysize*0.1), 1.0- y/(xsize*0.1)) ) end
addtris["floor"] = function (s,v,ysize) s:AddTriangle ( v-ysize-1, v , v-1  ) s:AddTriangle ( v-ysize-2 , v-ysize-1 , v-1 ) end
addtris["roof"]  = function (s,v,ysize) s:AddTriangle ( v-1, v , v-ysize-1  ) s:AddTriangle ( v-1 , v-ysize-1 , v-ysize-2 ) end

function Map:CreatePatch( surface , width , length , height , mode )
for x=0,width do
 for y=0,length do
  vcount = addvert[mode](surface,x,y,height,length,width)
  -- we degenerate first row and column when making a grid
  if ((y>0) and (x>0)) then
addtris[mode](surface, vcount , length)


Our room geometry code needs to call the patch builder with dimensions and the name of the component like thus...


-- example useage from the room builder
Map:CreatePatch(room.surface, 8 , 8 , 0 , "floor")
Map:CreatePatch(room.surface, 8 , 8 , 2 , "roof")


That's the easy part. We will need to extend Map:CreatePatch to take our merged room data and generate an appropriate mesh to fit the irregular shape of our rooms and corridors as supplied by our dungeon creator.


Now we have a method to generate basic rooms which is easy to modify we can look at the other problem; creating our random map.


Remember the map structure we're looking for, a grid of cells into which we position at random offsets a regular set of rooms (see figure below). Each room being of variable size and can overlap. For this part of the tutorial we're going to keep the rooms small enough to prevent overlap to keep the source size down and reduce the complexity. We'll cover triangulation for a more advanced geometry function in a later part. In other words I couldn't get it to work properly in the time allotted.



figure 2.3 - room and corridor structure



We'll begin with a creator function...


-- function to build entire map
--  params: random seed value, xsize and ysize (dimensions of map in cells)
--  roomscale (is multiplier of room size in world units)
function Map:Create( seed , xsize , ysize , roomscale )
math.randomseed( seed )
if roomscale == nil then
 roomscale = 1.0
Map.roomscale = roomscale
Map.roomheight = 2.0
Print("Creating map, dimensions " .. xsize .. " x " .. ysize)
-- table to store our rooms
Map.Rooms = {}


For our dynamically generated game level, we need to know a couple of things;

  • How big in game cells (how many rooms across and down)
  • The seed from which the random nature of all springs forth (how poetic)
  • How big we want the rooms to be relative to each game cell (room scale).

A tile is simply a value stored in a 2D array e.g. tile[x,y]


Our data would benefit from being organised into a grid. A 2D tile structure which represents an overhead view of our 3D world. This makes tile arrangement makes it simple to merge rooms and corridors, flag as walls, doors, traps and anything else we might want to generate. However...(c'mon you knew that was coming)...


If we want to make really HUGE levels then array mapping will be inefficient, the 400x400 grid in our example will be fine but anything larger will become resource hungry as we increase the world size. Much of it becomes empty space.


To avoid unnecessary memory usage and run-time costs we will virtualise the space a little. We've done it already with our room nodes (figure 2.4)




figure 2.4 - room nodes
virtualised rooms


Note: A room object simply exists at world_x, world_y and is this >< big. This is for boundary test and positioning.


We will use a 2D array of tiles for each room. Each tile maps to a room_x, room_y. This way the data is available to game logic for locating objects, spawn points.


After room generation is complete we run a post processing function to merge rooms, this is where the tile array comes in handy.


The room merge steps through all rooms, a boundary check is performed on neighbours and merging into a new room as needed. Corridors are considered rooms (just thin), where they bend they are in fact two overlapping rooms and should be merged during the same process.


After rooms have been merged, the geometry builder works on the new set of room tiles to spit out all the required meshes, lights and props.


Infinite Power!


In theory we can make an infinite dungeon if we move the rooms around us at the origin and use world space as a random seed for new rooms. An order of magnitude more advanced than Very Big Cave Adventure.

10 PRINT "You are in a cave (N,S,E,W)?"
20 INPUT a$
30 GOTO 10


Out of time!


Yes I've run out of time for part 02 due to code re-writes. I'll write up the room generator code as part 03 and post the example code with it. Then we'll start to see the two halves coming together and creating our procedural maps.


Preview: HUD Overhead Map


First pass on HUD to show location of rooms (with ID) within the randomly generated map complex.

1 Comment

Recommended Comments

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Add a comment...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

  • Create New...