Created
May 10, 2016 22:54
-
-
Save chuwilliamson/7d67322ecc1ae5971ec77984d67ffeb6 to your computer and use it in GitHub Desktop.
Revisions
-
chuwilliamson created this gist
May 10, 2016 .There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,278 @@ 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; }