Tuesday, 13 May 2008

a new Level Generation algorithm

I've mentioned Level Generation before, and I make no secret of the fact that I'm pretty dissatisfied with the current methods I use in Kharne. They're fine for certain types of levels, but there's really too many dead ends for them to be used for anything other than labyrinthine "twisty-turny"-themed levels:

So, as light relief from studying for my part-time Astrophysics Degree*, I've been messing about with a new level-generation system for "room and corridor" type of levels, based upon the one in Angband. I've been thinking along the same lines as Andrew Doull as to how to improve that algorithm, but those improvements will have to wait for now (a thousand thanks, Andrew, by the way, for some fantastic articles).

Here's an example of my version of the Angband algorithm in action, with a simple generated mini-level, using four rooms in fixed positions (yellow represents corridors, and red and blue are soft and hard room walls respectively):

Here's another. A bit messier, but still not too bad:

But it occasionally throws up weird levels:

My first explanation for this occasional weird behaviour was a bug I must have introduced during the rewrite from C to Object Pascal, but then I started up a fresh game of Vanilla Angband and noticed pretty much the same behaviour:

Pretty gross, eh? So I think I might have to introduce a directional weighting factor in the tunneling algorithm to stop the excess of tunneling. But for now, I'll get a basic version (without much of the metadata present in the Unangband versions

* The reason I mention this is that I'm intending to enter the next 7DRL challenge with a small Roguelike with a Quantum Mechanical theme (with a twist). Quantum Physics is actually rather fun, once you get your head around it. A bit like programming, in fact.


Dirk Kok said...

Have you thought of just placing a room at each dead-end?

You could introduce some variable which would determine how many dead-ends are allowed to manage this.

pbsl said...

thanks for sharing this site. you can download lots of ebook from here