Happy New Year quinor! Sorry I didn't get to you sooner, it's been a hectic few weeks and I wanted to make sure to write out a decent answer!
At its core, Ribbon Maze uses Eller's Algorithm. This algorithm has some excellent properties which the mod is designed to take full advantage of. For a given width of maze, the computational and storage cost to generate new "rows" for the maze is constant. Consequently, you can explore as deep as you like into the maze without experiencing any slowdown. It's more accurate to say the algorithm is linear with the width of maze, but the width doesn't change once a game is started. So, the algorithm is well suited to Factorio where performance is something a lot of players think about as their base grows.
It has these properties even though the maze is perfect no matter how many rows you generate.
I don't want to mislead here. I store the results of the algorithm. So there is a lua table that grows as the player explores. I do that because the maze must be generated in a strict sequence, one row at a time, but Factorio may ask for chunks in any order. I could delete the old rows once I know the corresponding chunks have all been generated, but chunks can also be destroyed, so I might need the old results again if it was then created a second time. What's absolutely key though, is that the results are not needed by Eller's algorithm. If you wrote an implementation of Eller's algorithm which just output the results to a text file, then the algorithm would be able to do so "append only". It would not need random access to the results.
Compare this to a randomized depth-first search, which typically uses some kind of stack and backtracking. The larger the maze, the larger the potential stack. Practically speaking you end up having to sacrifice the "perfect maze" so as to terminate the algorithm. Ribbon Maze has a small naive algorithm to measure corridor length when determining how good resources should be; this also has to terminate at some arbitrary point, because one corridor will be infinitely long. So whereas Eller's is perfect, my corridor measuring algorithm is not. Measuring the corridor length doesn't need a stack; the moment you hit any kind of branching point, you've finished measuring the length of the corridor, and don't need to backtrack. Whereas, if you use a tree search to generate a maze, you have to backtrack (or do some equivalent to backtracking).
Eller's achieves its excellent properties by using sets. You just keep track of which "cells" in the previous row were in which set. If they are in the same set, and you don't put a wall between them, then you would create a loop, so you have to put one there. And there are other rules like that. Here is a really good description of diagrams, which I found helpful in my own understanding of the algorithm, and I would highly recommend to anyone interested in procedural generation of mazes:
http://weblog.jamisbuck.org/2010/12/29/maze-generation-eller-s-algorithm
My Lua implementation, the maze generation code, is in its own file here:
https://github.com/h8ul-modder/factorio-ribbon-maze/blob/master/control/lib/maze.lua
There are a few key things to note, in the implementation.
One is that maze algorithms are usually described as walls between cells, rather than walls being cells themselves. So you might say "cells 1 and 2 have a wall between them". But in Ribbon Maze, the maze "wall" thickness is the same as the "corridor" thickness. So for Ribbon Maze, it'd be "cells 1 and 3 have a wall between them -- in cell 2". There's a game play reason for having the walls be so thick: if the mod had walls just a few tiles thick, then robots, turrets, and underground belts could easily bypass them. I deliberately wanted to prevent that, to increase the challenge. So unlike the basic Eller's algorithm, I have to distinguish between walls that go "above" a cell and "right" of a cell; essentially two rows/columns in the Ribbon Maze correspond with one row/column in Eller's algorithm. In fact the Factorio chunk that goes above AND right (if x % 2 == 0 and y % 2 == 0) is always a maze wall.
A further thing to note, is a Lua optimization, which makes my implementation quite different from any psuedocode I've seen of Eller's algorithm. Lua tables can be stored as references, so I don't need to number them. I just track Lua tables. The initialization of the Lua state is pretty much just this:
for column = 1, N do
local set = {}
set[column] = true
o.line[column] = set
end
So I only ever index the columns, not the sets. Done right, this cuts down on book keeping.
Final remark: I don't need to implement the last step of Eller's algorithm, which is to finish the maze. The maze just keeps going and is as practically infinite as Factorio's map itself:
https://wiki.factorio.com/World_generator#Maximum_map_size_and_used_memory
Hope that made some sense!
