How do I create a random path?

Question

I'm looking for an algorithm that can generate something like what's in this image:

I've read about drunken walk algorithms but they don't seem to quite fit what I need. I'm not sure if I can achieve what I'm looking for with a heavily modified drunken walk algorithm or if I should be looking for some other algorithm to mess with.

Answer 1

Since you want to avoid self-intersection, a random walk is going to be difficult to do correctly. You could easily paint yourself into a corner. I would suggest starting with a single line segment that crosses the area, then splitting this line segment somewhere in the middle and shifting the midpoint by some random amount proportional to the length of the line segment. Repeat this process recursively for the two new line segments. If you end up with a midpoint that causes one of the two new line segments to cross an existing line segment, then try a different midpoint. Stop the recursion when your line segments are short (however you want to define that).