An Introduction
The A* algorithm is a best-first search, which means it aims to find the cheapest path to the goal. To do this it relies on the problem space being represented as a weighted graph – a common practice in computer science fields. From a starting graph A* originates at the start node and expands out until it reaches the destination or exhausts all options. Building and maintaining a tree by simply looking at path options one edge at a time sorting options based on distance and heuristic costs.
A man I know once said: “If you can implement the A* algorithm, then you’re a programmer.” There is actually a lot of truth in that statement because it isn’t a trivial thing to do as a human being. Yet, as a programmer it isn’t exactly the most challenging thing you could do in the course of a day or two.
That man was Darren Reid – an instructor at NBCC. He wrote the steps to the A* algorithm on a class whiteboard. He instructed the class to individually implement the algorithm as written on top of a previous assignment which could randomly generate mazes of various sizes. A carefully calculated task to provide his students a challenge, and for those successful provide a level of confidence going forward that would provide a little grit when things got more difficult.
Description
Objectives
- Implement A*
- Test implementation using a previously implemented maze generator
- Compare different STL containers
- Insert new nodes to sorted position
Highlights
Successes
- Multiple A* implementations using preprocessors to select differing containers.
- Inserting new nodes to their sorted location in the Open List.
Challenges
- Debugging code that would work for one implementation and fail under another.
- Realizing there was a bug in the maze generator that created an edge case segfault.
Results
I was able to implement the algorithm faster than anyone else, so I took it upon myself to test different containers for the Open and Closed lists. Though I don’t have documentation of the result, and haven’t bothered to re-run them even though the code functions just fine present day. I’d reckon that the differences in run time were fairly marginal, and if there were clear front runners I’d bet they were what I left enabled (i.e. std::unordered_map for the Closed List, and std::vector with sorted_insert for the Open List).
If I were to ever modify, or rewrite this, I would change the results displayed to show the maze and the path found through it. Secondly, I’d redo the meta-programming and use templates as much as possible to avoid preprocessor logic.
Hypermaze
Shirly
Rover Recursive Pathfinding
Cheryl Engine
Orthanc Filter
