search

sraaphorst / spelunker

Maze generation and solving library
Other
11 stars 2 forks source link

Maze-shrinker: minimal representation of a maze as a graph #120

Closed sraaphorst closed 6 years ago

sraaphorst commented 6 years ago

Write an algorithm that takes a maze and shrinks it down to the minimal graph that describes it. This will consist of:

  1. One vertex for all cells of degree 1, 3, and 4: 1 represents a dead end, 3 represents a T juncture, and 4 represents a + juncture.

  2. Edges as appropriate, with weights being the number of cells in the original maze.

sraaphorst commented 6 years ago

This will provide plenty of statistical information: number of dead ends, number of junctures, numbers of passageways, compression size, etc.

sraaphorst commented 6 years ago

This was largely accidentally checked in as #119 tasks, and is a duplicate of #128. SquashedMaze and RoomFinder accomplish this task.