基础java小游戏难吗

科技前沿 • 2024-12-24 13:32 • 阅读 33

大家好，我是讯享网，很高兴认识大家。

很早就听说过A*算法，据说在寻路径时，是一种比较高效的算法。但是一直没有搞清楚原理。

这段时间刚好有个营救公主的例子：

题描述 :
公主被魔王抓走了，王子需要拯救出美丽的公主。他进入了魔王的城
堡，魔王的城堡是一座很大的迷宫。为了使问题简单化，我们假设这个迷宫是一
个 N*M 的二维方格。迷宫里有一些墙，王子不能通过。王子只能移动到相邻（上
下左右四个方向 ) 的方格内，并且一秒只能移动一步，就是说，如果王子在 (x,y ）
一步只能移动到 (x-1,y),(x+1,y),(x,y-1),基础java小游戏难吗(x,y+1) 其中的一个位置上。地图由
‘S’，‘P’，‘ . ’ ， ‘ *’ 四种符号构成， ‘ . ’ 表示王子可以通过， ‘ *’ 表示
墙，王子不能通过；'S'表示王子的位置；‘P’表示公主的位置； n表示公主存活的剩余时间，王子必须在 n 秒
内到达公主的位置，才能救活公主。

解题思路：

1、可以通过广度优先的算法进行演进，不停的查找王子的所有下一点的位置，没查找一次时间减1，直到找到了公主或者时间为0时终止。

这个算法能够比较快速的解决上述的迷宫问题；

2、通过A*算法，查找出每次移动可能到达的所有点，并设置了一定的权值规则，每次选取权值最小的一个点找它的下一个点……(当然，这是搞懂原理之后的后话:) )

本着锻炼下自己的原则选择了A*算法解决上面的问题。

原理我就不班门弄斧了，详细请看牛人的博文：http://www.blueidea.com/tech/multimedia/2005/3121_3.asp，下面的回复中还有个牛人实现了个Flash版的A*算法。我个人比较笨，看了好几遍才明白意思。各位如果没接触过且想学的，不妨在纸上或者电脑上按照图示演算一遍，相信很快就能搞清楚原理:)

代码实现简要说明：

1、定义了一个迷宫类 Maze，迷宫中包含了王子Prince（包含核心算法）和迷宫的地图MazeMap，迷宫（游戏）启动时，会先初始化地图，然后王子开始寻路（具体算法看代码）;

2、定义了一个位置类Position，描述了二维坐标信息，及加权的PositionWeight类，包含了位置信息、距离王子的距离（A*算法中的G）、距离公主的距离（A*算法中的H）、及二者的总开销(F=G+H)；

相信看懂了A*算法的原理的朋友，很快就能写出一个迷宫的实现方案。

下面贴一下我的实现，注释还算比较详尽，欢迎批评指正:)

讯享网

讯享网

讯享网

基础java小游戏难吗

相关推荐