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.

Continuing With Dart

I have now written around 1000 lines of Dart and am starting to get a feel for the language.

Programming in Dart is pretty easy. If you know Java/Javascript/C# (probably) then Dart feels like second nature within an hour or so of coding. More and more these days I feel a programming language should get out of your way. That is be small and easy to remember. If you have to pick up a book/documentation to remember how to do something in the core language then, in my opinion, that is a fail for language designer (Yes C++ I am looking at you). Note: everyone usually needs to look up API calls they don't regularly use I really mean core language here.

I have written a few examples using the HTML5 canvas and having auto completion on the context helps compared with doing the same in JavaScript. Yes after a few examples it was starting to stick into my head.

I don't want to give you a glowing view on Dart it is early days yet and I do have some gripes.

When hacking on small scripts I would like to be able to create inner classes. It is a small thing but it helps keep me in the flow. I am sure many would argue it is not the best form of encapsulation. For me it is a form of encapsulation that is useful when working on small scripts (that are growing). I don't want to break my flow and start a refactor of classes into separate files but I do want to ensure that a certain class is only visible inside another class to ensure things don't get too tangled up before the inevitable refactor happens.

I may have missed it but there the supplied libraries need fleshing out. How do I shuffle an array of objects and stuff like that. With Dart at V0.04 at the time of writing I am expecting this sort of thing to be missing. The really important stuff is there. In some way I am wishing Dart was a year to two further along the development path.

This one is not a gripe. Operator overloading is wonderful. If ever there was a feature that should be in more programming languages this is it. Coming from C++ not being able to overload the plus(+) for vectors in languages like Java and JavaScript just feels awkward at best. Even having to use myvector.get(idx) instead of myvector[idx] often feel odd to me. I am sure if you have grown up with this stuff operator overloading can feel odd or dangerous and just not needed. You can get carried away with operator overloading but most people don't and most use it in sensible ways.

I would like the IDE to gain one important feature. I would like it to check and download updates for itself. I missed one revision of the IDE. Sure the changes are minimal and you could make the automatic updating optional but I would like to not have to worry about manually checking for updates.

My biggest complaint so far is the size of the Javascript output by the Dart to JS compiler. At 6.5MB for a hello world it is too big. Google have given use a new language to play with so lets those that are playing share the stuff they have made without eating up tons of bandwidth.

The other night I created a simple little game about making squares disappear. It is simple but took about 2hrs to make including designing 18 levels. A nice evening hack and given a couple more evening of coding I could make it into a presentable little, simple game. At 6.5Mb I don't plan on uploading it for other to play any time soon.

In my opinion this large file size should be a top priority even at this early stage, people want to show what they have been making and that is a barrier to it. They say they plan on fixing it but the sooner the better.

On the whole I am quite happy with Dart. It is easy to focus on the negatives part but for now I plan on continuing to write some code and getting to know it a little better.

Early Nov 11 Update

Another small update....

It has been a bit of a strange few weeks as much of my time has been consumed by family stuff. So my coding time has been fairly limited. I have also been jumping around a fair bit on topics.

I have taught myself a little bit of OpenGL, The modern type, I used to know some way back when using GLBegin and GLEnd were all the rage. I am happy that it all turns out to be quite simple. Not being scared of matrices and vectors probably helps this.

Days Until has had another little iteration. Nothing spectacular and I have squashed the final bug that was holding up a release. So that should be posted soon.

Finally I having been taking a look at Dart. The new language from google. I quite like it even though it is in a very early state. I only took a look when they released the first iteration of an IDE for it.

I don't understand why they have a stand alone IDE rather than a plugin for eclipse. It is obviously based on eclipse. Perhaps there is a plan for the IDE that involves doing stuff that you cannot do as a plug in. That is perhaps they need to alter the core in some way. I am not to worried about it either way. Being in an Alpha state it does not contain much in the way of features.

So how have I found Dart? As I said before I kind of like it. I think this is because if you know Java you kind of already now most of the language. Well except for lambda functions that Dart has which is a definite plus point. There are probably other features I could think off that would be cool to add but then that would add complexity to the language, at the moment it is quite simple.

A lot has been said about Dart's type system most not nice. I have used enough different languages to not really be concerned either way. I perfer to have types if possible but can see why people prefer to not have them. I suspect once the tooling for the language get there it could be a nice solution.

I have not looked at performance or deployment but I imagine both will be OK once they get a few iterations into the life of Dart.

I guess so far Dart gets a B+ in terms of my feeling about it. I like it but it's not yet amazing. I get the feeling it has the potential to be quite a productive language.  Time will tell I guess.