Wednesday, November 19, 2008

Rapidly-Exploring Random Trees

Time to play a bit. I just learned about rapidly-exploring random trees while reading about motion planning. They look kind of like drainage networks so I had to try them out. I created a disc (a perfectly round island, if you will) and then generated a tree in the interior. Here are a couple of example results (click to enlarge):

The gist of the algorithm is that you generate a sequence of random points distributed uniformly over the interior. For each point, find the closest point on the tree and create a new branch from there, headed toward the random query point. You don't go all the way to the query point, though; just a small step. The net result of this is that the tree tends to head toward open areas.

I've shaded the tree edges as a function of how many other edges empty into them, so you can see the big rivers are darker than their tributaries.


Anonymous said...

How to you seed (start) the trees, and how is their growth stopped?

James McNeill said...

In this case the seeds are 128 points around the perimeter of the disc. All the rivers start from there. I picked an arbitrary number of iterations for adding edges to the trees; in this case, 5000. However, it doesn't necessarily add 5000 edges to the tree, because I also reject new edges if they are shorter than my step size (in other words, if the random query point is less than a step's distance from the closest point on the tree); this keeps the tree from getting bunchy.

To be completely technically correct it should be possible to branch from the middle of an edge in the tree, if that's the closest point to the random query point. However, I didn't bother to do this; I just made the step size small so there are lots of vertices.

You could play with having variable step size, too; for example stepping a fraction of the distance to the random query point, instead of a fixed distance.

Anonymous said...

I used this concept in my soils class today. We were learning about erosion and so I spent some time playing around. To simulate a slope I made the random point only consider the parts of the tree within 45 degrees of straight down hill.

For rills their branching structure is much less bushy and their growth is biased down the hill. Since rills do not carve drainage basins for themselves, from the perspective of one rill the rest do not exist until they meet. This means I can simulate their path with lines starting from a random point moving randomly downward like the path of a Plinko chip.

If I wanted to make it more accurate I would make the chance of starting at a given point proportionate to the amount of non channeled water present at that point. Another way I could make it more accurate is to not bias the direction that it flows, but instead change the step distance based on how far water would flow in that direction in a moment.

So thanks for putting this up, it's a really fun idea.