Log In now to add this Gigapan to a group gallery.
Log In now to add this Gigapan to a gallery.
About This Gigapan
Toggle- Taken by
- Devedse
- Explore score
- 1
- Size
- 274.88 Gigapixels
- Views
- 20220
- Date added
- Apr 11, 2015
- Date taken
- Apr 14, 2014
- Categories
- experimental
- Galleries
- Competitions
- Tags
- maze programming image generation algorithm backtrack efficient c# csharp
- Description
-
Hey all, I've been working on a maze generator as a side project for quite some time now, it's open source and can be found here:
github.com/devedse/DeveMazeGenerator
.
During the last few weeks I've changed my code to be able to generate even bigger mazes.
.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
.
Some statistics about this maze:
Size: 524.288 pixels * 524.288 pixels
Size in GB when every pixel takes 1 bit (not byte): 32 GB
Generation time: 17930 seconds (4,98 hours)
Time to find the directions: 8203 seconds (2,28 hours)
Count of directions: 205.913.715 junctions
Time it took to determine path based on directions: 956 seconds
Path length: 6.656.172.313
Path size if we would have to store it in memory completely (Per step 4 bytes for X, 4 bytes for Y, 1 byte for color): 55,39 GB
Time it would take to walk the path at 5 steps per second: 43,28 years
Time it took to save maze to PNG: 433077 seconds (120,29 hours or 5,01 days)
Size of PNG image: 77,4 GB
Time it took to upload: 2 days and 23 hours
.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
.
Some explanation about the algorithms used:
The algorithm that was used to generate this maze is the BacktrackingAlgorithm. Normally this algorithm stores the complete path is traversed, because this would take way too much memory though I have created a way that it only stores a small 2 bit direction for every junction it created. Besides this the algorithm also uses a way to only have the part of the maze it's working on in memory. This means that if a certain area of the maze is not being written to/read from for a while it will write it down to disk to make sure we don't have to keep the complete maze in memory.
.
To find the path I used a similar aproach with storing the directions only. First the pathfinder does a DepthFirst search to find the path using the directions way of storing it (this is faster then A* because there's just one possible path so heuristics are not really required).
.
The storage of the maze has to be done line by line. But since we can't store the complete path in memory we have to take subsets of this path for every x lines (60.000 in this case). This means that every 60.000 lines we are going to re-determine the path based on the directions and only store the path positions with an Y value of >= 0 and < 60.000 (or the second time it would be >= 60.000 and < 120.000). This way we only ever store a part of the path in memory and can simply sort this partial path on Y and X coordinate so that we can write it when we're doing the line by line PNG writing.
Gigapan Comments (0)
Toggle Minimize gigapan_comment