L-Systems

[wire_hall_medic]

I like to have things with a broad need for access, like the current map, creature list, and the player character, to be global static variables.  Otherwise, I run into problems of what should own what, and everything would need getters and setters for the same six classes and lists.

[Paul Jeffries]

It sounds like what you're after is the Medial Axis/Topological Skeleton, which is basically a voronoi diagram for curves/boundaries rather than points - you could use that to find the set of points where your red and green lines would be the same length.
 
Of course this may or may not help you depending on what it is exactly you're trying to achieve.  The trouble with cities is there are not really any 'rules' for how they are laid out, and what conventions exist will vary depending on where in the world you are.  There are a couple of things you could try to prioritise - broadly rectangular plots, following the contours of the topology and so on.  I doubt you'll really find a 'one size fits all' approach for doing this, however - what decent-looking city generators I've seen look  like they intentionally use several different algorithms layered on top of one another.

[lithander]

Sorry, I was getting ahead of myself. Gonna push to finish the interpreter + renderer first. Clean it up. Make a blogpost. Then I can delve deeper into finding out how it could be used for map generation.

[lithander]

I give up on the L-System front. I'm quite happy with what I achieved so far but my motivation has burned out too much to push it further. Here's a screen capture of a demo I've scripted in the last week. All the animations visible in the above video are real time generated, rendered at 60 FPS in my Grove Script interpreter and captured with hypercam. As the script is only 1KB big, the perceived complexity and the way the result is randomized is a nice demonstration of the power of L-Systems and emergence.


http://www.youtube.com/watch?v=twZLhxi_964

And this is how the script of the demo looks like:

Code: [Select]

//set some basic constant parameters to be used in expressions
//feel free to play with the values and see how the animation
//adapts
set speed, 15
set pause, 15
set fadetime, 15
set budstep, 5
set maxage, 80
set leafAge, 5
//let the size of the structure adapt with window size
set step, 0.4*_height/480

//these variables change every frame because they all depend on the current
//value of the time() function.
//Thanks to the modulo operate age wraps around at maxage.
set age, (speed*time()) % maxage
set fade, min(1, (maxage-age-pause) / fadetime)
out fade
set age, 2.5*age^0.55
set frac, max(0.01, frac(age))

//each structure should look unique.
//So we use a different random seed for every new structure
out 'rnd seed, floor(time()*speed/(maxage))
shuffle floor(time()*speed/(maxage))

//init the turtle
dir random(360)
pos 0, step*(5*age-100)

//set the axiom of the 'plant' structre
seed plant, A(0,0,1)
//apply the ruleset 'r1' as often as the plant is old.
repeat age
grow plant, r1

//fun info: how many buds were generated?
out budCnt

//render 'plant' twice - mirrored.
push
rotate -45
run plant
pop
rotate 135
run plant

//Now the Tokens that the L-System operates upon are defined.

//light blue tips of the structure
#A(age, angle)
run shade(leafAge/frac)
size frac^0.5
move step*frac^0.5, angle

//what becomes of A in the next cycle - a simple curve
#B(t, angle)
run shade(leafAge/(t+frac))
size (t+frac)^0.5
move step*(t+frac)^0.5, angle

//B becomes C when it's old enough to spawn leaves - does the same thing, though
#C(t, angle)
run B(t, angle)

//a growing leaf
#L(t, angle)
run leaf(t+frac, angle)

//a finalized leaf
#xL(t, angle)
run leaf(t, angle)

//a growing bud
#Y(t, spread, angle)
run bud(0.3*(t+frac), (spread+frac)*budstep, 0.1*angle)

//a finalized bud
#xY(t, spread, angle)
run bud(0.3*(t+frac), (spread+frac)*budstep, 0.1*angle)

//render a bud
#bud(len, angle, curve)
run budshade(1/len)
//left side
push
size 2*len^0.3
rotate angle
move len^0.3, angle
size len/2
rotate -90
move len, -angle
pop
//right side
push
size 2*len^0.3
rotate -angle
move len^0.3, -angle
size len
rotate 90
move len, angle
pop
//stem
rotate curve
move 0.55*len^0.7

//render a leaf
#leaf(len, ang)
size 1
rotate 10*ang*len^0.6
move 0.5*len^0.3
move len^0.6, ang*(60+len*5)
rotate 180 - ang*0.4*(60+len*10)
move 0.5*len^0.5, -ang*(len*5)
move 0.7*len^0.5, ang*(len*10)

//color buds
#budshade(alpha)
visible alpha * fade
rgb 1.0-0.8*alpha*alpha, 0.6*alpha+0.2, 0.2*alpha*alpha

//color rest
#shade(alpha)
visible alpha * fade
rgb 1.0-0.5*alpha, 0.5*alpha+0.5, 0.3*alpha

#[
push

#]
pop

//The rules are evaluated in the order of appearance.
//rare rules appear first, if all are skipped the general case is usually to just grow the existing tokens
#r1
//BRANCHING
//higher c makes a vine less likely to bend or split but increases chance to spawn buds
A(i, j, c) : rnd(0, c) > 2+budCnt -> B(1, j) Y(0, 1, j)
raise budCnt, 1
//if old enough there's a chance to split into 3
A(i, j, c) : i > c and rnd() < 0.5/c -> B(1, j) [ A(0, rnd(-40,-60), c+2) ] [ A(0, rnd(40,60), c+2) ] A(0, 0, c+1)
//...or into 2
A(i, j, c) : i > c and rnd() < 0.5/c -> B(1, j) [ A(0, rnd(-40,-60), c+1) ] A(0, rnd(40,60), c+1)
//or just change the direction
A(i, j, c) -> B(1, j) A(i+1, j+rnd(-90, 90)/(c+1), c)
//LEAVES
//based on the curvature leaves spawn on different sides
B(i, j) : j < 0 and i = leafAge-1 -> C(i+1, j) [ L(0, 1) ]
B(i, j) : j > 0 and i = leafAge-1 -> C(i+1, j) [ L(0, -1) ]
//GROWTH
//and of course everything needs to grows
Y(i, j, k) -> Y(i+1, j+1, k) xY(i, j, k)
B(i, j) -> B(i+1, j)
C(i, j) -> C(i+1, j)
L(i, j) : i > 1+rnd(7) -> xL(i+1, j)
L(i, j) -> L(i+1, j)

[lithander]

And a blog post to wrap it all up: http://blog.pixelpracht.net/?p=431

Done!

[Quendus]

The vines are pretty cool but it would be nice to have an example of dungeons, citys, monsters, behavior, talent trees, or branching storylines being generated with this. I'm sure the potential's there.