本系列文章由七十一雾央编写,转载请注明出处。
http://blog.csdn.net/u011371356/article/details/10289253
作者:七十一雾央 新浪微博:http://weibo.com/1689160943/profile?rightmod=1&wvr=5&mod=personinfo
因为前段时间在学习Cocos2d-X引擎,然后自己最近就练手写了个小游戏练习,花了自己不少时间,所以这个系列没怎么更新,不过以后雾央会继续更新的,分享自己学到的新东西。
上一节本来雾央说要先讲迷宫,但是至少在现在,雾央觉得迷宫用处不是太大,所以就不打算详细写了,这里只是简略的介绍一下吧。
在以前的游戏中,由于硬件性能的原因导致不能负担起丰富的画面,同时也为了减轻美术人员的工作量,如何利用少数的资源创造出不同的游戏是一个很值得探讨的问题,前辈游戏程序员们给出的答案就是迷宫。使用迷宫,一方面可以利用几面墙就可以采用算法随机生成无穷无尽的地图,使玩家得到不同的体验,另一方面,也可以大大延长游戏的时长,毕竟,大家不希望自己画几十块钱买来的游戏一会就通关了吧。
对于迷宫,涉及到的一个问题就是随机生成算法。
大家可以首先将迷宫看成一个个方格,比如下图
我们可以规定一个入口和一个出口,比如左上角的格子和右下角的格子
现在我们需要的就是有一条路连接入口和出口,一般情况下都是要求路线是唯一的。
如果我们把每个格子都看作一个点,那么它实际上就是一个图。问题也就是等价于找到这张图的生成树。那么涉及到生成树的算法我们都可以拿来用了,比如BFS,DFS,Prim,Kruskal等等
对这些感兴趣的朋友,可以看这篇文章
讲解的非常好
它里面还提到一种巧妙的方法,递归分割,感觉很巧,大家可以看看。
另外,在学数据结构的时候,我们学习过并查集,也叫不相交集,利用并查集也可以得到一种不错的算法。一开始每个格子都是一个集合,然后随机的选择一面墙将它拆掉,将墙两边的格子连接起来,合并它们俩所在的集合,判断出口和入口格子是不是在同一个集合中,如果不在则重复拆墙合并过程。
迷宫的另外一个问题就是寻路算法
高端的算法当然都是适用的,但是一般迷宫只是为了寻找一条通路而已,常用的DFS,BFS的就可以了,容易理解,也容易实现。
今天主要是想说一下雾央最近学习的A*算法,雾央也是个算法渣,但是最近迫切的感觉到了寻路算法的重要性,所以还是要认真学习下,网上有很多人写的A*算法,都很不错,下面写的都是雾央的理解,希望可以尽可能通俗。
最近雾央写了一个小游戏,其中的普通地图如下:
大家看到是采用摇杆来控制运动的,雾央是把这个游戏移植到Android上了,所以大家肯定是会觉得很蛋疼,那么小的屏幕上怎么好控制!其实雾央也不想这样的,直接点哪人物走哪不是很好吗,可是那样就涉及到一个问题了:寻路问题!地图上是有障碍物的,点击了一个地方后,人物肯定要以最短路径走过去,这是雾央学习中的第一个Android游戏,就没想给自己找麻烦,所以采用了蛋疼的摇杆操作。
用安卓机的朋友们,如果感兴趣,可以感兴趣试玩一下,呵呵,详细请点击这篇文章点我啊。
扯上面这些其实是想说,寻路算法还是挺重要的,今天只说最基础的A*算法,没有任何变异的品种。
由于A*算法的重要性和基础性,网上对A*算法的研究比比皆是,有很多大神都会他们进行过各种讨论和延伸。但是很多对于我们初学者来说并不合适,下面这个链接是对A*算法最基础最明了的说明,英文好的朋友可以直接看这篇文章
英文不好的朋友也可以看这篇中文版,翻译的还行,大家应该也可以看懂。
大家看上面这两篇应该就可以了,下面的是雾央学习A*算法对它的理解,再叙述一遍加深自己对它的理解,希望可以更通俗一点,有兴趣的朋友可以参考下。
问题与目标
首先明确一下希望解决的问题,我们看一下下面这张图。
这张图就代表我们的地图,为了方便,我们用方格代替,当然它也可以是多边形神马的。
绿色方格代表起点,红色方格代表终点,蓝色方格代表障碍物。
我们的目标就是找到一条最短路径从绿色方格到达红色方格。
路径评估方案
我们在寻找路径的时候会遇到很多种选择,那么那一条是最好的呢?这需要我们做出判断,也就需要一个标准。我们采用的评判公式是
F=G+H
下面雾央来具体解释一下这个公式的含义
F代表这条路径的长度,我们就希望找到具有最小F值的那条路
我们在寻路时从起点A出发是要经过一系列方格到达终点的,比如我们中途到达了某一结点M点,那么从起点A到结点M的路径已知,就是这里的G值啦
但是从M点到终点B的过程又是这样的一个寻路问题,我们不知道它的长度,所以需要采用估算算法,它的估计值就是H了。
剩下的下次再写,等会要睡觉了。
另外要开学了,最近雾央也很忙,因为雾央也在尝试着做自己的游戏,也在不断的学习,所以更新的没有七月份那么及时了。这个博客系列主要就是分享雾央学习的东西,大家初学游戏也需要自己思考怎么实现一些东西,其实到现在这些东西,已经足够大家做出自己的小游戏了,建议大家可以尝试做一下了,看似很复杂的游戏逻辑可以一点点写,慢慢组装起来,等以后再考虑架构可维护性神马的问题。先实现功能,在考虑改进优化的问题。在微博上有好几位多朋友问雾央学习的过程,其实雾央到现在也是一个初学者,到现在雾央学习过的东西都写在这篇文章中了,有兴趣的朋友可以看看,希望对你有一些参考意义,雾央学过的东东,其实更重要的是自己动手实践,写几个小游戏慢慢就会成长。