Pathfinder - a simulation to explore Dijkstra, A*, and heuristic algorithms

This simulation was a lot of fun to write, and my class had fun using it.

First, run the executable. Select one of the three 'scenarios' and hit Start, then hit Reset, change the Algorithm, and run again. As well as the visual rendering of the nodes visited, and the final planned path, the window shows the path length and the total nodes visited. (Note that the robot can move one square only at a time, orthogonally or diagonally - but a diagonal move has a path length of the square root of 2.

(Parenthetical comment: Is A* a heuristic approach? I think it is, but it would not fit the AQA exam board definition - because A* is guaranteed to produce the optimal result, provided that your estimation of the cost-to-destination is guaranteed to be less than or equal to the actual cost, which is not hard. I realise that A* is not on the AQA specification, but it is on OCR's, I think).

If you have time and your pupils read C# or VB then explore the source code in either language, and try modifying it. Here are a few interesting questions:

1. Does the GridGraph class use an Adjacency Matrix or an Adjacency List to hold the edges? A: Neither: it does not even store the edges, but calculates them as needed. Discuss why this works and is a good design here.

2. How does the graph represent the 'obstacles' (fences, rocks)? A. It doesn't! The 'obstacles' are just the absense of navigable points on the grid. Hence none of the algorithms can be described as 'wall following'.

3. Try creating your own scenarios (e.g. a conventional maze - or you might even create a maze automatically using a maze-generation algorithm). All you need to do is create a new instance of the class Scenario, and add an instance of it to the list in the Scenarios.AllScenarios() function - the GUI will pick it up automatically.

4. Look at the implementations of the three algorithms (in the GridGraph.NextNodeToVisit method). What are they doing? Try modifying the algorithm, or even adding a new one, by adding a new value to the Algorithms Enum and then writing the line(s) of code in NextNodeToVisit .

5. As the 'Rocky field' (Mars rover ?) and Fences scenarios use a random generator - they will produce different maps each time you run the simulation (though not between changes of algorithm). It is possible therefore that they could produce a disconnected graph - where there is no path from source to destination. The simulation should make clear what has happened. How does the simulation detect this situation?

Implementation note: My preferred style of coding is to separate a program like this into multiple projects keeping the GUI, the domain model (graph & algorithms), and data fixtures (scenarios) in separate projects - and have plenty of tests. I have melded them into one project here for simplicity of running, and to allow the algorithm to update the display directly (not great practice but simpler to follow in this case).

Level: A-level

Duration: A few minutes (for using the simulation), up to one double lesson if you explore and modify the source code

Teaches: Dijkstra's shortest path algorithm, A*, heuristic approach (that generates non-optimal result, but very fast), alternative approach to implementing a graph