Learning Go (I) - A* Algorithm

Over the past year, I have been considering the idea of mastering Go, a programming language that has become notably relevant in recent times. Initially, I embarked on a project with this purpose in mind, but defying the advice shared in this article: Breaking It Down, its complexity exceeded my expectations, ultimately leading me to abandon it.

In order to rectify this experience, I have decided to start a series of smaller projects, designed to explore various aspects of Go and its frameworks in an agile and effective manner.

These projects will revolve around the A* algorithm. It is a pathfinding algorithm that I have implemented on multiple occasions, both in personal and academic projects, as well as in hackathons. In this context, I will prioritize technical aspects over functional complexity, allowing me to focus on achieving my objectives.

About A*

A* is a pathfinding algorithm used to find the shortest path between two points in a graph. It is widely used in games and robotics, it uses Dijsktra algorithm as a base, adding a heuristic approach to guide the search.

If you want to learn more about the algorithm, I recommend watching Sebastian Lague's video on the subject.

Objectives

The objective of this project is not to create the most efficient implementation of the algorithm, but to learn about the go programming language, data structures and project structure.

Results

The project is running and the algorithm is able to find the shortest path between two points in a simple grid.

There is room for improvement in many ways:

• The algorithm can be optimized to avoid performing unnecessary searches on some data structures.
• Probably using more sophisticated data structures would improve the performance of the algorithm.
• Some tooling would help to create different scenarios to compare the performance of the algorithm.
• It would be interesting to measure the performance of the algorithm in different scenarios and compare it with other implementations.
• Some testing would be nice to ensure the correctness of the implementation.

Some of these topics will be addressed in future projects, but for now, the objective was achieved.