gpt4 book ai didi

java - 冰上滑动拼图寻路

转载 作者:行者123 更新时间:2023-12-03 21:41:08 26 4
gpt4 key购买 nike

我为有点模糊的标题道歉,我不确定你会怎么称呼这个谜题。

我正在制作一种寻路方法来找到移动最少的路线,而不是行进的距离。

游戏规则很简单,你必须从橙色方 block 穿越到绿色方 block ,但你只能沿直线移动,并且不能停止向那个方向移动,直到碰到边界(竞技场的墙壁或障碍物),就好像他们在冰上滑行一样。

示例 map ,除非我弄错了,否则所需的路径(8 次移动)

Example map
Desired path

Arena.java:https://gist.github.com/CalebWhiting/3a6680d40610829b1b6d

ArenaTest.java: https://gist.github.com/CalebWhiting/9a4767508831ea5dc0da

我假设这最好使用 Dijkstras 或 A* 路径查找算法来处理,但是我不仅对这些算法不是很有经验,而且也不知道我将如何定义路径规则。

提前感谢您的任何帮助。

最佳答案

这是我的解决方案(Java),以防有人仍然感兴趣。正如@tobias_k 在他的 comment 中所建议的那样以上,确实 BFS 是要走的路:

import java.util.LinkedList;

public class PokemonIceCave {
public static void main(String[] args) {
int[][] iceCave1 = {
{0, 0, 0, 1, 0},
{0, 0, 0, 0, 1},
{0, 1, 1, 0, 0},
{0, 1, 0, 0, 1},
{0, 0, 0, 1, 0}
};
System.out.println(solve(iceCave1, 0, 0, 2, 4));
System.out.println();

int[][] iceCave2 = {
{0, 0, 0, 1, 0},
{0, 0, 0, 0, 1},
{0, 1, 1, 0, 0},
{0, 1, 0, 0, 1},
{0, 0, 0, 1, 0},
{0, 0, 0, 0, 0}
};
System.out.println(solve(iceCave2, 0, 0, 2, 5));
}

public static int solve(int[][] iceCave, int startX, int startY, int endX, int endY) {
Point startPoint = new Point(startX, startY);

LinkedList<Point> queue = new LinkedList<>();
Point[][] iceCaveColors = new Point[iceCave.length][iceCave[0].length];

queue.addLast(new Point(0, 0));
iceCaveColors[startY][startX] = startPoint;

while (queue.size() != 0) {
Point currPos = queue.pollFirst();
System.out.println(currPos);
// traverse adjacent nodes while sliding on the ice
for (Direction dir : Direction.values()) {
Point nextPos = move(iceCave, iceCaveColors, currPos, dir);
System.out.println("\t" + nextPos);
if (nextPos != null) {
queue.addLast(nextPos);
iceCaveColors[nextPos.getY()][nextPos.getX()] = new Point(currPos.getX(), currPos.getY());
if (nextPos.getY() == endY && nextPos.getX() == endX) {
// we found the end point
Point tmp = currPos; // if we start from nextPos we will count one too many edges
int count = 0;
while (tmp != startPoint) {
count++;
tmp = iceCaveColors[tmp.getY()][tmp.getX()];
}
return count;
}
}
}
System.out.println();
}
return -1;
}

public static Point move(int[][] iceCave, Point[][] iceCaveColors, Point currPos, Direction dir) {
int x = currPos.getX();
int y = currPos.getY();

int diffX = (dir == Direction.LEFT ? -1 : (dir == Direction.RIGHT ? 1 : 0));
int diffY = (dir == Direction.UP ? -1 : (dir == Direction.DOWN ? 1 : 0));

int i = 1;
while (x + i * diffX >= 0
&& x + i * diffX < iceCave[0].length
&& y + i * diffY >= 0
&& y + i * diffY < iceCave.length
&& iceCave[y + i * diffY][x + i * diffX] != 1) {
i++;
}

i--; // reverse the last step

if (iceCaveColors[y + i * diffY][x + i * diffX] != null) {
// we've already seen this point
return null;
}

return new Point(x + i * diffX, y + i * diffY);
}

public static class Point {
int x;
int y;

public Point(int x, int y) {
this.x = x;
this.y = y;
}

public int getX() {
return x;
}

public int getY() {
return y;
}

@Override
public String toString() {
return "Point{" +
"x=" + x +
", y=" + y +
'}';
}
}

public enum Direction {
LEFT,
RIGHT,
UP,
DOWN
}
}

关于java - 冰上滑动拼图寻路,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29170368/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com