Kist List

I got very nearly no programming done this week. And so I present to you a list of things I have seen that are “kist”:

• Sunkist
• Rainkist
• Snokist
• Magikist
• Lipkist
• Sugarkist

Seen any others?

Random offsets to streets, and not always connecting a built square to a neighbor:



The random offsets have to be unified to ensure that the streets match up properly. In my sleep-deprived state it took me a while to figure out how to do this.

I'm still not sure if this is the right approach to constructing streets and placing buildings. Its advantages are that it is very fast and ensures things are always tightly packed with no wasted space. A major disadvantage is that the buildings are clearly laid out on a grid. You can't have larger buildings in one area and smaller buildings in another unless you do so in increments of the grid size.

At the moment I'm mulling over some crystallization-type ideas, or simulating building construction over time. All of these things are likely to be more expensive to compute so they'd need to be worth it.

City Generation Progress

Here's a visual progress report on random city construction (click for larger versions):




I'm still not happy with it but it's coming. I need major roads which are very wide and connect gates to major compounds (palace, temple, market), minor roads which run fairly straight, and then alleyways which are narrow and twisty. I'd like for major and minor roads not to have any dead ends. I'd also like a little variation in building footprint thickness. I'll need landmarks as well, like open squares where major roads meet.

Figuring out how to marry my rectilinear buildings to the curvy river is another problem. I may make the river chunkier, or I may put in terrain features like park that can assume any shape in the triangular blank spaces.

The current algorithm involves figuring out which squares on a larger grid will contain buildings; then connecting each building square to one of its neighbors.

A River Runs Through It

This week I did a bit more work on random city map generation.

I'd like this kind of city to be in a floodplain with a meandering river running through it, perhaps joining with another river. Accordingly I decided to start with the river and build up from there.

Random river construction is not something that is well-documented on the web. Luckily I know Dr. J. Wesley Lauer at Seattle University, who specializes in the interaction between rivers and their floodplains. He's given me a couple of leads to follow.

The simplest model of a meandering river is a sine-generated curve, also known as a meander curve. The river direction oscillates via a sine wave as a function of arc length. Scaling the direction angle results in a river that meanders more or less. Here are some examples (maximum angles of 1.0, 1.5, and 2.0 respectively):







Here's an example with a varying direction angle scale:



It's really easy to generate these. Here's some Python code I used to generate the SVG diagrams above:

from math import sin, cos

viewSizeX = 300
viewSizeY = 300

x = 0
y = 20
angle = 0

angle_inc = 0.1
dir_scale = 1.0
step_size = 4.0

points = [(x, y)]

while x < viewSizeX:
        dir_angle = dir_scale * sin(angle)
        dir_x = step_size * cos(dir_angle)
        dir_y = step_size * sin(dir_angle)
        angle += angle_inc
        x += dir_x
        y += dir_y
        points.append((x, y))

print '<?xml version="1.0" encoding="UTF-8" ?>'
print '<svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" width="%d" height="%d">' % (viewSizeX, viewSizeY)
print '  <g fill="none" stroke="blue" stroke-width="2">'
print '    <polyline points="%s"/>' % (' '.join(map(lambda p: '%g,%g' % (p[0], p[1]), points)))
print '  </g>'
print '</svg>'

The next step is to replace my rather-lame first attempt at river shaping with something based on sine-generated curves. Here's what I'd be replacing:



The rivers in this version are based on some quadratic curves. The buildings are just splattered down in such a way as to not overlap; that'll be replaced with an algorithm that generates streets and city blocks and then subdivides the blocks into buildings. There's a bunch of little green lines which represent a gradient estimate, which I may use to guide some of the roads.

Random map generation

This week I've been working on random map generation for my Thief/Rogue hybrid. This is what new Roguelike developers generally start on, and they can easily waste years with it. It's a hard problem. I put it off on my project because I knew what a morass it could be, and because I didn't feel like I had a handle on what the gameplay would need from the landscape. Now that I have a pretty good idea of what the gameplay is, I've decided it's time to tackle landscape randomization.

By the way, here are some Roguelike development sites I keep an eye on:

• rec.games.roguelike.development
• Temple of the Roguelike
• Gearhead
• Kaduria
• Kharne
• LambdaRogue
• RogueHut
• Oblong
• Writing Kode

What I'd like is something like the streets of Toledo (España, not Ohio):



(Image by ctankcycles.)

I don't have any great images handy, but Google Maps does a pretty good job of showing what I'm after:



Of course this has to be rectangularized to some extent.

I tried out a Voronoi diagram on a grid. Very unsatisfactory:



There's a paper in this year's SIGGRAPH that has some ideas I might try.

Space Steering Revisited

I had to make a detour from my current project to finish up some Newtonian spaceflight steering stuff I worked on a year ago (detailed in parts one, two, and three).



You could think of it as the beginnings of an AI for playing the old game Space Wars, or its descendants the two-player Star Control combat modes.

The rocket is flying to a target position in the lower left; in the background I'm plotting a graph of the objective function it's trying to minimize in order to pick the correct direction to point its thruster. At the moment it's finding the minimum pretty well (its result is the yellow cross). There are situations where it doesn't do so hot, though. I'm doing an extremely simple, brute-force approach to searching for it, and I'm sure I can do much better. I just need to learn something about minimization of nonlinear functions, especially ones with hard-to-compute derivatives.

Review: Treasures of a Slaver's Kingdom

Treasures of a Slaver's Kingdom is a text adventure of sorts by S. John Ross. It's likely to offend the sensibilities of Real Interactive Fiction lovers, as it pares down input to a handful of commands. I love this because I hate “guess the verb” gameplay. Treasures also features simple stats-'n'-dice-based combat, which puts some people off. On the positive side, it's a giddy pulp pastiche of Conan, Star Wars, and more. Atomic dinosaur? Sure! Give him a light saber! The writing is frequently hilarious. The game is solidly designed: the environment is fairly small, the inventory is kept to a manageable size at all times, and you can't really get stuck.

I discovered the game through Emily Short's excellent (as always) review over at Play This Thing. I really can't add much to her review, so head over there to read it.

Treasures does a good job of making memorable non-player characters. You actually feel like you've got a relationship with them. I think the limited input vocabulary helps here as it keeps you from getting frustrated trying to interact with them.

The full game costs $13, which I think might be slightly much for the amount of gameplay. I got through the game in under eight hours, although I made fairly extensive use of the crypto-clues offered in the instruction manual, to the point of writing a Python script to decode them for me. However, I spent the entire time playing the game with a big grin plastered on my face and laughed out loud on several occasions.

There's a free demo that lets you play the first fifth or so of the game. Try it out and see if it agrees with you. You will also need a Z-machine interpreter to run the game; Gargoyle is a very nice-looking one.