Map generation #1

And suddenly my interest peaks again. o_O

In the previous post, when I say I had an idea kicking around my head, what really peaked my interest was this random dungeon generator. I made an earlier post about using some kind of predefined style sets to generate rooms, and in the above link, whoever made that generator really did almost exactly what I was talking (or at least thinking) about, and that has given me some ideas of how to make a dungeon map in a somewhat clever way. Looking at what it does, there doesn’t seem to be much overall sense in how the map gets built, but considering it’s normal to have exploding barrels in dungeons that hardly ever make sense in video games, I don’t see this as a problem.

Unlike some map generators, this one doesn’t seem to have a source out in the open so I can’t directly look at it and adapt it to python, but either way that would be cheating and that’s no fun. But, having maps that look as wild and varied as that would be fun, so I figured why not try to make a generator that makes similar maps?

Here’s what I was able to get from it: The algorithm itself, at the most basic level, has predefined tile pieces (to be called predefs from here on), apparently taken from a rather good looking set of commercial tiles for D&D players. These predefs are then randomly chosen and placed down at will on a grid of up to 14×30 of these predefs. Looking at each piece, it looks like they themselves are made up of different edits to a 6×6 grid of smaller tiles. Also, each predef has connection points to any of its four edges, with as few as one connection (a dead end), or as many as all 4 edges (a + junction or room square). If we look at the actual dimensions of the predefs, we have 14*6×30*6, or 84×180 total individual tiles. Scaling this back to what would be my map size of ~70×70, you’d have 70/6×70/6, or roughly 12×12 predefs required to make a map of equivalent size in Graff.

What does this mean? If I wanted to make a map using predefined tile pieces, with dead ends, circles, hallways, T junctions, + junctions, what have you, the algorithm itself only needs to work on a 12×12 array to make a 70×70 map. Even better, let’s say we want to make these predefs ourselves, you only need 15 of them minimum. Why 15? If we, in this 12×12 array of predefs (or, 72×72 array of individual tiles), assign each entry to be a binary value from 00012 to 11112, each digit represents a certain side, and a 1 represents a connection and a 0 represents no connection. 00002 would be a blank space, but I’m not going to include that. Arbitrarily I will say the order goes like so: Left-Up-Right-Down, so a 01012 would correspond to a predef that is a vertical hallway, a T junction would be 10112, etc.

At this point, the problem is looking more like a simple math problem than something that’s actually really complex. From this, here’s some really basic pseudocode to generate a map randomly:

create 12x12 blank array1
for each tile in array1:
       tile = random value between 00012 and 11112

open up tilesheet and create an array2 of length 14 for each predef
for every X/Y pixels on the screen:
       blit image from array2 using corresponding index value of array1
refresh and draw the screen, scale the image for clarity

So all I’m really doing at this point is every 6 pixels I’m picking a random predef and putting it on the screen, with there being 14 total predefs that correspond to every possible connection a 4-sided object can have. Then I go over a number of pixels, and repeat, all according to what Array1 looks like. What’s the result?

map attempt 1

Pretty ugly. Black = floor tiles, white = unwalkable. There’s one minor display glitch in here that I’ve since fixed, but regardless you get the general idea. There are far too many ‘islands’ of halls, and another problem with it is that it looks like there are no rooms, just halls. A future post will continue this topic, as this post has gotten far too long. Hopefully that wasn’t too confusing.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: