Randomly generated dungeon – Part I

Why I am doing this …

Its safe to say tiles make me crazy. To me its very abstract to make a random generated dungeon.

I am going to start off by saying I am not a programmer. So I might be going about this the complete wrong way, I hope not, but it might be. It started a week ago, when I got this idea that I wanted to make a dungeon crawler, semi randomly generated. When I say semi, I mean I want some custom events in the levels, but I want the journey between the custom events to be a random generated dungeon.

I also like to tinker with Blueprints, I love blueprints in fact.

On the spare time, I have been doing a lot of different things in blueprints. I have made inventories, AI, etc etc. Coming from a 3D designers point of view, its a different way of creating something, and I like it. It also learns me a whole different way of thinking about things. If this is true keep reading. Hah!

So back to this idea I had, the dungeon crawler. I have tried for a week now to understand how to get the maze to go the way I wanted it to go. You see, I wanted to have the tiles always have 1 tile to separate them.

Much like this dungeon creator I used for inspiration : Dungeon Creator

I ran into weird bugs where it spawned a single tile in the middle of nowhere, I ran into bugs where my tiles would just stop, and I couldn’t understand why. I looked at a lot of tutorials from the unreal engine community like these ones :

 


 

 
 

But I didn’t want to just copy paste blueprints and variables, I wanted to understand it, so I could add my own features and control it. So, to do this, I took a more visual approach to understanding how to get this done. So just to be clear, I am not going to go into a ton of blueprints, there will only be some. There are tons of tutorials to learn to understand how to use a loop or a variable. I am rather trying to make myself, and perhaps you, understand how to create a randomly generated dungeon and how it works. This is mostly to satisfy my own curiosity.

This is part one……

So this is what we are trying to achieve. A tile that starts at 0,0 and ends up at 4,0. The reason I want it to end up at a specific point is because I have this idea I mentioned earlier. That I want to have events (a puzzle, a boss fight or a level exit locked beyond a door). The point being that the journey between those custom events will be different every time you play the level. The image below shows the first step of what I am trying to achieve. This small grid is something I just made to demonstrate, the dungeons will be much larger and also contain rooms that are locked, or contain secrets.


So back to the part of trying to get an idea of what I am doing, I made this smaller grid representing what directions we must check when standing on a tile. The tile I want to check here is :  X : 0 Y : 0.

So If I want to check if I can move to the North tile above me, I have to check if X : 0 Y : -1 is free. Which means I have to subtract 1 in Y.

Just to clear up.

  • Check North tile : Y + 1
  • Check South tile : Y -1
  • Check West tile : X -1
  • Check East tile :  X +1

This makes it really easy for me to understand what tiles I have to check in both X or Y and what number.

If I am going to check 5 tiles (-1 – 1, 1 -1, -1 0, 1 0 and 0, 0) on top of the image, something I will be doing later, I can just check this “map” for what I need. Just check if my array contains those five tiles.

The first one is easy, just get X and Y. The left is X minus 1. The right is X plus 1. Left top corner is : X minus 1 and Y minus 1. The top right corner is  X plus 1 and Y minus 1. This helped me a lot to understand what sort of calculations I had to do to make my maze work the way I wanted.

Check the tile …

I made an array in blueprints, the purpose of the array is to contain all the tiles that I have visited. I start by adding 1 tile, this is the starting tile. It can be anywhere really, but I put to 0,0 in my blueprint. (Image above.)

Now here comes the tricky part, what tiles do we check? I drew up this (image to the right), I call it the 5 tile check. Lets imagine we are standing on x : 0 and y : 1 (if you don’t know where that is, check the “map”, as I did.).

We then move North to x : 0 and y : 0. Before we can add a tile there we want to check if there are any tiles blocking it from being made. This is where the 5 tile check comes in. I check all the yellow tiles, and the tile I am trying to move to. If there isn’t any tiles there, I can move there. 🙂

Why check 5 tiles? Because it makes sure that I have spacing between the tiles like I mentioned earlier. I have a couple of images demonstrating this later as well.

Now lets see what happens, I have added bounds. Tiles you cant go to at all. You can still move south, its just the initial tile, the one you are trying to move to, can never go out of bounds. I did this easy in blueprints, I just check if it is < 0 in when going North (-y). < 0 when its going West (-x). > 4 when going South (+y). > 4 when going East (+x). Look at image below.

 

So it will pick a random direction. Do the 5 way check for the random picked direction, and if it can move there, it will add that tile to the array. If the check fails, then try another direction and so on. If the tile gets stuck, we simply loop trough all the tiles to try to see if we can find a tile where we can move.

In this case I chose “randomly” to check if we can go South, and as you can see we can move South. Orange is the tile you are checking if you can move to, and the yellow ones also need to be free to be able to move there. Now remember, out of bounds is only for the orange tile, the one you are trying to move to.

 

 

So just to see how it looks when I “randomly” try to go east and there are no out of bound tiles in the check. As you can see, we can safely move East.

 

 

This is where the 5 way check does its job. Lets imagine after previously going east, that we now try to go North.  There are 2 yellow tiles that are out of bounds, but you can now see that a previously tile (x : 0 y : 0) in the array blocks us from trying to go North. So we have to pick another direction.

 

 

So we “randomly” picked to go east again, all tiles check out, and we can move east.

 

 

Just two more examples to get the point in. We “randomly” go south, tiles check out, so we are free to move there.

 

 

And final example, again to show where the 5 tile check does its job. After we previously went South, we try to go West. As you can see the 5 tile check figures out that there are already 2 tiles that denies this move. x : 0 y : 1 and x : 1  y : 1.

 

 

Conclusion ….

After attaching this logic together in blueprints. I finally achieved the result I hoped for. It still doesn’t end up at the X4 Y0 every time, but I will deal with that later. It doesn’t branch either. In part II we will look at the blueprints for creating this.

 

Voila