C++游戏开发十六 游戏中的寻路算法（二）：迷宫&A*算法基础2014-11-04因为前段时间在学习Cocos2d-X引擎，然后自己最近就练手写了个小游戏练习，花了自己不少时间，所以这个系列没怎么更新，不过以后雾央会继续更新的，分享自己学到的新东西。上一节本来雾央说要先讲迷宫，但是至少在现在，雾央觉得迷宫用处不是太大，所以就不打算详细写了，这里只是简略的介绍一下吧。在以前的游戏中，由于硬件性能的原因导致不能负担起丰富的画面，同时也为了减轻美术人员的工作量，如何利用少数的资源创造出不同的游戏是一个很值得探讨的问题，前辈游戏程序员们给出的答案就是迷宫。使用迷宫，一方面可以利用几面墙就可以采用算法随机生成无穷无尽的地图，使玩家得到不同的体验，另一方面，也可以大大延长游戏的时长，毕竟，大家不希望自己画几十块钱买来的游戏一会就通关了吧。对于迷宫，涉及到的一个问题就是随机生成算法。大家可以首先将迷宫看成一个个方格，比如下图
我们可以规定一个入口和一个出口，比如左上角的格子和右下角的格子现在我们需要的就是有一条路连接入口和出口，一般情况下都是要求路线是唯一的。如果我们把每个格子都看作一个点，那么它实际上就是一个图。问题也就是等价于找到这张图的生成树。那么涉及到生成树的算法我们都可以拿来用了，比如BFS，DFS，Prim，Kruskal等等对这些感兴趣的朋友，可以看这篇文章各种迷宫随机生成算法讲解的非常好它里面还提到一种巧妙的方法，递归分割，感觉很巧，大家可以看看。另外，在学数据结构的时候，我们学习过并查集，也叫不相交集，利用并查集也可以得到一种不错的算法。一开始每个格子都是一个集合，然后随机的选择一面墙将它拆掉，将墙两边的格子连接起来，合并它们俩所在的集合，判断出口和入口格子是不是在同一个集合中，如果不在则重复拆墙合并过程。迷宫的另外一个问题就是寻路算法高端的算法当然都是适用的，但是一般迷宫只是为了寻找一条通路而已，常用的DFS，BFS的就可以了，容易理解，也容易实现。今天主要是想说一下雾央最近学习的A*算法，雾央也是个算法渣，但是最近迫切的感觉到了寻路算法的重要性，所以还是要认真学习下，网上有很多人写的A*算法，都很不错，下面写的都是雾央的理解，希望可以尽可能通俗。最近雾央写了一个小游戏，其中的普通地图如下：
更多精彩内容：http://www.bianceng.cn/Programming/VC_NET/
易网时代-编程资源站