Autogenerated Dungeons

From PSwiki
Jump to navigation Jump to search

(Go back to the main GSoC 2015 page)


Skills needed

Our server and client are all coded in C++ and the database is MySql. The mechanisms will have to be implemented both client and server side, so good knowledge of C++ is needed for this project.


The dungeon generator aims to generate random dungeons using the idea of a "Superblock" which is a 9x9x9 units box with a grid of connection points. This superblock will be used to generate the actual blocks part of the dungeon. With predefined connection points, a set of standard blocks can be used to create the final area by placing one block next to the other and generate a coherent set of tunnels, rooms, and passages. Additional props can be added to the generated area, like for example special locations, loot, chests, doors, etc... This project aims at creating the algorythms and the actual database tables to store the autogenerated areas.

Detailed Description

Dungeon generator aims to generate random dungeon using Superblock which are defined as following :

  • SuperBlock needs to have borders connections points. These connections are

defined by a fixed number of vertices in determinate location for each border/joint (for instance 24 vertex)

  • Superblock is defined as illustrated. Vertices in red are generic to border/joint

requirement and vertices in blue are specific superblock type :


Here is an example of one block using 2 connectors:


  • Superblock is made of « virtual Block » which are assume to be an unit cube of 9x9x9 meter in game.
  • Superblock Texture density is to defined according to this
  • Superblock have to be filled by Props (elements like mushrooms, crystals, etc..) .

Props are automatically locate. There are part of a superblock specificity.

  • Rooms and corridors are Superblock. We may need some special Superblock for

huge rooms.

    • Corridors are ways between 2 points and stay as defined.
    • Rooms are "living/action" place. We have to define spot to drop "special items or NPCs" by dungeon generator

Dungeon generator have to used Superblock to create 3d world. So it has to manage :

  • X direction : Building left/midlle/right
  • Y direction : Building left/midlle/right
  • Z direction : Building up/level/down
  • To reduce workload, we can use :
    • some 3x3x2 superblock to build up to down / down to up
    • some 3x3x1 superblock to build at same level

So we assuming the following points :

  • Superblock can only have 1 "gate block" by side
  • Superblock having more than "2 gate block" are "plate" (same level for each

gate block)

  • Superblock having only 1 gate are "Portal" to go out and one of them is the

drop entrance too

  • Up <=> down mean a change of level for start to end else start and end are a

the same level.

  • According to mirroring on X or Y axes and available rotation 90°, we can

considered all superblocks needed are defined in the following table:


Dugeon generation rules of uses:

  • Dungeon is defined by the number of "superblock" needed to construct it and by

its grid of superblock

  • A superblock can not be added in world grid at a location if :
  • it creates a situation where a superblock of more than 1 level up or down is

required between the "Block gate"

  • it creates a situation where a superblock of more than 2 "Block gate" with a

level change is required

  • A superblock has to be added until all Block gate are closed
  • Dungeon shall have a « Start room » and a « End room »
  • We assume all rooms and portal are type :impass

Additional ideas

  • Collapse the geometry of multiple blocks to create a single piece for performance reasons. This requires some CS internals knowledge and we need CS help.