Maxim Gumin on X: "Did you know that WFC algorithm can generate ~unbiased (not-necessarily-shortest) paths between A and B? Each tile here has an even number of outgoing edges, therefore all paths split into cycles, except A and B, which become connected by a path! Tiles by @beast

Post

Maxim Gumin
@ExUtumno
Did you know that WFC algorithm can generate ~unbiased (not-necessarily-shortest) paths between A and B? Each tile here has an even number of outgoing edges, therefore all paths split into cycles, except A and B, which become connected by a path! Tiles by @beast_pixels. Thread.
GIF
3:23 PM · Jul 31, 2018
3
Maxim Gumin
@ExUtumno
Jul 31, 2018
Take a tileset with Lines, Turns and DeadEnds, but ban DeadEnds everywhere except 2 endpoints. The key is to NOT include T-shaped roads, as they have odd number of outgoing edges, and the result then doesn't have to split into cycles. X-shaped intersections are fine though.
GIF
3
Maxim Gumin
@ExUtumno
Jul 31, 2018
WFC may be an overkill for simple 2d paths, but it's very handy for more complex geometries like 3d stairs or heavily constrained tilesets.
GIF
1
Maxim Gumin
@ExUtumno
Jul 31, 2018
The most common method I've seen to generate not-necessarily-shortest paths: 1. Generate a random metric (as noise, for example) 2. Find the shortest path in that metric. reddit.com/r/proceduralge… By controlling noise frequencies (octaves) you affect the resulting path frequencies.
reddit.com
From the proceduralgeneration community on Reddit: Procedurally Generated Road
Explore this post and more from the proceduralgeneration community
1
Maxim Gumin
@ExUtumno
Jul 31, 2018
And you can go for models more interesting than Perlin noise, your random metric doesn't even have to be induced from a heightfield. Examples from Scott Sheffield's website: straight lines in random geometries math.mit.edu/~sheffield/spo… math.mit.edu/~sheffield/geo…
1
Maxim Gumin
@ExUtumno
Jul 31, 2018
Another fun method for generating ~unbiased paths: @boris_brave's chiseling algorithm 1. Start with everything covered in path tiles. 2. Remove tiles one by one until only a thin path remains. boristhebrave.com/2018/04/28/ran… It can connect >2 points or be stopped early for thicker paths.
boristhebrave.com
Random Paths via Chiseling
I went over a previous project to randomly generate paths between points and came up with a much more efficient and versitile algorithm. (EDIT: In 2022 I found an even better way.) The algorithm is…

Did you know that WFC algorithm can generate ~unbiased (not-necessarily-shortest) paths between A and B? Each tile here has an even number of outgoing edges, therefore all paths split into cycles, except A and B, which become connected by a path! Tiles by @beast_pixels. Thread.

GIF

3:23 PM · Jul 31, 2018

Post

Post

Maxim Gumin on X: "Did you know that WFC algorithm can generate ~unbiased (not-necessarily-shortest) paths between A and B? Each tile here has an even number of outgoing edges, therefore all paths split into cycles, except A and B, which become connected by a path! Tiles by @beast_pixels. Thread."