Pathfinding Issue.

Question

EDIT - Update the script and know am getting alot further but i get null reference at the last node for some reason.... new path in Picture 3 :)

Hey guys - Ive been working on my won pathfinding for a while now and got everything going great, i can build nodes, link them all together so each node knows its neighbour and its position and so on - not a problem but when trying to get a path i hit a wall, you see i can build a list of nodes from start to finish easy enough as shown in Picture 1 build getting a path using them nodes gives me a less then pleasing result as soon in Picture 2, i think the problem lies with GetClosestPath Function but not entirely sure neway ive posted my Seeker script below - any help would be much appreicted :)

~ Popper

Picture 1

Link - url

Picture 2

Link - url

Picture 3 - Pathfinding with new edit

alt text Link - url

 using UnityEngine;

using System.Collections; using System.Collections.Generic; using System.Diagnostics;

public class PathNode { public Node Node; public float Cost; public PathNode(Node node, float distance_from_start, float distance_to_end) { Node = node; Cost = distance_from_start + distance_to_end; } }

public class Seeker : MonoBehaviour {

 List<Node> Nodes = new List<Node>();
 int NodeSpacing = 0;

 List<Node> OpenList = new List<Node>();
 List<Node> ClosedList = new List<Node>();

 List<PathNode> OpenPath = new List<PathNode>();
 List<PathNode> ClosedPathNodeList = new List<PathNode>();

 public List<Vector3> SelectedPath = new List<Vector3>();

 Node StartNode = null;
 Node EndNode = null;

 public List<Vector3> BuildPath(Vector3 Start, Vector3 End)
 {
     Stopwatch CodeTimer = new Stopwatch();
     CodeTimer.Start();
     ClearAll();

     bool Failed = false;
     Nodes = Pathfinding_Core.Nodes;
     NodeSpacing = Pathfinding_Core.NodeSpacing;

     StartNode = GetFirstNode(Start);
     EndNode = GetFirstNode(End);

     Node ParentNode = StartNode;
     OpenList.Add(ParentNode);

     while (ClosedList.Contains(EndNode) == false)
     {
         if (OpenList.Count == 0)
         {
             UnityEngine.Debug.Log("Broke out of building path...");
             Failed = true;
             break;
         }
         ParentNode = GetClosest(ParentNode, End);
     }

     UnityEngine.Debug.Log("Heusitc nodes - " + ClosedPathNodeList.Count);

     if (Failed == false)
     {
         Node PathNode = EndNode;
         OpenPath.Add(new PathNode(PathNode, 0, 0));
         while (SelectedPath.Contains(StartNode.Position) == false)
         {
             if (OpenPath.Count == 0)
             {
                 UnityEngine.Debug.Log("Broke out of getting path...");
                 UnityEngine.Debug.Log("Path count was at " + SelectedPath.Count + " nodes.");
                 //SelectedPath.Clear();
                 Failed = true;
                 break;
             }
             PathNode = GetClosestPath(PathNode, StartNode.Position);
             if (PathNode != null)
             {
                 SelectedPath.Add(PathNode.Position);
             }
             else
             {
                 break;
             }
  
         }

         if (Failed == false)
         {
             SelectedPath.Insert(0, End);
         }

     }

     RemoveDuplicates();
     SelectedPath.Reverse();
     CodeTimer.Stop();
     UnityEngine.Debug.Log("Complete in " + CodeTimer.ElapsedMilliseconds + "ms!");
     return SelectedPath;
 }

 private Node GetClosest(Node Parent,Vector3 Destination)
 {
     foreach (var NewNode in Parent.Connections)
     {
         if ((OpenList.Contains(NewNode) == false) && (ClosedList.Contains(NewNode) == false))
         {
             OpenList.Add(NewNode);
         }
     }

     float shortest = 99999999;
     Node NodeToUse = null;

     foreach (var OpenNode in OpenList)
     {
         float Distance = Vector3.Distance(OpenNode.Position, Destination);
         if (Distance < shortest)
         {
             shortest = Distance;
             NodeToUse = OpenNode;
         }
     }

     ClosedPathNodeList.Add(new PathNode(NodeToUse, Vector3.Distance(NodeToUse.Position, StartNode.Position), Vector3.Distance(NodeToUse.Position, Destination)));
     ClosedList.Add(NodeToUse);
     OpenList.Remove(NodeToUse);
     return NodeToUse;
 }

 private Node GetClosestPath(Node Parent, Vector3 Destination)
 {
     OpenPath.Clear();
     foreach (var NewNode in ClosedPathNodeList)
     {
         if (Vector3.Distance(Parent.Position,NewNode.Node.Position) < (NodeSpacing * 1.9f))
         {
             if (NewNode.Node != EndNode)
             {
                 OpenPath.Add(NewNode);
             }
         }
     }

     float shortest = float.MaxValue;
     Node NodeToUse = null;
     PathNode Node = null;

     foreach (var OpenNode in OpenPath)
     {
         if (OpenNode.Cost < shortest)
         {
             shortest = OpenNode.Cost;
             NodeToUse = OpenNode.Node;
             Node = OpenNode;
         }
     }

     ClosedPathNodeList.Remove(Node);
     return NodeToUse;
 }

 private Node GetFirstNode(Vector3 Start)
 {
     float shortest = 99999999;
     Node NodeToUse = null;

     foreach (var Node in Nodes)
     {
         float Distance = Vector3.Distance(Node.Position, Start);
         if (Distance < shortest)
         {
             shortest = Distance;
             NodeToUse = Node;
         }
     }
     return NodeToUse;
 }

 private void ClearAll()
 {
     SelectedPath.Clear();
     ClosedPathNodeList.Clear();
     OpenList.Clear();
     ClosedList.Clear();
     OpenPath.Clear();
 }

 private void RemoveDuplicates()
 {
     List<Vector3> NewList = new List<Vector3>();
     foreach (var item in SelectedPath)
     {
         if (NewList.Contains(item) == false)
         {
             NewList.Add(item);
         }
     }
     SelectedPath = NewList;
 }

 void OnDrawGizmos()
 {
     foreach (var opennode in OpenList)
     {
         Gizmos.color = Color.blue;
         Gizmos.DrawSphere(opennode.Position, 0.1f);
     }

     foreach (var closednode in ClosedList)
     {
         Gizmos.color = Color.black;
         Gizmos.DrawSphere(closednode.Position, 0.1f);
     }
 }

}

Answer 1

I just looked through some old projects and found an old pathfinding algorithm I wrote a long time ago. Beware this is really unoptimized but it does find a pretty good path.

 using UnityEngine;
 using System.Collections;
 using System.Collections.Generic;
 
 [RequireComponent(typeof(CharacterController))]
 public class astar : MonoBehaviour {
     
     private List<GameObject> OpenList = new List<GameObject>();
     public List<Vector3> FinalPath = new List<Vector3>();
     
     public void getPath(Vector3 startPos, Vector3 endPos){
         FinalPath.Clear();
         
         GameObject[] nodes = GameObject.FindGameObjectsWithTag("pathnode");
         if(nodes.Length > 0){
             //Find start node.
             GameObject StartNode = null;
             float srcDis = Mathf.Infinity;
             foreach(GameObject node in nodes){
                 float dis = Vector3.Distance(startPos, node.transform.position);
                 if(dis < srcDis){
                     srcDis = dis;
                     StartNode = node;
                 }
             }
             
             //Find end node.
             GameObject EndNode = null;
             srcDis = Mathf.Infinity;
             foreach(GameObject node in nodes){
                 float dis = Vector3.Distance(endPos, node.transform.position);
                 if(dis < srcDis){
                     srcDis = dis;
                     EndNode = node;
                 }
             }
             
             //Setup the algorithm.
             GameObject current = StartNode;
             current.GetComponent<pathnodeScript>().Weight = 0;
             
             OpenList.Clear();
             foreach(GameObject node in nodes){
                 OpenList.Add(node);
             }
             
             //Start weighting.
             while(current != EndNode){
                 OpenList.Remove(current);
                 foreach(GameObject node in current.GetComponent<pathnodeScript>().LinkedNodes){
                     if(OpenList.Contains(node) == false){
                         continue;
                     }
                     float newh = current.GetComponent<pathnodeScript>().Weight;
                     float newg = Vector3.Distance(node.transform.position, (EndNode.transform.position - node.transform.position));
                     float newcost = newh+newg;
                     if(newcost < node.GetComponent<pathnodeScript>().Weight){
                         node.GetComponent<pathnodeScript>().Weight = newcost;
                         node.GetComponent<pathnodeScript>().PrevNode = current;
                     }
                 }
                 
                 //Find next current.
                 float weightSrc = Mathf.Infinity;
                 foreach(GameObject node in OpenList){
                     if(node.GetComponent<pathnodeScript>().Weight < weightSrc){
                         weightSrc = node.GetComponent<pathnodeScript>().Weight;
                         current = node;
                     }
                 }
             }
             
             //Backtrack to find path.
             current = EndNode;
             FinalPath.Add(current.transform.position);
             while(current != StartNode){
                 current = current.GetComponent<pathnodeScript>().PrevNode;
                 FinalPath.Add(current.transform.position);
             }
             
             FinalPath.Reverse();
             
             //Clean up.
             foreach(GameObject node in nodes){
                 node.GetComponent<pathnodeScript>().Weight = Mathf.Infinity;
                 node.GetComponent<pathnodeScript>().PrevNode = null;
             }
         }
     }
     
 }

Look through it.. Maybe it will give you an idea as to how you can fix yours.

Answer 2

Answer by Popper · May 04, 2012 at 04:03 PM

cheers, just got back from a trip and just had a look over your code and i think its gonna help a lot - cheers again :)

Add comment · Share

Answer 3

Answer by Popper · May 04, 2012 at 07:36 PM

Whats the Weight refering to? the cost it already has?

Add comment · Share

Pathfinding Issue.

3 Replies

Your answer

Follow this Question

Related Questions