当前位置: 首页 > 编程语言 > VC.NET > 正文

C++游戏开发十六 游戏中的寻路算法(二):迷宫&A*算法基础

时间:2014-11-04

因为前段时间在学习Cocos2d-X引擎,然后自己最近就练手写了个小游戏练习,花了自己不少时间,所以这个系列没怎么更新,不过以后雾央会继续更新的,分享自己学到的新东西。

上一节本来雾央说要先讲迷宫,但是至少在现在,雾央觉得迷宫用处不是太大,所以就不打算详细写了,这里只是简略的介绍一下吧。

在以前的游戏中,由于硬件性能的原因导致不能负担起丰富的画面,同时也为了减轻美术人员的工作量,如何利用少数的资源创造出不同的游戏是一个很值得探讨的问题,前辈游戏程序员们给出的答案就是迷宫。使用迷宫,一方面可以利用几面墙就可以采用算法随机生成无穷无尽的地图,使玩家得到不同的体验,另一方面,也可以大大延长游戏的时长,毕竟,大家不希望自己画几十块钱买来的游戏一会就通关了吧。

对于迷宫,涉及到的一个问题就是随机生成算法。

大家可以首先将迷宫看成一个个方格,比如下图

我们可以规定一个入口和一个出口,比如左上角的格子和右下角的格子

现在我们需要的就是有一条路连接入口和出口,一般情况下都是要求路线是唯一的。

如果我们把每个格子都看作一个点,那么它实际上就是一个图。问题也就是等价于找到这张图的生成树。那么涉及到生成树的算法我们都可以拿来用了,比如BFS,DFS,Prim,Kruskal等等

对这些感兴趣的朋友,可以看这篇文章

各种迷宫随机生成算法

讲解的非常好

它里面还提到一种巧妙的方法,递归分割,感觉很巧,大家可以看看。

另外,在学数据结构的时候,我们学习过并查集,也叫不相交集,利用并查集也可以得到一种不错的算法。一开始每个格子都是一个集合,然后随机的选择一面墙将它拆掉,将墙两边的格子连接起来,合并它们俩所在的集合,判断出口和入口格子是不是在同一个集合中,如果不在则重复拆墙合并过程。

迷宫的另外一个问题就是寻路算法

高端的算法当然都是适用的,但是一般迷宫只是为了寻找一条通路而已,常用的DFS,BFS的就可以了,容易理解,也容易实现。

今天主要是想说一下雾央最近学习的A*算法,雾央也是个算法渣,但是最近迫切的感觉到了寻路算法的重要性,所以还是要认真学习下,网上有很多人写的A*算法,都很不错,下面写的都是雾央的理解,希望可以尽可能通俗。

最近雾央写了一个小游戏,其中的普通地图如下:

更多精彩内容:http://www.bianceng.cn/Programming/VC_NET/