Pathfinding Issue.

Questions & Answers
1

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 :slight_smile:

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 :slight_smile:

~ Popper

Picture 1

1
Link - 2

Picture 2

3
Link - 4

Picture 3 - Pathfinding with new edit

alt text
Link - 6

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);
    }
}

}

2

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.

3

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 :slight_smile:

4

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