3 ms·

I wonder which algorithms are most easily generalised to three or more dimensions. Also what would be the best way to visualise and navigate a 4d maze? I can im

by n4r9 7y ago

I wonder which algorithms are most easily generalised to three or more dimensions. Also what would be the best way to visualise and navigate a 4d maze? I can imagine one where the maze structure changes as you go forwards or backwards in time, and in each cell you may or may not be able to time travel. The number of time coordinates wouldn't have to be very large to make this fiendishly difficult.

zentiggr 7y ago
That 4d structure sounds like a very steep jump in complexity. I love it, and I imagine I might never finish one.
- n4r9 7y ago
  Having slept on this, the biggest issue I have with my idea is that there's no easy way to have an overarching view of the whole maze, across all time. In the classic 2D maze you can view the whole thing at once which makes finding the solution easier. If you restrict a 2D maze so that you can only see one cell at a time, that already ramps the difficulty way up without any need for extra dimensions.
gliese1337 7y ago
Anything based on graph traversal generalized trivially. And any maze-generation algorithm by definition will generate a spanning tree, so you can always post-process the generated trees to re-embed the graph in an arbitrary number of dimensions. For https://github.com/gliese1337/M4ZE.js https://github.com/gliese1337/M4ZE.js (a prototype 4D maze navigation game), I used a 4D specialization of Prim's algorithm. There is no time travel involved--it's just straight-up 4 fully equivalent spatial dimensions, with full 4D maneuverability and no privileged directions. At any given time, the maze is visualized as a 2D projection of a 3D hyperplanar slice through the maze, and one type of control action is to rotate your viewing hyperplane. It is actually far easier to navigate than I initially thought it would be when I started working on it. I recently implemented a 4pi-steradian all-around view to make it a little bit easier, but the bump in navigation ease is minor (though I kept it because it's cool, and allows for tricks like running the maze entirely backwards). User testing so far indicates that kids and teenagers adapt to it quite quickly, while most adults have significantly more trouble.
- n4r9 7y ago
  Cheers for the input, that's really interesting. I'm not much of a javascript bod but if I get some time I'll install npm and then have a go =]

by n4r9 7y ago

zentiggr 7y ago

That 4d structure sounds like a very steep jump in complexity. I love it, and I imagine I might never finish one.

n4r9 7y ago
Having slept on this, the biggest issue I have with my idea is that there's no easy way to have an overarching view of the whole maze, across all time. In the classic 2D maze you can view the whole thing at once which makes finding the solution easier. If you restrict a 2D maze so that you can only see one cell at a time, that already ramps the difficulty way up without any need for extra dimensions.

gliese1337 7y ago

Anything based on graph traversal generalized trivially. And any maze-generation algorithm by definition will generate a spanning tree, so you can always post-process the generated trees to re-embed the graph in an arbitrary number of dimensions. For https://github.com/gliese1337/M4ZE.js https://github.com/gliese1337/M4ZE.js (a prototype 4D maze navigation game), I used a 4D specialization of Prim's algorithm. There is no time travel involved--it's just straight-up 4 fully equivalent spatial dimensions, with full 4D maneuverability and no privileged directions. At any given time, the maze is visualized as a 2D projection of a 3D hyperplanar slice through the maze, and one type of control action is to rotate your viewing hyperplane. It is actually far easier to navigate than I initially thought it would be when I started working on it. I recently implemented a 4pi-steradian all-around view to make it a little bit easier, but the bump in navigation ease is minor (though I kept it because it's cool, and allows for tricks like running the maze entirely backwards). User testing so far indicates that kids and teenagers adapt to it quite quickly, while most adults have significantly more trouble.

n4r9 7y ago
Cheers for the input, that's really interesting. I'm not much of a javascript bod but if I get some time I'll install npm and then have a go =]