A* Algorithm – Group 3


A* 3 group:

Bordon, Catalano, Nicolini, Noulis.

At the beginning of this project, we asked ourselves in what way we could explain the A* algorithm so as to be innovative and different than usual. Therefore, we decided that we wanted to avoid the old-school approach, where a teacher is explaining the theory of an abstract concept, such as algorithms, with the traditional written approach.

Furthermore, our goal was to make our topic understandable also by people without a computer science background. For this reason, we have created an application that focused on the didactic aspect.

Our program is aiming at introducing and explaining the path planning algorithm A* (3) by showing its evolution from other basic algorithms, such as Breadth-First Search (2) and Dijkstra. To achieve this, we exploited Unity to create a 3D environment, where someone can learn how the algorithms work, and play with them.

At the beginning, using Unity we created some short animations where the most important steps of each algorithm are highlighted. Then, we recorded these animations in video format, incorporating text guidelines with a more detailed voice description in background, in order to achieve the maximum understanding from our audience. For the creation of the anthropomorphic voice, we used Amazon Polly, a web service that turns text into mp3 files. About the backend code behind the Unity application, we created classes for the creation and configuration of the square grid, for the implementation of the path finding algorithms, using priority queues, cells weights and heuristic approaches. For the animations the timeline feature of unity has been used.

To wrap this all together, we used Unity to create a total of four scenes, one for each algorithm, and a main menu scene. In main menu scene (1), the user can decide which algorithm to explore among the three mentioned above or to have a first theory introduction about some general concepts.

Each algorithm scene has the same structure: at first, the video explanation introduces the algorithm, how it works, its benefits and drawbacks; then the user passes to the “game mode” phase, where he/she can practice with the algorithm by playing on a grid and see how it is performing in the searching of the best path from an initial to a goal position. The mining environment has been added as a background environment in the game mode to emphasize that the presented algorithms can be used in a mine.


Lascia una risposta