While starting this research I noticed how many of these “maze” posts start with an explanation of just why you would be interested in mazes… and as I have nothing new to offer in that category, I will refrain from revealing my reasons, and dive right in…
History of Mazes and Labyrinths
So the idea of a “maze” goes back 4,000 years to the ancient Egyptians (specifically Amenemhat III ). Who, by the time of Herodotus, had created a great Labyrinth in the town Arsinoë (also known as Crocodopolis), about which Heroditus claimed :
“I found it greater than words could tell, for although the temple at Ephesus and that at Samos are celebrated works, yet all the works and buildings of the Greeks put together would certainly be inferior to this labyrinth as regards labor and expense.” –ref (more on Wikipedia) (more on amazeingart.com)
Another ancient writer Pliny wrote of the temple:
“.. banquet halls reached by steep ascents, flights of ninety steps leading down from the porticoes, porphyritic columns, figures of gods and hideous monsters, and statues of kings.” … “Some of the palaces are so made that the opening of a door makes a terrifying sound as of thunder. Most of the buildings are in total darkness.”
The resulting legacy has echoed through time, with ideas like the Minotaur’s Labyrinth in Knossos, populating the nightmares of Greek and Roman children, they have worked their way into Christianity, and were even a part of Native American religious traditions. Over time they have lost their ominous overtones and become more a thing of novelty such as the “footprint of a Colossus” in Gloucestershire.Today they are a form of entertainment for children and people trying to waste time (my own opinion). But what about the fundamentals?
Maze Code Samples
|Source||Type||Article Type||Lang.||Sample Image|
|2D||HWS Math & CS||Sample||Java|
Mazes in Higher dimensionality
Video Games like Portal (play flash version here) have taken the concept of a maze to an entirely new level, by introducing a virtual reality where Pirisannni and M.C. Escher would have felt right at home. A couple of interesting applications of higher dimensional spatial pathfinding puzzles are the movie Cube and the The Rotating Labyrinth (access to a playable version here)
Notice any similarities?
Creating the Maze
Because of the variability in Maze anatomy and dimensionality branching etc, there are a number of ways to generate mazes, however in my experience using randomness like this results in a boring sort of normality (think about probability distribution and you will see what I’m talking about). Pockets of “order” IMHO add to the confusion of the Human solving the puzzle. This can be seen in the Movie “Labyrinth” when the little creatures start messing with the protagonists “bread crumbs”.
Solving the Maze
Solving the maze (or any network problem) is one of the fundamental discreet math concepts. There are gaming variants of this problem primarily the A* Algorithms, and typically when solving a typical maze one is looking for the shortest path. Due to the structure of the solution space of this type of problem (no a priori structure per se) Maze solving algorithm’s typically do so by brute force exploration of the solution space. A graphical “tutorial” about longest/shortest path solving can be found at pathery.
The Tower defense game is in my opinion an inversion of the Maze concept where instead of the least longest path one is striving for the longest path. A sample of this can be seen at Pathery, but typically the game is centered around having a path, and then trying to introduce obstacles to that path, typically the path is exemplified by “living” units” (AI Agents) which can be killed by the sections of maze wall which are often offensive “towers”, some games from this category are Plants vs. Zombies, and Defense Grid.