December 29, 2015 by jonmillymiles
Well that didn’t work. After succeeding with the Recursive Backtracker and noticing the speed of dungeon generation, I tried a more efficient “scan and place” methodology, but it didn’t go as I expected.
The premise is simple:
- Place a room
- Find a random tile adjacent to a tile
- Place a corridor or room.
- Goto 2
Sounds simple but there are a couple of things that need to be considered with this. Firstly, you do not know which direction your dungeon will go in, with the Recursive Backtracker we fill it, add the rooms and then trim it back. With this algorithm we could have five large rooms all in a single direction with interconnecting corridors. We need to overcome this problem.
Secondly the rooms or corridors need to be expanded perpendicular to the tile that is scanned and that is going to take a lot of code.
After working on the complexities of maze generation for the previous weeks, this new challenge had me stumped. I was temped to avoid it because it seemed so far removed from what I had already developed, however, it is a valid form of dungeon generation and one that could have some very interesting applications. In effect it works the way that a human would create a dungeon with a pen and paper. They make a start and see where it goes from there. But when coding this we cannot just add on another piece of paper, certainly if we need to test for overlapping: we need a common data structure to test. This is where I had a huge problem, not with the code, but with my mindset.
To date I have built all of the maps in a grid that is 21 x 21 tiles as this allows me to test variance with extremely short build times. I couldn’t think how I could write the code that would enable me to create long thin dungeons or equally proportioned dungeons from the same code. Then one night I had an epiphany… I just needed the biggest piece of paper I could find. So I changed my map size to 100 x 100 and that’s where the problems started.
There have been issues with Unreal Engine 4 and large arrays, I wasn’t aware of this at the time but my compile time for the blueprint slowed from five to ten seconds to closer to 5 minutes. That’s five minutes of not being able to do a thing with my project. Whats’ more, this was happening every time I changed a variable, added a function or deleted a function and it has made development infuriating. The psudocode for the algorithm is based simply on the sequence above, however to begin with I have only worked with placing rooms:
- Place a room
- Choose a random empty square within the boundaries of that room plus one square on each side.
- Place another room
- Re-size the boundaries to incorporate the new room
- Goto 2
Now getting this working over the past few weeks has been painful, but I did it. I can now place rooms, but they overlap. I therefore decided to include the code from the random room creation algorithm that I developed in Major Rework and this is where I have hit a hurdle: with the overlap detection activated, no rooms are built. This is a core requirement of building a map otherwise rooms can be built into and inside of other rooms and this can lead to game breaking errors.
And then there was an update – I’m not sure why, but for some reason my large array size for this Blueprint is no longer causing long delays. And so I am left having “wasted” three weeks of development time with pushing through delays and failing code.
Do I have enough time to push forward with this experiment??? I think that I will take a pass on this one – I have a working generator on a small scale, despite it being inefficient and there are other things that I really want to do to build in to create a random dungeon generator these are:
- Different types of rooms
- A start room
- An end room
- Spawned objects (gold, possibly monsters?)
- Walls would also be nice
- Keys, this would be fun if I can get it working.
So my plan is this:
- Get the walls in
- Get the different types of room generated
- Get the doors in
- Get the player in a start room and generate an end room with a message
- Spawn some objects
- See if I can get keys working
- If I have time, get the scan and place algorithm working.
After losing so much time on this phase, I really want to press ahead – I have no time for optimisation or new code at this moment.