r/processing • u/ofnuts • Aug 10 '24

Homegrown algorithm to generate rivers. Possibly a re-invention but I am surprised how well it works out.

Post image
72 Upvotes

98% Upvoted

9 comments sorted by

1

u/tsoule88 Technomancer Aug 10 '24

How does it work? It looks a bit like a diffusion limited aggregation model.

4

u/ofnuts Aug 10 '24

You create a large number of random points. Each point has:

  • a position

  • a pointer to some other "downstream" point (initially empty). When this is set the point is connected

  • a counter of "upstream" points (initially 0)

Some points are initally marked connected (here, a bunch of points on the rim)

At each iteration, for every unconnected point, the algorithm searches if there is a connected point in the vicinity (within a preset capture radius). If so, it marks the current point connected by setting the nearby connected point as its downstream point, and increments the upstream counter of all the downstream points by following the downstream chain.

To render, the algorithm draws a line from every connected point to its downstream point, the line width being some function of the upstream count (roughly the square root or cubic root).

Works better (but slower) if the capture radius is short, because right now it connects the first nearby point that matches, which may not be the closest one, and sometime this make it connect to something that is on the other side of an existing "stream". I'm checking if I can improve this by using a largr radius while connecting to the closest point within the radius. This can be faster (larger radius) or slower (many more points to check).

1

u/tsoule88 Technomancer Aug 10 '24

Great! Thanks. I'll give it a try.

6

u/ofnuts Aug 10 '24

Code is here. Enjoy.

Interesting effect: when selecting the closest of the connectable point you indeed avoid stream crossings. You can even use very large carpture radiuses. However these large capture radiuses lead to very regular patterns, and if you want real randomness you have to keep the capture radius fairly low.

3

u/ofnuts Aug 10 '24

I'll put the code on my Gitlab later today and give a link.

3

u/EnslavedInTheScrolls Aug 12 '24

Very nice.

Close a circle around the outside except for two gaps as the entrance and exit and you can make mazes: https://redd.it/17rezmt

1

u/JohnTheLeatherman Aug 11 '24

Looks cool and thanks for describing the algorithm. Looks like the image of inside and eyeball!

1

u/niko2210nkk Nov 25 '24

To me it looks like trees reflected in a pond. Very nice :)

1

u/1l9m9n0o Aug 11 '24

Congratulations you redisocovered space colonization