游戏人工智能——A*寻路算法实践

简介: A*寻路算法实践一、题目背景随着多媒体设备、虚拟现实、增强现实、物联网等技术的飞跃发展,计算速度与存储容量的日益提高以及相关软件的研究取得长足进步,人工智能的应用得以进一步推广发展起来。地图寻径问题是人工智能技术的一个重要领域。在网络游戏中,寻径问题必须考虑多方面的因素,比如游戏地图中文件结构和起点与目标点之间是否可以连通以及游戏运行时运行内存资源占用、可扩展更新性、安全程度等。长久以来,游戏开发者在开发过程中为了实现这些绞尽脑汁。在搜索寻径问题中,Dijkstra算法是目前许多工程解决最短路径

 A*寻路算法实践

一、题目背景

随着多媒体设备、虚拟现实、增强现实、物联网等技术的飞跃发展,计算速度与存储容量的日益提高以及相关软件的研究取得长足进步,人工智能的应用得以进一步推广发展起来。地图寻径问题是人工智能技术的一个重要领域。在网络游戏中,寻径问题必须考虑多方面的因素,比如游戏地图中文件结构和起点与目标点之间是否可以连通以及游戏运行时运行内存资源占用、可扩展更新性、安全程度等。长久以来,游戏开发者在开发过程中为了实现这些绞尽脑汁。

在搜索寻径问题中,Dijkstra算法是目前许多工程解决最短路径问题采用的理论基础,只是不同工程对Dijkstra算法在不同方面采用了各异的改进方法。常见的搜索算法有深度优先算法(DFS )、广度优先算法(BFS )、迭代加深算法、双向广度优先搜索算法、IDA* 算法、A* 搜索等。它们分为盲目式与启发式两种。盲目式是指其没有目的性的搜索,其可以在一定的规则下全局进行搜索;而启发式则是指有目的性地朝着一定的目标进行搜索。深度优先算法意在每次先向深度中进行搜索,如果未找到结果,再换一条路线进行搜索查询,直到查询到结果。此算法较为容易理解,会占用更小的内存,但是可能会需要更长的时间。广度优先算法每次查询时,首先搜索周围,如若没有查找到结果,则扩大范围,直到查询到结果。此算法虽然速度较快但是占用内存偏多,可以应用到许多关于有速度要求的应用上。迭代加深算法在深度优先算法基础上,增加了一个深度记录,以防止在深度优先算法中无限制地搜索,等其查找到一定的深度时就进行返回。IDA*算法在迭代加深算法基础上增加了一个评估函数,此函数可以对接下来的路径进行评估,从而更快地预估出路径是否存在结果,即可以说是对迭代加深算法的一种优化。但是困难的地方在于评估函数的编写,如果评估函数优秀,那效果良好。相反,如果评估函数一般,它可能会和上一代有着相同的浪费程度。

A * 算法是游戏开发中应用最为广泛的一种路径搜索方法,可以说它是广度优先算法( BFS )的一个升级版。此算法使用了Dijkstra算法的节点信息、广度优先算法的节点扩展方式、加入队列判重、路径点估价函数等。 A * 算法的广泛应用证实了其在搜索路径中的优势与地位。其在人工智能中属于一种典型的启发式搜索算法。而相对于理论,更难的是如何将其应用在游戏工程中,因为游戏中需要考虑到更多元素,包括起点终点连通性以及障碍物、人物碰撞体等。

二、算法原理

   A * 算法是游戏开发中人工智能寻路方面最为常用的算法之一。此算法类似于对广度优先算法的优化,其原理也是在查询点周围进行寻找,其不同点

在于以下两个方面:

   第一方面为加入了估价函数:

F(n)=g(n)+h(n)

g(n)代表某点n从当前位置上距离起点的代价函数值,它是由有限个数起始点与目标点代价函数的值累加构成。h(n)代表点n从其位置上距离终点的代价函数值。即用F(n)代表n点总的路径代价。常用的经典启发函数代价计算方法 h(n)有:曼哈顿距离(Manhattan Distance)、对角线距离、欧几里得距离(Euclidean Distance)等。

第二方面为增加两个表(Open-List与Close-List)来进行路径点的筛选与扩展,更好地统计整理路径点,通过判断和比较来节省资源消耗。

三、算法实现

算法具体过程描述如下:

① 通过循环提取Open-List中的值并不断地比较寻找此时列表中代价最低的路径点,将代价最低点移除Open-List,加入 Close-List后进入 ②。持续循环此步骤直到Open-List中的路径点个数为0 。

② 判断此路径点是否为寻路终点,若是则计算路径,直接进入④。否则,获得此点周围的非障碍点,进入③ 。

③ 判断周围非障碍点是否已经存在于Open-List中,如果存在,重新计算并更新路径点代价函数值。如若不存在,计算路径点代价函数值后并将路径点储存在Open-List中。后将 ① 中的提取点与此周围非障碍点设为父子关系,方便最终路径点的提取。

④ 得到最终点,依次根据节点的父子关系寻找父节点并存入数列中,直至寻找到初始路径点。数列中所有点的集合,即为寻路路径。

四、程序流程

//Grid.cs
using UnityEngine;
using System.Collections;
using System.Collections.Generic;
public class Grid : MonoBehaviour {
    public GameObject NodeWall;
    public GameObject Node;
    // 节点半径
    public float NodeRadius = 0.5f;
    // 过滤墙体所在的层
    public LayerMask WhatLayer;
    // 玩家
    public Transform player;
    // 目标
    public Transform destPos;
    /// <summary>
    /// 寻路节点
    /// </summary>
    public class NodeItem {
        // 是否是障碍物
        public bool isWall;
        // 位置
        public Vector3 pos;
        // 格子坐标
        public int x, y;
        // 与起点的长度
        public int gCost;
        // 与目标点的长度
        public int hCost;
        // 总的路径长度
        public int fCost {
            get {return gCost + hCost; }
        }
        // 父节点
        public NodeItem parent;
        public NodeItem(bool isWall, Vector3 pos, int x, int y) {
            this.isWall = isWall;
            this.pos = pos;
            this.x = x;
            this.y = y;
        }
    }
    private NodeItem[,] grid;
    private int w, h;
    private GameObject WallRange, PathRange;
    private List<GameObject> pathObj = new List<GameObject> ();
    void Awake() {
        // 初始化格子
        w = Mathf.RoundToInt(transform.localScale.x * 2);
        h = Mathf.RoundToInt(transform.localScale.y * 2);
        grid = new NodeItem[w, h];
        WallRange = new GameObject ("WallRange");
        PathRange = new GameObject ("PathRange");
        // 将墙的信息写入格子中
        for (int x = 0; x < w; x++) {
            for (int y = 0; y < h; y++) {
                Vector3 pos = new Vector3 (x*0.5f, y*0.5f, -0.25f);
                // 通过节点中心发射圆形射线,检测当前位置是否可以行走
                bool isWall = Physics.CheckSphere (pos, NodeRadius, WhatLayer);
                // 构建一个节点
                grid[x, y] = new NodeItem (isWall, pos, x, y);
                // 如果是墙体,则画出不可行走的区域
                if (isWall) {
                    GameObject obj = GameObject.Instantiate (NodeWall, pos, Quaternion.identity) as GameObject;
                    obj.transform.SetParent (WallRange.transform);
                }
            }
        }
    }
    // 根据坐标获得一个节点
    public NodeItem getItem(Vector3 position) {
        int x = Mathf.RoundToInt (position.x) * 2;
        int y = Mathf.RoundToInt (position.y) * 2;
        x = Mathf.Clamp (x, 0, w - 1);
        y = Mathf.Clamp (y, 0, h - 1);
        return grid [x, y];
    }
    // 取得周围的节点
    public List<NodeItem> getNeibourhood(NodeItem node) {
        List<NodeItem> list = new List<NodeItem> ();
        for (int i = -1; i <= 1; i++) {
            for (int j = -1; j <= 1; j++) {
                // 如果是自己,则跳过
                if (i == 0 && j == 0)
                    continue;
                int x = node.x + i;
                int y = node.y + j;
                // 判断是否越界,如果没有,加到列表中
                if (x < w && x >= 0 && y < h && y >= 0)
                    list.Add (grid [x, y]);
            }
        }
        return list;
    }
    // 更新路径
    public void updatePath(List<NodeItem> lines) {
        int curListSize = pathObj.Count;
        for (int i = 0, max = lines.Count; i < max; i++) {
            if (i < curListSize) {
                pathObj [i].transform.position = lines [i].pos;
                pathObj [i].SetActive (true);
            } else {
                GameObject obj = GameObject.Instantiate (Node, lines [i].pos, Quaternion.identity) as GameObject;
                obj.transform.SetParent (PathRange.transform);
                pathObj.Add (obj);
            }
        }
        for (int i = lines.Count; i < curListSize; i++) {
            pathObj [i].SetActive (false);
        }
    }
}

image.gif

//FindPath.cs
using UnityEngine;
using System.Collections;
using System.Collections.Generic;
public class FindPath : MonoBehaviour {
    private Grid grid;
    // Use this for initialization
    void Start () {
        grid = GetComponent<Grid> ();
    }
    // Update is called once per frame
    void Update () {
        FindingPath (grid.player.position, grid.destPos.position);
    }
    // A*寻路
    void FindingPath(Vector3 s, Vector3 e) {
        Grid.NodeItem startNode = grid.getItem (s);
        Grid.NodeItem endNode = grid.getItem (e);
        List<Grid.NodeItem> openSet = new List<Grid.NodeItem> ();
        HashSet<Grid.NodeItem> closeSet = new HashSet<Grid.NodeItem> ();
        openSet.Add (startNode);
        while (openSet.Count > 0) {
            Grid.NodeItem curNode = openSet [0];
            for (int i = 0, max = openSet.Count; i < max; i++) {
                if (openSet [i].fCost <= curNode.fCost &&
                    openSet [i].hCost < curNode.hCost) {
                    curNode = openSet [i];
                }
            }
            openSet.Remove (curNode);
            closeSet.Add (curNode);
            // 找到的目标节点
            if (curNode == endNode) {
                generatePath (startNode, endNode);
                return;
            }
            // 判断周围节点,选择一个最优的节点
            foreach (var item in grid.getNeibourhood(curNode)) {
                // 如果是墙或者已经在关闭列表中
                if (item.isWall || closeSet.Contains (item))
                    continue;
                // 计算当前相领节点现开始节点距离
                int newCost = curNode.gCost + getDistanceNodes (curNode, item);
                // 如果距离更小,或者原来不在开始列表中
                if (newCost < item.gCost || !openSet.Contains (item)) {
                    // 更新与开始节点的距离
                    item.gCost = newCost;
                    // 更新与终点的距离
                    item.hCost = getDistanceNodes (item, endNode);
                    // 更新父节点为当前选定的节点
                    item.parent = curNode;
                    // 如果节点是新加入的,将它加入打开列表中
                    if (!openSet.Contains (item)) {
                        openSet.Add (item);
                    }
                }
            }
        }
        generatePath (startNode, null);
    }
    // 生成路径
    void generatePath(Grid.NodeItem startNode, Grid.NodeItem endNode) {
        List<Grid.NodeItem> path = new List<Grid.NodeItem>();
        if (endNode != null) {
            Grid.NodeItem temp = endNode;
            while (temp != startNode) {
                path.Add (temp);
                temp = temp.parent;
            }
            // 反转路径
            path.Reverse ();
        }
        // 更新路径
        grid.updatePath(path);
    }
    // 获取两个节点之间的距离
    int getDistanceNodes(Grid.NodeItem a, Grid.NodeItem b) {
        int cntX = Mathf.Abs (a.x - b.x);
        int cntY = Mathf.Abs (a.y - b.y);
        // 判断到底是那个轴相差的距离更远
        if (cntX > cntY) {
            return 14 * cntY + 10 * (cntX - cntY);
        } else {
            return 14 * cntX + 10 * (cntY - cntX);
        }
    }
}

image.gif

五、程序运行结果

image.gif编辑

image.gif编辑

红色小球作为起始点,而蓝色小球作为目标点,键盘的wasd控制蓝色小球的移动,键盘方向键可以控制红色小球的移动;A*寻路算法可以实现在迷宫中用最短路径找寻目标点,上图中蓝色的路径就是算法所呈现出的最短路径。本次实验使用A*算法实现了一款类似迷宫的小游戏,可以已最快的路径实现起始点与目标点的相遇。

注释:

本次实验是使用unity游戏引擎进行实践。是对网上开源代码与模型进行修改与学习。

相关文章
|
21天前
|
机器学习/深度学习 人工智能 算法
猫狗宠物识别系统Python+TensorFlow+人工智能+深度学习+卷积网络算法
宠物识别系统使用Python和TensorFlow搭建卷积神经网络,基于37种常见猫狗数据集训练高精度模型,并保存为h5格式。通过Django框架搭建Web平台,用户上传宠物图片即可识别其名称,提供便捷的宠物识别服务。
221 55
|
2月前
|
机器学习/深度学习 人工智能 自然语言处理
人工智能的边界拓展:从理论到实践的飞跃####
本文探讨了人工智能(AI)技术的最新进展,特别是深度学习领域的创新如何推动AI从理论研究走向广泛应用。通过分析几个关键领域的实际应用案例,如医疗健康、自动驾驶和自然语言处理,本文揭示了AI技术的潜力及其对社会和经济的深远影响。文章还讨论了当前面临的挑战,包括伦理问题和技术瓶颈,并展望了未来的发展趋势。 ####
|
2月前
|
机器学习/深度学习 人工智能 TensorFlow
人工智能浪潮下的自我修养:从Python编程入门到深度学习实践
【10月更文挑战第39天】本文旨在为初学者提供一条清晰的道路,从Python基础语法的掌握到深度学习领域的探索。我们将通过简明扼要的语言和实际代码示例,引导读者逐步构建起对人工智能技术的理解和应用能力。文章不仅涵盖Python编程的基础,还将深入探讨深度学习的核心概念、工具和实战技巧,帮助读者在AI的浪潮中找到自己的位置。
|
1月前
|
机器学习/深度学习 人工智能 算法
【宠物识别系统】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+图像识别
宠物识别系统,本系统使用Python作为主要开发语言,基于TensorFlow搭建卷积神经网络算法,并收集了37种常见的猫狗宠物种类数据集【'阿比西尼亚猫(Abyssinian)', '孟加拉猫(Bengal)', '暹罗猫(Birman)', '孟买猫(Bombay)', '英国短毛猫(British Shorthair)', '埃及猫(Egyptian Mau)', '缅因猫(Maine Coon)', '波斯猫(Persian)', '布偶猫(Ragdoll)', '俄罗斯蓝猫(Russian Blue)', '暹罗猫(Siamese)', '斯芬克斯猫(Sphynx)', '美国斗牛犬
160 29
【宠物识别系统】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+图像识别
|
30天前
|
机器学习/深度学习 人工智能 算法
深入解析图神经网络:Graph Transformer的算法基础与工程实践
Graph Transformer是一种结合了Transformer自注意力机制与图神经网络(GNNs)特点的神经网络模型,专为处理图结构数据而设计。它通过改进的数据表示方法、自注意力机制、拉普拉斯位置编码、消息传递与聚合机制等核心技术,实现了对图中节点间关系信息的高效处理及长程依赖关系的捕捉,显著提升了图相关任务的性能。本文详细解析了Graph Transformer的技术原理、实现细节及应用场景,并通过图书推荐系统的实例,展示了其在实际问题解决中的强大能力。
155 30
|
1月前
|
存储 算法
深入解析PID控制算法:从理论到实践的完整指南
前言 大家好,今天我们介绍一下经典控制理论中的PID控制算法,并着重讲解该算法的编码实现,为实现后续的倒立摆样例内容做准备。 众所周知,掌握了 PID ,就相当于进入了控制工程的大门,也能为更高阶的控制理论学习打下基础。 在很多的自动化控制领域。都会遇到PID控制算法,这种算法具有很好的控制模式,可以让系统具有很好的鲁棒性。 基本介绍 PID 深入理解 (1)闭环控制系统:讲解 PID 之前,我们先解释什么是闭环控制系统。简单说就是一个有输入有输出的系统,输入能影响输出。一般情况下,人们也称输出为反馈,因此也叫闭环反馈控制系统。比如恒温水池,输入就是加热功率,输出就是水温度;比如冷库,
278 15
|
1月前
|
机器学习/深度学习 人工智能 算法
人工智能浪潮下的编程实践:构建你的第一个机器学习模型
在人工智能的巨浪中,每个人都有机会成为弄潮儿。本文将带你一探究竟,从零基础开始,用最易懂的语言和步骤,教你如何构建属于自己的第一个机器学习模型。不需要复杂的数学公式,也不必担心编程难题,只需跟随我们的步伐,一起探索这个充满魔力的AI世界。
49 12
|
30天前
|
机器学习/深度学习 人工智能 自然语言处理
揭秘人工智能:深度学习的奥秘与实践
在本文中,我们将深入浅出地探索深度学习的神秘面纱。从基础概念到实际应用,你将获得一份简明扼要的指南,助你理解并运用这一前沿技术。我们避开复杂的数学公式和冗长的论述,以直观的方式呈现深度学习的核心原理和应用实例。无论你是技术新手还是有经验的开发者,这篇文章都将为你打开一扇通往人工智能新世界的大门。
|
2月前
|
机器学习/深度学习 人工智能 算法
探索人工智能中的强化学习:原理、算法与应用
探索人工智能中的强化学习:原理、算法与应用
|
2月前
|
机器学习/深度学习 人工智能 自然语言处理
探索人工智能:从理论到实践的旅程
【10月更文挑战第41天】本文旨在通过一次富有启发性的旅程,带领读者深入理解人工智能(AI)的世界。我们将从AI的基本概念出发,逐步探讨其发展历程、核心技术、以及在现实生活中的应用实例。文章将展示如何利用Python编程语言实现简单的机器学习模型,以此揭示AI技术背后的原理和潜力。无论你是AI领域的初学者还是希望深化理解的专业人士,这篇文章都将为你提供有价值的见解和知识。