Unity) [유니티 2D] ChatGPT로 A*알고리즘 학습

Sure, here is an example Unity script based on the A* algorithm for a monster to find a player:

 

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

public class Monster : MonoBehaviour
{
    public Transform player;
    private Grid grid;

    private void Start()
    {
        grid = GetComponent<Grid>();
    }

    private void Update()
    {
        FindPath(transform.position, player.position);
    }

    private void FindPath(Vector3 startPos, Vector3 targetPos)
    {
        Node startNode = grid.NodeFromWorldPoint(startPos);
        Node targetNode = grid.NodeFromWorldPoint(targetPos);

        List<Node> openSet = new List<Node>();
        HashSet<Node> closedSet = new HashSet<Node>();
        openSet.Add(startNode);

        while (openSet.Count > 0)
        {
            Node currentNode = openSet[0];
            for (int i = 1; i < openSet.Count; i++)
            {
                if (openSet[i].fCost < currentNode.fCost || openSet[i].fCost == currentNode.fCost && openSet[i].hCost < currentNode.hCost)
                {
                    currentNode = openSet[i];
                }
            }

            openSet.Remove(currentNode);
            closedSet.Add(currentNode);

            if (currentNode == targetNode)
            {
                RetracePath(startNode, targetNode);
                return;
            }

            foreach (Node neighbour in grid.GetNeighbours(currentNode))
            {
                if (!neighbour.walkable || closedSet.Contains(neighbour))
                {
                    continue;
                }

                int newMovementCostToNeighbour = currentNode.gCost + GetDistance(currentNode, neighbour);
                if (newMovementCostToNeighbour < neighbour.gCost || !openSet.Contains(neighbour))
                {
                    neighbour.gCost = newMovementCostToNeighbour;
                    neighbour.hCost = GetDistance(neighbour, targetNode);
                    neighbour.parent = currentNode;

                    if (!openSet.Contains(neighbour))
                    {
                        openSet.Add(neighbour);
                    }
                }
            }
        }
    }

    private void RetracePath(Node startNode, Node endNode)
    {
        List<Node> path = new List<Node>();
        Node currentNode = endNode;

        while (currentNode != startNode)
        {
            path.Add(currentNode);
            currentNode = currentNode.parent;
        }

        path.Reverse();
        grid.path = path;
    }

    private int GetDistance(Node nodeA, Node nodeB)
    {
        int dstX = Mathf.Abs(nodeA.gridX - nodeB.gridX);
        int dstY = Mathf.Abs(nodeA.gridY - nodeB.gridY);

        if (dstX > dstY)
        {
            return 14 * dstY + 10 * (dstX - dstY);
        }

        return 14 * dstX + 10 * (dstY - dstX);
    }
}

In this script, the monster finds the player by calling the FindPath method in the Update function. The FindPath method uses the A* algorithm to calculate the optimal path from the monster's current position to the player's position.

The RetracePath method retraces the optimal path from the end node to the start node and sets the path as a list of nodes in the grid component.

The GetDistance method calculates the distance between two nodes using the formula for the diagonal distance heuristic.

Note that this script assumes that there is a Grid component attached to the same game object as the Monster script. The Grid component is responsible for creating the grid of nodes that the A* algorithm uses.

 

Yes, the script should work properly in a top-down game as long as the game objects have a position in 3D space and the Grid component is set up properly to match the top-down perspective.

The Grid component used in the script is responsible for dividing the game world into a grid of nodes that the monster can navigate. The Node class used in the script should have 3D coordinates for the x, y, and z variables that represent the position of the node in the game world.

As long as the Grid component is set up properly to match the top-down perspective of the game and the Node class has the correct 3D coordinates, the script should work properly in a top-down game.

 

The script I provided is written for a 3D environment where the game objects have a position in 3D space. To make it work properly in a 2D environment, some modifications need to be made to the code.

Here's a modified version of the script that should work for a 2D environment:

 

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

public class Monster : MonoBehaviour
{
    public Transform player;
    private Grid grid;

    private void Start()
    {
        grid = GetComponent<Grid>();
    }

    private void Update()
    {
        FindPath(transform.position, player.position);
    }

    private void FindPath(Vector3 startPos, Vector3 targetPos)
    {
        Node startNode = grid.NodeFromWorldPoint(startPos);
        Node targetNode = grid.NodeFromWorldPoint(targetPos);

        List<Node> openSet = new List<Node>();
        HashSet<Node> closedSet = new HashSet<Node>();
        openSet.Add(startNode);

        while (openSet.Count > 0)
        {
            Node currentNode = openSet[0];
            for (int i = 1; i < openSet.Count; i++)
            {
                if (openSet[i].fCost < currentNode.fCost || openSet[i].fCost == currentNode.fCost && openSet[i].hCost < currentNode.hCost)
                {
                    currentNode = openSet[i];
                }
            }

            openSet.Remove(currentNode);
            closedSet.Add(currentNode);

            if (currentNode == targetNode)
            {
                RetracePath(startNode, targetNode);
                return;
            }

            foreach (Node neighbour in grid.GetNeighbours(currentNode))
            {
                if (!neighbour.walkable || closedSet.Contains(neighbour))
                {
                    continue;
                }

                int newMovementCostToNeighbour = currentNode.gCost + GetDistance(currentNode, neighbour);
                if (newMovementCostToNeighbour < neighbour.gCost || !openSet.Contains(neighbour))
                {
                    neighbour.gCost = newMovementCostToNeighbour;
                    neighbour.hCost = GetDistance(neighbour, targetNode);
                    neighbour.parent = currentNode;

                    if (!openSet.Contains(neighbour))
                    {
                        openSet.Add(neighbour);
                    }
                }
            }
        }
    }

    private void RetracePath(Node startNode, Node endNode)
    {
        List<Node> path = new List<Node>();
        Node currentNode = endNode;

        while (currentNode != startNode)
        {
            path.Add(currentNode);
            currentNode = currentNode.parent;
        }

        path.Reverse();
        grid.path = path;
    }

    private int GetDistance(Node nodeA, Node nodeB)
    {
        int dstX = Mathf.Abs(nodeA.gridX - nodeB.gridX);
        int dstY = Mathf.Abs(nodeA.gridY - nodeB.gridY);

        if (dstX > dstY)
        {
            return 14 * dstY + 10 * (dstX - dstY);
        }

        return 14 * dstX + 10 * (dstY - dstX);
    }
}

The main modification is in the FindPath method where we use the NodeFromWorldPoint method of the Grid component to get the start and target nodes based on their 2D positions. The Node class used in this script should have 2D coordinates for the gridX and gridY variables instead of 3D x, y, and z variables. Also, the GetDistance method should calculate the distance based on 2D coordinates instead of 3D coordinates.

With these modifications, the script should work properly in a 2D

 

The original script I provided is written for a 3D environment and would not work properly in a 2D top-down game. However, the modified version of the script I provided earlier should work properly in a 2D top-down game.

To summarize the modifications needed to make the script work for a 2D top-down game:

• The Node class should have 2D coordinates for the gridX and gridY variables instead of 3D x, y, and z variables.
• The FindPath method should use the NodeFromWorldPoint method of the Grid component to get the start and target nodes based on their 2D positions.
• The GetDistance method should calculate the distance based on 2D coordinates instead of 3D coordinates.

With these modifications, the script should work properly in a 2D top-down game.

 

If there are a lot of monsters in the game, each with their own pathfinding behavior, it is possible that the memory load could become too severe if the script is not optimized.

One way to optimize the script is to use a technique called "object pooling." Object pooling is a design pattern that allows you to reuse objects instead of creating and destroying them repeatedly. Instead of creating a new pathfinding grid and nodes for each monster, you can create a pool of pre-allocated grids and nodes that can be reused as needed.

For example, you could create a pool of 10 pathfinding grids and 1000 nodes. Each monster that needs pathfinding would then grab a pathfinding grid and a set of nodes from the pool and use them for its pathfinding. Once the monster is done with the pathfinding, it returns the grid and nodes back to the pool for reuse by other monsters.

Another way to optimize the script is to use a technique called "coroutines." Coroutines allow you to pause the execution of a method and resume it later. By using coroutines, you can split the pathfinding process into smaller steps and allow other parts of the game to run in between each step. This can help reduce the impact of pathfinding on the game's performance.

In conclusion, there are techniques available to optimize the script and reduce the memory load, such as object pooling and coroutines. It's important to keep in mind the impact of the script on the overall game performance and optimize it accordingly.

 

To implement object pooling for the pathfinding grids and nodes, you can create a PathfindingPool class that manages a pool of grids and nodes. Here's an example implementation:

 

using System.Collections.Generic;
using UnityEngine;

public class PathfindingPool : MonoBehaviour
{
    public Grid gridPrefab;   // The prefab for the pathfinding grid
    public int gridCount = 10;   // The number of pathfinding grids in the pool

    public Node nodePrefab;   // The prefab for the pathfinding node
    public int nodeCount = 1000;   // The number of pathfinding nodes in the pool

    private Queue<Grid> gridPool = new Queue<Grid>();   // The pool of pathfinding grids
    private Queue<Node> nodePool = new Queue<Node>();   // The pool of pathfinding nodes

    private void Awake()
    {
        // Populate the pool with pathfinding grids
        for (int i = 0; i < gridCount; i++)
        {
            Grid grid = Instantiate(gridPrefab);
            grid.gameObject.SetActive(false);
            gridPool.Enqueue(grid);
        }

        // Populate the pool with pathfinding nodes
        for (int i = 0; i < nodeCount; i++)
        {
            Node node = Instantiate(nodePrefab);
            node.gameObject.SetActive(false);
            nodePool.Enqueue(node);
        }
    }

    // Get a pathfinding grid from the pool
    public Grid GetGrid()
    {
        if (gridPool.Count == 0)
        {
            // If the pool is empty, create a new pathfinding grid
            Grid grid = Instantiate(gridPrefab);
            grid.gameObject.SetActive(false);
            gridPool.Enqueue(grid);
        }

        // Get a pathfinding grid from the pool
        Grid result = gridPool.Dequeue();
        result.gameObject.SetActive(true);
        return result;
    }

    // Return a pathfinding grid to the pool
    public void ReturnGrid(Grid grid)
    {
        grid.gameObject.SetActive(false);
        gridPool.Enqueue(grid);
    }

    // Get a set of pathfinding nodes from the pool
    public Node[] GetNodes(int count)
    {
        if (nodePool.Count < count)
        {
            // If the pool doesn't have enough nodes, create new ones
            int diff = count - nodePool.Count;
            for (int i = 0; i < diff; i++)
            {
                Node node = Instantiate(nodePrefab);
                node.gameObject.SetActive(false);
                nodePool.Enqueue(node);
            }
        }

        // Get a set of pathfinding nodes from the pool
        Node[] result = new Node[count];
        for (int i = 0; i < count; i++)
        {
            Node node = nodePool.Dequeue();
            node.gameObject.SetActive(true);
            result[i] = node;
        }

        return result;
    }

    // Return a set of pathfinding nodes to the pool
    public void ReturnNodes(Node[] nodes)
    {
        foreach (Node node in nodes)
        {
            node.gameObject.SetActive(false);
            nodePool.Enqueue(node);
        }
    }
}

In this example, the PathfindingPool class has a gridPrefab and a nodePrefab that are used to create the pathfinding grids and nodes. The gridCount and nodeCount fields determine the number of grids and nodes in the pool.

In the Awake method, the pool is populated with the specified number of grids and nodes by instantiating them and adding them to the respective pools.

The GetGrid method gets a pathfinding grid from the pool. If the

 

the A* algorithm can be used to continuously update the path that a monster should take in real time to chase a moving player. To do this, you would need to call the A* algorithm periodically (e.g. every few frames) to recalculate the path from the monster's current position to the player's current position.

In order to avoid excessive calculations, you can also implement various optimizations such as using a grid with a lower resolution, limiting the number of nodes expanded by the A* algorithm per frame, or using an algorithm such as D* Lite that can update paths more efficiently than A* when the starting node or the cost of edges changes.

 

 

Sure! Here's an example implementation of a monster chasing the player using D* Lite and object pooling in Unity:

using System.Collections.Generic;
using UnityEngine;

public class Monster : MonoBehaviour
{
    public float speed = 5f;   // The speed of the monster
    public float refreshInterval = 0.5f;   // The interval in seconds between path recalculations
    public float nodeSize = 1f;   // The size of the pathfinding nodes

    private Transform player;   // The player's transform
    private Vector2 targetPos;   // The current target position for the monster
    private List<Node> path;   // The current path for the monster
    private int pathIndex;   // The current index in the path
    private float refreshTimer;   // The timer for path recalculations

    private PathfindingPool pathPool;   // The object pool for pathfinding nodes

    private void Start()
    {
        player = GameObject.FindGameObjectWithTag("Player").transform;

        // Get the pathfinding object pool
        pathPool = FindObjectOfType<PathfindingPool>();
    }

    private void Update()
    {
        // Recalculate the path periodically
        refreshTimer += Time.deltaTime;
        if (refreshTimer >= refreshInterval)
        {
            refreshTimer = 0f;

            // Get the current position of the monster and the player
            Vector2 startPos = transform.position;
            Vector2 endPos = player.position;

            // Recycle the previous pathfinding nodes
            if (path != null)
            {
                foreach (Node node in path)
                {
                    pathPool.ReturnNode(node);
                }
            }

            // Calculate the path using D* Lite
            Grid grid = pathPool.GetGrid();
            path = DStarLite.CalculatePath(grid, pathPool, startPos, endPos, nodeSize);
            pathIndex = 0;

            // Return the grid to the object pool
            pathPool.ReturnGrid(grid);
        }

        // Move towards the next node in the path
        if (path != null && pathIndex < path.Count)
        {
            Vector2 nodePos = path[pathIndex].position;
            transform.position = Vector2.MoveTowards(transform.position, nodePos, speed * Time.deltaTime);

            if (transform.position == nodePos)
            {
                pathIndex++;
            }
        }
    }
}

In this example, the Monster class has a speed field that determines the movement speed of the monster, a refreshInterval field that determines the interval between path recalculations, and a nodeSize field that determines the size of the pathfinding nodes.

In the Start method, the player transform is obtained, and the pathPool object pool for the pathfinding nodes is obtained by finding the PathfindingPool component in the scene.

In the Update method, the path is recalculated periodically using D* Lite. The current position of the monster and the player are obtained, and the previous pathfinding nodes are recycled by returning them to the object pool.

The path is then calculated using the DStarLite.CalculatePath method, which takes in the pathfinding grid, the pathfinding node pool, the start and end positions, and the node size as parameters, and returns a list of nodes representing the path from the start to the end position.

The grid used for pathfinding is obtained from the object pool using the pathPool.GetGrid method, and is returned to the object pool using the pathPool.ReturnGrid method after the path has been calculated.

The monster then moves towards the next node in the path using the Vector2.MoveTowards method, and

 

there are a few additional things you need to know to use this script:

1. The PathfindingPool class: In the script, we use an object pool to recycle the pathfinding nodes and the grid. To use this script, you need to create a PathfindingPool class that implements the object pooling functionality for the pathfinding nodes and the grid. Here's an example implementation:

using System.Collections.Generic;
using UnityEngine;

public class PathfindingPool : MonoBehaviour
{
    public GameObject nodePrefab;   // The prefab for the pathfinding nodes
    public int nodePoolSize = 100;   // The size of the node object pool

    private Queue<Node> nodePool;   // The object pool for the pathfinding nodes
    private Queue<Grid> gridPool;   // The object pool for the pathfinding grids

    private void Awake()
    {
        nodePool = new Queue<Node>();
        gridPool = new Queue<Grid>();

        // Populate the node object pool
        for (int i = 0; i < nodePoolSize; i++)
        {
            Node node = Instantiate(nodePrefab, transform).GetComponent<Node>();
            node.gameObject.SetActive(false);
            nodePool.Enqueue(node);
        }
    }

    public Node GetNode(Vector2 position, float size)
    {
        if (nodePool.Count == 0)
        {
            Node node = Instantiate(nodePrefab, transform).GetComponent<Node>();
            node.gameObject.SetActive(false);
            nodePool.Enqueue(node);
        }

        Node newNode = nodePool.Dequeue();
        newNode.gameObject.SetActive(true);
        newNode.position = position;
        newNode.size = size;
        return newNode;
    }

    public void ReturnNode(Node node)
    {
        node.gameObject.SetActive(false);
        nodePool.Enqueue(node);
    }

    public Grid GetGrid()
    {
        if (gridPool.Count == 0)
        {
            return new Grid();
        }

        return gridPool.Dequeue();
    }

    public void ReturnGrid(Grid grid)
    {
        grid.Reset();
        gridPool.Enqueue(grid);
    }
}

This class creates an object pool for the pathfinding nodes and the grid. In the Awake method, the node object pool is populated with nodePoolSize instances of the Node prefab.

The GetNode method is used to get a pathfinding node from the object pool. If there are no nodes in the pool, a new node is instantiated. The node is then activated, positioned at the given position, and returned.

The ReturnNode method is used to recycle a pathfinding node by deactivating it and returning it to the object pool.

The GetGrid method is used to get a pathfinding grid from the object pool. If there are no grids in the pool, a new grid is created.

The ReturnGrid method is used to recycle a pathfinding grid by resetting its state and returning it to the object pool.

 

The Node class: The Node class is a simple class that represents a pathfinding node. It has a position field that stores the position of the node, and a size field that stores the size of the node.

using UnityEngine;

public class Node : MonoBehaviour
{
    public Vector2 position;   // The position of the node
    public float size = 1f;   // The size of the node
}

 

You can attach this script to an empty GameObject and add a sprite renderer and a collider to make it visible and interactable in the scene.

The Grid class: The Grid class represents the grid used for pathfinding. It has a nodes field that

 

If adapting these scripts to your game is too difficult, you can consider using a pre-built A* pathfinding asset or plugin from the Unity Asset Store. There are many high-quality options available that will allow you to quickly add pathfinding to your game without needing to write custom scripts. Some popular options include A* Pathfinding Project, Aron Granberg's AI package, and Unity NavMesh. These assets are well-documented and typically come with example scenes and scripts to help you get started.

Alternatively, you can hire a freelance developer or a development team to help you integrate pathfinding into your game. Many developers specialize in Unity development and have experience with pathfinding algorithms and implementation. Hiring a developer can save you time and ensure that your pathfinding system is efficient and effective for your game.

 

The D* Lite algorithm is generally considered to be more efficient than the A* algorithm in scenarios where the environment is dynamic and changes frequently. This is because D* Lite is designed to quickly update the pathfinding solution when changes occur, whereas A* requires a complete recalculation of the path from scratch.

However, in scenarios where the environment is static or changes infrequently, A* can be more efficient than D* Lite. A* is a very fast and widely used algorithm that can quickly find the shortest path between two points in a static environment, and it is often used in game development for this reason.

Ultimately, the choice between D* Lite and A* will depend on the specific needs of your game and the characteristics of your environment. If your game has a dynamic environment where objects move frequently, D* Lite may be a better choice. If your environment is static or