Monday, July 28, 2008

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”:

Seen any others?

Monday, July 21, 2008

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.

Monday, July 14, 2008

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.

Monday, July 7, 2008

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="" xmlns: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.