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.
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.
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.
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.