移动点博弈的广度优先搜索

Question

您好，我一直在尝试使用广度优先搜索编写一种算法，该算法可以找到蓝点退出游戏的最短路径。我是 java 的新手，running/understanding class 的算法有问题。我有一个名为 gameModel 的 class，它存储每个点的状态。该算法旨在测试蓝点在不通过 o运行ge 点（已选择）的情况下退出棋盘的最快方式，如果没有出路，则玩家获胜。我保留运行程序并出现编译错误，我不知道如何修复。我包括了控制器 class，其中短点是运行。

import java.util.Random;

import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;

import javax.*;

/**
 * The class <b>GameController</b> is the controller of the game. It implements 
 * the interface ActionListener to be called back when the player makes a move. It computes
 * the next step of the game, and then updates model and view.

*/


public class GameController implements ActionListener {

private int size;
private GameModel gameModel;
private GameView gameView;
private boolean click;

 /**
 * Constructor used for initializing the controller. It creates the game's view 
 * and the game's model instances
 * 
 * @param size
 *            the size of the board on which the game will be played
 */
public GameController(int size) {
    this.size = size;
    this.gameModel = new GameModel(size);
    this.gameView = new GameView (gameModel, this);
    click =  false;
}


/**
 * Starts the game
 */
public void start(){
    if (click){
        List start = new List {gameModel.getCurrentDot().getX(), gameModel.getCurrentDot().getY()};
        List<int> targets = new ArrayList<>();
        List<int> blocked = nwq ArrayList<>();
        for (int i = 0; i < size; i++){
            targets.add(i, 0);
            targets.add(i, size);
            targets.add(1, size);
            targets.add(1, 0);
        }
        for (int i = 0; i < size; i++){
            for (int j = 0; j < size; j++)
                if(gameModel.getstatus(i, j) == SELECTED){
                blocked.add(i, j);
            }
        String path = Breadth-First-Start(start, targets, blocked);
        gameView = new GameView(gameModel, this);
        gameView.getBoardView().update();
    }
}

public Breadth-First-Start(start, targets, blocked){ // Need help with
    Queue queue = new LinkedList();
    queue.add(start + "");

    while(!queue.isEmpty()){
        String p = queue.remove();
        if (p != blocked){       //If p is not in blocked paths
            if (p == targets){   //If p is in targets
                return "q + {p}";
            } else {
                queue.add("q + {p}");
                blocked.add(p);
            }
        }
    }

Answer 1

您的方法 public Breadth-First-Start(start, targets, blocked) 被声明为错误。你不能在方法名中有 -，你还需要指定 return 类型（只有构造函数没有要定义的 return 类型）。您还需要指定参数类型。据我了解，目标和开始看起来像 String 类型，而阻塞看起来像 List，请尝试用以下方法替换方法头 public void breadthFirstSearch(String start, String targets, List blocked) 不确定你想要什么 return 类型，因为你没有任何 returns 在方法中。但在你的情况下，你可能想要路径，所以可能是 List 类型，或者一个布尔值来知道是否有路径。

Answer 2

你想做的事与图论有关。如果连接了两个节点，则会在它们之间创建一条边。在这种情况下，橙色点不会连接到任何东西，因为它们之间不存在路径。 Dijkstra 的算法对于做你想做的事情非常有用，尽管它是广度优先而不是深度优先。我建议从那里开始，我确信在 java.

中有实施该算法的示例

图中的边具有权重，比较这些边以找到两个节点之间的最短路径。

我看到您的阻止列表声明中有 nwq 而不是 new。那可能就是你的问题。

希望对您有所帮助

移动点博弈的广度优先搜索

Breadth-First-Search for moving dot game

java

breadth-first-search