加载中…简易的Unity A*寻路算法流程的归纳
(2017-11-15 17:34:01)
标签：
unity3d游戏算法 |
作者：MJ.风暴洋
作者感言
：欢迎大家来讨论，一起学习，一起进步。
首先要知道什么A星算法，干什么用的。（如果去那种RPG游戏的公司面试经常问你的两个问题就是，如何优化项目？说一下A*算法？）
在RPG或者2D角色类游戏中，有一个很常见地需求，就是要让一个角色从A点走向B点，我们都希望是让角色走最少的路。众所周知，直线就是最短的。没错，然而大多数时候，A到B中间都会出现一些角色无法穿越的东西，比如墙、坑等障碍物。这个时候怎么办呢？
这时候就需要一种算法解决该问题，算法的目标就是计算出两点之间的最短路径，而且要能避开障碍物。
那么，什么是A*算法，它被广大游戏研发人员叫A星寻路，这是一种在图形平面上有多个节点组成的路径，求最小通过的代价的算法。
一般来说用正方形做寻路算法的单元是比较简单的，我在网上看见过六边形或者三角形作为寻路单元，代码简直像天书一样。把一张地图分成若干个小的像素点，其实这个搜索区域就是一个二维数组而已。大家这么理解就简单了。
论述其原理（数学稍微差一点的同学可能会懵逼）：
首先需要两个列表集合，一个是open，一个是closed。open集合用来记录所有被考虑下来搜寻最短路径的格子；closed用来记录不用考虑被排除掉的格子，当然这是要在寻路类里使用的。
先在closed列表中加一个当前的位置，命名为curNode，然后把它相邻的可以走动的格子加进open集合。
![本地图片，请重新上传]()
说两个名词：节点和代价
我们都见过九宫格是什么样子的，脑补一下，假设你站在九宫格的中央，每个格子都是一个单位长度，那么你的相对坐标就是（0,0）那么到你对角线4个格子的长度是1.414，到相邻垂直或者水平的长度都是1，每个格子都看做一个节点，或者一个像素单元，那么代价则是你走到某个节点所走的单位长度。一般代价都用F（起点）、G（目标）、H（总长）表示。
http://b243.photo.store.qq.com/psb?/V10ll2SB4bWu6b/6czCs*aLEdZeyKxZu5X7gDNUU3N9X4Udr7lTFrHiYz0!/b/dPMAAAAAAAAA&bo=WgL.AVoC*gEDEDU!A*寻路算法流程的归纳" />
在寻路的过程中碰到障碍物了咋办？其实障碍物也是无数个不可通过的节点组成的，从一个节点移动到另一个节点时，自身节点相对于周围8个节点来说就是父节点。
↓↓下图是节点类Gird.cs类的封装。
http://b77.photo.store.qq.com/psb?/V10ll2SB4bWu6b/Mk3rra4CxhoRPUcGwQo6T1T3Rqo6XVxJy61AAfSqSSw!/b/dE0AAAAAAAAA&bo=mwOAAgAAAAADKBc!A*寻路算法流程的归纳" />
http://b242.photo.store.qq.com/psb?/V10ll2SB4bWu6b/kNiLbv2kvzm4qEuhKf5I9yDfUPWl1njdeRdcxYrAsUc!/b/dPIAAAAAAAAA&bo=5QF0AeUBdAEDEDU!A*寻路算法流程的归纳" />
http://b242.photo.store.qq.com/psb?/V10ll2SB4bWu6b/cGxxtGqEowqD*xE.SP.6p9OZkeVJnclCSk9017Sji*I!/b/dPIAAAAAAAAA&bo=DwN3Ag8DdwIDEDU!A*寻路算法流程的归纳" />
http://b242.photo.store.qq.com/psb?/V10ll2SB4bWu6b/qeb3yFkQ1jPC1Q37wjlQA5G9LFdroRK*YZLcWQfk5qU!/b/dPIAAAAAAAAA&bo=xwOAAtUDiQIDEC4!A*寻路算法流程的归纳" />
我在网上学到了三种估价算法：曼哈顿估价算法，几何估价算法，对角估价算法。搜了百度找到了数学建模图：
http://b243.photo.store.qq.com/psb?/V10ll2SB4bWu6b/OPGu*yYh*IgefTOC.I6np2lglurh2SlW80mnop9fWxA!/b/dPMAAAAAAAAA&bo=7wIgAe8CIAEDEDU!A*寻路算法流程的归纳" />
曼哈顿算法就是中国象棋里的“車”的走位，直上直下直左直右。
几何算法就是勾股定理。上过初中的都会。
对角算法是曼哈顿和几何算法的杂交算法，先按对角线走，走道与目标点垂直或者水平后再笔直的走，有点像黑白点阵像素电子词典里的一款游戏《海盗船》的走位。
↓↓我在百度上搜集到了这三种算法的示例代码，可惜不是C#脚本，看着像JS脚本，反正你仔细看看能看懂。
http://b242.photo.store.qq.com/psb?/V10ll2SB4bWu6b/PaDF0TS*52b1jndcw0WipRBD89qQN17vXmDPfzLG36M!/b/dPIAAAAAAAAA&bo=*gKsAf4CrAEDEDU!A*寻路算法流程的归纳" />
↓↓生成路径
http://b243.photo.store.qq.com/psb?/V10ll2SB4bWu6b/xc1COf.do*zo4thV*40rWudzbuUvYcYp75aQVqtMdXo!/b/dPMAAAAAAAAA&bo=jQLmAY0C5gEDEDU!A*寻路算法流程的归纳" />
A*寻路Demo效果
http://b242.photo.store.qq.com/psb?/V10ll2SB4bWu6b/SOTkPeRh62E3c5nitrby.euJk5tDbReHfGPrcFrIAPk!/b/dPIAAAAAAAAA&bo=oQNsAqEDbAIDEDU!A*寻路算法流程的归纳" />
我发现了bug，贼烦，我调了一下午了……大概思路就是这样，细节我继续修改一下，MJ.风暴洋祝大家工作顺利~https://qzs.qq.com/qzone/em/e113.gifA*寻路算法流程的归纳" />
http://b243.photo.store.qq.com/psb?/V10ll2SB4bWu6b/6czCs*aLEdZeyKxZu5X7gDNUU3N9X4Udr7lTFrHiYz0!/b/dPMAAAAAAAAA&bo=WgL.AVoC*gEDEDU!A*寻路算法流程的归纳" />
http://b77.photo.store.qq.com/psb?/V10ll2SB4bWu6b/Mk3rra4CxhoRPUcGwQo6T1T3Rqo6XVxJy61AAfSqSSw!/b/dE0AAAAAAAAA&bo=mwOAAgAAAAADKBc!A*寻路算法流程的归纳" />
http://b242.photo.store.qq.com/psb?/V10ll2SB4bWu6b/kNiLbv2kvzm4qEuhKf5I9yDfUPWl1njdeRdcxYrAsUc!/b/dPIAAAAAAAAA&bo=5QF0AeUBdAEDEDU!A*寻路算法流程的归纳" />
http://b242.photo.store.qq.com/psb?/V10ll2SB4bWu6b/cGxxtGqEowqD*xE.SP.6p9OZkeVJnclCSk9017Sji*I!/b/dPIAAAAAAAAA&bo=DwN3Ag8DdwIDEDU!A*寻路算法流程的归纳" />
http://b242.photo.store.qq.com/psb?/V10ll2SB4bWu6b/qeb3yFkQ1jPC1Q37wjlQA5G9LFdroRK*YZLcWQfk5qU!/b/dPIAAAAAAAAA&bo=xwOAAtUDiQIDEC4!A*寻路算法流程的归纳" />
http://b243.photo.store.qq.com/psb?/V10ll2SB4bWu6b/OPGu*yYh*IgefTOC.I6np2lglurh2SlW80mnop9fWxA!/b/dPMAAAAAAAAA&bo=7wIgAe8CIAEDEDU!A*寻路算法流程的归纳" />
http://b242.photo.store.qq.com/psb?/V10ll2SB4bWu6b/PaDF0TS*52b1jndcw0WipRBD89qQN17vXmDPfzLG36M!/b/dPIAAAAAAAAA&bo=*gKsAf4CrAEDEDU!A*寻路算法流程的归纳" />
http://b243.photo.store.qq.com/psb?/V10ll2SB4bWu6b/xc1COf.do*zo4thV*40rWudzbuUvYcYp75aQVqtMdXo!/b/dPMAAAAAAAAA&bo=jQLmAY0C5gEDEDU!A*寻路算法流程的归纳" />
http://b242.photo.store.qq.com/psb?/V10ll2SB4bWu6b/SOTkPeRh62E3c5nitrby.euJk5tDbReHfGPrcFrIAPk!/b/dPIAAAAAAAAA&bo=oQNsAqEDbAIDEDU!A*寻路算法流程的归纳" />
喜欢
0
赠金笔
前一篇：Unity3D 优化总结