0

我有一个关于我为学校项目 Pacman 制作的 Dijkstra 最短路径算法的问题。

该算法可以运行到“智能”幽灵可以通过多种方式进入吃豆人的地步。（虽然不是每次都这样）

发生这种情况（视频）： https ://vps.johnlokerse.nl/images/dijkstra_ghost_problem.mp4

运动场由“Vakje”（细胞）类组成。当人工智能在做奇怪的动作时，如视频所示，调试工具显示他要走最短的路，但此时它想回去。我不知道此时问题可能是什么。有什么想法吗？

这是代码：

public class Slim extends Spookje {
private HashSet<Vakje> afgehandeldeNodes = new HashSet<Vakje>();
private Stack<Vakje> nietAfgehandeldeNodes = new Stack<>();
private Map<Vakje, Vakje> gelinkteAfgehandeldeNodes = new HashMap<>();
private Map<Vakje, Integer> lengteRoute = new HashMap<>();

public Slim(Vakje startLok, GameEventListener spel, GameEventListener veld) {
    super(startLok, spel, veld);
    this.img = new ImageIcon(this.getClass().getResource("/img/slim.png")).getImage();
}

@Override
public void bewegen(Richting richting){
    verplaatsNaarVakje(zoekBuurvakjeOpKortstePad());
    afgehandeldeNodes.clear();
    nietAfgehandeldeNodes.clear();
    gelinkteAfgehandeldeNodes.clear();
    lengteRoute.clear();
}

@Override
public void actionPerformed(ActionEvent event){
    bewegen(Richting.NOORD);
}

public Vakje zoekBuurvakjeOpKortstePad() {
    lengteRoute.put(ligplaats, 0);
    nietAfgehandeldeNodes.add(ligplaats);
    while (nietAfgehandeldeNodes.size() > 0) {
        Vakje node = nietAfgehandeldeNodes.pop();
        afgehandeldeNodes.add(node);
        getAfTeHandelenBuren(node);
        if (node.getSpelObject() instanceof Pacman) {
            return getGevondenPad(node);
        }
    }
    throw new RuntimeException("Pacman is niet te vinden!");
}

private void getAfTeHandelenBuren(Vakje node) {
    java.util.List<Vakje> buren = getNietAfgehandeldeBuren(node);
    for (Vakje buur : buren) {
        lengteRoute.put(buur, lengteRoute.get(node) + 1);
        gelinkteAfgehandeldeNodes.put(buur, node);
        Spelobject object = buur.getSpelObject();
        if (!(object instanceof Muur)) {
            nietAfgehandeldeNodes.add(buur);
        }
        if (object instanceof Pacman) {
            break;
        }
    }
}

private java.util.List<Vakje> getNietAfgehandeldeBuren(Vakje node) {
    java.util.List<Vakje> buren = node.getBuren();
    Iterator<Vakje> iter = buren.iterator();
    while (iter.hasNext()) {
        Vakje buur = iter.next();
        if (isAfgehandeld(buur)) {
            iter.remove();
        }
    }
    return buren;
}

private boolean isAfgehandeld(Vakje vertex) {
    return afgehandeldeNodes.contains(vertex);
}

public Vakje getGevondenPad(Vakje doel) {
    LinkedList<Vakje> route = new LinkedList<>();
    Vakje node = doel;
    if (gelinkteAfgehandeldeNodes.get(node) == null) {
        return null;
    }
    route.add(node);
    while (gelinkteAfgehandeldeNodes.get(node) != null) {
        node = gelinkteAfgehandeldeNodes.get(node);
        route.add(node);
    }

    Collections.reverse(route);
    return route.get(1);
}
4

0 回答 0