Astar Unity

astar.cs

using UnityEngine;
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

public class AStar : MonoBehaviour
{
		public enum State
		{
				NOTDONE,
				DONEWITHPATH,
				DONEWITHOUTPATH,
		}

		public class LowestF : Comparer<GameObject>
		{
		
				public override int Compare (GameObject object1, GameObject object2)
				{
						NodeInfo Object1 = object1.GetComponent<NodeInfo> ();
						NodeInfo Object2 = object2.GetComponent<NodeInfo> ();
						if (Object1.F.CompareTo (Object2.F) != 0) {
								return Object1.F.CompareTo (Object2.F);
						} else
								return 0;			
				}
		}


		
		//pass this function the Information about our search space we are pathfinding
		//Entry point into the processing of astar
		public void DoWork (SearchSpaceInfo searchSpace, float pathSpeed)
		{
				
				_searchSpaceInfo = searchSpace;
				_spawn = searchSpace.StartNode;
				_destination = searchSpace.EndNode;
				_spawn.GetComponent<NodeInfo> ().Walkable = true;
				_destination.GetComponent<NodeInfo> ().Walkable = true;
				StartCoroutine (JankStar (_searchSpaceInfo, _spawn, _destination, pathSpeed));
				
		}




		private IEnumerator<YieldInstruction> JankStar (SearchSpaceInfo searchSpace, GameObject spawn, GameObject finish, float pathSpeed)
		{
				
				_currentState = AStar.State.NOTDONE;
	
				List<GameObject> OpenList = new List<GameObject> ();
				HashSet<GameObject> ClosedList = new HashSet<GameObject> ();
				
				GameObject Start = spawn; //initialize Start Node
				GameObject Finish = finish;				
				GameObject Current = Start;
				
				
				
				
				OpenList.Add (Start);		//add the first square to the openlist		
				
		
				
				while (OpenList.Count > 0) { //while the openlist is not empty
						
						Current = GetLowestF (OpenList); //get the lowest F value of all squares in the open list
						//yield return new WaitForSeconds (pathSpeed);
						//first iteration is just the start square
						yield return new WaitForEndOfFrame ();
						ClosedList.Add (Current); //add it to the closed list 
						OpenList.Remove (Current);
						if (Current == Finish) { //if the current element is the last element then we have found our path
								//take the lowest F value out of the open list														
								_currentState = State.DONEWITHPATH;
								_datShort = RetracePath (Current, Start);
								yield break;
								
						} else {//otherwise keep on looking...

								
								
								
								List<GameObject> Neighbors = GetNeighborList (Current);								
								foreach (GameObject adjacent in Neighbors) {
										NodeInfo AdjacentInfo = adjacent.GetComponent<NodeInfo> ();	
										NodeInfo CurrentInfo = Current.GetComponent<NodeInfo> ();
										if (!ClosedList.Contains (adjacent)) {
												
												
												if (!OpenList.Contains (adjacent)) {//if it's not in the open list												
														OpenList.Add (adjacent); //add it to the open list										
														ChangeParent (Current, adjacent); //change it's parent to the cell that looked at it														
														AdjacentInfo.G = CalculateGCost (Current, adjacent);
														yield return new WaitForSeconds (pathSpeed);
														
												}

										} else {
												
												if (AdjacentInfo.G < AdjacentInfo.G + CurrentInfo.G && AdjacentInfo.Walkable == true) {
														print ("cheaper route!"); //if it is cheaper to go there;
														ChangeParent (adjacent, Current);//change the parent of the cheaper cell to the previous cell																					
														AdjacentInfo.G = CalculateGCost (Current, adjacent);//recalculate the cost to move to it
														yield return new WaitForSeconds (pathSpeed);
												
												}
										}
								
								}
						}	
						
						
				}

				

				_currentState = State.DONEWITHOUTPATH;
				yield break;
				
				
		}

		
	#region Rules
		private void ChangeParent (GameObject parent, GameObject child)
		{

				child.GetComponent<NodeInfo> ().Parent = parent;
				child.GetComponent<LineRenderer>().SetPosition (0, child.transform.localPosition);
				child.GetComponent<LineRenderer>().SetPosition (1
		                                                 , parent.transform.localPosition);
				

		}

		private List<GameObject> GetNeighborList (GameObject current)
		{

				List<GameObject> NewNeighbors = new List<GameObject> ();
				NodeInfo CurrentNodeInfo = current.GetComponent <NodeInfo> ();
				GameObject [,] CurrentSearchSpaceArray = CurrentNodeInfo.ParentSearchSpace;
				for (int i = -1; i < 2; i++) {						
						for (int j = -1; j < 2; j++) {
								int offSetX = CurrentNodeInfo.PositionX + i;
								int offSetY = CurrentNodeInfo.PositionY + j;
								if (ValidNeighbor (current, offSetX, offSetY)) {
										NewNeighbors.Add (CurrentSearchSpaceArray [offSetX, offSetY]);										
								} 
						}
				}
				return NewNeighbors;
		}

		private bool ValidNeighbor (GameObject current, int neighborPositionX, int neighborPositionY)
		{			

				
				if (!BoundaryCheck (current, neighborPositionX, neighborPositionY))				
						return false;
				
						 
								
				GameObject Neighbor = current.GetComponent<NodeInfo> ().ParentSearchSpace [neighborPositionX, neighborPositionY];
						
				if (!SameCellCheck (current, Neighbor))
						return false;
				if (!WalkableCheck (Neighbor))
						return false;
				else
						return true;
				
		}

		private bool BoundaryCheck (GameObject current, int neighborPositionX, int neighborPositionY)
		{			

				if (neighborPositionX < _searchSpaceInfo.LeftBoundary)		
						return false;
				if (neighborPositionX > _searchSpaceInfo.RightBoundary) //change this to not be a private member accesing things
						return false;
				if (neighborPositionY < _searchSpaceInfo.LowerBoundary)
						return false;
				if (neighborPositionY > _searchSpaceInfo.UpperBoundary) //change this to not be a private member accessing things
						return false;
				 					
				return true;
		}

		private bool WalkableCheck (GameObject neighbor)
		{
				NodeInfo CurrentNodeInfo = neighbor.GetComponent<NodeInfo> ();		
				if (CurrentNodeInfo.Walkable == true)
						return true;
				else						
						return false;
		}

		private bool SameCellCheck (GameObject current, GameObject neighbor)
		{
				if (current == neighbor) {
						
						return false;
				} else
						return true;
			

		}

		private bool SameAxis (NodeInfo source, NodeInfo destination)
		{
				if (source.PositionX == destination.PositionX) { //if the x values of the source and destination are the same                                              //then they are on the same axis (horizontal)
						return true;
				} else if (source.PositionY == destination.PositionY) //or if the y values of the source and destination are the same
						return true;                                    //then they ar eon the same axis (horizontal)
		else
						return false; //otherwise they are on different axis (diagonal)
		}
	#endregion
		private int CalculateGCost (GameObject source, GameObject destination)
		{
				NodeInfo sourceInfo = source.GetComponent<NodeInfo> ();
				NodeInfo destinationInfo = destination.GetComponent<NodeInfo> ();
				if (SameAxis (sourceInfo, destinationInfo))
						return  10;
				else
						return 15;


    
		}

		
		private void PrintList (List<GameObject> array)
		{
				for (int i = 0; i < array.Count; i++)
						print ("array list contains" + array [i]);

		}
		private List<GameObject> RetracePath (GameObject finish, GameObject start)
		{
				List<GameObject> shortestPath = new List<GameObject> ();
				GameObject currentTraceNode = finish;
				while (currentTraceNode != start) {
						shortestPath.Add (currentTraceNode);
						currentTraceNode = currentTraceNode.GetComponent<NodeInfo> ().Parent;
				}
				return shortestPath;
		}
	#region getters and setters
		public List<GameObject> getListShortest ()
		{
				return _datShort;
		}

		public AStar.State CurrentState {
				get{ return _currentState;}
		}
		private GameObject GetLowestF (List<GameObject> openList)
		{
		
				openList.Sort (new LowestF ());				
				return openList.First ();
		
		}
	#endregion
		private GameObject _spawn;
		private GameObject _destination;
		private List<GameObject> _datShort;
		private List<GameObject> _datDone;
		private AStar.State _currentState;
		private SearchSpaceInfo _searchSpaceInfo;
		public bool debug;

}