Bandits to the left of me, Goblins to the right. My Python CRPG engine can now randomly populate its dungeon rooms – but I may have gotten a little carried away!

After talking about my “Roguesque” game engine last week, I meant to move on to some other projects, but it’s been hard to stop tinkering with it.  One of the advantages of using a language as expressive as Python, and working on the early prototype stages of a project like this, is that it’s really easy to pick small chunks of work to do.  I’ve been picking away at it in half-hour or hour free spots in my schedule, and really enjoying the process.

For example, I’ve tried a couple different variations of implementing the “Fog of War” – in this case, hiding the parts of the dungeon that the character hasn’t visited yet.  In NetHack, as you wander through passages, only the square you move into is revealed.  When you enter a room, the entire rectangular room becomes visible at once.  I started with a similar method, except I revealed a little more of the surrounding area in the passages.  I implemented the fog of war using bitwise logic, since I hadn’t done any of that in Python.  My map is a 2-dimensional list of integers, so I figured I could use the bottom 8 bits as a tile identifier (e.g. wall, floor, dirt, water) and the top 8 bits for extra information (1 bit for fog of war, maybe a few more to store the room number a square is in, and so on).  I’m not limited to 16-bit numbers, of course, but I’m playing with ideas that I could transplant to other (8-bit?) systems.

I also tried a Fog of War technique that cleared a circular area with a 2-square radius around the character, because it gave me a chance to play with Python’s generators.  Generators are a kind of coroutine (if you’re familiar with the CS jargon).  A generator is a little bit like an iterator – it’s a function that, once called, can “yield” a series of values.  For example, this generator returns the coordinates of squares in a 2-square circle around the (x,y) position passed to it, while filtering out values that are off the edge of the map:

    def Adjacent2Squares (self,x,y):
        """ Generator that iterates over the squares adjacent to x,y
        (including (x,y) itself) that are valid map coordinates."""
        adj = [(-1,-1),(0,-1),(1,-1),(-1,0),(0,0),(1,0),(-1,1),(0,1),
	       (1,1),(-2,-1),(-2,0),(-2,1),(2,-1),(2,0),(2,1),(-1,-2),
	       (0,-2),(1,-2),(-1,2),(0,2),(1,2)]
        for (x1,y1) in adj:
            if (x+x1) in range (0, self.width) and 
               (y+y1) in range (0, self.height):
                yield (x+x1,y+y1)

Coroutines are an interesting kind of construct that don’t get a lot of attention because they’re hard to implement well in languages like C.  This one can be used in a for loop like “for (x,y) in map.Adjacent2Squares(player.x,player.y):”.  When Adjacent2Squares() is called, it runs until it hits the “yield” statement, and then it’s suspended.  The next time through the for loop, execution of Adjacent2Squares() picks up exactly where it left off until the next yield, and so on.

While I was working on the Fog of War, and starting to think about how to automatically populate my dungeon with monsters and traps, I realized that my concept of rooms needed some refinement.  My map-generation routine allows rectangular rooms to overlap, creating interesting shapes, but doesn’t keep track of that in a useful way.

Rooms are made of overlapping rectangles. This room has unexplored exits on the left and right.

I decided to redefine my rooms to be lists of rectangular areas.  When building the map, each time I create a rectangle I check if it overlaps with any rectangle of any existing room.  If it does, I add it to that room, and if not, I create a new room.  With this data structure, I can quickly check if an (x,y) map coordinate is inside a room by checking if it’s inside any individual rectangle.  I can select a reasonably random point within a room by randomly picking x and y coordinates inside a random rectangular area (yeah, that favors squares where areas overlap, but that’s not necessarily a bad thing).

To implement this stuff, I had to write a set of functions for “contains” and “overlaps”.  I only realized afterwards that I could have saved a few lines of code by using PyGame’s Rect class – oops!  I broke one of the cardinal rules of lazy programmers: always let your libraries do the heavy lifting!

Now that my map structure had a better understanding of how its rooms were shaped, I was able to look into randomly populating those rooms.  I wanted to do this in a “data-driven” way.  For example, all the information about different kinds of monsters is currently stored in a Python dictionary:

monster_db = {"goblin": {"hp":12, "ac":8, "graphic_name":"goblin.png"},
"troll": {"hp":18, "ac":12, "graphic_name":"troll.png"},
"bandit": {"hp":4, "ac":8, "graphic_name":"bandit.png"},
}

All monsters use the same class; they just fill in different data.  I wanted to do something similar for the room contents.  Each room could have a randomly selected flavor, like so:

room_types = {"goblin_room":[("goblin",1,5),("troll",0,1)],
"empty_room":[],
"bandit_room":[("bandit",2,6)]
}

You can read that as “a goblin room contains between 1 and 5 goblins and sometimes 1 troll, while a bandit room contains between 2 and 6 bandits”.   To populate a dungeon level, we just select a type for each room, and then fill in the contents according to the list.  This could be expanded to include furnishings, traps, and so on.  This is a great example of how easy Python makes it to express these kinds of ideas.

Of course, in a “real” game engine, those tables wouldn’t be hardcoded – they’d be read out of a file or database.  Well, maybe I’ll get to that later.

Speaking of objects, I’ve been thinking about how to represent all the stuff you might find down in a dungeon (monsters being just one example).  There are lots of ways to do this.  I’ve tried big class hierarchies and different kinds of object composition in C++ before.  Python gurus seem to be fond of duck-typing solutions, so that’s where I’m going.  For example, anything with hit points and an armor class can be attacked, anything with a “climb” method can be climbed, and so on.  I’m playing with ways of implementing that, and using Python’s reflection capabilities to keep it all as data-driven as possible.  I may write another post on that topic when it’s more fully developed.

Right now, though, it’s time to take a break from writing games to play some games.  I’ve been slowly trying to rebuild the collection of computer games I had as a kid, and the latest one just arrived courtesy of eBay.  Questron II wasn’t exactly ground-breaking, but I remember it being fun.  We’ll have to see how it holds up.

Amiga version.   Hmm….

After a hard day’s coding, it’s time to kick back with some retro-gaming. I just need to figure out how to run this thing…

The most basic element of a CRPG: hitting a goblin with a sword.

It’s been a strange week.  I’ve been to a concert and a wedding, I’ve sold CDs to an eager throng, I’ve reconnected with some old friends, and, like a lot of people, I’ve watched far more CNN over the past few days than can possibly be healthy.

Somewhere among all that other stuff, I found some time to write some code.

When I’m learning a new programming language or UI library, I like to write little toy game engines to try things out.  I’ll warn you now: these things usually get half-finished and then abandoned, and I’m okay with that.  It’s really more about what I learn in the process.

For Python, I wanted to do something meatier than the Life program I made last month.  I’ve been thinking about engines for CRPGs a little bit, probably because of some of the Kickstarters that I’ve backed lately.  A lot of that thinking so far has been in the context of C64 programming, but I thought Python might be a good fast way to prototype some ideas that’d take much longer to put together in 6502 assembly.

As for learning Python, there are a few goals with this project.  One is simply to get more comfortable with the syntax – I keep leaving off colons at the ends of statements and writing my for loops in C style.  Beyond the syntax, there’s the stylistic differences of the language and its philosophy.  A lot of what I’m writing looks like C transliterated into Python, so it’s good to explore more “Pythony” ways of expressing ideas.  And beyond that there’s the library – both learning particular features like, say, the random number generator, and learning where to find things and how to use the built-in documentation (which is quite good).

My touchstone for CRPG design has always been the Ultima series, from which I grabbed a few images to use for monsters and heroes.  This time around, I decided to start with the most dead-simple monster and combat system I could (as opposed to the last time I did something like this, and I got bogged down in representing a complicated damage and resistances system inspired by 3rd edition Dungeons & Dragons).  In this case, I wanted nothing more complex than for my character to wander around the screen, bashing monsters until they run out of hit points.

The monsters, still lacking any sort of AI, just stand there and take it, which makes for a pretty boring game.  But the point was to be able to add and remove “actors” from the screen, and monitor input and detect collisions and so forth.  It is kind of neat (and very Pythony) to be able to search through the array of monsters with a single statement:

return [m for m in monsters if m.x == x and m.y == y]

Before getting into the AI, I figured it was time to create a map.  That would make things more interesting than just wandering around a featureless black plain.  I was going to just make a quick parser to read in a static map file, but then another part of the problem caught my fancy.  I started thinking about “Roguelike” games, such as NetHack and, well, Rogue.  One of the features of these games is a randomly-generated series of dungeon levels.  The typical level is a group of rectangular rooms connected by passageways.

How do you create a random map like that and make sure it works?  And what I mean by works, for now, is that you can actually navigate from wherever you start to every other part of the map.  If the stairs down to the next level are in a completely detached section from the player’s starting position, that’s going to be… very frustrating, right?  So how do you randomly generate a set of rooms with connecting passages that let you get from one room to another, and how do you make the automatically generated maps interesting?

Of course, a game like NetHack is open source, so I could have just looked up its algorithm to see how it works.  But where’s the fun in that?  I’d rather try out a few ideas of my own first, and then see how they compare.  I figured there were two routes I could go: either I could create a set of rooms, and then generate passages to connect them; or I could generate an interconnected set of passages, and then attach rooms to them.

I suspect Rogue itself goes rooms-first, while NetHack is less obvious.  The passages-first idea interested me, so I started there.  I figured I could generate passageways using a kind of random walk.  A random walk is a way of traversing a grid where, at every intersection, you randomly choose which direction to go.  I switched things up a little by walking a random number of squares before making the next direction choice.  That gave me something that looked more like “dungeon hallways” than a regular random walk, which would tend to create “clumps” of visited squares.

An early attempt at interconnected passageways. A little too “boxy” for my tastes.

I very quickly had something that at least technically worked, in that it gave me a pattern of interconnected passages that I could attach rooms to.  But my first attempts weren’t very pleasing to me aesthetically:  they didn’t “feel” like dungeon passages.

Some of my early attempts generated too regular grids of passages – I tended to have passages stretching all the way across the map, reminiscent of city blocks.  I tried changing both the total length of passage I created and the maximum length of straight sections, using trial and error to find a sweet spot between city streets and “a maze of twisty little passages, all alike”.  Eventually I made the distance range for choosing directions proportional to the distance to the map edge in the direction traveled, though there’s probably still room for a better heuristic.

The more interesting results after applying some heuristics.

Another problem with the passages was that they tended to hug the edges of the map.  Once the random walk hit the edge, two of the three available directions were parallel to it.  I added a special case near the map edges that forced the walk to move away from the edge (though it might be better to allow it to parallel the edge for a short space before turning away).

I eventually had something I felt was “good enough”, though I’d still like to add some more irregularity and an idea of diagonal passageways to it.

My plan for adding rooms was to randomly select a handful of squares along the passageways that would be the “seeds” for rooms.  Then I’d generate a random rectangular size for each room, with openings in the walls wherever they touched a passageway.  Eventually, I’ll want to add doors and secret doors to some of those openings.

A dungeon with rooms added. I like the effect of the overlapping rectangles.

For now, I’m letting rooms overlap.  This results in occasional irregularly-shaped rooms, which I find appealing.  The next step would be to stock the dungeon with monsters, traps, and treasures.  One idea I have is to randomly choose a personality for each room, which would imply a particular list of monsters and features to choose from.  We’ll have to see if overlapping causes a problem there.

I’m still impressed with how quick and easy the Python development for these projects has been.  However, I still haven’t decided how long to continue this project on this particular platform.  I might have to dust off some of the other toy game engines I’ve done and compare them, and decide which programming bug to scratch next.