时下的电脑游戏都已经慢慢开始向纯鼠标操作方式发展,那我们的Flash游戏也同样不能和人家差得太远。那么,使用鼠标后,人物的移动就会面临一个非常大的问题:应该如何时走才能到那个地方,怎么走才是最理想的位置。很显然,这就必须的将计算机里面一个非常麻烦的名词给抓出来,那就是最短路径。
对于对短路径的算法,其实是一个非常考验人的问题,一直以来都有很多的程序员在努力的研究更简单的计算方式,以达到性能等方面的最优化。呵呵,偶没有什么经验,在这里就仅仅将火舞寒冰曾经贴过了一段代码拿出来和大家讨论讨论了。
效果请参见:
dispbbs.asp?BoardID=10&ID=195589
其实这种寻路的思想比较简单,就是将二维数组转换成一维数组来实现。简单的说就是以起始点人初始点位,将可移动的四个方向上的点位编号都存入相应的数组中,然后再通过循环进行叛定。逐一找出下一个可移动点位在数组中的编号,直到到达终点为止。虽说这不是一种最优化的算法,但至少,对于单个场景数组不是很大的话,是可行的。
好吧。那么接下来我们就来简单的说说这些东西了。这里我画一张阵形图来简单的说明一下:
假设地图数组为 map_array ,然后我们就创建三个另外的数组 path_array,next_array,lost_array。path_array 用于保存很经过时的每一个对象所在的点位编号,它是最终的数组。而 next_array 则用于记录下一个可以行走的点位坐标,lost_array 则用于存放已经经过的点位的坐标。
现我们如果有这样一张图。$ 代表主角,& 代表终点,0 代表可移动区,1 代表不可移动区。首先我们可以看到,当前的起点编号应该是 0 号,因为主角在左上角:
$ 0 1 0 0 1 0 1
0 0 0 0 1 0 0 0
1 0 0 1 0 0 0 0
& 0 1 0 0 1 0 0
1 0 0 1 0 1 0 1
好了,我们的地图便已经完成了。接下来我们便来看看如何实现移动。首先,通地计算,可以得出绿色区是最先或以移动的地方:
$ 0 1 0 0 1 0 1
0 0 0 0 1 0 0 0
1 0 0 1 0 0 0 0
& 0 1 0 0 1 0 0
1 0 0 1 0 1 0 1
那么,我们就先分别将这两个点对应的编号存入 next_array 数组,此时,next_array 中包含(1,8)这两个点位编号了。接下来就开始进行第二次判定,此时,先将由的主角所在的位置存和 lost_array 中,就是让 lost_array 中存入(0)这个数据。我们继续看:
0 $ 1 0 0 1 0 1
0 0 0 0 1 0 0 0
1 0 0 1 0 0 0 0
& 0 1 0 0 1 0 0
1 0 0 1 0 1 0 1
现在我们已经尝试将主角移动到 1 号位置,再进行四周判断。此时发现,0 号和 2 号都已经不可移动了,只有第二行第二列(也就是 9 号格)还可以移动。所以,此时我们再将 9 号格加入到 next_array 中,并删除数组中第一个已经尝试过的对象,此时, next_array 中的对象变成了(8,9)。因为 1 号也已经走过了,所以我们将 1 号这个已经尝试过的区块也加入到 lost_array 中,使其变成(0,1)。
此时,我们要做的另外一位重要事情就是记录一下出发点编号了。因为现在尝试的是 1 号坐标,而移动到 1 号是从 0 号移动过来的,所以,我们要将 path_array[1] 的值设置成 0 ,表示,要移动到 1 号坐标的话,必须的从 0 号开始移动。
接下来是对 next_array 中的第一个对象(也就是 8 号位置)进行尝试了:
0 0 1 0 0 1 0 1
$ 0 0 0 1 0 0 0
1 0 0 1 0 0 0 0
& 0 1 0 0 1 0 0
1 0 0 1 0 1 0 1
从图上不难看出,除了 9 号位置外,0 号和 16 号位置都不能移动了。而我们也会发现,9 号已经放置于 next_array 数组中了。所以,这一回合,我们不用在 next_array 中加入新值,而只需要删除当前已经尝试过的 8 号便可,此时 next_array 中的值为(9),就一个。同样的,也要将 8 号这个已经尝试过的对象对号存入到数组 lost_array 中,表示已经尝试过了。
最后也不能忘记了,要将 path_array[8] 的值赋值为起点编号 0 。因为到移动到 8 号,是从 0 号移动过来的。
那么,在这里,第一个尝试的起点 0 编号位置就已经没有再可移动区了。接下来就要将尝试起点设置成 8 号。也就是取 lost_array 中最后一个点位的信息了。
那么,接下来我们可以看到,可移动图变成了这个样子:
0 0 1 0 0 1 0 1
0 $ 0 0 1 0 0 0
1
0 0 1 0 0 0 0
& 0 1 0 0 1 0 0
1 0 0 1 0 1 0 1
根据前面的说法,很自然就可以发现,现在可移动的位置也只有 10 号 和 17 号两个了。于是,再次修改相应的数组,便 next_array 值为(10,17),lost_array 值为(0,1,8,9)。
并将 path_array[9] 的值设置为 8 ,表示它是从 8 号格才移动过来的。再继续。
0 0 1 0 0 1 0 1
0 0 $ 0 1 0 0 0
1
0 0 1 0 0 0 0
& 0 1 0 0 1 0 0
1 0 0 1 0 1 0 1
此时,再尝试检查 10 号点,发现 11 号 以及 18 号是可移动区,并将相关数据再传入数组。具体的数据值这里不再详细讲述。并设置 path_array[10] 的值为 9。
0 0 1 0 0 1 0 1
0 0 0 0 1 0 0 0
1
$ 0 1 0 0 0 0
& 0 1 0 0 1 0 0
1 0 0 1 0 1 0 1
...... 直到最后成这个效果:
0 0 1
0 0 1 0 1
0 0 0 0 1 0 0 0
1
0 0 1 0 0 0 0
& $ 1 0 0 1 0 0
1
0 0 1 0 1 0 1
此时不难看到,从点位 26 号便可以移动到 终点 25 号点了。于是,我们便再进行最后一次数组转换。便可以得出这样一组数组:
25 -> 26 ->18 ->9 -> 8 -> 0 (该数据是根据 path_array 中的记录推算出来)。
这便是寒冰的那个最短路径的原理展示。因为目前我没用 Flash 软件来尝试(还不是因为偶懒嘛),就暂时用理解来画了。可能在具体的运算后输出的值出这个值有些不一样,但原理就是这个样子。
以上这种方式,只要大家能够加以变通,那么,做出能满足你游戏实际需要的寻路算法是比较容易的了。
啊,好累呀!累死我了。先歇会吧!