Random dungeon generator (Node based)

Attached Files

The following files have been attached to this tutorial:

.capx

dungeon-generator-tutorial-start.capx

Download now 211.51 KB
.capx

dungeon-generator-completed.capx

Download now 246.52 KB

Stats

7,367 visits, 10,913 views

Translations

This tutorial hasn't been translated.

Tools

Demonstration

Demo of Dungeon Generator

Getting started

This tutorial will show how to create a random generated dungeon based on a node system. In theory there are no limit to how big a dungeon you can make. but it will of course take a longer time to generate them the bigger they get. Since this tutorial is meant for advanced users im not going to explain every single line of code in great details and what exactly they do, I will assume that people wanting to make a generator have a somewhat good understanding of how C2 execute code, how functions works and how to read code in general, so you will not find any explanation of how tilemaps works, if you are not sure how to use them this tutorial wont help on that. Also note this will take quite a long time to make, so its not a 1 hour tutorial and can get very confusing at time.

This tutorial will include the following things:

- Generate a random system of hallways

- Dungeon size limitation

- Room generation

- Line of sight or light control for the dungeon

- Player control so its possible to move around it

Material

There are two versions, one is completely blank and only contain the objects you need to make it from the bottom up. This include tilemaps and all objects created before hand with names and so on and there are a completed version with all code included and are the one I have used for the screenshots throughout this tutorial. The only difference is that the blank version uses a tilemap for working purpose, which means the tiles contain the number they hold in the tilemap which will make it a lot easier to make.

1. Blank version: "Dungeon_generator_tutorial_start.capx"

2. Completed version: "Dungeon_generator_completed.capx".

Node system

Before starting here is a brief explanation of the system it self and the theory behind it, as its probably won't make much sense if this is not understood.

Luckily its pretty simple and is based on the idea that each tile only have so many ways that they are able to connect to other tiles. These connection points I refer to as nodes hereby the name node system, looking at the tiles below the nodes are indicated by the red half circles.

The system is an expanding one, so it will start at a certain point and from here expand the dungeon.

Each new tile are then expanded again over and over until the dungeon is completed and the desired dungeon size have been reached.

Content explanation

Each of the CAPX contains several elements that are explained here.

Resources

1. Loading text that is shown whenever a dungeon is generated.

2. This is used to show the coordinates of the tilemap, and is only needed during development so you don't have to keep track of them.

3. Is the "dungeon control" will go into details with it later, but basically this is what control the settings for the dungeon, it could have been made with global variables. However this reduce the amount of global variables needed and allow the use of Booleans.

4. Player dummy object which represent the player on the map.

Dungeon tiles X and Y lists

These lists hold the X and Y coordinate of the tiles which should be expanded.

Possible tiles

This will hold the possible tiles which can be connected at a given tile.

Besides these there are 2 tilemaps one which will hold the actual dungeon and the other which will act as cover while the dungeon is created and as the line of sight tilemap. Each tilemap are 26 tiles wide and 16 in height with each tile being 64x64px.

If you move the top tilemap several buttons will show. There are one for each size of dungeon that can be created "Large", "Medium", "Small" and two which are for controlling the line of sight, one called "Torch" and one called "Lantern". These buttons are just for testing purpose.

With the objects in place lets start to create the generator. It might be a good idea for now just to move the line of sight tilemap out of the way as we don't need it for now. When we need it just set the position to 0,0.

Step 1 - Start of layout

Most of these settings are just for resetting things to default, so they aint that important. This is stuff like Dungeon_size, Current_dungeon_size and so on, for now just use the settings that I have in the screenshots and you can change them in a second when they have been explained.

However there are one important thing which is that the "List_dungeon_tile_X" and "List_dungeon_tile_Y" are empty, this is due to two reasons.

First of all we want to be sure that it doesn't contain a blank element, which can happen even if you remove the content in the properties menu. (Think it might be a bug in C2) and the other reason is that the generator will use the item count of "List_dungeon_tile_X" to decide whether it should expand the dungeon or not.

Therefore we start by making sure that they are empty,

Next we need to tell the dungeon where we want it to start, which is done by calling a function with two arguments which are the TileX and TileY placement on the tilemap. Will get to the function in the next step. But for now i have just made these 12 and 8 so it will always start somewhat in the middle of the map.

(Since working with tilemaps can be somewhat confusing and to make it easier to read them while working with them, I normally add a functionality that will show the coordinates of the tiles, so I don't have to count them each time)

To do this I use a double loop to go through each tile in the tilemap and place a txt_dungeon_tile_nr object and set the text to the loopindex of the loops ("Add tile nr X" and "Add tile nr Y").

Each of the loop I make start on tile 0 and end at the tilemap.width or height divided by 64. This is because i know that the tilemap size is based on this factor, so if i should ever want to increase the map, i can just increase the tilemap by 64 pixel each time and that way i don't have to change any code.

When the dungeon generator is completed you can just disable this again.

Step 2 - Place start tile

Before we get into this lets take a look at the dungeon controller (The purple square)

"Dungeon_size" is an indicator of how big we want the dungeon to be, its not that the dungeon will be exactly this size, which is because it will finish off any open nodes first. But this is measured in number of tiles, so a Dungeon size of 25 will be at least 25 tiles big.

"Current_dungeon_size" Will keep track of how big the dungeon currently is.

"Open_node_count" This is simply used as i trigger.

"Dungeon_walls_created" This is also used as a trigger.

"Nr_of_rooms" Are how many rooms there should be in the dungeon.

"Tile_to_place_room_X" hold the Tile X location of where the room should be placed.

"Tile_to_place_room_Y" hold the Tile Y location of where the room should be placed.

"Player_placed" Used as trigger.

"Player_start_position_X" Hold the tile X location of player starting point

"Player_start_position_Y" Hold the tile Y location of player starting point

This will set the starting tile and then we increase the size of the dungeon by 1 since we have now placed a tile. After that we want it to update the list of tiles for which it should expand. So we call the function "Update open node count" which are the first part of this.

Step 3 - Update open node count

This is a fairly big function but its pretty much just a lot of "ORs" put together.

The first thing we do is to set the Open_node_count to 0, this is because it will count all available nodes each time due to the loops in the function. So when its done we will then have the correct Open_node_count. (Why this is important is probably not clear now, but will soon.)

This makes sure that only hallway tiles are checked.

Each of these sub events are organized into nodes. This is just so its easier to read the code. And they are just copy/pastes of each other and you need one for each type of tile. As the loops go through the tilemap, it will look for tiles that are Hallways (All tiles from 0 to 14) and the comments shows which tile is which. So in the highlighted example, if it encounters a tile 0.

We can see on the image that it have 1 node to the right. Since the loopindex "Tile X" and "Tile Y" have encountered this tile means its already on the map, so what we want it to do is to add the tile which this one leads to, to the list of tiles it should add next.

This might sound a bit confusing, so here is an example.

The blue tile is the tile that the loopindex X,Y currently have encountered. So looking through the tiles of the tilemap, this would be tile number 14, which have two nodes, one going left and one going downwards. Each of the tiles it leads to are marked with red.

So looking at the code for tile 14:

Since we are not interested in adding nodes to the list_dungeon_tile_X and Y, which already have tiles, we check to see if the node tiles already have tiles, which is done by checking if the tile number is < 0. In the example the downwards tile at 2,4 already contain a tile, so we only add the left tile. And by doing this we increase the Open_node_count by 1, since we added a new one. And then we call the function "Dungeon open list" with loopindex of X and Y with a modification in the direction that we want to add a tile. So in this case we can see that its the node on the left side, so we call it with loopindex("Tile X") - 1 but maintain the loopindex("Tile Y"). And we do that for all tiles in the map.

So you have to make one for each of the 14 tiles and for each of there nodes. (Its not really needed for the end tiles (0 - 3) so you can skip these if you want.)

Step 4 - Dungeon open list

This will add the passed values from "Update open node count" with the modifications to the List_dungeon_tile_X and Y list, the tile X coordinate is added to the X list and the Y coordinate to the Y list and each time we do this we increases the size of the current_dungeon_size by 1. This is because we already know that those nodes that are passed to this function are going to be part of the dungeon.

This pretty much round of the first part, which is adding new tile coordinates to the open list which will now be turned into actual tiles, since we haven't actually placed any tiles yet besides the very first one.

Step 5 - Build dungeon

This might seem a bit complicated at first, which is most likely because i choose to use lists rather than arrays, its just my way of doing it, i just prefer using them over arrays.

The first thing to notice is that this is done every tick as long as there are actually something in the "List_dungeon_tile_X", since we wont do anything to this list that we wont do with the "List_dungeon_tile_Y" list we just use the X list as the controlling list and therefore only check versus this.

The first thing we do is call the function "Check tile" which we will get to next. But what this does is it find all possible tiles for the selected tile in the list_dungeon_X and Y, and it is this function that actually places the tiles on the tilemap. When it returns from this function it will then remove the current tile from the list as it have now been added to the tilemap and no longer needed.

This part will only trigger when there are no more tiles to be expanded. So when the list is empty and the current size of the dungeon is less than the size of dungeon that we specified in the dungeon controller, it will call the "Update open node count" again, which means it will go through the tilemap once again for another pass. And this is how it will keep expanding.

If the current size of the dungeon is larger than the desired dungeon size, it will set the "Open_node_count = 0" which will be used as a trigger later when we create walls for the dungeon and need to finalize the dungeon. (I do believe that you can make it without this variable, but since i did, it will stay in this tutorial :))

Step 6 - Check tile

The way Check tile works and why its called "Check tile" is because it actually checks surrounding tiles, but you can of course call it whatever you like.

Since this function is quite big ill try to explain it in steps, it is also the one that is by far the most confusing one. So first of all the whole idea behind how it works, is that it is based on subtracting possible tiles from the possibilities that are available. This might sound a bit confusing and it is, especially when coding it, its very easy to make bugs in this part.

The first thing we do is to clear the list which hold the different possibilities, this is just to make sure that there are no tiles in the list from a former check, as this would screw up the tiles that should be available.

Next thing is that we always start checking the tile above the one we are currently placing (This is important as we can't can sure that there are a tiles here, so we have to check the other directions as well if its the case that there isn't one. But I will elaborate on that in a little bit.), and what we are looking for is to see if there are any valid tile there, which are tiles with a node pointing downward, in which case tiles (2, 4, 6, 8, 9, 10, 12, 14) are valid. If that's the case then we want all tiles with a node pointing up to be possible tiles for placement. So we add tiles (1, 4, 5, 6, 7, 9, 11, 12) to the list of possible tiles. Since not all these tiles might actually be possible in the end as we have only checked the top tile, we have to check the other directions as well. This will be done in sub events and the order in which you do this doesn't matter as all needs to be checked anyway.

Now this is different from the first one, Since now we want to find all tiles that are NOT valid, meaning those that doesn't have a node going upwards. So tiles (0, 2, 3, 8, 10, 13, 14, 15).

If any of these tiles are below the tile we are checking, we can then remove certain possibilities from the list. In this case tiles (4, 6, 9, 12) are no longer valid tiles As these tiles have a node pointing downwards. So we remove these from the list of possibilities.

Then we do the same for the left and right side.

The highlighted area above is very important as you can see in the image, after the "Start checking top tile" there is a "Start checking bottom tile" placed in an else, this is because if there are no tile above the one we are currently checking we have to check if there are one below it, so we start here instead, and likewise if there are none here, we will start at the left side and if that doesn't have one either we start at the right side, all these are placed on else statements. So Start checking left tile is an else to Bottom and Start checking Right tile is an else to Left. We have to do it like this, because otherwise it will be very difficult to know what possibilities we have for placing a tile.

This is the part that actually places the tile when all possibilities have been found. There is one twist to this and that is that it also controls whether the dungeon should be forced bigger or smaller. Which in it self are fairly easy if the first part is done correctly.

If we want to force the dungeon bigger, we simply remove the possibilities that would close off hallways. Which are tiles (0 to 3) as these are end points, so we remove these from the list. So it will always choose a tile which have at least 1 open node.

And we can do the same if we want to make the dungeon smaller. Which are done in the else, and in the exact same way as forcing the dungeon bigger, except in this case we remove all other tiles than tiles (0 - 3).

This round up the part of actually creating the dungeon it self, as these things will keep running until the variable "Current_dungeon_size" is bigger than the desired Dungeon size set in "Dungeon_size" which both are set in the Dungeon_controller object.

However this doesn't mean we are done, at this point the dungeon will not look very smooth. As there might be tiles that doesn't fit correctly into the dungeon. This is because we don't know how the dungeon expand and therefore tiles might end up looking weird, It could have been done so it was cleaned up on the fly, but personally i find it easier to simply correct it when its done. But to fix this we run a clean up on the dungeon.

Step 7 - Create dungeon walls

The first part of our clean up is to fill all empty tiles with wall tiles. If we take a look at it.

The first thing is the triggering it self, so you can see how it is connected to the rest of the program.

The trigger is done by both "Open_node_count = 0" and the Boolean "Dungeon_walls_created = false"

Since "Dungeon_walls_created" is actually false by default, the actual triggering is done by "Open_node_count = 0" which is done in the "Build dungeon" (Step 5) when the current size of the dungeon is larger than the desired dungeon size if that's the case "Open_node_count" is set to 0.

What it then does is pretty straight forward as it just goes through each tile and check if they are less than 0, if that's the case it just places a wall tile (15). To make sure this is only done once we change the Boolean "Dungeon_walls_created" to true.

And then we call the function "Finalize dungeon design" which will clean up the whole dungeon making it look correct and when that's done we will place the rooms and finally the player.

Step 8 - Finalize dungeon

This is pretty simple as it again just run through each tile in the tilemap and if they are not walls (15) then it will call the function "Correct tile" with the TileX and TileY value.

Step 9 - Correct tile

This function is very big and would require a lot of images to show, so ill try to show it with an example.

But the way it works is that it checks a tile to see whether one or more of its nodes are blocked and then replaces it accordingly. Its quite simple to make, but just requires a lot of coding.

All tiles except tiles (0 to 3) need to have a correction, the reason is that tile 0 to 3 are end tiles so they cant be placed wrong.

But this is how it works.

This example uses the code shown in the above screenshot. From the description we can see "Tile 4 correction, Bottom is blocked replace with 7" Which funny enough is exactly what it does.

To check whether a direction is blocked i use 4 different functions that each check a direction and return either true or false. And this is pretty much the whole idea of the node system, as each tile only have so many possibilities so making these four functions are really easy.

Here is the one that handles top tiles.

These will never change and are all tiles which have a node pointing downwards. The others are exactly the same except for the bottom tile it needs to have a node point upwards. And it should be (Function.Param(1) + 1 instead of - 1)

So looking at the first screenshot again of the correction code for tile 4. (Tile 4 is the one with the blue color in the second screenshot). We can see it have 3 nodes (Top, Right, Bottom) And for the correction to take place the bottom node needs to be blocked. So we start by checking the top node by calling the function "Check tile top" and then we check the return value to see if its true, in this case it is, As the tile above tile 4 is a tile 10, which are a valid tile in the Check tile top function. Next we do the same again this time for the bottom tile and we want this to return a false. Since the tile below tile 4 is tile 13, and is not a valid tile it will return false. And finally we will check the right tile the same way and since tile 5 is a valid right tile, it will return true, and then we replace tile 4 with a tile 7.

When you have gotten the hang of it, it is quite easy and fast to make this for all tiles. But as you can see you have to make one for all possibilities for each tile, so you need to make a lot of these. But none of them are any more complex than this one.

Step 10 - Create rooms

Create room is the next part after finalizing dungeon design in Create dungeon walls. (Step 7)

This part is really easy due to the way the dungeon is generated and it just replaces hallways with rooms tiles that matches them.

We simply let it run until it have created all rooms specified in the Dungeon_controller object. Since we don't really care how many times it runs or how many times it select wrong tiles as it will do it very fast anyway, we don't really have to make a lot of checks, the only thing we need to check is what tile it have selected and if its a hallway tile, then we just tell it to replace it with the correct room tile and then subtract one from "nr_of_rooms".

So you simply make one for each tile.

Step 11 - Place player

Next is to place the player dummy object, and is the last step of the actual dungeon generator. but first lets take a look at the variables.

"Player_tile_X" just hold the tileX value, this is simply so we don't have to calculate it all the time.

"Player_tile_Y" just hold the tileY value, this is simply so we don't have to calculate it all the time.

"Current_tile_number" Is used for doing collision detection when the player moves around the dungeon, and to make it easier when needing to do collision checks.

"Line of sight" How many tiles the player can see.

The way the player is placed is done exactly the same way as how rooms are placed, it just keep trying to place the player until it find a valid spot. I try random locations and store them in the dungeon_controller object, and then use these to see if they are valid and if that's the case, i copy these to the player object and move it to where it should be. Then i call a function which will just set "Current_tile_number" variable to the type of tile that the player is standing on. And then set the "player_placed" to true, this is actually not used for anything. But can be used as a trigger should you want to do something after the player have been placed, like generate random loot, placing enemies and so on.

And finally we call the function "Update line of sight" will get to this in a bit and last we remove the loading text as dungeon is completed and the player should be able to move around and explore.

Step 12 - Player control

This just allow the player to move around the dungeon.

Since we need to know which type of tile the player is currently standing on for the collision detection, i start by calling the function "Set player tile number", which is very simple.

After that we need to check if the player can actually move in the desired direction so we call another function which will check this for us.

Im not gonna post the whole function here as its also quite long and is fairly simple as well. And uses the same principle as the "Check tile top, bottom, left, right" shown earlier. Which are that each tile only have a certain amount of possibilities controlled by the type of nodes they have available.

Looking at the first few lines, we check to see if player is currently standing on tile 0 or tile 22 which are the hallway and the room of equal type.

And finally we just use the angle of the player to see if they can move there and if that's the case then we return true. So just add one for each type of tile and room.

After we have checked for the collision we simply check what direction the player is facing and move them in that direction and update the "Player_tile_X and Y" accordingly, so its ready for next time the player moves.

And finally we call the function "Update line of sight" again as the player have moved and therefore they can see new things.

Not really anything to add as its pretty basic, it just rotate the player.

Step 13 - Update line of sight

This is what handles line of sight (NOTICE THAT THIS USES BOTH TILEMAPS!!!)

This will make the player able to move around the dungeon as if they had limited vision.

The first thing we want is to make all tiles on the line_of_sight tilemap black and then we erase the tiles that should be visible. So we set all tiles to 0 which are the black tiles.

Next we erase the tile where the player is currently standing as this tile should always be visible we do this using the function "Erase tile".

And finally add a loop that runs from 0 to the line_of_sight that we want the player to be able to see.

Step 14 - Erase tiles

This will erase tiles based on the type of tile its current working with. And again it uses the same principle of the node limitation as "Check tile top, bottom, left, right".

So if the tile the function current checks are a tile 0 it will erase the tile Right of it, as it have a node in that direction.

And since in the Update line of sight function it is looping it will do this as many times as the line of sight of the player. To make sure that the player cant look through walls. I added a check to see if the tile before the one its currently checking are visible, if that's not the case it will not update line of sight in that direction. It will call Erase tile for each direction that's why there are 4.

Optional - Generate dungeon buttons

This are just the buttons and the only thing they do are just resetting the dungeon with the desired values. If you have completed the tutorial this part should be pretty easy to understand :D

(You don't need the last two "Remove item 0" its just some leftover garbage code that didn't get removed.)

Reset dungeon function, just reset the tilemaps and unfocus the buttons as they can cause problem with the player movement if not done.

Change line of sight settings.

That round up the tutorial, hope it was helpful and that more people will create some generators can never have enough of these :D

.CAPX

dungeon-generator-tutorial-start.capx

Download now 211.51 KB
.CAPX

dungeon-generator-completed.capx

Download now 246.52 KB
  • 0 Comments

  • Order by
Want to leave a comment? Login or Register an account!