A Star Search Algorithm by Vladdd97 - 1

AI

[APA ] Course Project at Design and Analysis of Algorithms. A* ( pathfinding algorithm ) implementation in C# (unity)

Unknown VersionUnknown LicenseUpdated 101 days agoCreated on February 20th, 2018
Go to source

Course Project at Design and Analysis of Algorithms

About project

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 .

Unity part

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

Show all projects by Vladdd97