Maze Generator/Validator/Solver
-
source: Jared Hopf, 2003
Description:
Grog's Dungeon and Labyrinth Excavators is looking to expand and improve its business. Grog is wanting to have some method of designing state of the art dungeon maps to give to his goblin excavator teams for creation of his clients. Grog wants to be able to create dungeons that utilize every possible section of space available so that there are no sections of a created dungeon that are not accessible. Grog also insists that each dungeon made is a complete dungeon in that you can enter and leave the dungeon as well. Some sample dungeons that Grog has hand made are as follows:
- ********************
- * ** * * Dungeon Key:
- * * * * * **
- * ** * * * *** * E - Entrance
- * * * * X - Exit
- * * ** * * * - Wall
- * **
- ** * *
- *** * * *
- ** ** * * **
- **** * * * * *
- ** X ** ** *
- * * * * E *
- ** * ** * * **
- * * ***** *
- * * * * *
- * * ** * ** * * *
- * ** * * *
- * **
- ********************
|
Some examples of a maze that is not valid for Grogs purposes is of the following in that not all areas of the dungeon are not accessible.
- ******************** *****************
- ** ** * * * *X * * * * * E*
- ** * * ** * * **** ** ** * * ** * **
- * ** ** * E***** * * * * * * *
- **** * * * * ** ** ** ** **
- * * ** * * * * ** * *
- * * X * ** * *** * *** **
- ** * * * * * * *
- *** ** * * * * *
- ** ** * ** * ** *****************
- **** *** * * * *
- ** * ** ** ***
- * * * *** * *
- **** ** * * **
- * * * ***** * *
- * * * * * *
- * * ** * ** * * *
- * ** * * * * *
- * ** **
- ********************
|
- Requirements:
- Grogs minimum requirements for a solution are:
- 1. Creation of an N X N maze (Max size 30 X 30).
- 2. The ability to enter previous hand made maze designs.
- 3. The ability to determine if a given maze is solvable.
- 4. Display of mazes, and their solutions.
- Additional/Optional requirements:
- 1. Ability to save/recall dungeons.
- 2. Being able to validate an entire dungeon is accessible.
- 3. Creation of variable sized dungeons (M X N, any size.)
- 4. Find the optimal solution for the Dungeon.
- 5. Create a series of linked dungeons and determine if the collection of dungeons are solvable.
- Concepts:
- 2D Array access.
- Random Numbers.
- Recursion (Solving and Validating Maze)
- Input/Output.
- General Class fundamentals.
- Optional Concepts:
- Iterative Solution. (State of the Maze, Stacks)
- Pointers and memory allocation.
- File I/O.
