I think pass two is intended to introduce additional regions of concavity (mostly by replacing straight lines), which in effect introduces a bunch of inflection points, helping creating the organic "spiny" feel, as opposed to a "bubbly" feel. Without it, the resulting caves look a bit more like if you spilled liquid on a waxy surface, and less like thorns.
If you go into the javascript and replace "for(let p=0;p<3;p++)" with "for(let p=1;p<3;p++)", and then re-execute the block in the console, you can generate run through a bunch of generations without step 2
Cool, the interactive visualisation is a great way to explain it.
Maybe a similar-ish idea could be done in a continuous 2d space, without a grid, using 2D computational geometry operations (e.g. GEOS's [1] buffer operation to grow shapes by a given radius & so on).
Each component is a point-set -- a subset of points in the 2d space we're working in.
1. sample a bunch of seed points from some distribution. these define initial connected components
2a. grow each component by radius r. union any components that touch.
2b. shrink each component by radius r + delta. delete components that contain no points
3. delete any components that are 'too small': shrink each component by r_min, delete any components that now contain no points, then grow each surviving component by r_min again
4. link the surviving connected components somehow:
4a. identify pairs of components that are adjacent (e.g. compute voronoi 'triangulation' using components as seeds instead of points, if two resulting triangles border then their components are neighbours)
4b. propose candidate corridors linking the nearest points between each pair of adjacent components
4c. find a minimal/interesting spanning tree on component-corridoor graph using corridor lengths as edge weights
4d. carve selected corridors by growing each coridoor line by some radius
4e. everything should be some big connected component
5. sanity check that we got something playable (maybe based on area). if it's too small/uninteresting, reject & try again from step 1
I'm not sure of an efficient/reasonable way to do step 4a in the plane - it'd be simple & efficient to do this on a graph (Voronoi-triangulating a graph has similar computational cost to finding all shortest paths from some source - it's like a multi-source BFS with bookkeeping to recover a shortest path to the closest source, with a little extra bookkeeping & logic).
Nethack's cellular automata gnomish mine algorithm on a small grid is of course going to be massively faster than stuffing about with masses of GEOS Buffer & Union calls, but it's fun to think through how much of this extends.
Nothing in the description refers to individual neighbouring cells. All those numbers are counts -- if 0 to 2 of the neighbouring cells are rock, do this, etc.
You're talking about the post, or something in the source code?
In the post, it just counts how many of the 8 tiles are floor (which means 9 possibilities, including none of them). They aren't assigned index numbers.
Edit: ha, we all jumped on you. So now this is explained three different ways.
It sounds like the same algorithm described here:
https://www.roguebasin.com/index.php/Cellular_Automata_Metho...
I think pass two is intended to introduce additional regions of concavity (mostly by replacing straight lines), which in effect introduces a bunch of inflection points, helping creating the organic "spiny" feel, as opposed to a "bubbly" feel. Without it, the resulting caves look a bit more like if you spilled liquid on a waxy surface, and less like thorns.
If you go into the javascript and replace "for(let p=0;p<3;p++)" with "for(let p=1;p<3;p++)", and then re-execute the block in the console, you can generate run through a bunch of generations without step 2
This is my favorite kind of procgen blog post: here's what we did, and here's a little widget you can play with to see how it works.
You would also probably like this old post of mine:
https://journal.stuffwithstuff.com/2014/12/21/rooms-and-maze...
Oh man, I'd forgotten about this one. Thanks for sharing it again! (And thanks for having done it in the first place!)
Oh wow. I had no idea this was based on cellular automata. It really does give a totally different feel versus the other sections of the dungeon.
Cool, the interactive visualisation is a great way to explain it.
Maybe a similar-ish idea could be done in a continuous 2d space, without a grid, using 2D computational geometry operations (e.g. GEOS's [1] buffer operation to grow shapes by a given radius & so on).
Each component is a point-set -- a subset of points in the 2d space we're working in.
I'm not sure of an efficient/reasonable way to do step 4a in the plane - it'd be simple & efficient to do this on a graph (Voronoi-triangulating a graph has similar computational cost to finding all shortest paths from some source - it's like a multi-source BFS with bookkeeping to recover a shortest path to the closest source, with a little extra bookkeeping & logic).
Nethack's cellular automata gnomish mine algorithm on a small grid is of course going to be massively faster than stuffing about with masses of GEOS Buffer & Union calls, but it's fun to think through how much of this extends.
[1] https://libgeos.org/
All that work for some miscreant dwarf archeologist with a pick-axe (me) to show up and dig it to hell for a bunch of worthless glass.
Related, TNNT starts in 9 days (Nov 1), anyone can join the tournament.
https://tnnt.org/
Looking forward to it! I just started my first-ever NetHack 5.0 game to practice a bit.
I don't get the neighboring tile numbering. Is it like this?
What's the current cell?
A diagram would help
Nothing in the description refers to individual neighbouring cells. All those numbers are counts -- if 0 to 2 of the neighbouring cells are rock, do this, etc.
There’s no numbering, it just counts the neighbours. ‘0-2’ means zero, one or two neighbours.
You're talking about the post, or something in the source code?
In the post, it just counts how many of the 8 tiles are floor (which means 9 possibilities, including none of them). They aren't assigned index numbers.
Edit: ha, we all jumped on you. So now this is explained three different ways.
I always have a lot of respect for people who are really good at procedural generation