星际争霸，魔兽争霸中那样大群单位的寻路该适用何种算法实现，有推荐教材吗

2021-04-29 19:08发布

站内问答 / 游戏开发
1603 3 4
发送
3条回答
studentaaa
2楼 · 2021-05-03 19:09

剥除代码，A* 算法非常简单。算法维护两个集合：OPEN 集和 CLOSED 集。OPEN 集包含待检测节点。初始状态，OPEN集仅包含一个元素：开始位置。CLOSED集包含已检测节点。初始状态，CLOSED集为空。从图形上来看，OPEN集是已访问区域的边界，CLOSED集是已访问区域的内部。每个节点还包含一个指向父节点的指针，以确定追踪关系。

　　算法有一个主循环，重复地从OPEN集中取最优节点n（即f值最小的节点）来检测。如果n是目标节点，那么算法结束；否则，将节点n从OPEN集删除，并添加到CLOSED集中，然后查看n的所有邻节点n’。如果邻节点在CLOSED集，它已被检测过，则无需再检测（*）；如果邻节点在OPEN集，它将会被检测，则无需此时检测（*）；否则，将该邻节点加入OPEN集，设置其父节点为n，到n’的路径开销g(n’) = g(n) + movementcost(n, n’)。

　　这里有更详细的介绍，其中包含交互图。

　　（*）这里我略过了一个小细节。你应当检查节点的g值，如果新计算得到的路径开销比该g值低，那么要重新打开该节点（即重新放入OPEN集）。


具体代码实现:

  1. OPEN = priority queue containing START


  3. CLOSED = empty set


  5. while lowest rank in OPEN is not the GOAL:


  7.   current = remove lowest rank item from OPEN


  9.   add current to CLOSED


  11.   for neighbors of current:


  13.     cost = g(current) + movementcost(current, neighbor)


  15.     if neighbor in OPEN and cost less than g(neighbor):


  17.       remove neighbor from OPEN, because new path is better


  19.     if neighbor in CLOSED and cost less than g(neighbor): **


  21.       remove neighbor from CLOSED


  23.     if neighbor not in OPEN and neighbor not in CLOSED:


  25.       set g(neighbor) to cost


  27.       add neighbor to OPEN


  29.       set priority queue rank to g(neighbor) + h(neighbor)


  31.       set neighbor's parent to current


  33. reconstruct reverse path from goal to start


  35. by following parent pointers

蜗牛
3楼 · 2021-05-21 09:44

楼主可以查阅下知乎或者其他的文章找寻一下最优方案

Transform
4楼 · 2021-08-13 10:03

如果使用Unity一般用A*算法，算法比较复杂，楼主可以百度下此知识点。

相关问题推荐

  • Unity中如何把在另一个项目中做好的场景导入到其2020-05-20 09:59
    回答 6

    第一步:对着Assets点击右键,选择ExportPackage第二步:选择场景文件以及和场景相关的资源或者素材,然后点击Export第三步:给导出的资源取名,并且选择要保存的位置即可

  • 我打游戏里还是不是可以从事游戏开发啊2020-03-24 09:33
    回答 87
    已采纳

    玩游戏玩的很好，说明你对于游戏里面的规则、剧情设置还是比较了解的，对于从事游戏相关岗位来说也是优势之一。但是学习游戏开发还是要对游戏开发的工作内容做进一步的了解，游戏开发涉及代码较多，可以通过进一步的了解，判断自己是否适合学习这个方向，另外...

  • 学游戏开发难吗？自学好还是培训好，要学多久啊 2020-05-18 11:36
    回答 11

    游戏开发入门不难。后期发展需要你有丰富的奇思妙想。游戏开发肯定是培训好，自学学得不系统，并且不易发现自身薄弱之处。游戏开发的学习时长还是要看你自己对知识与技术的掌握能力，一般来说，游戏开发的学习时长大约在五个月左右。...

  • 游戏开发难学吗，自学有可能吗？2020-05-20 16:27
    回答 18

    个人觉得如果有一定的技术基础的话还是可以考虑自学，如果零基础的话可能会有些难度

  • 【Unity粒子】unity粒子特效不显示怎么办？Unity3D 2020-12-23 14:34
    回答 10

    问题还是出在粒子的sorting fudge。在unity的2d模式下，游戏本身的背景相当于是sorting fudge的0，当你把粒子的sorting fudge设为0以上的时候，粒子就都会被背景盖住。所以在3d模式下给alpha正值来给add垫底的话，到了2d模式下就会通通不显示。所以遇上这样的...

  • 和平精英是用什么语言写的呢2021-01-24 14:17
    回答 17

    虚幻4引擎，你会看到和平精英加载页面左下角有这个图标。

  • unity引擎都开发过哪些著名的游戏大作？2020-06-24 13:48
    回答 8
    已采纳

    转载知乎上的两位答友的回答，各有道理。作者：风小锐链接：https://www.zhihu.com/question/322249959/answer/675883379来源：知乎著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。未来Unity有可能出现3A大作吗？ 有可能。基于Unity已...

  • 【Unity基础】unity材质球怎么创建？Unity3D Unity脚本类 2020-10-30 10:51
    回答 11

    在Assets文件夹里面.点击右键Create/Material即可以创建材质球

  • 如何实现在一面墙上挖一个矩形的门？Unity3D 2021-08-06 19:59
    回答 23

    可以让模型师直接作出这样的形状，如果用纯Unity制作，就要用基本游戏对象拼接了，包括楼梯，城堡，都可以拼接出来。正常情况不会这样做，因为不够精美，都是建模师来实现，毕竟Unity不属于专业的建模软件，侧重于实现功能。...

  • 如何学习UNITY的粒子系统?2021-07-20 10:37
    回答 18

    粒子系统由粒子发射器、粒子动画器和粒子渲染器三部分组成，主要用于游戏场景中一些特殊效果，如水、烟火等等

  • 用Unity写小游戏是否比用Python简单？2021-07-20 10:34
    回答 18

    首先，Python开发游戏非常尴尬，原因是没有好用的游戏开发库。Python开发游戏仅推荐PyGame，PyGame是对多年以前很流行的游戏开发库——SDL的封装。但是说实话功能太简陋了，做个动画都得考虑刷新的问题。楼主要做简单小游戏，只需要画一两周熟悉Unity引擎，然...

  • 制作可交互的水体具体分为哪些步骤？分别是什么？2021-07-13 13:34
    回答 9

    1.标记水体碰撞的位置2.计算水波的传递 通过波动公式，3D或者2D 波动公式都行3.水面顶点采样波动传递结果计算结果做顶点Y轴偏移

  • Unity实时阴影实现的原理是什么？2021-07-13 13:32
    回答 15

    Unity3D中两种阴影的实现传统的ShadowMapShadowMap说起来十分简单，把摄像机和光源的位置重叠，那么场景中该光源的阴影区域就是那些摄像机看不到的地方，主要应用在前向渲染路径中。具体实现分以下几个步骤：如果有平行光开启了阴影，Unity就会为该光源计算它...

  • Unity有哪些常用且好用的插件？2021-07-12 15:14
    回答 18

    Doozy UI是Unity UI视图层的框架，本身使用的还是UGUI的组件，但提供了一套强大的UI管理功能，可以很方便的实现一些炫酷效果，方便的UI系统管理与事件传递机制。

  • 学习游戏开发的两个方向 Cocos2d-x 和 U2021-07-12 15:14
    回答 12

    Unity3d更好，因为U3D占有的市场更大，目前cocos大都是用来开发棋牌游戏的，在这方面它有着巨大的优势。而Unity3d既可以用来开发大型3D游戏，也可以用来开发vr游戏、vr应用，这是比较不错的，未来有着巨大的前景。另外ue4也是个不错的选择，近年来用ue4开发的...

  • 为什么现在大部分Unity公司还是在用Lua热更新2021-07-12 15:12
    回答 11

    当Unity 需要做热更新的时候(2013年开始)，而普通的C#又做不到的时候，而对于游戏行业来说Lua脚本热更新已经是很成熟的方案，自然Lua 热更新就成为了Unity热更新的首选。

没有解决我的问题，去提问