浏览 3598 次
|
锁定老帖子 主题：Java实现的连连看
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2009-05-29
最后修改：2009-05-29
在Linux下想玩连连看，可没有windows下简单。费尽周折，找到一个开源的，但在我的机器上编译报错，貌似少一个头文件。我也懒得去找这个头文件在那个依赖包中。其它的Flash版连连看要么是太简单，要么是要在线玩，太没意思。干脆自己写一个。参考网上的算法描述，然后自己用Swing实现了一个Java版的连连看。下面就说我的实现。
介绍数据结构和算法前，先重复一下连连看的规则： 1、可以连通的两个物体必须是相同的。 2、可以连通的两个物体间存在一条不超过两个拐角的路径，这条路径上不能有其它的物体。 基本数据结构 1、数据结构：用一个二维整数数组表示游戏，0表示该位置没有物体，大于0表示有。 算法描述： 1、当前路径上的已有拐角已大于2，则该路径不可连通。算法终止，否则继续第2步。 2、当前路径上的已有拐角小于2，当前位置的东、南、西、北是否是目标位置，如果是，路径找到，算法终止，否则继续。 3、当前路径上的拐角等于2，和到达当前位置的方向在同一直线上的相邻位置是否是目标位置，如果是，路径找到，算法终止，否则继续。 4、逐一检验当前位置的东南西北四个位置是否可达（即是否为0），如果可达，由当前方向向相应方向移动一个位置，如果当前位置的前进方向和到达该位置的方向不在一条直线上，拐角数加一，递归调用本过程。 呵呵，算法描述比较枯燥，不习惯的话看下面的源代码吧。
/**
*寻找一条从(fromX, fromY)到(toX, toY)的拐角数不大于2的路径。
*/
protected boolean canPathBeFound(int fromX, int fromY, int toX, int toY,
int cornerCounter, int originalDirection) {
int turns = 0;
if (cornerCounter > 2) {
return false;
}
boolean aPathFound = false;
/**
* 已经走过的路径上拐角数小于2
*/
if (cornerCounter < 2) {
if ( fromX == toX ){
if (fromY -1 == toY || fromY + 1 == toY )
aPathFound = true;
}
else if ( fromY == toY ){
if(fromX - 1 == toX || fromX + 1 == toX )
aPathFound = true;
}
}
/**
*拐角数已经到达2，不再允许拐弯
*/
else { /* cornerCounter == 2; */
if (originalDirection == Direction.EAST) {
if (fromX == toX && fromY - 1 == toY)
aPathFound = true;
} else if (originalDirection == Direction.WEST) {
if (fromX == toX && fromY + 1 == toY)
aPathFound = true;
} else if (originalDirection == Direction.NORTH) {
if (fromX + 1 == toX && fromY == toY)
aPathFound = true;
} else if (originalDirection == Direction.SOUTH) {
if (fromX - 1 == toX && fromY == toY)
aPathFound = true;
}
}
/**/
if( aPathFound ){
logStep("end", fromX, fromY, toX, toY, aPathFound );
return aPathFound;
}
/**
* 当前位置的向东方向可达，且不是由东方到达当前位置，则尝试向东前进一个位置。
*/
if (canForward(fromX, fromY + 1) && originalDirection != Direction.EAST) {
/**
* 如果到达当前位置的方向和由当前位置前进的方向不在同一条直线上，拐角加1
*/
turns = needTurn(originalDirection, Direction.EAST, cornerCounter);
aPathFound = canPathBeFound(fromX, fromY + 1, toX, toY, turns,
Direction.WEST);
logStep("eastForward", fromX, fromY, fromX, fromY + 1, aPathFound );
}
if (aPathFound)
return true;
if (canForward(fromX, fromY - 1) && Direction.WEST != originalDirection) {
turns = needTurn(originalDirection, Direction.WEST, cornerCounter);
aPathFound = canPathBeFound(fromX, fromY - 1, toX, toY, turns,
Direction.EAST);
logStep("westForward", fromX, fromY, fromX, fromY - 1, aPathFound);
}
if (aPathFound)
return true;
if (canForward(fromX + 1, fromY)
&& Direction.SOUTH != originalDirection) {
turns = needTurn(originalDirection, Direction.SOUTH, cornerCounter);
aPathFound = canPathBeFound(fromX + 1, fromY, toX, toY, turns,
Direction.NORTH);
logStep("sourthForward", fromX, fromY, fromX + 1, fromY, aPathFound);
}
if (aPathFound)
return true;
if (canForward(fromX - 1, fromY)
&& originalDirection != Direction.NORTH) {
turns = needTurn(originalDirection, Direction.NORTH, cornerCounter);
aPathFound = canPathBeFound(fromX - 1, fromY, toX, toY, turns,
Direction.SOUTH);
logStep("northForward", fromX, fromY, fromX - 1, fromY, aPathFound);
}
return aPathFound;
}
核心算法就是这样了。用了递归，效率还可以（道听途说：Flash允许的递归深度是256，用我这个算法似乎不行，因为递归深度超过了3w）。一个20X20的游戏，测试发现最多经过30000步可以找到一条路径。哪位xdjm有更高效的算法欢迎贡献出来。我的算法中不足的地方，也欢迎拍砖。 声明：ITeye文章版权属于作者，受法律保护。没有作者书面许可不得转载。
推荐链接
|
| 返回顶楼 | |
|
发表时间：2009-06-01
连连看我也做过的,只是没有要递归,只要水平扫描一下和垂直扫描一下,不要那么多步的.很好判断的.
/**
* 求pos1与pos2两位置之间可通的路径
* @param pos1
* @param pos2
* @return
*/
private Position[] getPath(Position pos1, Position pos2) {
int type1 = getDatum(pos1);
int type2 = getDatum(pos2);
if (pos1.equals(pos2) || type1 == BLANK || type2 == BLANK
|| type1 != type2) {
return null;
}
out: for (int row = 0; row < 11; row++) {// 垂直扫描
int r, c;
for (r = Math.min(row, pos1.row); r <= Math.max(row, pos1.row); r++) {
if (r == pos1.row) {
continue;
}
if (getDatum(r, pos1.column) != BLANK) {
continue out;
}
}
for (c = Math.min(pos1.column, pos2.column); c <= Math.max(
pos1.column, pos2.column); c++) {
if (c == pos1.column || c == pos2.column) {
continue;
}
if (getDatum(row, c) != BLANK) {
continue out;
}
}
for (r = Math.min(row, pos2.row); r <= Math.max(row, pos2.row); r++) {
if (r == pos2.row) {
continue;
}
if (getDatum(r, pos2.column) != BLANK) {
continue out;
}
}
if (r == Math.max(row, pos2.row) + 1) {
return new Position[] { pos1, new Position(row, pos1.column),
new Position(row, pos2.column), pos2 };
}
}
out2: for (int col = 0; col < 18; col++) {// 水平扫描
int r, c;
for (c = Math.min(col, pos1.column); c <= Math
.max(col, pos1.column); c++) {
if (c == pos1.column) {
continue;
}
if (getDatum(pos1.row, c) != BLANK) {
continue out2;
}
}
for (r = Math.min(pos1.row, pos2.row); r <= Math.max(pos1.row,
pos2.row); r++) {
if (r == pos1.row || r == pos2.row) {
continue;
}
if (getDatum(r, col) != BLANK) {
continue out2;
}
}
for (c = Math.min(col, pos2.column); c <= Math
.max(col, pos2.column); c++) {
if (c == pos2.column) {
continue;
}
if (getDatum(pos2.row, c) != BLANK) {
continue out2;
}
}
if (c == Math.max(col, pos2.column) + 1) {
return new Position[] { pos1, new Position(pos1.row, col),
new Position(pos2.row, col), pos2 };
}
}
return null;
}
|
| 返回顶楼 | |
|
发表时间：2009-06-03
yy629 写道 连连看我也做过的,只是没有要递归,只要水平扫描一下和垂直扫描一下,不要那么多步的.很好判断的.
/**
* 求pos1与pos2两位置之间可通的路径
* @param pos1
* @param pos2
* @return
*/
private Position[] getPath(Position pos1, Position pos2) {
int type1 = getDatum(pos1);
int type2 = getDatum(pos2);
if (pos1.equals(pos2) || type1 == BLANK || type2 == BLANK
|| type1 != type2) {
return null;
}
……
水平和垂直扫描算法，在不支持递归的语言中或者递归深度受限制（Java的递归栈也是有深度限制的，只是这个深度很大，一般不会溢出）的语言中有更好的运用。递归的方法也不复杂，我说的3w是最坏的情况，一般在100步左右就可以递归结束。 |
| 返回顶楼 | |
|
发表时间：2009-06-03
东西呢？ 我还说玩玩呢
|
| 返回顶楼 | |
