Because the tree grows toward each random point from the closest river or shore, it's extremely unlikely that you'd ever replicate South America, with most of the water draining to one side. This can be remedied by adding obstacles (click to enlarge):
Obstacles are defined as line segments which block line of sight between each randomly generated point and the tree. They manually specify some of the ridges on the terrain. Note that rivers will tend to cut quite close to the ends of the obstacles, so the obstacles don't represent just the highest parts of the ridges.
With my brute-force algorithm (coded in a couple of hours) the addition of obstacles slowed it down by a large amount that scales directly with the number of obstacle line segments. As the shape of the obstacles gets more mazelike, the algorithm will require drastically more iterations to fill in the tree, too, since it won't get line of sight to the inner portions for quite some time.
I also did some experiments with RRTs on a grid, where tree edges are all oriented horizontally or vertically. It turns out to bear a strong resemblance to maze-generation algorithms in that context.
4 comments:
Your posts are always fascinating and inspiring, keep up the good work! :)
What the next step on rrt will be?
Have you thought about using "soft" obstacles?
Something like line segments that does not block the line of sight completely, but simply double the distances calculated for paths that cross them.
It would get the trees to stay away from those, quite like the obstacles but sometimes, when the tree already got close to the obstacle, they would be able to cross it, like rivers would do on a terrain with low hills and a few valleys.
Soft obstacles are an interesting idea. They would obviously slow things down even more since you'd have to sum up the effects of all obstacles along each test line. Another way to do obstacles would be to define an obstacle function on a grid, using a bitmap or something like that. Each ray would have to sum up the values of all the grid cells it intersected in some fashion.
In terms of next steps, I'm not sure. An easy one would be to allow manual definition of lakes. This would be an outline on the map which would initially be unused. As soon as a river grew to the point where it touched the lake, the entire lake shore would be added to the tree, so that additional rivers could sprout off anywhere around it.
It would be really nice to be able to have elevation data somehow. This would allow you to mark mountains, plains, and so forth. I haven't figured out yet how elevation data might be inferred. The river beds define a set of constraints on allowable elevations for things: the river needs to increase in elevation as you climb toward its sources (although the actual amount of increase isn't necessarily constrained). Another constraint might be that any point on the map that isn't in a river needs to be higher than the closest river bed. These constraints leave a lot of leeway for how the actual terrain is shaped, though, and I haven't decided how that would be resolved.
Wow, awesome stuff. I've been an avid river basin fan as a random terrain method and it has led me to work on my current procedural world generation utilising events.
I'd been hunting for exactly this type of RRT algorithm for a long time and had developed a couple of prototypes that didn't get anywhere as far as this.
One thing you might want to consider is that mountains are almost exclusively an inverted river basin. You should be able to seed the map with exit points for rivers (under the ocean, in a lake, etc) as well as mountain peaks. Now let the RRTs grow to fill in the gap between the 2 states.
It should work without heights if you just want a concept picture, but to use it effectively in random terrain generation you will need to also track heights to build the output.
If heights are used you will need to have 2 tests, one for the nearest "river" branch node, and one for the nearest "mountain" branch node. The heights and proximity of these 2 branches should be able to guide the new point's height so that the mountain and river trees converge in z-space.
Excellent stuff!
This might be considered "cheap", but what about starting with a mountain-high plain (ie, all height values "high") and then carving an area around each edge (or more easily, each node). The area would be proportional to the weight of the edge/node.
(I'm thinking something like subtracting a value inversely proportional to the distance or distance^2 to the edge/node.)
The idea is that areas close to end branches are mountains, and areas close to big rivers are valleys and plains. Really cheap but might yield an interesting height map. Most important of all it's entirely based on the RRT.
Post a Comment