Course Project at Design and Analysis of Algorithms
This is my (DAA) courser project [ year-II , semester- I] . It is about A* (pathfinding algorithm) . The project was made in unity ,code was written in C# .
How to run
- You have to make a new project in unity
- Download Assets
- Replace this Assets with the Assets you have in the new created project
- It’s done , now just run the project in unity .
In unity you will see 4 scenes.
The first scene 1)ShowPath is jut for finding the best path from seeker (blue sphere) to target (green sphere).
- white squares is free nodes, seeker can pass through them.
- red squares is obstacles, seeker can’t pas through them, it has to go around them.
- gray squares is all nodes which were taken in consideration during execution of A* algorithm.
- black squares is the best path from seeker to target.
To have the possibility to see just nodes, without obstacles and seeker, or target, you have to go to Scene window and to disable the objects visibility.
Scenes 2,3 and 4 is for visualizing how seeker moves to target. There you will find the different labyrinths and will have the possibility to see how A* works. For that just run the project and press SPACE button.
A* pseudo code
OPEN //the set of nodes to be evaluated CLOSED //the set of nodes already evaluated add the start node to OPEN loop current = node in OPEN with the lowest f_cost remove current from OPEN add current to CLOSED if current is the target node //path has been found return foreach neighbour of the current node if neighbour is not traversable or neighbour is in CLOSED skip to the next neighbour if new path to neighbour is shorter OR neighbour is not in OPEN set f_cost of neighbour set parent of neighbour to current if neighbour is not in OPEN add neighbour to OPEN