So, one of the things I've been toying with recently is the idea of a Diablo-style hack & slash. One of the most important aspects of the hack & slash is level generation. There's lots of ways you can generate levels and lots of different "looks" you can give your levels. I plan to explore a few different techniques over the next few weeks. My first attempt, which I've included below, gives a sort of cavernous look that I think would be good for boss levels:
The technique is quite simple, I "borrowed" the idea from this page. Basically, the algorithm runs as:
- Fill the board with random walls. Each square starts with a 45% chance of being filled.
- Each iteration, for each square, count the number of walls around that square. If there is more than 5, fill the wall in a new version of the map.
- Repeat step 2 until the map is "stable" (that is, until two iterations produce the same map).
In the example above, you just let it run normally, it'll do a few iterations, then complete the run in one go and pause for a few seconds so you can see the outcome. You can click "stop" then use the "reset" and "step" buttons to manually progress through the iterations.
There's a couple of problems with this, though. Firstly, it tends to make very open levels. I guess depending on the game, that may or may not be OK, but for our purposes, I think I'd like something a little more close-quarters. Another problem is that it produces overly "smooth" walls, that is, there are no sharp corners and no sharp points. Again, depending on your level design, that may or may not be OK, but I'd like to do something about it.
For the second problem, the solution is actually quite simple: just don't run the algorithm so many times. If we cap the number of iterations to, say, 10, then we end up with more jagged walls. But that introduces an extra problem: sometimes it will leave behind very tiny "islands" of walls, which the old alorithm would have smoothed away. That can be fixed by a "manual" cleanup afterward where we simply remove the small islands.
For the first problem, we modify the algorithm slightly:
Map.prototype.iterate = function() {
var newMap = new Map(this.width, this.height);
newMap.clearMap();
for (var x = 0; x < this.width; x++) {
for (var y = 0; y < this.height; y++) {
if (this.numWallsWithinSteps(x, y, 1) >= 5) {
newMap.setCell(x, y, 1);
} else if (this.stepNo < 6 && this.numWallsWithinSteps(x, y, 2) < 2) {
newMap.setCell(x, y, 1);
}
}
}
newMap.stepNo = this.stepNo + 1;
return newMap;
};The above algorithm can be seen in the map below:
As you can see, this version results in much more "cramped" level than the first version. You can download the full code for the final version here.
This is a pretty simple algorithm and produces nice levels for boss fights, but next time, we'll want to try a slightly more complicated algorithm for generating the room/corridor style levels that you come to expect.