My maze generator written in C#, highly optimized to generate huge mazes (128.000x128.000 for example), find the shortest path and then save it all to an image. In the latest version I've also added a MonoGame project to render the mazes in 3D (also works on android)
Currently the fastest algorithm is "AlgorithmBacktrack" with "BitArreintjeFast". If you want a fast maze, use that ;).
If you want to create a MASSIVE maze take "AlgorithmBacktrackSmartMemory" as algorithm and "Hybrid" as InnerMap (I'm talking about MASSIVE 512.000x512.000 and bigger) (It's about 40% of the speed of the AlgorithmBacktrack with the BitArreintjeFast innermap but uses almost no memory).
Above, a 4096*4096 maze (Generated in 0,5 seconds)
The largest maze I generated and saved was 262.144*262.144. It can be found on the following website: http://gigapan.com/gigapans/161644
- Generate mazes
- See them being generated live
- See pathfinding live
- Save them with or without path (to png, bmp, jpeg, etc)
- Calculate walls (can be used to draw maze in 3d, I also have a sample of this if anyone is interested)
- A GUI application with all kinds of buttons that do things
- Different inner storage formats (Highly optimized BitArray, the normal .net BitArray, a Boolean array, a directly mapped on the hard drive and a Hybrid storage format (see below))
- On a hard drive with 2TB you could theoretically generate a maze of the following size (This will take weeks / months to complete though):
SQRT(2000000000000*8)=4000000, so a maze of about 4 million * 4 million
- See the % of a maze being generated by using the callback (See the GUI application for an example, The HUUUGE maze button)
- Added button to get the walls from a maze and draw them, I sort this list in very unique ways for cool effects :P
- Added a new project for 3D mazes
- Add like 8 other maze generation algorithms (Kruskal, prim, eller, division, etc)
- Enums are default ints, this means they take up 32-bit (or 4 bytes) in memory when placed in an array.
- 64-bit projects can use way more memory.
- You can use the option "AllowVeryLargeObject" to allow bigger objects.
- Booleans are 1 byte in memory size.
- A BitArray can be used to store 8 booleans in 1 byte.
- How to implement different maze generation algorithms.
- How to profile code in Visual Studio.
- How to create images without wasting memory when creating them.
- Writing callbacks with Actions.
- That the Random class is not Thread safe :/.
- How to write my own pathfinder that's faster then A* (It finds "a path" which is always the shortest since the mazes have only 1 path)
- How the garbage collector won't collect all garbage sometimes (when generating loads of mazes multithreaded for a long time)
- How you can use 2 bits to store a direction where you came from with BitShifting
- Lot's more
My nickname is Devedse, I did this project for fun and to learn more about C#. If anyone is interested or has any questions you can send me a message :).
- AlgorithmBacktrack (100%) (Fast, cool mazes, very low memory usage)
- AlgorithmBacktrackSmartMemory (100%) (About 70% of the speed of AlgorithmBacktrack but uses about 0,1% of the memory for storing the path while generating internally)
- AlgorithmKruskal (90%) (Average speed, cool mazes, high memory usage)
- AlgorithmDivisionBreadthFirst (30%) (Not done)
- AlgorithmDivisionDepthFirst (30%) (Not done)
- AlgorithmEller (30%) (Not done)
- AlgorithmPrim (30%) (Not done)
- AlgorithmPrimCenter (30%) (Not done)
- AlgorithmHuntKill (30%) (Not done)
The AlgorithmBacktrackSmartMemory only saves every junction in a maze when generating, at these junctions only the previous direction is saved, so only 2 bits are needed per junction. Junctions occur only every 50 steps, this reduces memory by about 50 times. Also this algorithm saves these with bitshifting, this reduces the memory usage even further to about 0.1%.
- BooleanInnerMap (Memory usage = n, Speed = 100%)
- BitArreintjeFastInnerMap (Memory usage = n/8, Speed = ~90%)
- DotNetBitArrayInnerMap (Memory usage = n/8, Speed = ~80%)
- BitArrayMappedOnHardDiskInnerMap (Memory usage = 0, Speed = ~0,2%)
- Hybrid (Memory usage = like 20 mb max with default settings, Speed = ~50%) This hybrid map divides the maze in a number of parts (a grid). Each part will be loaded into the memory when needed and written to the disk if possible too. This really is the best way to generate REALLLYYY REAALLLLYYYYY big mazes pretty fast. (This only works well with AlgorithmBacktrackSmartMemory though because the other algorithms have more overhead)
The steps I took for minimal memory usage (Focussing mainly on AlgorithmBacktrack and eventually AlgorithmBacktrackSmartMemory):
- I first created this maze generator where it used an enum for every point in the maze, solid or not solid. (32 bits per point)
- The first issue I ran against was that the memory was overflowing when generating big mazes, I changed the execution from 32bit to 64bit and in the App.config I allowed VeryLargeObjects.
- I changed this enum to a boolean (8 bits per point)
- I started to use BitArray's (1 bit per point)
- I created my own implementation of the BitArray that's faster then the one from C# and used "MethodImpl(MethodImplOptions.AggressiveInlining)" (20% speed increase)
- I optimized out some code in the AlgorithmBacktrack class and started using an Array which gets reused for finding the next destination (10% speed increase)
- I then chose to create a new implementation of the InnerMap that stored the maze completely on the hard disk sacrificing speed for 0 memory usage.
- This resulted in a very slow solution. That's why I then chose to create the Hybrid map, it loads only 10 parts of the maze it's currently working on in memory, so the memory usage stays really low while still maintaining about 50% of the original speed.
- The issue I ran into after this solution was that the stack used by the AlgorithmBacktrack was actually using the most memory. That's why I retought the solution and created a stack which only stores junctions instead of every point while generating a maze. These junctions are stored as a direction to the previous point we came from (for example top if we came from the top). Since we only have 4 values here we only need 2 bits to store these values. That's why I created the "QuatroList" and "QuatroStack" which stores an int between 0 - 3 in only 2 bits.
- After all these optimizations the Hybrid map only uses 20mb memory max and AlgorithmBacktrackSmartMemory uses about 0.1% of the memory the stack used previously.
If you have any issues, questions or just want to talk to me, throw me a message and get in contact with me :).