Map generation #4

#4? Where’d #3 go? Post #3 would be useless because, from where I finished at #2, I’ve completely rebuilt the code in a separate file. Refactoring, joy.

Last time I posted, I had an algorithm that was reasonably good at generating a network of hallways. I don’t think I have any screenshots, but with some edits to the tileset, you can get some really wacky maps generated out of it, one of which could work as a ruined set of roads that I might save later, though I don’t have a picture of it. I’ll probably stash away that code file for later.

Put simply, most of the previous code followed this basic pattern:
make a matrix, and randomly assign an index to it, with the index corresponding to a certain image of a predef.
afterwards, go through and check each matrix cell for connections between predefs that should be there, and connect them.

The important part about it was that each index was a binary number from 0001 -> 1111. When you introduce in rooms, however, that scheme needs to be so modified that my “randomly do it and fix it later” approach fell to the ground. Not only do you have connections for 0 and 1 (nothing and hallway), you’ve got 2, 3, and 4 (room lower, room upper, room filled), and so the numbers just get rather large when trying to do it the old way. What I’ve got now, looks like this:

make a matrix of zeros
set the corner tiles to something that does not leave the grid and has 2 connections going inside
for each tile in the top row:
  pick a tile whose connection type (0,1,2,3,4) on the left of the tile matches that of the left tile's right side
for each tile in the left column:
  [repeat, checking upper tile instead of left tile]
for each tile inside the bounds of the matrix:
  [again repeat, checking upper and left tile's connections so they match up]
for each tile on the bottom row:
  [repeat, checking left tile, upper tile]

and so on, until the matrix has been filled, then draw the appropriate tiles to the screen in the right positions. So, instead of doing it all and checking it later, we’re immediately putting in a tile that is known to fit the previously known connections. What really delayed me was that the corners, top, left, right, bottom, and inside all check for different things–the top tiles have to set themselves to be a good tile who’s top is a 0 and left matches the adjacent tile; the inside tiles have to check the left tile and the top tile; the bottom row has to have a bottom of 0, match the top, and match the left tile, and so forth. As a result there wasn’t a very easy way for me to take all four of those action and combine them into one thing.

What’s the result now? Here are some shots of the same code, but with edits to the tileset.png part:

Option 1: Plain tiles
plain map
Option 2: Walls
wall map generation
Option 3: Tile edit 1
curvy map generation
Option 4: Tile edit 2
crumbling map generation

There’s a few glitches in part because sometimes, it’s impossible to connect the right tile–that combination just can’t exist, so you get a few gaps there when defining say, the walls in that second picture in the bottom right–optimally all the white should be outlined by red. Eventually I might fix that, either by adding in those “impossible tiles” into the set or something else, though that’ll be saved for later. I’ll also have to re-check the code once more to see if there isnt just a simple glitch that’s getting in the way, too.

Regardless, the results themselves look nice to me. I have coded in place a way to (somewhat painstakingly) add in additional tiles. Compared to the generator that gave me the idea, if you select only Dungeon 1 tiles, the results are pretty close. If I want to change the distribution and say, add more hallways than rooms to a map, I could always add in additional hallway predefs, so that the random.choice will be more inclined to pick hallway connections than room connections. Likewise, the pictures above show how altering a few of the ~40 or so tiles can make the map look significantly different.

Where will this little thing go next? I probably won’t bother spending a post writing about it, but pygame has a surfarray subsection to the module that lets me convert pixels on an image into a numpy matrix. From there it’s rather trivial to integrate what I’ve got into the standard set of code I’ve got and get it playable.

Code of this and the dialogue system will be up on my other site..eventually.


Map generation #2

Alright, so where were we? Right, we had that ugly looking “almost looks like a somewhat broken maze” kind of thing, that looked like this:
map attempt 1

And there were a few issues with it. The first is that we had a lot of non-connected tiles. My first gut instinct was to just remove the dead ends at the tilesheet image–which, I may not have mentioned, is just a 90×6 image, and every 6×6 ‘box’ of pixels represents a particular connection–ends, T junctions, etc. The first four of these are the dead-end connections. To remove them, I first tried doing just that: taking the T junctions and just copy/pasting over the dead ends with them, I get this:
covering up connections

Better, but it still looks a little off. The problem now is that we’ve got ‘islands’ of connected segments, and it looks a little weird. After some staring blankly at the screen, the I decided to fix this I’d have to actually work with code, specifically, this code:

def checkAdjacent(array,row,col):
  New = 0
  current = array[row,col] #current type is a numpy.int32, not plain old python int
  current = '%04d' % int(bin(current)[2:]) #net result is a 4 digit binary string
  #pull out the 4 digit binary string from each adjacent tile
  try: top = '%04d' % int(bin(array[row-6,col])[2:])
  except IndexError: top = None

  #check if adjacent tile 'wants' to connect
  if str(left)[2]=='1' or current[0] == '1':New+=8#;print "catch right"
  if str(top)[3]=='1' or current[0] == '1':New+=4#;print "catch bottom"

return New

Sooo, what does this all do? Put simply, it scans through the matrix and changes predefs so that they appear joined by changing one of the 0's in the four bit long number to a 1 to match the adjacent predef. To explain further:

First, I'll note that I added some redundant code that could (should?) have gone into a function and made this thing about 4 times smaller; I just left out the redundant parts where it checks the other 3 directions for both cases.

The first bit of code is where the function takes the current cell in an array (defined as array[row,col]), and using the line '%04d' % int(bin(number)[2:]) converts a "numpy int" (NOT a regular int, oddly) into a binary number that is then sliced and padded and converted into a string all at once and formatted. Long story short, it takes a number like 6, and turns it into a string of "0110". Then, we do that for the cell found to the left, right, bottom, and top of the current cell (top is the only operation shown). Try/Except syntax lets me fudge it so that if I try to get a bad index it just doesn't go through, instead of quitting with an IndexError.

Once we do that, we enter the second part of the function, where what happens is that we are effectively OR'ing the value of "current" in binary with the corresponding digit of each adjacent tile, and that result is fed into the int New by adding binary's significant figures accordingly (8=1000, 4=0100, etc). This is where the cells are actually coordinated into being joined. Outside of the function, the value of 'current' is then replaced with that of New when the function is called.

Now we simply call that function on every cell in the matrix, and what happens is this:
fixed connections

...well that's a little different. Something I didn't mention was that along the way is that I've been fudging the dimensions a little, now I'm up to 6x6 pixel sets of predefs and everything is bigger. Regardless, I'm closer to making a reasonable'ish network of hallways, but now the opposite problem is happening than before: the map is now just a plain old grid and is too connected, and that's not interesting. So how about we add a condition that predefs are joined only, say, 50% of the time? Well we do that, and end up with:


It looks a little better. There seem to be definite sections of hallways, and I can almost see where rooms could be set via those grids. Looking back at that online dungeon map generator, I've noticed 2 distinct types of connections: hallway connections, and room connections. I'm not sure where I'm going with this at this point, but if I make more headway with this and find a way to reasonably explain it, I'll post next about getting rooms in here.

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.

And now for something different.

I definitely haven’t had the time to work in anything into the code lately due to some rather..distracting health issues that should be resolved soon, and with classes starting in a week my free time will soon disappear; this and a few other things mean my interest is again waning on turning Graff from “generic project” to “original game”.

That said, I plan on still making some posts about some things. I mentioned before about trying to encapsulate some features in a self-contained “bubble” that could then be inserted into Graff as a whole at a later date–I’ve talked enough of dialogue systems, and I’ve got an idea I’m currently kicking around my head to work on some new map algorithms that could be done in this way, as well as a few other ideas I might try. What I’ve got noted down as things I should be working on don’t seem like things I could encapsulate all that well, so what I have planned for the next update probably won’t look anything like what I actually put up, but either way, if anything comes of it, I’ll be posting about it. 🙂

Random notes

Note 1. I’m pretty sure WP’s blog stats don’t tell me when someone visits the front page, only when they visit a certain article. How odd.

Note 2. A great part about trying to work on an overly ambitious thing like a game means you get lots of ways to distract yourself by working on another part of the code. In this particular case, I don’t really feel too much like working directly on the program but still want to feel productive, so when that happens I usually make a “bubble” of a feature–that is, something that can be self-contained and implemented outside of the actual Graff folder, and moved in later. Map generation, text, cfg parsing, and a few other things were first implemented that way previously, and that bit of obfuscation will have begun that way as well.

In this case, I’ve worked out a suitable way for getting dialogue done. Currently it runs through the terminal (print statements and so on), but I have a framework that works. It’s not that complicated to describe so I won’t go too far into detail, but I have a file whose structure is like this:

<NPC text>1 2 3

and repeat for each statement/response. is for NPC text, [] is for player response text, and numbers point to the lines in which the response can be found in the file. Then, one can simply open(file), and say X = file.readlines(), and then (with some Str.split() and slicing), one can extract a certain line of text with just a call of Str[line #].

The problems are, first, the file becomes cumbersome after enough dialogue, but I’m not expecting to make a Planescape: Torment-sized set of dialogue so that shouldn’t be an issue. Second, editing is always cumbersome: if, say I want to add in a response I need to go over every number in the file and change them accordingly, or add the response at the end of the file, at which point things just get rather messy. I can hopefully mitigate this by just limiting the amount of dialogue; next release will include a sample NPC to talk to (hopefully) that might show the extent of the talking going on in this game. Third, memory could theoretically become an issue later on, again if the dialogue gets too big.

Note 3. Hot weather with no air conditioning = Hard to think. Eugh.

Note 4: I’ll upload the dialogue tree example when I release 0.0.8–or maybe before that if I call it release 0.1.0 depending on how much I get done by then.

A word on obfuscation.

One of the issues I have with python, even though this particular issue becomes helpful at times, is the lack of compiling going on. To make a program it’s a matter of grabbing the .py files, running them, and off you go. On the other hand, when working with such open code like that, cheating tends to be a bit of an issue. Why bother with levelling up a character to take down a creature Y, if all you have to do is open up the configs and take a few significant figures off of the creature’s health stat?

Now obviously there’s no such thing as an unbreakable code, and I don’t want to discourage modification of my code–if someone wants to give themselves God Mode at the start for some reason, then go for it, but it would be nice if there were a way to make sure that, if a player gets a high score, the game knows to not include that run in the scoring table because he or she cheated. Cheating itself I’m fine with, but if I can I’d like to discourage circumventing the game’s logic that ensures a fair playthrough was, in fact, a fair one.

Looking around, there seems to be a few different ways to combat cheating of this sort with a language like python.

The first is to hand out only the .pyc files. As far as I can tell, they function exactly the same as .py files, but they’re unreadable unless if decompiled. However, I plan on releasing the source anyway (as I have been), and it’s trivial to just replace the .pyc files with .py ones and make changes there. And I don’t want to hide code from people, at least in such a blunt way.

Option two, is the use obfuscation. Python has a nice little function called “lambda“, that can be used to allow one to repeatedly nest a function inside a function, and the net result is it gets really hard to read after a short while. A quick example:

“lambda [variables]: [formula] (optional input if not being assigned to a variable)” is the general syntax, with the result of formula being returned. An equivalent def statement would be something like “def lambda(variables): return formula”.

So, if we wanted to make a lambda function that would return a value of 2*input, we’d have:
“val = lambda x: 2*x”
Then you could just call val(5) and it would return a value of 10. Where does obfuscation come into play?
“val = (lambda x: 2*(lambda y: y)(x))
val(5) will still return 10, but I replaced the second “x” with “lambda y: y”. In other words, I nested another inline function that simply returns the input asis, and that returned input is then multiplied by 2.

for added fun, one can assign extra dummy variables:
“val = (lambda x,a=1,b=3: 2*(lambda y:y)(x))”

then, say, instead of “a = 1” I could’ve written “a = lambda c: c (1)” and still get the same result, and then the code looks like:
“val = (lambda x,a=(lambda c:c(1)),b=3: 2*(lambda y:y)(x))”

what if we wanted to return 4*input? We can take the y:y and inline inside of that the previous line:
“val = (lambda x,a=(lambda c:c(1)),b=3: 2*(lambda y:((lambda x,a=(lambda c:c(1)),b=3: 2*(lambda y:y)(x)))(x))(x))”

and so on. A few other functions like map() can also be used within lambdas to make things even more confusing and throw in arrays.

So what’d be the point? If I, for example, added in a calculation that checks to make sure the .py files are original via a hash, it’d be very simple for the player to just change wherever I put “if baseFileHash == calculatedFileHash” to “if basefile == basefile” and as a result allow the player to, for example have a high score at the end. But if I’ve got the comparison split across a gigantic nested lambda in various places, well then if the player’s going to cheat to make the game think it’s a legitimate playthrough, he’s at least going to have to work for it.

That and intentionally trying to make working yet incomprehensible python code is in some ways pretty fun, hah.

Still alive here.

For the time being, that is, what with college looming and all. Got a fancy title screen implemented in Graff, and by fancy, I mean it’s a plain blank page with the text “[S]tart [K]eybinding [Q]uit” on it. I’m thinking eventually I’ll try to make up some little ascii art thing to give the title page something worth looking at, but what’s somewhat more important about the title page is now… I have a title screen!

As a person mentioned to me, on a laptop you can’t really use this thing because of a lack of a numpad. I’ve rectified that now by setting it up so that, before the program runs, you can press K at which point it’ll run through the 10 or so keys to bind. Once you’re done, you can press S to go right into the main game, using those newly bound keys. In addition I’ve made it so the keys are saved to a file via ConfigParser–as a result, technically it is human-readable, though keys are listed as numbers (up = 97, etc). The idea is that when I feel the need to create an options menu, one could either edit the options in the game, or they can pull up the .ini and play with the options there, too.

Funny thing, too. Raw python seems to not have a way of capturing numpad inputs (and differentiate them from the regular keyboard keys), at least with the raw_input() method. That tripped me up for a bit since I was hoping to implement this title screen in the terminal, but no big deal. There’s probably a package somewhere that fixes this, but the fewer external dependencies I have, the better.

My list tells me that the next things I’ll be working on will be inventory systems. Following that, NPCs and shops. Fun fun. I should probably toy with equipment first, though. If I remember right my armor system needed to be retooled a bit.