当前位置: 首页 > article >正文

游戏AI实现-寻路算法(Dijkstra)

戴克斯特拉算法(英语:Dijkstra's algorithm),又称迪杰斯特拉算法、Dijkstra算法,是由荷兰计算机科学家艾兹赫尔·戴克斯特拉在1956年发现的算法。

算法过程:

1.首先设置开始节点的成本值为0,并将开始节点放入检测列表中。

2.将检测列表中的所有点按到目标点所需的成本值排序,选择成本最小的节点作为当前节点,并将其移出检测列表。

3.将当前点周围的点中不包含在检测列表中的点加入到检测列表,将周围点加入到已检测列表中。

4.更新检测列表中的节点到当前节点的成本值。

5.重复2,3,4直到找到目标点。

代码实现:

public class Dijkstra : FindPathAlgorithm
{
    public Dijkstra(int[,] mapData, int xCount, int zCount) : base(mapData, xCount, zCount){}

    public override List<Vector2Int> FindPath(Vector2Int startPos, Vector2Int goalPos)
    {
        DataNode dataNode = this.DijkstraFind(startPos, goalPos);
        if (dataNode == null)
        {
            Debug.LogError("寻路有误,请检查参数是否正确");
            return null;
        }
        return Utils.GetPath(dataNode);
    }

    DataNode DijkstraFind(Vector2Int startPos, Vector2Int goalPos)
    {
        //存储要检测的点
        List<DataNode> frontier = new List<DataNode>();
        //存储已经检测的点
        List<Vector2Int> reached = new List<Vector2Int>();

        DataNode startNode = new DataNode(startPos, null);
        startNode.gCost = 0;
        frontier.Add(startNode);
        reached.Add(startPos);

        while (frontier.Count > 0)
        {
            DataNode currentNode = GetLowestgCostNode(frontier);
            frontier.Remove(currentNode);
            if (currentNode.pos == goalPos)
            {
                Debug.Log("完成!!!");
                return new DataNode(goalPos, currentNode.parent);
            }

            List<DataNode> neighbors = GetNeighbors(currentNode.pos, reached);
            foreach (DataNode neighbourNode in neighbors)
            {
                if (!frontier.Contains(neighbourNode))
                {
                    neighbourNode.parent = currentNode;
                    frontier.Add(neighbourNode);
                }
                reached.Add(neighbourNode.pos);
            }

            this.UpdateCost(frontier, currentNode);
        }

        return null;
    }

    //更新成本值
    void UpdateCost(List<DataNode> nodes, DataNode currentNode)
    {
        for (int i = 0; i < nodes.Count; i++)
        {
            int newCost = currentNode.gCost + CalculateDistanceCost(nodes[i].pos, currentNode.pos);
            if (nodes[i].gCost > newCost)
            {
                nodes[i].gCost = newCost;
            }
        }
    }

    List<DataNode> GetNeighbors(Vector2Int current, List<Vector2Int> reached)
    {
        List<DataNode> neighbors = new List<DataNode>();
        for (int i = 0; i < Utils.pointDir.Count; i++)
        {
            Vector2Int neighbor = current + Utils.pointDir[i];
            if (this.IsCanAdd(neighbor, reached))
            {
                neighbors.Add(new DataNode(neighbor, null));
            }
        }
        return neighbors;
    }

    bool IsCanAdd(Vector2Int current, List<Vector2Int> reached)
    {
        if (reached.Contains(current))
            return false;
        if (current.x >= 0 && current.y >= 0 && current.x < MapData.m_MapData.GetLength(1) && current.y < MapData.m_MapData.GetLength(0))
        {
            //如果是障碍物,则不能被Add
            if (MapData.m_MapData[current.y, current.x] == 1)
            {
                return false;
            }
            return true;
        }
        return false;
    }

    private int CalculateDistanceCost(Vector2Int a, Vector2Int b)
    {
        return Mathf.Abs(a.x - b.x) + Mathf.Abs(a.y - b.y);
    }

    private DataNode GetLowestgCostNode(List<DataNode> pathNodeList)
    {
        DataNode lowestFCostNode = pathNodeList[0];
        for (int i = 1; i < pathNodeList.Count; i++)
        {
            if (pathNodeList[i].gCost < lowestFCostNode.gCost)
            {
                lowestFCostNode = pathNodeList[i];
            }
        }
        return lowestFCostNode;
    }
}

结果:

参考链接:

Pathfinding in Unity - Part3: Dijkstra Algorithm Theory (youtube.com)

Pathfinding in Unity - Part4: Dijkstra Algorithm Implementation (youtube.com)

How Dijkstra's Algorithm Works (youtube.com)

戴克斯特拉算法 - 维基百科,自由的百科全书 (wikipedia.org)


http://www.kler.cn/a/447957.html

相关文章:

  • UVM 验证方法学之interface学习系列文章(十二)virtual interface 终结篇
  • 【NLP 16、实践 ③ 找出特定字符在字符串中的位置】
  • 全脐点曲面当且仅当平面或者球面的一部分
  • Windows中运行Linux(WSL)
  • AI的进阶之路:从机器学习到深度学习的演变(三)
  • gitee给DeployKey添加push权限
  • 【机器人】机械臂位置、轨迹和转矩控制概要
  • 【计算机视觉基础CV-图像分类】01- 从历史源头到深度时代:一文读懂计算机视觉的进化脉络、核心任务与产业蓝图
  • 从0-1开发一个Vue3前端系统页面-9.博客页面布局
  • 医药垃圾分类管理系统|Java|SSM|JSP|
  • 【序】前端监控:打造高效稳定的用户体验
  • JAVA数字人创作文案视频链接提取数字人源码小程序+公众号+APP+H5
  • Mysql复习(二)
  • ES学习Promise对象(九)
  • 分布式系统架构2:服务发现
  • 【CVE-2024-38819】:功能性 Web 框架中的路径遍历漏洞(内含复现)
  • Docker的容器编排
  • draw.io 导出svg图片插入word后模糊(不清晰 )的解决办法
  • datasets笔记:两种数据集对象
  • 【前端爬虫】关于如何获取自己的请求头信息(user-agent和cookie)
  • 单片机:实现PWM LED灯亮度调节及Proteus仿真(附带源码)
  • 【编辑器扩展】打开持久化路径/缓存路径/DataPath/StreamingAssetsPath文件夹
  • Restaurants WebAPI(三)——Serilog/FluenValidation
  • SSH特性|组成|SSH是什么?
  • Netty解决粘包半包问题
  • Spring常见问题