1. I define a set of possible moves (eg. straight ahead, left turn, junction, etc). One possible move is a dead-end, which looks a bit like a house in my interpretation.
2. Each move is assigned a relative weight (eg. continuing straight ahead 10x more likely than turning left).
3. Each iteration, for each of the roads under construction, a random move is selected. Some moves are impossible (based on other roads already drawn on the map) and so it will ensure not to select one that would result in a collision. At worst, it will terminate the road with a dead-end.
4. Repeat forever, until every road has terminated in a dead-end.
Most of the script itself is dealing with the rendering logic. To avoid collisions I maintain a 2D array of all visited points.
Thanks. It's plain JavaScript, rendering with an HTML canvas.
I did investigate JS 2D graphics libraries but decided in the end that this was sufficiently simple to not warrant one. It was harder than I expected to get the drag & zoom to work!
Ach! this reminds me of an artist who worked mostly with Processing ( https://processing.org ) and either did this or something very like it (and a bunch of other stuff.)
I just got it -- thanks for sharing this! Could watch it for hours...
If anyone else wants to download the screensaver, you can get it for linux/osx/ios/android: https://www.jwz.org/xscreensaver/ . Most in the collection aren't great (unless you're in an early-2000s aesthetic mood), but I just installed the substrate one :)
Being able to see the random seed used in the console and use it in the hash is a nice touch. I found a few large ones and one with a single path between two points (1592751582695)
It is artificially limited to a 1001 x 1001 grid - just to stop it from growing forever (which could get quite slow on lower end devices). In practice I rarely encounter maps that go that far.
Not really, I've no experience with e-ink displays, if I was to do it, I'd hunt for an older-generation large-size e-book reader and try to hack the firmware a bit.
I have two Kobo readers that are 5+ years old, the small one, I cracked open and found that the Linux OS was on a normal SD card in a normal socket, so I removed it and flashed it to a bigger card, I think one of those should be easy(ish) to hack :)
I feel I'm missing something when people ask what algorithm this is using. I'm imagining it as a bunch of Math.random and If statements. In fact, I don't think I've ever googled for a specific algorithm or implemented one. Am I doing programming wrong?
51 comments
[ 2.7 ms ] story [ 131 ms ] threadRoads without context are just paths. You need the roads to provide useful destinations as efficiently as possible.
Many of these paths lead nowhere. In fact, all of them go nowhere, I don’t even think there’s loops.
I wrote a brief description in this comment: https://news.ycombinator.com/item?id=23592538
Initially I had envisaged something a bit cleverer, but for an art project keeping it simple seemed to do the trick.
https://random-roads--edwardcunningh2.repl.co/script.js
It's not especially clever:
1. I define a set of possible moves (eg. straight ahead, left turn, junction, etc). One possible move is a dead-end, which looks a bit like a house in my interpretation.
2. Each move is assigned a relative weight (eg. continuing straight ahead 10x more likely than turning left).
3. Each iteration, for each of the roads under construction, a random move is selected. Some moves are impossible (based on other roads already drawn on the map) and so it will ensure not to select one that would result in a collision. At worst, it will terminate the road with a dead-end.
4. Repeat forever, until every road has terminated in a dead-end.
Most of the script itself is dealing with the rendering logic. To avoid collisions I maintain a 2D array of all visited points.
I considered adding logic to prevent this, but have decided to embrace it as a feature rather than a bug.
I quite like some of the small-ish maps, like this: https://random-roads--edwardcunningh2.repl.co/#1592759118928
I did investigate JS 2D graphics libraries but decided in the end that this was sufficiently simple to not warrant one. It was harder than I expected to get the drag & zoom to work!
If anyone else wants to download the screensaver, you can get it for linux/osx/ios/android: https://www.jwz.org/xscreensaver/ . Most in the collection aren't great (unless you're in an early-2000s aesthetic mood), but I just installed the substrate one :)
I enjoy the large ones (eg. https://random-roads--edwardcunningh2.repl.co/#1589058113269) where I imagine the gaps left in the middle to be parks.
this one seems to show the boundaries of the display plane : https://random-roads--edwardcunningh2.repl.co/#1592753917190
It is artificially limited to a 1001 x 1001 grid - just to stop it from growing forever (which could get quite slow on lower end devices). In practice I rarely encounter maps that go that far.
https://github.com/mxgmn/WaveFunctionCollapse
What algorithm is this using? Got a GitHub link?
Here's the source https://random-roads--edwardcunningh2.repl.co/__repl
This would be great on A4 sized e-ink paper, mounted in a nice frame and refreshing a few times a day.
Just need to track down a e-ink display for this sort of fun project. Anyone know of any good ones that would make this easy?
I have two Kobo readers that are 5+ years old, the small one, I cracked open and found that the Linux OS was on a normal SD card in a normal socket, so I removed it and flashed it to a bigger card, I think one of those should be easy(ish) to hack :)