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.

  • Blog Entries

    • By Josh in Josh's Dev Blog 0
      Leadwerks 4 supports compressed and encrypted game files in ZIP format, but there are many different custom package formats different games use. The plugin system in Leadwerks 5 allows us to create importers for these different package formats so we can access content directly from commercial games you have installed on your computer. The example below shows how to load a VTF texture from the game Half-Life 2 directly from the game's install files.
      First we need to load some plugins to deal with these weird file formats.
      --Load VPK package loader plugin local vpkloader = LoadPlugin("Plugins/VPK.dll") --Load VTF texture loader plugin local vtfloader = LoadPlugin("Plugins/VTF.dll") Next we will load a single VPK package directly from the Half-Life 2 install directory. If you have Steam installed somewhere other than the default path you can change the value of the STEAM_PATH variable to load the package from somewhere else.
      --Steam installation path local STEAM_PATH = "C:/Program Files (x86)/Steam" --Load package (Half-Life 2 must be installed) local pkg = LoadPackage(STEAM_PATH.."/steamapps/common/Half-Life 2/hl2/hl2_textures_dir.vpk") Now we can load content directly from the Half-Life 2 game files. Although the file specified below does not actually exist in the game folder, it will be loaded as if it was because of the VPK package we previously loaded.
      --Load texture local tex = LoadTexture("materials/building_template/buildingset040a.vtf") Here is the result when I run the program:

      Now if you wanted to load all the HL2 data files when your game starts, that is easy to do too. If you place this script in the "Scripts/Start" folder all the content will be automatically made available:
      local STEAM_PATH = "C:/Program Files (x86)/Steam/" local HL2_PATH = STEAM_PATH.."steamapps/common/Half-Life 2/hl2/" local dir = LoadDir(HL2_PATH) local k,v LoadedPackages = {} for k,v in ipairs(dir) do local ext = Lower(ExtractExt(v)) if ext == "vpk" then local pkg = LoadPackage(v) if pkg ~= nil then table.insert(LoadedPackages, pkg) end end end What is this good for? You can browse and view all the content in your installed games and use some assets as placeholders. Valve is pretty lenient with their IP so if your game is only published on Steam, you could probably use all the Source games textures and models. You could make a mod that replaces the original game engine but requires the game to be installed to run. It would also not be too hard to integrate these features into the new editor so that it can be used as a modding tool for different games and allow you to create new game levels.
      You can get the source for this and other plugins on Github.
    • By Josh in Josh's Dev Blog 2
      I've restructured the plugin SDK for our new engine and created a new repository on Github here:
      The GMF2 format will only be used as an internal data transfer protocol for model loader plugins. Our main supported file format will be GLTF.
      As of now, the plugin system can be used to write texture loaders for different file formats, model loaders, or to modify behavior of particles in the new particle system. The FreeImage texture loader has been moved out of the core engine and into a plugin so you no longer have to include the FreeImage DLL unless you want to use it. The main supported texture format will be DDS, but the FreeImage plugin supports many common image file formats.
    • By Admin in Leadwerks Company Blog 0
      The GMF2 file format provides the fastest possible load times for 3D models. A preliminary specification and SDK for loading and saving files in the GMF2 file format is now available on GitHub here:
      A Quake 3 MD3 model loader is included as an example.
  • Create New...