Maze Algorithm For Solving Difficult 2D and 3D Mazes

Showcase
1

Hello Three.js Community!

Over the past few months, I have been building an open-source maze-solving algorithm that can accept dynamic inputs and produce dynamic outputs. It can also auto-generate complex animations for the viewer. More information can be found in the setup tutorial.

You can find it on NPM as maze3d.js

It uses a breadth-first search in order to navigate a 3D matrix, finding the shortest possible route. The package can generate both static models and animated models that use spotlights with togglable shadows. This demo only showcased cubic mazes, however, the 3D matrix can be swapped (as long as it is formatted correctly) for any combination of barriers to solve for any shape. This is the basis of another project I am working on.

When this project first started, I didn’t know anything about Three.js or modeling on the web. Over the past 8 months, I have been working with Three.js, React, and React-three-fiber to start on some awesome projects.

Here is a Youtube Video showcasing some basic solves: Maze Algorithm Solving Increasingly Difficult 2D and 3D Mazes - YouTube. The program can do much more than what is in the video.

Here is the Youtube Video explaining how to set up the NPM package. The first few minutes of the video showcase how to use the demo below: maze3d.js - Dynamic 3D Maze Solving Algorithm - YouTube

Warning: Generating animations takes an extreme amount of ram. For some larger mazes (45x45x45) it still takes 10 seconds with my 32 GB of ram + 8 GB vram.

I am currently working on a more complex project that also works in voxels. This is my first ever NPM package and my first large-scale JavaScript project. It took months to do and tons of your help.

1 Like
2

Hey, nice work! I left a comment on your youtube page also. Regarding how much memory it takes to save your animations, did you know that you could save one frame at a time as a sequence of images using CCapture? I’ve used it before and would be glad to help if you do give it a try.

Also, I just released a game that may make use of your maze finder algorithm! Check it out (and give it a star on Github!): Retro-futuristic tank game - SYNTH*BLAST

1 Like
3

Thank you for the feedback!

CCapture is very cool. I have always thought about simply making a method to save mazes as an image file, but the ability to record the canvas in non-real time to then create a smooth animation is amazing.

Since CCapture works in the render cycle, it is up to the client in order to set it up for more high-powered renders. The biggest issue I have encountered is that the generation of the animations is massively taxing on the client’s computer. Some of the animations for the video took 10 or more seconds to generate. This is because every single slice has its own animation mixer and material. Even with instance meshing, this still produces a significant amount of performance drop. Otherwise, I am able to play the animation back without a performance issue.

One solution is to pre-compute the animations before the users need them in a game, and then simply play them back when needed. This would give the downside that the user cannot change the maze directly, only see a pre-computed animation.

Three.js is an API of WebGL, which is an API to OpenGL ES, which is an API to OpenGL, which is an API to the GPU. When you have this level of abstraction, performance will drop even with optimizations.

The Animation API for my library needs some work. It took 4 rewrites to get working to the form it is now, and I still have issues with height-layer slices going from top to bottom instead of bottom to top. The animation function doesn’t sort layers if they are on the same slice type (all height-layer slices) if the layers are from a different component of the maze. However, It will be cool to see what others could do with this concept of animating the processing of various algorithms.

The algorithm for solving is the fastest it can possibly be because it can see the entire maze at once.

Currently, I am working on another large project for generating 3D voxel objects with a convex hull shell algorithm. The maze3d.js library can be updated if I think of any large changes and have the time. I only started working with Three.js, node.js, React and R3F this year, so working on my first large project has been a learning curve.

Excited to see what you can do with this! Keep me updated if you implement this in your game.

1 Like
4

Just stumbled into this now. Very cool. My interest, though, is more in the maze solver than the associated 3D graphics. I’m wondering if it could be adapted to solve a different problem - a problem I state as “extrication”. What do I mean? Very simply, a solver for getting something completely out of a complex and cluttered environment. Let’s say I have a cluttered 3D environment with all sorts of objects lying around in space. The objects can be of different sizes and shapes, can be close to one another or far apart. Now, suppose I want to pick one of these objects and see if I can extricate it completely from this 3D environment - without colliding into the other objects. Can the solver show me the extrication path? That’s the problem statement - more or less. Would be grateful to hear thoughts and comments from this 3JS community…Thanks much…OLDMAN

5

This might become the ultimate generalization in 3D for the Moving sofa problem.