Skip to content

Home

Jump to bottom
Vincent Y edited this page Mar 23, 2023 · 2 revisions

Maze Solver Wiki

The provided Python code defines a module that contains two classes for solving mazes: BFSMazeSolver and AStarMazeSolver. These classes implement the Breadth-First Search (BFS) and A* algorithms, respectively, to find the shortest path through a maze.

Invert Dictionary

The invert dictionary contains key-value pairs representing opposite directions. This dictionary is used to reverse the direction of movement when navigating through the maze.

BFSMazeSolver

The BFSMazeSolver class is a Breadth-First Search (BFS) implementation to solve a maze. It takes in a maze dictionary, a start room, and an end room as input. The solve() method is called to find the shortest path from the start to the end room.

Methods

  • __init__(self, maze, start, end): Initializes the BFSMazeSolver object with the maze, start room, and end room.
  • _find_end(self, moves): Checks if the current position in the maze is the end room.
  • _valid(self, moves): Determines if the given moves are valid in the maze.
  • _navigate_maze(self, current_loc, move): Moves in the given direction from the current location and returns the new location and a boolean indicating if the move was valid.
  • solve(self): Solves the maze using BFS and returns the shortest path as a string of directions.

AStarMazeSolver

The AStarMazeSolver class is an A* algorithm implementation to solve a maze. Like the BFSMazeSolver, it takes a maze dictionary, a start room, and an end room as input. The solve() method is called to find the shortest path from the start to the end room.

Methods

  • __init__(self, maze, start, end): Initializes the AStarMazeSolver object with the maze, start room, and end room.
  • __get_neighbors__(maze, curr): Returns a list of neighboring rooms for the given room.
  • __heuristic__(self, curr, end): Calculates an estimate of the cost from the current room to the end room.
  • __reconstruct_path__(came_from, current_node): Reconstructs the path taken by the algorithm to reach the current node, returns a string of directions.
  • __neighbor_nodes__(self, room): Returns a list of neighboring rooms and their corresponding directions for a given room.
  • solve(self): Solves the maze using the A* algorithm and returns the shortest path as a string of directions.

Usage

To use one of the maze-solving classes, first create an instance of the class, passing in the maze, start room, and end room. Then, call the solve() method on the instance to find the shortest path through the maze.

Example:

maze_solver = BFSMazeSolver(maze, start, end)
shortest_path = maze_solver.solve()
print(shortest_path)
maze_solver.start = "new room ID"
maze_solver.end = "new room ID"
another_shortest_path = maze_solver.solve()
print(another_shortest_path)

Clone this wiki locally