Unity中的A*寻路算法

1.什么是A*寻路算法

这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC（Non-Player-ControlledCharacter）的移动计算，或线上游戏的BOT（ROBOT）的移动计算上。该算法像Dijkstra算法一样，可以找到一条最短路径；也像BFS一样，进行启发式的搜索。
A*算法是一种启发式搜索算法，启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。
简单来说：A星算法=Dijkstra算法+启发式搜索。

2.为什么选择A*寻路算法

A*是静态网格中求解最短路最有效的方法。也是耗时的算法，不适合寻路频繁的场合。一般来说适合精度需求高的场合。

合适的场景

策略游戏的策略搜索
方格化游戏中的寻路

3.A*寻路算法的实现

寻路区域数据化

要进行寻路，首先需要把寻路的区域进行数据化。将待搜索的区域简化成一个个小方格，最终找到的路径就是一些小方格的组合。

核心公式

F = G + H

F - 方块的总移动代价

G - 开始点到当前方块的移动代价

H - 当前方块到结束点的预估移动代价

概述算法步骤

(1)将初始节点放入到open列表中。

(2)判断open列表。如果为空，则搜索失败。如果open列表中存在目标节点，则搜索成功。

(3)从open列表中取出F值最小的节点作为当前节点，并将其加入到close列表中。

(4)计算当前节点的相邻的所有可到达节点，生成一组子节点。对于每一个子节点：

如果该节点在close列表中，则丢弃它

如果该节点在open列表中，则检查其通过当前节点计算得到的F值是否更小，如果更小则更新其F值，并将其父节点设置为当前节点。

如果该节点不在open列表中，则将其加入到open列表，并计算F值，设置其父节点为当前节点。

(5)转到2步骤

进一步解释

F值是一个估计值，用F(n) = G(n) + H(n) 表示，其中G(n)表示由起点到节点n的预估消耗，H(n)表示节点n到终点的估计消耗。H(n)的计算方式有很多种，比如曼哈顿H(n) = x + y，或者欧几里得式H(n) = sqrt(x^2 + y^2)。本实例采用曼哈顿式。

4.A*寻路算法实例


using System;
using System.Collections;
using System.Collections.Generic;
using System.Drawing;
using TMPro;
using UnityEngine;
using UnityEngine.PlayerLoop;
public enum nodeType { Walkable, Obstacle };
/// <summary>
/// 节点
/// </summary>
public class Node
{
    //是否为障碍物
    public nodeType nodetype;
    //位置
    public Vector2 pos;
    //格子坐标
    public int x, y;
    //父节点
    public Node parent;
    //F=G+H
    public int G, H;
    public int F { get { return G + H; } }

    public Node(nodeType nodetype, Vector2 pos, int x, int y)
    {
        this.nodetype = nodetype;
        this.pos = pos;
        this.x = x;
        this.y = y;
    }
    public Node() { }
}
public class ASTAR : MonoBehaviour
{
    public Vector2 origin;
    public bool isMoving = true;
    public float speed = 0.1f;
    public float stopDistance = 0.1f;
    public float updateTime = 1f;
    public Vector2 target;

    public List<Node> path = new List<Node>();
    List<Node> openList = new List<Node>();
    List<Node> closeList = new List<Node>();
    //地图中心
    public Vector2 mapCenter;
    //高宽
    public float height, width;
    //墙体层级
    public LayerMask WhatLayer;
    // 节点半径
    [Range(0.002f, 1f)]
    public float NodeRadius = 0.2f;
    public Node[,] nodes;
    public bool arrive;
    public int H_Manhattan(Node node, Node end)
    {
        return 10 * ((int)(Math.Abs(node.x - end.x)) + (int)(Math.Abs(node.y - end.y)));
    }

    /// <summary>
    /// 初始化地图
    /// </summary>
    public void InitMap()
    {
        nodes = new Node[(int)(width / NodeRadius / 2), (int)(height / NodeRadius / 2)];
        for (int i = 0; i < (int)(width / NodeRadius / 2); i++)
        {
            for (int j = 0; j < (int)(height / NodeRadius / 2); j++)
            {
                Vector2 center = new Vector2(mapCenter.x + NodeRadius + 2 * NodeRadius * (i - width / NodeRadius / 4),
                    mapCenter.y - NodeRadius + 2 * NodeRadius * (height / NodeRadius / 4 - j));
                bool isWall = Physics2D.OverlapCircle(center, NodeRadius - 0.001f, WhatLayer);
                nodes[i, j] = new Node(
                    isWall ? nodeType.Obstacle : nodeType.Walkable, center, i, j
                );
            }
        }

    }
    public void FindPath(Vector2 startPos, Vector2 endPos)
    {
        if (startPos.x < mapCenter.x - width / 2 ||
            startPos.x > mapCenter.x + width / 2 ||
            startPos.y > mapCenter.y + height / 2 ||
            startPos.y < mapCenter.y - height / 2 ||
            endPos.x < mapCenter.x - width / 2 ||
            endPos.x > mapCenter.x + width / 2 ||
            endPos.y > mapCenter.y + height / 2 ||
            endPos.y < mapCenter.y - height / 2)
        {
            path.Clear();
            return;
        }
        
        Node start = getNode(startPos);
        
        Node end = getNode(endPos);
       
        if (end.nodetype == nodeType.Obstacle)
        {
            path.Clear();
            return;
        }
        closeList.Clear();
        openList.Clear();

        start.parent = null; start.G = 0; start.H = H_Manhattan(start, end);
        openList.Add(start);
        for (int i = -1; i <= 1; i++)
        {
            for (int j = -1; j <= 1; j++)
            {
                // 如果是自己，则跳过
                if (i == 0 && j == 0)
                    continue;
                int g = (i * j) != 0 ? 14 : 10;
                FindNearNode(start.x + i, start.y + j, g, start, end);
            }
        }
        while (openList.Count > 0)
        {
            Node curnode = openList[0];
            for (int i = 0; i < openList.Count; i++)
            {
                if (openList[i].F <= curnode.F && openList[i].H <= curnode.H)
                    curnode = openList[i];
            }
            openList.Remove(curnode);
            closeList.Add(curnode);

            if (curnode == end)
            {
                generatePath(start, end);
                return;
            }
            for (int i = -1; i <= 1; i++)
            {
                for (int j = -1; j <= 1; j++)
                {
                    // 如果是自己，则跳过
                    if (i == 0 && j == 0)
                        continue;
                    int g = (i * j) != 0 ? 14 : 10;
                    FindNearNode(curnode.x + i, curnode.y + j, g, curnode, end);
                }
            }
        }
        generatePath(start, end);
    }
    private void generatePath(Node start, Node end)
    {
        path.Clear();
        if (end != null)
        {
            Node temp = end;
            while (temp != start)
            {
                path.Add(temp);
                temp = temp.parent;
            }
            path.Reverse();
        }
    }

    public Node getNode(Vector2 pos)
    {
        Vector2 t;
        t.x = (pos.x - mapCenter.x - NodeRadius) / (2 * NodeRadius) + width / NodeRadius / 4;
        t.y = -((pos.y - mapCenter.y + NodeRadius) / (2 * NodeRadius) - height / NodeRadius / 4);

        return nodes[(int)t.x, (int)t.y];
    }
    private void FindNearNode(int x, int y, int g, Node parent, Node end)
    {
        if (x < 0 || x >= (int)(width / NodeRadius / 2) ||
            y < 0 || y >= (int)(height / NodeRadius / 2))
            return;
        Node node = nodes[x, y];
        if (node == null ||
            node.nodetype == nodeType.Obstacle ||
            closeList.Contains(node) ||
            openList.Contains(node))
            return;
        node.parent = parent;
        node.G = parent.G + g;
        node.H = H_Manhattan(node, end);
        openList.Add(node);
    }
    IEnumerator Move()
    {
        int count = 0;
        while (count < path.Count)
        {
            while (Vector2.Distance(path[count].pos, transform.position) > stopDistance)
            {
                transform.position = Vector3.Lerp(transform.position, path[count].pos, speed);
                Vector3 temp = transform.localScale;
                //右侧
                if (transform.position.x > path[count].pos.x)
                {
                    temp.x = -Math.Abs(temp.x);
                }
                else
                {
                    temp.x = Math.Abs(temp.x);
                }
                transform.localScale = temp;
                yield return null;
            }
            count++;
        }
        arrive = true;
    }
    public void startMove(Vector2 target)
    {
        if (path.Count == 0)
        {
            InitMap();
        }
        StopCoroutine("Move");
        isMoving = true;
        arrive = false;
        FindPath(transform.position, target);
        if (path.Count == 0)
        {
            stopMove();
        }
        else
        {
            this.target = target;
            StartCoroutine("Move");
        }
    }
    public void stopMove()
    {
        StopCoroutine("Move");
        isMoving = false;
    }
    public void NodeChange(Vector2 vector,nodeType nodeType)
    {
        getNode(vector).nodetype = nodeType;
    }
    private void Start()
    {
        InitMap();
    }
}

Unity中的A*寻路算法

Unity中的A*寻路算法

1.什么是A*寻路算法

2.为什么选择A*寻路算法

3.A*寻路算法的实现

4.A*寻路算法实例

CATALOG

FEATURED TAGS

FRIENDS