Isn’t it A-mazing!?


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

Image and caption from unmuseum.org

Paul Lucas sketched this drawing of the supposed remains of the Egyptian Labyrinth in 1700.

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)

Map Showing relative location of Crocodilopolis (alt image credit)

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 Terms
Definitions based on Branching
Unicursal Maze without branches. Sometimes called a circuit maze.
Multicursal Maze with branches and dead ends.
Maze Anatomy
Branch A path inside a maze.
Island A section of the maze containing walls not connected to the external wall of the maze. Sometimes also referred to as a detached wall.
Blind Alley Branch that has a dead end.
Hub An enlarged area inside the maze with multiple choices of branch leading in/out.
Types of Maze
Braid Maze A type of maze with branches, but without dead ends. All branches loop back to other branches.
Perfect Maze Maze with no islands or isolated sections. A perfect maze has only one solution.
  Delta Maze Maze consisting of interlocking triangles.
  Orthogonal  A type of maze composed of square cells.
Plainair Maze A maze on something other than a flat surface. For example, a maze painted on the outside of a cube or sphere.
  Sigma  A type of maze composed of Hexagons.
  Theta  A type of maze composed of concentric circles.

Maze Code Samples

 Source Type Article Type Lang. Sample Image
2D MSDN tutorial C#
2D CSharpCorner Maze Generation C#
2D HWS Math & CS Sample Java
3D Falstad  Sample  Java
3D jsmadeeasy  Sample  JavaScript  Ascii output
3D threejs  potential  JavaScript

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.

Tower Defense

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.

— and since I don’t have a rational place to close this discussion so I will just present you the exit:

Advertisements

About Larry Louisiana

I'm a Microsoft Partner Consultant.
This entry was posted in Digest, Game Development, Math, Review & Comparison and tagged , , , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s