Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

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

Closed
sraaphorst opened this issue Jun 25, 2018 · 2 comments
Closed

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

sraaphorst opened this issue Jun 25, 2018 · 2 comments
Labels
enhancement New feature or request shared Code common to all libraries squashedmaze A squashed representation of a maze into a minimal graph.

Comments

@sraaphorst
Copy link
Owner

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 sraaphorst added enhancement New feature or request shared Code common to all libraries labels Jun 25, 2018
@sraaphorst sraaphorst mentioned this issue Jun 25, 2018
Merged
@sraaphorst
Copy link
Owner Author

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

@sraaphorst sraaphorst changed the title Graph-shrinker: minimal representation of a maze Maze-shrinker: minimal representation of a maze as a graph Jun 25, 2018
@sraaphorst
Copy link
Owner Author

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

@sraaphorst sraaphorst added the squashedmaze A squashed representation of a maze into a minimal graph. label Jul 4, 2018
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
enhancement New feature or request shared Code common to all libraries squashedmaze A squashed representation of a maze into a minimal graph.
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@sraaphorst