Imagine a grid of cells where the cells have data about which direction you can move through (a wall or an empty space). I typically do this just with x/y axis but it can be expanded to be n-dimensional using all the same concepts. There’s no need to store complete data in every cell though. For instance a cell that has information about if there is a wall in the positive x direction would overlap with its neighbor’s data about if there is a wall in it’s negative x direction. So the cells only need to contain 2 bits of information, for example ‘is there a wall in the positive x axis’ and ‘is there a wall in the positive y axis’, and the information about if there is a wall in the negative x/y axis can be determined by checking the neighbor in that direction. For a 2d maze you can store this info in a bit array and treat it like a 3d array (x axis, y axis, the two walls). Visually a single cell is rendered as a 2x2 but one of the spaces is always a wall, one is always a path, and the other two are the variables. To render a full maze you need to also add an extra containing wall on two of the sides or it’ll look chopped but that’s visual only no data needs to be stored about that. So a maze that is 100x100 ‘choices’ in size would be rendered like a grid that’s 200x200 and take only 1.25kb of memory. Here’s a C++ implementation of this concept using a vector<bool> as the bit data structure. Let me know if you also want pictures of the different steps, completed mazes, or the nonsense you can do by extending it to 3 dimensions to build a nearly impossible to solve maze pyramid in a game
Oh shit, how do you do it?
Imagine a grid of cells where the cells have data about which direction you can move through (a wall or an empty space). I typically do this just with x/y axis but it can be expanded to be n-dimensional using all the same concepts. There’s no need to store complete data in every cell though. For instance a cell that has information about if there is a wall in the positive x direction would overlap with its neighbor’s data about if there is a wall in it’s negative x direction. So the cells only need to contain 2 bits of information, for example ‘is there a wall in the positive x axis’ and ‘is there a wall in the positive y axis’, and the information about if there is a wall in the negative x/y axis can be determined by checking the neighbor in that direction. For a 2d maze you can store this info in a bit array and treat it like a 3d array (x axis, y axis, the two walls). Visually a single cell is rendered as a 2x2 but one of the spaces is always a wall, one is always a path, and the other two are the variables. To render a full maze you need to also add an extra containing wall on two of the sides or it’ll look chopped but that’s visual only no data needs to be stored about that. So a maze that is 100x100 ‘choices’ in size would be rendered like a grid that’s 200x200 and take only 1.25kb of memory. Here’s a C++ implementation of this concept using a vector<bool> as the bit data structure. Let me know if you also want pictures of the different steps, completed mazes, or the nonsense you can do by extending it to 3 dimensions to build a nearly impossible to solve maze pyramid in a game
Oh, sweet! Thanks for actually writing this out, its cool!