This is the blogpost for our “Robotic’s Perception and Action”‘s project about the A* algorithm, we will briefly explain what its intent was and in what ways we tried to convey that.
The main object of our work was to create a fully self-contained lesson about A*, such notion can be summarized in these points:
- No necessity to consult other sources of information to get a well rounded and complete understanding of the subject
- A clear flow to the lesson tied with the ability to navigate freely though its parts to find easily what the user is interested in
- An easy enough explanation of the subject aided through the use of Unity’s features to explain visually concepts not so well carried through text
- The ability to test the concepts shown in the lesson to achieve a deeper understanding of them
To implement these concepts, we opted to divide the lesson in three subparts, one explaining the theory regarding the algorithm (Theory), one letting the student experiment with the workings of A* and other algorithms (Simulation) and one to show in a lively manner its efficacy (Play). Moreover, the totality of the experience has a clear and playful theme, as the learner is put in the shoes of a mine owner with the objective of improving his venture.
As the user presses the “LEARN” button, he is sent to the theory environment.
In this scene we’re put in a mine environment and at its center a mining cart moves along a rail. The “learning path” is marked by crystals which the user will follow along driving the cart. Slides on the subject are introduced each time the user reaches a crystal. The explanation takes advantage of animations that show the peculiar aspects of each path-searching algorithm.
At any time during the theory explanation the user can return to the starting scene. When he reaches the end of the path he is given the choice to test his knowledge through the simulation section, or to verify A* capabilities through the play section.
In the simulation environment the user can interact with a 2D grid map by adding obstacles (Rocks) or painting textures which symbolize different types of terrain with different penalties associated. These are taken into account by Dijkstra and A* algorithms while searching for the path. Once the user has selected the algorithm, the starting point and the goal, he can “enter the algorithm brain” and have a simplified view over the calculation steps followed, thanks to specific tiles.
At last there is the gaming section designed for the user to challenge the algorithm (and his friends!!!!) and concretely see why it’s so efficient in path searching. But, who knows, a well prepared player may succeed against the AI.
There’s no need to waste more words about what can be shown in a simpler way: just download the executable and give it a go (the source is also available), we would love to hear your feedback!
Riccardo Bertollo (riccardo.bertollo AT studenti.unitn.it)
Lorenzo Paiola (lorenzo.paiola AT studenti.unitn.it)
Pasquale Romano (pasquale.romano-1 AT studenti.unitn.it)
Federico Santacatterina (f.santacatterina-1 AT studenti.unitn.it)