Procedural road generation ?

[Lowercase]

I would like to generate a random road map, thirst in 2D, then extrude on a 3d heightmap.

the main problem is, i can't find a satisfying algorithm, i tried perlin 1d and bezier curve... I searched without success on vterrain.org

Do someone know about that ?

I don't know if i'm in the right forum, if so, excuse me

[Robert Kosek]

Okay, you have either one of two questions. One I can help you with, the other I can't.

You either want:
1) Procedural road texture generation
2) Procedural path (aka, road) generation

The difference being 1 is virtual and in memory only, and the other is a texture. I can't help with the texture, but I can give some advice about the procedural paths.

[chronozphere]

Also very important. What do you want the road to look like??

Should it be a road with some smooth curves in it? Should it have sharp corners? Should it go up and down through the landscape? Any T-Junctions? Or do you want to generate a network of roads, or prehaps all the roads of a whole city?

We need more info.

[Lowercase]

i'm really sorry for the lack of information..

I was talking about a "network of roads" like Simcity or GTA.

many thanks for your interrest.

PS: I have just found an article on http://www.citygen.net/

[chronozphere]

Ah.. In that case i have a suggestion.

You could use voronoi diagrams. Check:

http://en.wikipedia.org/wiki/Voronoi_tessellation

You can implement an algorithm (like the sweep line algo here):

http://en.wikipedia.org/wiki/Fortune%27s_Algorithm

It takes a set of center-points and divides the space into regions. Each region has one center. It creates nice mosaic patters. You may want to use this. You could let the regions be the building, parks or whatever and the borders between the regions could be the roads.

I would like to implement this myself one day.

Hope this is usefull.

[Lowercase]

I'll give it a try, but there are at least 2 problems with it (if I understood correctly) :

* the diagram is open on it's edges
* the center of each region need tobe calculated before (so that there's no acute angle)

but it's a good start, thanks[/list]

[chronozphere]

* the diagram is open on it's edges

I'm not sure what you mean. :?

* the center of each region need tobe calculated before (so that there's no acute angle)

I guess you can just pass a big array of points to the algorithm, without any extensive pre-processing. I can imagine you want to check the distances between the points and delete the close ones, so that the points are nicely distributed over the area.

Unfortunatly, i cant help you with the actual implementation. I think fortune's algo can be implemented without a lot of problems. You have to check if it's suitable for your purposes and if it can deliver the information you want.

[Lowercase]

excuse me, i have a little english..

and i don't have the exacts words for geometry.

i was meaning that on the edges of the drawing, the lines are endless

[Lowercase]

Well ... This is what I undestood :

1) Sort each point by X ascending
2) for each point, make a triangle with the point n, point n +1, point n+2 then calculate the barycentre of this triangle. So if other points are ouside the circle of center=barycentre and distance=barycentre to any edge of triangle then you're alowed to use this triangle.

It's more or less delaunay algorithm which is dual to voronoi

I still don't understand how to draw voronoi diagram.

Do someone has any documents on how-to contruct it ?

[chronozphere]

Hmmm... just a guess:

1> First, generate a set of delaunay triangles by using an array of vertices (that will be centers of the regions in the vonoroi diagram)
2> Second, calculate center points for every triangle (by interpolating it's vertices).
3> Then, pass all these points to the algorithm again (points used in step 1 and the points calculated in step 2).
4> Delete all edges and triangles that connect to any of the vertices that were passed in step 1.

So what you have left, are the vertices and edges (conflict lines) that seperate the regions. And that's you voronoi diagram.

I could be wrong about step two; Instead of interpolating the three vertices of a triangle, you could also calculate the center of the triangle's circumscribing circle.

Again, it's just a guess so i cannot give you any guarantee it will work. As far as i can see it should work. I'm into computational geometry, that's why i can tell you this info. I would like to test this hypothesis and write a test app. Unfortunatly school occupies too much of my time, so i can't do that for now.

Hope you can get this working.