跪求一款游戏的寻路算法 10C

根据地图的二值化数据写寻路算法,还需要在其中加上判断障碍物类型,例如:可以破坏和不可破坏。
还有障碍物碰撞检测,简单说就是判断当前人物是否撞墙。

-1

3个回答

这个是图的搜索,一般分为深度优先和广度优先
1.深度优先,每次进入到一个新的格子,判断周围的格子,然后选定第一个非墙且未走过的路,直到没有路了,退回到有其他选择的节点,递归进行
2.广度优先,每次进入一个新的格子,把周围所有的格子都入栈,然后遍历每个,将每个可能性的周围继续搜索,直到找到目标节点

1
qiuzhu001
qiuzhu001 回复llxiaoh: 对啊我现在也就是这个问题,其实我在做一个游戏的脚本现在就是难在不知道怎么样把地图换成二值化黑白地图
2 个月之前 回复
u011892089
llxiaoh 这样怎么考虑是不是墙,是不是可以走得通呢
2 个月之前 回复
qiuzhu001
qiuzhu001 你好我现在有一个想法不知道对不对,就是取出两点之间的坐标,套用距离公式,这样可以么?
2 个月之前 回复

可以考虑A*算法,效率高,有成熟的算法描述,且网上有很多源代码可用。需要加入的只是对于地图中格子的属性描述(是否障碍物、是否可破环等),并在寻路过程中进行判断。

0
qiuzhu001
qiuzhu001 你好我现在有一个想法不知道对不对,就是取出两点之间的坐标,套用距离公式,这样可以么?
2 个月之前 回复

这个用A*算法。 下面我给您贴上核心代码

A*算法类
/// <summary>
    /// 节点移动方向
    /// </summary>
    public enum CompassDirections
    {
        /// <summary>
        /// 未设置
        /// </summary>
        NotSet = 0,
        /// <summary>
        /// 上移(北)
        /// </summary>
        North = 1,
        /// <summary>
        /// 右上移(东北)
        /// </summary>
        NorthEast = 2,
        /// <summary>
        /// 右移(东)
        /// </summary>
        East = 3,
        /// <summary>
        /// 右下移(东南)
        /// </summary>
        SouthEast = 4,
        /// <summary>
        /// 下移(南)
        /// </summary>
        South = 5,
        /// <summary>
        /// 左下移(西南)
        /// </summary>
        SouthWest = 6,
        /// <summary>
        /// 左移(西)
        /// </summary>
        West = 7,
        /// <summary>
        /// 左上移(西南)
        /// </summary>
        NorthWest = 8
    }

    /// <summary>
    /// A*算法,节点对象
    /// </summary>
    public class AStarPoint
    {
        /// <summary>
        /// 从起点,沿着产生的路径,移动到网格上指定方格的移动耗费。 
        /// </summary>
        public int G = 0;
        /// <summary>
        /// 从网格上那个方格移动到终点B的预估移动耗费。
        /// </summary>
        public int H = 0;

        /// <summary>
        /// X 坐标
        /// </summary>
        public int X
        {
            get { return CurrentPoint.X; }
            set { CurrentPoint.X = value; }
        }
        /// <summary>
        /// Y 坐标
        /// </summary>
        public int Y
        {
            get { return CurrentPoint.Y; }
            set { CurrentPoint.Y = value; }
        }

        /// <summary>
        /// 初始化当前节点的坐标
        /// </summary>
        /// <param name="_x">X坐标</param>
        /// <param name="_y">Y坐标</param>
        public AStarPoint(int _x, int _y)
        {
            CurrentPoint = new Point(_x, _y);
        }

        /// <summary>
        /// 初始化当前节点对象
        /// </summary>
        /// <param name="currentPoint">当前节点</param>
        /// <param name="parentPoint">父节点</param>
        /// <param name="costG">代价G</param>
        /// <param name="costH">代价H</param>
        public AStarPoint(Point currentPoint, AStarPoint parentPoint, int costG, int costH)
        {
            this.CurrentPoint = currentPoint;
            this.ParentPoint = parentPoint;
            this.G = costG;
            this.H = costH;
        }

        /// <summary>
        /// 当前节点
        /// </summary>
        public Point CurrentPoint = new Point(0, 0);
        /// <summary>
        /// 父节点
        /// </summary>
        public AStarPoint ParentPoint = null;

        /// <summary>
        /// F = G + H
        /// </summary>
        public int F
        {
            get
            {
                return this.G + this.H;
            }
        }

        /// <summary>
        /// 重置当前节点的父节点和代价G
        /// </summary>
        /// <param name="parentPoint">父节点</param>
        /// <param name="costG">代价G</param>
        public void ResetParentPoint(AStarPoint parentPoint, int costG)
        {
            this.ParentPoint = parentPoint;
            this.G = costG;
        }
    }

0
qiuzhu001
qiuzhu001 回复qq_36718671: 我就是只要生成二值化的黑白地图就可以了您可以留个联系方式么
2 个月之前 回复
qiuzhu001
qiuzhu001 回复qq_36718671: 人物当前坐标这些都可以搞啊就是不知道怎么去生成二值化的黑白图片啊
2 个月之前 回复
qq_36718671
qq_36718671 回复qiuzhu001: 如果是本游戏可以判断人物在地图坐标数组位置,然后生成图片。要是外挂系统,对不起啊!这个要指针相关内存操作,我不会。
2 个月之前 回复
qiuzhu001
qiuzhu001 你好我您知道怎么通过游戏内存绘制出游戏当前角色所处的地图的二值化黑白图片么?
2 个月之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
深入理解游戏中寻路算法
摘要: 看似寻常的路径行走,在程序看来就需要一定的寻路算法来解决,如何在最短时间内找到一条路径最短的路线,这是我们首要考虑的问题。 如果你玩过MMOARPG游戏,比如魔兽,你会发现人物行走会很有趣,为了模仿人物行走的真实体验,他们会选择最近路线达到目的地,期间会避开高山或者湖水,绕过箱子或者树林,直到走到你所选定的目的地。 这种看似寻常的寻路在程序实现起来就需要一定的寻路算法来解决,如
即时战略游戏中实用的寻路算法总结与比较
本文授权转载自知乎关于《即时战略游戏中实用的寻路算法都有哪些,比较如何?》的回答,文/伍一峰 rts中的寻路系统一般需要满足有以下几个条件, 1. 效率高,因为rts普遍地图大,单位多,所以处理效率很重要 2. 易编辑,以便于level design 3. 效果真实,如能找出最优(或者是看上去合理) 4. 可以应对动态的游戏世界,例如起建筑 如@王亞暉所说,
浅谈游戏中的A*寻路算法
作者:锐亚教育(www.insideria.cn) 本文为锐亚教育原创文章,转载请注明转载自锐亚教育 A*寻路 A*算法基本原理 A*(念作A星)算法对初学者来说的确有些难度。本文并不试图对这个话题作权威性的陈述,取而代之的是描述算法的原理,使你可以在进一步的阅读中理解其他相关的资料。下面我们就利用图文并茂的方式向大家展示它的基本原理。 简化搜索区域   如图1所示,假...
浅谈游戏自动寻路A*算法
寻路是游戏中非常重要的一个元素,如何找到一条最短的路径是程序需要设计的算法,现在最为流行的寻路算法是A*算法。A*算法与状态空间搜索结合的相当紧密。     状态空间搜索,就是将问题求解的过程表现为从初始状态到目标状态寻找这个路径的过程,通俗的说就是在解一个问题的时候找到一条解题过程可以从求解的开始到问题的结束。     由于求解过程中求解条件的不确定与不完备性使得问题的求解过冲中的分支有很多
【Unity3D】学习笔记(第8记)游戏中的自动寻路算法
  最近两天刚好有空研究了下游戏中的自动寻路功能,收获颇丰,感觉用相应的算法去解决相应的问题真的非常重要啊!至少比自己想的流水账逻辑流程管用。看来以后得花多点时间研究下算法方面的知识了。   游戏中的自动寻路,顾名思义就是找路,从地图找到从起点到终点的可行最短路径。既然是从地图找路,那么地图就应该是可数据化的,要不怎么找呢。   所以自动寻路的有两个重点是分别是地图数据化和搜索算法。   地...
游戏里的跨地图寻路算法
转自:http://www.cnblogs.com/lijiajia/p/7150162.html前段时间遇到一个跨地图寻路的需求,需要在任意两个地图之间自动寻路。我们的寻路算法用的是AStar,每个地图都有一份格子数据,地图之间有传送门通过。首先这是一个最短路径问题,常用的最短路径算法有Dijkstra、Floyd。这里我的思路是选择Dijkstra来实现。具体的Dijkstar算法原理可以参考...
静态游戏环境中几种实用的自动寻路算法
http://www.gameres.com/447725.html GameRes游资网授权发布 文 / 王凝   想从一个更系统的角度来叙述pathfinding这一系列问题,希望可以成为一个更容易理解的tutorial。这里所涉及的寻路算法不限于RTS这类游戏,其中一些方法可能更适合静态的游戏环境。   这里所包含的topics涉及:   1.游戏地图的划分及其优劣性
探索小游戏(三):A*算法实现自动寻路
关于A*算法,推荐一篇博客: 这里写链接内容博客中介绍了A*算法的原理,通过这个探索小游戏实现自动寻路,结合代码加深对A*算法的理解。首先定义了一个Point类:local Point = class('Point',{}) -- r 行 c 列 function Point:ctor(r,c) self.r = r self.c = c endfunction Point:get
A* 算法处理游戏自动寻路
这两天研究了下 A* 寻路算法, 主要学习了这篇文章, 但这篇翻译得不是很好, 我花了很久才看明白文章中的各种指代. 特写此篇博客用来总结, 并写了寻路算法的代码, 觉得有用的同学可以看看. 另外因为图片制作起来比较麻烦, 所以我用的是原文里的图片.         当然寻路算法不止 A* 这一种, 还有递归, 非递归, 广度优先, 深度优先, 使用堆栈等等, 有兴趣的可以研究研究~
即时战略游戏中实用的寻路算法都有哪些,比较如何?
 rts中的寻路系统一般需要满足有以下几个条件, 1. 效率高,因为rts普遍地图大,单位多,所以处理效率很重要 2. 易编辑,以便于level design 3. 效果真实,如能找出最优(或者是看上去合理) 4. 可以应对动态的游戏世界,例如起建筑 如 @王亞暉 所说,一般用于寻路的算法是A Star, 首先是A Star有利用到
游戏开发中A*自动寻路算法解析
在游戏中应用A*算法主要是以下步骤: 1.将地图划分包含多个等大区域的网络:传统做法是将地图划分为多个等大的正方形小格子,或者也有将地图划分为由菱形小格子组成;另外如果将地图划分为多个凸多边形情况下,便是NAV导航网格寻路的思路了。       每个小格子就是一个导航路点(waypoint),这种寻路算法就是常说的路点寻路算法。       疑问:地图有多大,小格子多大一个,就会对寻路的效率...
RTS游戏中A*寻路算法优化
 RTS游戏中A*寻路算法优化(转) (2012-05-22 19:49:26) 转载▼ 标签: 杂谈 分类: 学习   众所周知,A*算法在游戏中使用相当广泛。对于单人寻路的网络游戏,A*算法当然是游刃有余。但是当A*算法使用到寻路人数动则上百的RTS游戏中却会使得捉襟见付。电脑的运算当然是不能全部让给一个
《C++游戏开发》十七 游戏中的寻路算法(三):A*算法原理
A*算法路径的评价公式为F=G+H 其中H为某个已达格子到目的地的估算距离,估算的方法有很多种,比如: 1、曼哈顿距离:即两点水平距离加上竖直距离。比如(x1,y1)到(x2,y2)的曼哈顿距离就是|x2-x1|+|y2-y1|。 2、欧式距离:即两点之间的真实距离。(x1,y1)到(x2,y2)的欧式距离就是 sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1))。 3、切比雪夫距离:水平方向和竖直方向上的距离最大
盘点即时战略游戏中高实用性寻路算法
原文:   编者按:在即时战略(RTS)游戏中,寻路系统可谓其核心要素之一,但它的算法也是较难攻克的内容之一。在这篇文章中,来自iSamurai工作室的伍一峰为广大游戏开发者带来了他对即时战略游戏寻路算法的深入思考。   在即时战略(RTS)游戏中,寻路系统一般需要满足以下几个条件:   1)效率高,由于rts地图普遍较大,单位较多,因此处理效率很重要;   2)易编辑,便于l
游戏人工智能之A *寻路算法(适合初学者)
引言:小生今日分享的是寻路系统中常用的A*寻路算法,在此特别感谢Siki学院的老师们。如果大神发现错误,请评论告知!再次感谢!开发版本:unity 2017.1.1f1适合人群:Unity有一定基础的童鞋开启学习之旅吧!寻路:寻找最短路径并避开障碍物首先将地图虚拟化,将地图划分为一个一个的小方块,这样可以用二维数组来表示地图。如下所示,绿色块(A)是起点,红色块(B)是终点,中间蓝色块是障碍物,白...
java游戏AI寻路算法(非常实用,附带源码与可视操作界面)
java游戏AI寻路算法(非常实用,附带源码与可视操作界面),类似于A*但又不同于A*!很实用!供参考!
【H5/JS】游戏常用算法-路径搜索算法-A*寻路算法
原理参考:点击打开链接&amp;lt;!DOCTYPE html&amp;gt; &amp;lt;html lang=&quot;en&quot;&amp;gt; &amp;lt;head&amp;gt; &amp;lt;meta name=&quot;viewport&quot; content=&quot;width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=0&quot;&amp;gt; &amp
游戏地图寻路算法 -- A*(分析 + 实现 + 教学视频连接)
首先理解游戏地图怎么设定那里不让走那里让走: 把图片分成一块一块格子,标记各个格子是否能走; 介绍一下A* A*的核心就是 : 一个评估函数 F = G + H + 2个表假设 从A点到B点: F = G + H: - F: 从A到B的最短路径长度; - G: 从起点,沿着产生的路径, 移动到指定点的耗费; - H: 预估值,估计从A到B多长
RTS游戏的寻路算法:群体移动时如何绕开友军阻挡
  参考: https://www.zhihu.com/question/29885931   wq yang 这个函数: https://github.com/spring/spring/blob/a2a84b654354e5da1f828b5fd7db280d90d0596d/rts/Sim/MoveTypes/ClassicGroundMoveType.cpp#L754 主...
游戏开发中一种新的高效寻路算法 B*寻路算法
与传统的A*寻路算法相比,本文提出的B*寻路算法具备更高的效率。在网络游戏中,寻路已经成为一种自然的AI需求,但在游戏服务器端,除非有独立的AI处理线程或独立的AI服务器模块,否则无法允许可能消耗大量时间的寻路搜索,即使是业界公认最有效的A*寻路算法。">与传统的A*寻路算法相比,本文提出的B*寻路算法具备更高的效率。在网络游戏中,寻路已经成为一种自然的AI需求,但在游戏服务器端,除非有独立的AI处理线程或独立的AI服务器模块,否则无法允许可能消耗大量时间的寻路搜索,即使? [更多]
如何在Cocos2D游戏中实现A*寻路算法(一)
大熊猫猪·侯佩原创或翻译作品.欢迎转载,转载请注明出处. 如果觉得写的不好请告诉我,如果觉得不错请多多支持点赞.谢谢! hopy ;) 免责申明:本博客提供的所有翻译文章原稿均来自互联网,仅供学习交流之用,请勿进行商业用途。同时,转载时不要移除本申明。如产生任何纠纷,均与本博客所有人、发表该翻译稿之人无任何关系。谢谢合作! 该篇博客由iOS课程团队的Johann Fradj发布,他现在是一个
A*自动寻路算法—java版
前段时间一直在写一个小游戏,需要用到自动寻路,于是就百度了一番,终于完成了,现在将原理及代码展示出来,方便有兴趣的朋友参考。说明一下,本次只展示了上下左右四个方向的移动。如图:如果从A点走到B点,有很多条路线,如何自动找到路线,以及如何找到最短的路线,就是这次要解决的问题。首先,需要讲解一下计算的公式,F=G+H,主要用于判断最佳路线。G:(左上角数值)起点到当前点的消耗(即步数),比如C点,与A...
基于JAVA的迷宫自动寻路算法实现
通过鼠标点击来获取一个目的地,然后方块自动寻路并到达目的地,提供了Keylistener借口和Runnable接口,可进行相关扩展。
游戏中的人工智能之流场寻路
本文介绍一种近几年开始流行了一种寻路技术,美其名曰流场寻路,有人说它的出现颠覆了RTS寻路技术。它与传统的A*寻路不同,希望通过本文可以让更多的朋友了解该技术。
一种高效的寻路算法——B*寻路算法
转:http://qinysong.iteye.com/blog/678941 在此把这个算法称作B* 寻路算法(Branch Star 分支寻路算法,且与A*对应),本算法适用于游戏中怪物的自动寻路,其效率远远超过A*算法,经过测试,效率是普通A*算法的几十上百倍。  通过引入该算法,一定程度上解决了游戏服务器端无法进行常规寻路的效率问题,除非服务器端有独立的AI处理线程,否则在
游戏中常用的寻路算法的分享(1):A*算法介绍
http://www.gameres.com/484360.html  物体的移动算法似乎显得很简单,然而寻路规划问题却十分复杂。考虑下面这个例子:   这个单位的初始位置在地图的下方,想要到达地图的顶部。如果物体所能侦测到的地方(粉色部分所示)并没有障碍,那么物体就会直接向上走到它的目标位置。但在距离顶端较近的位置时,物体侦测到了障碍,因而改变了方向。该物体将不得不行
RPG游戏制作-03-人物行走及A*寻路算法
在游戏中,可以控制人物的方法一般有:1.键盘 2.虚拟摇杆 3.鼠标 4.手机触碰。键盘一般是在PC端较为常用,如果在游戏中使用wasd等操作人物的话,那么在移植到安卓端时,就需要使用虚拟摇杆或虚拟按钮来模拟键盘,以实现处理的统一性。鼠标类似于手机的单点触碰,而手机触碰一般分为单点和多点触碰。这里使用触碰操作人物。 既然使用触碰进行操作人物,那么就需要一个从出发点到目的地的路径,这里选用的是A星...
C++中简单寻路算法的介绍
    首先,每次做一个东西,我们都应该当成一个项目来做,做项目,肯定要明白自己要做什么,寻路算法怎样给代价介绍清楚,就要列好步骤,对项目有个清晰的认识,按照步骤来做,思路很清楚,不容易出错。寻路算法的步骤:1.先做出一个界面      用图形库比较直观    二维数组来实现2. 寻路算法: (1)首先应该有一个辅助二维坐标值和界面中坐标的值一样 (坐标, 是否走过,还应该有值)(2)规定人物走的...
A*算法、自动寻路算法C++源码
A*算法、自动寻路算法C++源码
【游戏跨场景寻路】基于as3语言的游戏地图跨场景寻路功能的实现
一般在2D游戏场景中,我们通常需要用到寻路,常用的就是A星算法。 如果涉及到多个场景间寻路,就需要先找到涉及链接的场景,在游戏中通常指的是《传送门》 什么是传送门?在2D游戏中,走一到一个场景的边缘处,通常会有一个带特效的传送点。 比如:通往 长安城 等等。这个就是一个链接点。 比如我在:新手村,想要寻路到 长安城 的某个NPC处。 在程序中通常的做法是:先找到 新手村
as3A*寻路算法与它的速度
如果你是一个游戏开发者,或者开发过一些关于人工智能的游戏,你一定知道A*算法,如果没有接触过此类的东东,那么看了这一篇文章,你会对A*算法从不知道变得了解,从了解变得理解。 我不是一个纯粹的游戏开发者,我只是因为喜欢而研究,因为兴趣而开发,从一些很小的游戏开始,直到接触到了寻路等人工智能,才开始查找一些关于寻路方面的文章,从而知道了A*算法,因为对于初期了解的我这个算法比较复杂,开始只是copy
Unity3D A* 寻路算法
笔者介绍:姜雪伟,IT公司技术合伙人,IT高级讲师,CSDN社区专家,特邀编辑,畅销书作者,国家专利发明人;已出版书籍:《手把手教你架构3D游戏引擎》电子工业出版社和《Unity3D实战核心技术详解》电子工业出版社等。CSDN视频网址:http://edu.csdn.net/lecturer/144 A*寻路算法通常是应用于大型网络游戏中,A*算法通常应用在服务器中,在移动端游戏开发中,A*算法
Cocos2d-x 寻路算法之三 A Star
1.A Star 寻路算法介绍: 看过之前的两篇文章:《Cocos2d-x 寻路算法之二 离目的地的距离优先》,《Cocos2d-x 寻路算法之一 距离优先》的读者知道,这两种寻路算法都有问题,前一个搜索太广了,资源浪费;后一个还不够聪明,有时候会找不到最佳路线。为什么要先介绍这两种不佳的算法呢?因为A Star 寻路算法就是前面两者的结合。同时考虑离起点的距离和离终点的距离。
Python程序_利用递归法和pygame实现迷宫寻路的动态展示
Pospro写的一个Python程序:利用递归法和pygame实现迷宫寻路的动态展示
流场寻路算法学习及实现
流场寻路算法简单实现 Flow field pathfinding algorithm implementation 当前实现的主要效果: 1.地图上随机分布200个移动目标; 2.移动目标可绕过障碍物,沿着地图的流场找到最短路径(最小代价的路径)到达目标点; 3.可通过点击地图上的非障碍物区域,实时的更改目标地点,并更新流场; 4.可通过按着鼠标左键在地图上拖拽,实时绘制障碍物,并动态更新
2D地图和3D地图的A*寻路算法
制作虚拟社区类的游戏,一个好的寻路算法是很重要的,其中A*寻路算法是用得最广泛的了。 而普通的2D地图的A*算法比较普遍,而用Flash开发3D地图(可以旋转视角)的寻路算法还是比较少的。 现在国外有个家伙(drawk)研究出一些成果了。 http://drawk.wordpress.com/2007/07/04/3d-pathfinding-in-as3/ 不过我测试了一下,...
高效游戏地图寻路,提供算法以及源码
高效游戏地图寻路,一个老游戏的,可以提供一些思路
战旗游戏简单寻路的例子续
直接上代码,里面的注释很详细,只是简单的实现了 &amp;lt;!DOCTYPE html&amp;gt; &amp;lt;html lang=&quot;en&quot;&amp;gt; &amp;lt;head&amp;gt; &amp;lt;meta charset=&quot;UTF-8&quot;&amp;gt; &amp;lt;title&amp;gt;走动步数&amp;lt;/title&amp;gt; &amp;lt;/head&amp;gt; &amp;lt;body &
3d地图的a*寻路
对于2d地图的a星算法其实很多。原理都是一样的,我做这个的3d的寻路其实只是在2d地图数据中加入了一个高度的数据,而在权重中由原来的两个坐标的勾股定理变为三维坐标系的勾股定理,以前我做cocos2dx开发时曾写过一个lua版的a星,就用这个作为说明吧(涉及a星的原理就不必再说明了,很多博客都会有): 其中的mapInfo可以更改为如下 self.MapInfo =      {  
游戏中常用的寻路算法的分享(4)处理移动中的障碍物
http://www.gameres.com/thread_487419_1_1.html 一个寻路算法会计算出一条绕过静止障碍物的路径,但如果障碍物会移动呢?当一个单位移动到达某特定点时,原来的障碍物可能不在那点了,或者在那点上出现了新的障碍物。如果路线可以绕过典型的障碍物,那么只要使用单独的避障算法来配合你的寻路算法。寻路算法会寻找到期望的路径,并且在沿着路径的同时绕过障碍物。但是如果障碍物
文章热词 设计制作学习 机器学习教程 Objective-C培训 交互设计视频教程 颜色模型
相关热词 mysql关联查询两次本表 native底部 react extjs glyph 图标 跪求人工智能编程培训 一款单机游戏开发价格