Simple Dungeon Generation

In my last post I talked a little bit about Maze/Dungeon generation. As I was typing out the post it became clear I needed some pictures. So this post is going to repeat a lot of what I said in the previous post but with pictures.

As a learn Dart project I decided maze generation would be a nice thing to fiddle with. To be honest it is not really a learn Dart more get a feel for whether I enjoy the optional typing and other features Dart provides. Dart is pretty easy to learn.

I started with a couple of algorithms that I picked up from Wikipedia. That is a depth first algorithm and Kruskals algorithm for maze generation. Wikipedia outlines these algorithms and I don't feel the need to explain them. Long story short mazes are generated and here are a couple of examples

Depth First Maze Generation Algorithm

Kruskals Maze Generation Algorithm

Yay! We have mazes. The little blue lines represent doors. I randomly place them in places where doors can be, that is cells with only two exits. The black dots are just the top left and bottom right. finally the yellow circle is the little player guy who can traverse the maze. Any way the important thing is Yay a maze!

Next up I wanted to carve out the maze to create caverns as they are way more interesting then mazes. Well depending on you point of view. I wrote an algorithm that works the rooms in the maze. A room is all the cells on the same side of a door. I then remove what I termed Dangling walls. That is a wall that can get from one side to the other by taking only 3 steps. I actually write the algorithm in an iterative way so I could gradually remove the wall if I wanted to. Here is how it looks

Hollowing Out The Rooms

Finally I want to do something to make the walls look a little less random. I to do that I wrote another algorithm that would look for cells in a room that only have one entrance/exit and give them to random neighbouring rooms. This actually work quite well, see the image below.

Trimming Cell That Stick Out (Where Possible)

For reference here is a picture before I trimmed the nodes, notice how a number of the rooms have been squared off a little bit. I don't move doors so there is a limit to the amount of squaring off I can do with this algorithm.

Original Maze Before Cell Trimming

Overall I am quite happy with the results. The caverns or rooms produced are not exactly the most awe inspiring designs but the are suitable for the next topic I wish to explore. More on that in a minute.

First some more thoughts on Dart. Dart still feels pretty nice to code in. Just recently the IDE gained the ability to optimise the Javascript produced so the output file is measure in Kb rather than Mb for the canonical hello world example. This means people can actually deploy some of their Dart experiments.

As a language it feels like coding at a slightly higher level than Java. It is comfortable and I rarely think about the actual language. I do tend to find myself putting in the types a reasonable bit most to get code completion to work in the IDE. I am quite happy to use var or say List instead of List and so on. I guess what I am saying is there is no problem in my mind in jumping between typed and untyped parts of my code. I certainly appreciate the arguments that types act as a form of documentation. 

The IDE is simple at best but functional and is productive to use. Give it another year an it should start to actually be pretty. At the moment there is not real debugging support so you are left printing to the console or trying to make sense of the outputted Javascript.

So far my bugs have been simple enough that printing to the console was all that I needed to do. I did use the JS profiler built into chrome as many of my algorithms are written to be simple and slow. Currently generating a maze takes a reasonable number of seconds. It is pretty easy to use the profiler and while the function names have been mangled a fair bit they are not beyond use.

So my next stage is speed up my maze generation with the aim of it taking less than a second on my laptop. Then I want to experiment with dungeon generation a little further by creating some algorithms that will lock doors and hide keys the player has to find to progress. Perhaps levers to pull and so on.