Search Unity

Movement NPCwith A* algorithm

Discussion in 'Scripting' started by diahnovianti, Sep 1, 2019.

  1. diahnovianti

    diahnovianti

    Joined:
    May 15, 2019
    Posts:
    4
    Hello,, I'm new here, and I'm still learning coding :oops:
    I found some code for making game where NPC can chase player using A* algortihm. I not use Navmesh or something else.
    A* works well.. but I don't know, how to make NPC move along path that has been found.
    I try to use MoveTowards, but NPC still does not move according to the path, this is seen from how the NPC crashed into the obstacle.
    This is all of code :
    Code (CSharp):
    1. //CODE FOR CREATE GRID
    2. using System.Collections;
    3. using System.Collections.Generic;
    4. using UnityEngine;
    5.  
    6. public class Grid : MonoBehaviour
    7. {
    8.  
    9.     public LayerMask unwalkableMask;
    10.     public Vector2 gridWorldSize;
    11.     public float nodeRadius;
    12.     Node[,] grid;
    13.  
    14.     float nodeDiameter;
    15.     int gridSizeX, gridSizeY;
    16.  
    17.     void Start()
    18.     {
    19.         nodeDiameter = nodeRadius * 2;
    20.         gridSizeX = Mathf.RoundToInt(gridWorldSize.x / nodeDiameter);
    21.         gridSizeY = Mathf.RoundToInt(gridWorldSize.y / nodeDiameter);
    22.         CreateGrid();
    23.     }
    24.  
    25.     void CreateGrid()
    26.     {
    27.         grid = new Node[gridSizeX, gridSizeY];
    28.         Vector3 worldBottomLeft = transform.position - Vector3.right * gridWorldSize.x / 2
    29.             - Vector3.forward * gridWorldSize.y / 2;
    30.  
    31.         for (int x = 0; x < gridSizeX; x++)
    32.         {
    33.             for (int y = 0; y < gridSizeY; y++)
    34.             {
    35.                 Vector3 worldPoint = worldBottomLeft + Vector3.right * (x * nodeDiameter + nodeRadius)
    36.                     + Vector3.forward * (y * nodeDiameter + nodeRadius);
    37.                 bool walkable = !(Physics.CheckSphere(worldPoint, nodeRadius, unwalkableMask));
    38.                 grid[x, y] = new Node(walkable, worldPoint, x, y);
    39.             }
    40.         }
    41.     }
    42.  
    43.     public List<Node> GetNeighbours(Node node)
    44.     {
    45.         List<Node> neighbours = new List<Node>();
    46.  
    47.         for (int x = -1; x <= 1; x++)
    48.         {
    49.             for (int y = -1; y <= 1; y++)
    50.             {
    51.                 if (x == 0 && y == 0)
    52.                     continue;
    53.  
    54.                 int checkX = node.gridX + x;
    55.                 int checkY = node.gridY + y;
    56.  
    57.                 if (checkX >= 0 && checkX < gridSizeX && checkY >= 0 && checkY < gridSizeY)
    58.                 {
    59.                     neighbours.Add(grid[checkX, checkY]);
    60.                 }
    61.             }
    62.         }
    63.  
    64.         return neighbours;
    65.     }
    66.  
    67.  
    68.     public Node NodeFromWorldPoint(Vector3 worldPosition)
    69.     {
    70.         float percentX = (worldPosition.x + gridWorldSize.x / 2) / gridWorldSize.x;
    71.         float percentY = (worldPosition.z + gridWorldSize.y / 2) / gridWorldSize.y;
    72.         percentX = Mathf.Clamp01(percentX);
    73.         percentY = Mathf.Clamp01(percentY);
    74.  
    75.         int x = Mathf.RoundToInt((gridSizeX - 1) * percentX);
    76.         int y = Mathf.RoundToInt((gridSizeY - 1) * percentY);
    77.         return grid[x, y];
    78.     }
    79.  
    80.     public List<Node> path;
    81.     void OnDrawGizmos()
    82.     {
    83.         Gizmos.DrawWireCube(transform.position, new Vector3(gridWorldSize.x, 1, gridWorldSize.y));
    84.  
    85.         if (grid != null)
    86.         {
    87.             foreach (Node n in grid)
    88.             {
    89.                 Gizmos.color = (n.walkable) ? Color.white : Color.red;
    90.                 if (path != null)
    91.                     if (path.Contains(n))
    92.                         Gizmos.color = Color.black;
    93.                 Gizmos.DrawCube(n.worldPosition, Vector3.one * (nodeDiameter - .1f));
    94.             }
    95.         }
    96.     }
    97. }
    98. //CODE FOR SAVE NODE
    99. using System.Collections;
    100. using System.Collections.Generic;
    101. using UnityEngine;
    102.  
    103. public class Node
    104. {
    105.     public bool walkable;
    106.     public Vector3 worldPosition;
    107.     public int gridX;
    108.     public int gridY;
    109.  
    110.     public int gCost;
    111.     public int hCost;
    112.     public Node parent;
    113.  
    114.     public Node(bool _walkable, Vector3 _worldPos, int _gridX, int _gridY)
    115.     {
    116.         walkable = _walkable;
    117.         worldPosition = _worldPos;
    118.         gridX = _gridX;
    119.         gridY = _gridY;
    120.     }
    121.  
    122.     public int fCost
    123.     {
    124.         get
    125.         {
    126.             return gCost + hCost;
    127.         }
    128.     }
    129. }
    130. //THIS CODE FOR PATHFINDING AND MOVEMENT
    131. using UnityEngine;
    132. using System.Collections;
    133. using System.Collections.Generic;
    134. using System.Diagnostics;
    135. using System.Linq;
    136.  
    137. public class Astar : MonoBehaviour
    138. {
    139.  
    140.     Transform dicari;
    141.     public Transform musuhNPC;
    142.     public GameObject sistemGrid;
    143.     public string tagPlayer = "Player";
    144.     public int maxJarak;
    145.  
    146.  
    147.     public Stopwatch timer;
    148.  
    149.     Grid grid;
    150.  
    151.     void Awake()
    152.     {
    153.         timer = new Stopwatch();
    154.         grid = sistemGrid.GetComponent<Grid>();
    155.     }
    156.     void Start()
    157.     {
    158.  
    159.     }
    160.     void Update()
    161.     {
    162.         if (GameObject.FindGameObjectWithTag(tagPlayer))
    163.         {
    164.             dicari = GameObject.FindGameObjectWithTag(tagPlayer).GetComponent<Transform>();
    165.         }
    166.  
    167.         if (this.gameObject && dicari)
    168.         {
    169.             FindPath(dicari.position, musuhNPC.transform.position);
    170.         }
    171.     }
    172.  
    173.     void FindPath(Vector3 startPos, Vector3 targetPos)
    174.     {
    175.         timer.Reset();
    176.         timer.Start();
    177.         Node startNode = grid.NodeFromWorldPoint(startPos);
    178.         Node targetNode = grid.NodeFromWorldPoint(targetPos);
    179.  
    180.         UnityEngine.Debug.Log("Posisi Awal NPC: " + musuhNPC.transform.position);
    181.         UnityEngine.Debug.Log("Posisi Player: " + dicari.transform.position);
    182.  
    183.         List<Node> openSet = new List<Node>();
    184.         HashSet<Node> closedSet = new HashSet<Node>();
    185.         openSet.Add(startNode);
    186.  
    187.         while (openSet.Count > 0)
    188.         {
    189.             Node currentNode = openSet[0];
    190.             for (int i = 1; i < openSet.Count; i++)
    191.             {
    192.                 if (openSet[i].fCost < currentNode.fCost || openSet[i].fCost == currentNode.fCost
    193.                     && openSet[i].hCost < currentNode.hCost)
    194.                 {
    195.                     currentNode = openSet[i];
    196.                 }
    197.             }
    198.  
    199.             openSet.Remove(currentNode);
    200.             closedSet.Add(currentNode);
    201.  
    202.             if (currentNode == targetNode)
    203.             {
    204.                 RetracePath(startNode, targetNode);
    205.                 timer.Stop();
    206.                 UnityEngine.Debug.Log("waktu (milidetik) : " + timer.ElapsedMilliseconds);
    207.                 UnityEngine.Debug.Log("===BATAS==================================================================================================================");
    208.                 return;
    209.             }
    210.  
    211.             foreach (Node neighbour in grid.GetNeighbours(currentNode))
    212.             {
    213.                 if (!neighbour.walkable || closedSet.Contains(neighbour))
    214.                 {
    215.                     continue;
    216.                 }
    217.  
    218.                 int newMovementCostToNeighbour = currentNode.gCost + GetDistance(currentNode, neighbour);
    219.                 if (newMovementCostToNeighbour < neighbour.gCost || !openSet.Contains(neighbour))
    220.                 {
    221.                     neighbour.gCost = newMovementCostToNeighbour;
    222.                     neighbour.hCost = GetDistance(neighbour, targetNode);
    223.                     neighbour.parent = currentNode;
    224.  
    225.                     if (!openSet.Contains(neighbour))
    226.                         openSet.Add(neighbour);
    227.                 }
    228.             }
    229.         }
    230.     }
    231.  
    232.     void RetracePath(Node startNode, Node endNode)
    233.     {
    234.         List<Node> path = new List<Node>();
    235.         Node currentNode = endNode;
    236.         Vector3 posisiNode = new Vector3(0.0f, 0.0f, 0.0f);
    237.  
    238.         while (currentNode != startNode)
    239.         {
    240.             path.Add(currentNode);
    241.             currentNode = currentNode.parent;
    242.             UnityEngine.Debug.Log("Node (Grid X: " + currentNode.gridX + ", Grid Y: " + currentNode.gridY);
    243.             posisiNode = currentNode.worldPosition - new Vector3(-0.5f, 0.1f, -0.5f);
    244.             UnityEngine.Debug.Log("Posisi Node:" + posisiNode);
    245.         }
    246.         path.Reverse();
    247.         UnityEngine.Debug.Log("Jumlah Path : " + path.Count);
    248.         grid.path = path;
    249.         MovementTarget(path);
    250.      
    251.     }
    252.  
    253.     int GetDistance(Node nodeA, Node nodeB)
    254.     {
    255.         int dstX = Mathf.Abs(nodeA.gridX - nodeB.gridX);
    256.         int dstY = Mathf.Abs(nodeA.gridY - nodeB.gridY);
    257.  
    258.         if (dstX > dstY)
    259.             return 14 * dstY + 10 * (dstX - dstY);
    260.         return 14 * dstX + 10 * (dstY - dstX);
    261.     }
    262.  
    263.     void MovementTarget(List<Node> path)
    264.     {
    265.         if (path.Count - 1 != 0)
    266.         {
    267.             musuhNPC.position = Vector3.MoveTowards(musuhNPC.position
    268.                 , new Vector3(path[0].worldPosition.x, musuhNPC.position.y, path[0].worldPosition.z)
    269.                 , maxJarak * Time.deltaTime);
    270.         }
    271.      //rotate
    272.      Quaternion rotasi = Quaternion.LookRotation(target.position - transform.position);
    273.     transform.rotation = Quaternion.Slerp(transform.rotation, rotasi, Time.deltaTime * lembamRotasi);
    274.     }
    275. }
    Please help me and thank you :)
     

    Attached Files:

    • 1.png
      1.png
      File size:
      154.7 KB
      Views:
      421
    diahnovianti, Sep 1, 2019
    #1