Demo video: https://youtu.be/AuF9cMaVBsg
Disc image: (Shift-Break to load, Z X * ? to scroll around) Screenshots:
I started prototyping a bit in BASIC with algorithms that randomly chose which cells were solid or not, subject to certain constraints, trying to get something that produced interesting patterns with enough connectivity but not too much. That was pretty effective, but a bit slow so I switched to Shadertoy to prototype more efficiently. This let me quickly render at different scales, scroll around in real time, and I added a second pass to the algorithm to round off some edges for a more organic look, and to allow passage between diagonally-adjacent cells.
As that was working pretty well, I started coding for the Beeb - cross-assembling using xa. My general plan was to make something that works a bit like the Repton games - with a square playfield, hardware scrolling, MODE 5, 4x4 character tiles. As it scrolls it draws rows/columns of characters at the edge, this isn't currently quite fast enough to happen within the vertical blanking interval. It also regenerates the world in the vicinity of the screen, covering about twice as much as the visible area - this is very redundant, just a proof of concept, and ultimately it should only regenerate the bits that are about to scroll on.
The procedural generation actually occurs in two passes, and it does use a couple of arrays. The screen is filled by an 8x8 grid of "fine" tiles. The first pass of procedural generation happens a couple of levels coarser - it considers each coarse region of 4x4 fine tiles, deciding whether each quarter of the region (a "medium" tile, 2x2 fine tiles) is generally solid or not. Then the second pass decides, for each fine tile, which graphic should be used, based on solidness of its neighbours. It picks edged tiles where the neighbours are empty, and also replaces some solid tiles with triangular ones to open passages, and some empty tiles with triangles to make a more interesting look overall.
I haven't optimized it much, just trying to get a ballpark feel for how fast or slow it would be, but I was quite happy with the result so far - it runs at 50Hz, mostly. For gameplay purposes this is probably way too fast, it'll probably play better at 25Hz, but I'm not sure what the gameplay will be yet.
The sprites were rendered by a BASIC program that's also on the SSD disc image attached. It was interesting writing code to create them programmatically. It let me refine them progressively - from solid colours to a brick-like pattern, and straight line edges to more interesting ones that wrap around the bricks a bit.
At the moment it only uses a 256x256 world, wrapping at the edges. The algorithm can easily support larger worlds, if necessary - it would just require things like the current screen X/Y coordinates to be stored with more bytes, and the hashing routine that calculates random cell contents to use the extra bits as well.
Probably the next thing to add is background objects, artifacts, and other decorations. The Shadertoy prototype has a quick hack to use green to indicate where I could place foliage, and blue and purple for maybe different kinds of artifact. As the real thing on the Beeb actually has a bit more local knowledge, it may be possible to automatically place things like doors in areas where a passage is only one tile high, and other things like that.
Another thing I played with in Shadertoy was varying the density of the caverns, so that some regions are more connected than others, and that could be interesting too.
.