My Portfolio

This project demonstrates the application of the A* pathfinding algorithm using waypoints to simulate roads for a tank navigating a terrain. It showcases both the algorithm’s efficiency and the ability to dynamically change the destination points, providing an interactive and visual experience.

Core Features

• Waypoint Graph Setup: Defines nodes (waypoints) and edges (connections) to create a graph structure representing roads.
• A Pathfinding Algorithm*: Implements the A* algorithm to find the shortest path between nodes in the graph.
• Real-Time Navigation: The tank dynamically follows the calculated path to reach the user-defined endpoint.
• Interactive Controls: Users can set different destination points for the tank using buttons.

1. Graph Structure (Graph.cs)

This script manages the graph of nodes and edges, and implements the A* algorithm to find the shortest path.

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

public class Graph
{
    private List<Edge> edges = new List<Edge>();
    private List<Node> nodes = new List<Node>();
    public List<Node> pathList = new List<Node>();
    
    public Graph() { }

    public void AddNode(GameObject _id)
    {
        Node node = new Node(_id);
        nodes.Add(node);
    }

    public void AddEdge(GameObject fromNode, GameObject toNode)
    {
        Node from = FindNode(fromNode);
        Node to = FindNode(toNode);

        if (from != null && to != null)
        {
            Edge e = new Edge(from, to);
            edges.Add(e);
            from.edgeList.Add(e);
        }
    }

    Node FindNode(GameObject _id)
    {
        foreach (Node n in nodes)
        {
            if (n.GetID() == _id) return n;
        }

        return null;
    }

    public bool AStar(GameObject startID, GameObject endID)
    {
        if (startID == endID)
        {
            pathList.Clear();
            return false;
        }
        
        Node start = FindNode(startID);
        Node end = FindNode(endID);

        if (start == null || end == null) return false;

        List<Node> open = new List<Node>();
        List<Node> closed = new List<Node>();

        float tentativeGSscore = 0;
        bool tentativeIsBetter;

        start.g = 0;
        start.h = distance(start, end);
        start.f = start.h;
        
        open.Add(start);

        while (open.Count > 0)
        {
            int i = LowestCost(open);
            Node thisNode = open[i];
            if (thisNode.GetID() == endID)
            {
                ReconstructPath(start, end);
                return true;
            }
            
            open.RemoveAt(i);
            closed.Add(thisNode);
            Node neighbour;
            foreach (Edge e in thisNode.edgeList)
            {
                neighbour = e.endNode;

                if (closed.IndexOf(neighbour) > -1) continue;

                tentativeGSscore = thisNode.g + distance(thisNode, neighbour);
                if (open.IndexOf(neighbour) == -1)
                {
                    open.Add(neighbour);
                    tentativeIsBetter = true;
                }
                else if (tentativeGSscore < neighbour.g)
                {
                    tentativeIsBetter = true;
                }
                else tentativeIsBetter = false;

                if (tentativeIsBetter)
                {
                    neighbour.cameFrom = thisNode;
                    neighbour.g = tentativeGSscore;
                    neighbour.h = distance(thisNode, end);
                    neighbour.f = neighbour.g + neighbour.h;
                }
            }
        }

        return false;
    }

    public void ReconstructPath(Node startID, Node endID)
    {
        pathList.Clear();
        pathList.Add(endID);

        var p = endID.cameFrom;
        while (p != startID && p != null)
        {
            pathList.Insert(0, p);
            p = p.cameFrom;
        }
        pathList.Insert(0, startID);
    }

    float distance(Node a, Node b)
    {
        return (Vector3.SqrMagnitude(a.GetID().transform.position - b.GetID().transform.position));
    }

    int LowestCost(List<Node> l)
    {
        float lowestCost = 0;
        int count = 0;
        int iteratorCount = 0;

        lowestCost = l[0].f;
        
        for (int i = 1; i < l.Count; i++)
        {
            if (l[i].f < lowestCost)
            {
                lowestCost = l[i].f;
                iteratorCount = count;
            }
            count++;
        }

        return iteratorCount;
    }
}

2. Node Definition (Node.cs)

This script defines the node structure, representing each waypoint in the graph.

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

public class Node
{
    public List<Edge> edgeList = new List<Edge>();
    public Node path = null;
    
    private GameObject id;
    public float x, y, z;
    
    public float f, g, h;
    public Node cameFrom;

    public Node(GameObject i)
    {
        id = i;
        x = i.transform.position.x;
        y = i.transform.position.y;
        z = i.transform.position.z;
    }

    public GameObject GetID()
    {
        return id;
    }
}

3. Edge Definition (Edge.cs)

This script defines the edges connecting nodes in the graph.

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

public class Edge
{
    public Node startNode;
    public Node endNode;

    public Edge(Node from, Node to)
    {
        startNode = from;
        endNode = to;
    }
}

4. Waypoint Manager (WPManager.cs)

This script sets up the waypoints and links, initializing the graph for pathfinding.

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



[System.Serializable]
public struct Link
{
    public enum direction { UNI, BI }
    public GameObject node1;
    public GameObject node2;
    public direction dir;
}

public class WPManager : MonoBehaviour
{
    public GameObject[] waypoints;
    public Link[] links;
    public Graph graph = new Graph();
    
    // Start is called before the first frame update
    void Start()
    {
        if (waypoints.Length > 0)
        {
            foreach (GameObject wp in waypoints)
            {
                graph.AddNode(wp);
            }

            foreach (Link l in links)
            {
                graph.AddEdge(l.node1, l.node2);
                if (l.dir == Link.direction.BI)
                {
                    graph.AddEdge(l.node2, l.node1);
                }
            }
        }
    }
}

5. Tank Navigation (FollowWP.cs)

This script handles the tank’s movement along the path calculated by the A* algorithm, allowing the user to set different destination points.

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

public class FollowWP : MonoBehaviour
{
    private Transform goal;
    public float speed;
    public float accuracy;
    public float rotSpeed;

    public GameObject wpManager;
    private GameObject[] waypoints;
    private GameObject currentNode;
    private int currentWP = 0;
    private Graph g;
    
    // Start is called before the first frame update
    void Start()
    {
        waypoints = wpManager.GetComponent<WPManager>().waypoints;
        g = wpManager.GetComponent<WPManager>().graph;
        currentNode = waypoints[0]; // de acolo incepe ca pe nodu ala se afla tanku
    }

    public void GoToHeli()
    {
        g.AStar(currentNode, waypoints[0]);
        currentWP = 0;
    }
    
    public void GoToRuin()
    {
        g.AStar(currentNode, waypoints[11]);
        currentWP = 0;
    }
    
    public void GoToFactory()
    {
        g.AStar(currentNode, waypoints[10]);
        currentWP = 0;
    }
    
    public void GoToHangar()
    {
        g.AStar(currentNode, waypoints[3]);
        currentWP = 0;
    }

    // Update is called once per frame
    void LateUpdate()
    {
        if (g.pathList.Count == 0 || currentWP == g.pathList.Count) return;
        
        if (Vector3.Distance(g.pathList[currentWP].GetID().transform.position, this.transform.position) < accuracy)
        {
            currentNode = g.pathList[currentWP].GetID();
            currentWP++;
        }

        if (currentWP < g.pathList.Count)
        {
            goal = g.pathList[currentWP].GetID().transform;
            Vector3 lookAtGoal = new Vector3(goal.position.x, this.transform.position.y, goal.position.z);
            Vector3 direction = lookAtGoal - this.transform.position;
            
            this.transform.rotation = Quaternion.Slerp(this.transform.rotation, Quaternion.LookRotation(direction), rotSpeed * Time.deltaTime);
            
            this.transform.Translate(0, 0, speed * Time.deltaTime) ;
            
        }
    }
}