Map Generation
==============

The first question that popped to my mind after I decided to
make a roguelike was: how do I generate random levels?
The fact that my first question was NOT about gameplay shows
that I'm no game designer, and that's fine: I'm not, really :)

The goal for me was to come up with an algorithm that was both
good enough in terms of output and fast/with low memory consumption,
since it needs to be run by a 0.9Mhz processor.

I decided to use a cellular automata algorithm, which is well documented
and can generate cave systems pretty easily: right now, levels
can be generated in less than 30 seconds on the Commodore 64.

The problem with the cellular automata is that there is no guarantee
that the cave system will be fully connected: we might end up with isles
of floor tiles, not connected to the rest of the map.
At the beginning, I thought that maybe I didn't need the area to be fully
connected: maybe it would be a good idea to allow the player to did tunnels,
the same way Spelunky allows players to destroy walls.
However, in the end, I realized that allowing digging comes with its set of
problems:
 * You need to give the player some indication where it's worth digging,
   otherwise it's just boring.
 * Pacing: I want my game to be not too slow and forcing the player to dig
   tunnels doesn't fit the bill.
After realizing that I didn't want the players to dig in the map,
I had to come up with an algorithm to connect separate isles together.
This was done by running a flood-fill to locate the isles and then digging
corridors to connect them.

Finally, I added some unit test to test the basic blocks of the algorithms

In a way, I feel I approached this part in the wrong way. Normally, first you
figure it out what kind of gameplay you want, and then you create a
level generation algorithm that can support that kind of gameplay.
Instead, I did the other way around: I created the maps first and now the
question was: what kind of game can we do in these levels?
The answer to this question is that I want to have a combat system that is
mostly melee based. The player needs to balance the need of get surrounded
in order to unleash powerful AOE skills and the need to stay alive but not
being entirely swarmed. Since maps have almost no chocking points, the
player can't just find a safe spot and kill enemies one by one.