Assignment 12 - A* Maze

Source

This is a nifty assignment from 2008 proposed by Don Blaheta. Source

Learning Outcomes

Stacks
Queues
Shortest Path
Graphing

Goals

The purpose of this assignment is to learn to

Generate a random maze on a 2D Grid
Write the A* algorithm for traversing a grid
Display the algorithm at each step to the grid as it traverses the maze

Description

Tasks

Create a maze on a 2D grid. There are many maze algorithms
Write a pathfinder using the A* algorithm to traverse the 2D grid
Choose two points on opposite sides of the grid and use the pathfinder get from point a to b.
During each step in the algorithm color in the pathfinder's current position
After the goal is reached pop back and display the full path.

Create the maze

There are plenty of algorithms for generating a maze. Prims algorithms is a good place to start. Then create a grid to display the maze and keep track of the open positions and walls on the grid.

Create the pathfinder

Create a pathfinder that uses the A* algorithm to traverse the grid towards a goal point.

Extensions

Help