A procedural multi-layer dungeon generator
JavaScript GLSL
Switch branches/tags
Nothing to show
Clone or download
Pull request Compare This branch is 47 commits ahead of CIS700-Procedural-Graphics:master.
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
Results
images
src
.gitignore
Final Report.pdf
LICENSE
README.md
bundle.js
bundle.js.map
deploy.js
framework.js
index.html
package.json
webpack.config.js

README.md

Interesting Level Generator

Overview

The 'Interesting Level Generator' is a procedural multi-layer dungeon generator that generates levels based on a dynamically generated voronoi like graph after it has been heavily modified by various filters. Realistic fog, crumbling pathways, and terrain are added over the basic level layout to give it a unique mysterious foreign world aesthetic.

Original Design Goals

  • Procedural 3D game level ( multiple stacks of 2D maps ).
  • Implicit surfaces to create terrain on the resulting map floors
  • Custom fog shader

The specifications below will be implemented if I have enough time in the final week:

  • Controllable Player character
  • Collision handling so player can’t walk through geometry.

Techniques Used

2D Maps Level Generation:

Room Generation:

  • Using sampling and rejection to layout the slabs in a given space.
  • Then use a fake voronoi generation technique to create a graph. The fake voronoi technique consists of first starting with 3 connected nodes, and then for every new node you want to add to the graph you find the 2 closest neighbours from the existing graph and form edges between them.
  • We can improve the above technique a bit more by sorting the positions of the slabs along one axis. This makes the connections look more like a voronoi pattern.
  • This graph is highly connected so we randomly remove connections.
  • The graph can end up with intersecting edges in a few edge cases, so we carry out 2D line intersection tests and remove any intersections if they exist.

Walkways between slabs:

  • Because of the graph we created above we have edge and node data, in other words we know which points to connect. So between any 2 points we could lay out corridors(planes) to connect them, but this is boring.
  • Instead we can use instancing to place many many tiny cubes along the line segment and then randomly remove cubes to make it look like a crumbling walkway.
  • We also need to give the walkway some width so we take the cross product of the direction of the line segment and the y axis (up) to get a horizontal ortho-normal direction for width. Add instanced cubes not just on the line segment but for a certain width for each line segment.

3D Level Generation:

We can create multiple 2D maps at different heights.

Interlevel Connecting Paths:

  • This is a similar problem to the one we solved in “Walkway between slabs” section; But now it’s in 3D.
  • For every layer we pick a random node/slab as the starting point of our path between layers.
  • For the end point of that line segment we search through the nodes in the layer above for rooms that are beyond a certain distance from the randomly picked starting node (so paths don’t go straight up and there is more complexity in connections), and form a list of these “toNodes”.
  • Pick a random “toNode”, and using the random starting node we have a 3D line segment.
  • Create a similar instancing cubes setup for these paths as we did with the walkways.
  • Remove random lines, and also carry out 3D intersection tests and remove any intersecting paths, if they exist.

Path shifting for Paths:

  • To make the paths connecting walkways seem more organic and prevent janky looking paths that start at the center of each cell and end at the center of the other one ( this is a problem as a player can never go to a higher layer, they will be stuck underneath the “toNode” ).
  • We need to shift paths to the edges of the cells they are connecting. Simply offset by the width and length in the correct direction.
  • To add organic paths we should shift by both the width and length.

Fog:

  • Created in the shader, with global control of density, color, and a on/off switch.
  • A good approximation of fog fall-off is: e-(fogDensity2 x distance2)
  • Fog also appears to have different densities at the periphery of our vision, so we need to account for rimColor.
  • Resource: http://in2gpu.com/2014/07/22/create-fog-shader/

Terrain:

  • Terrain was created in the shader.
  • Create an elevation map and a moisture map using smoothed 2D noise with different seed values (or different noise functions).
  • Use the elevation map to deform vertices in the shader.
  • Create a moisture map ( similar to the elevation map ).
  • Use the float values from the elevation and moisture as uv values to determine colors from gradients.

Grid based Acceleration:

  • Takes too much memory, and so was never used for anything.

Future Work

  • kD tree acceleration Structure for Collision Handling
  • Character with basic character controls
  • Collision handling for the character
  • Trampolines to fill up empty and negative space

Resources

Moar Images!!