使用BFS的路徑尋找算法不會讓我的角色移動

Question

有點弄亂間距哈哈，但方法bfs直到最後一個方法屬於LyannaMormont類。這是來自我們教授給出的機器問題。基本上這個遊戲有一個英雄，小兵，消耗品和裝備。我們的教授向我們提供了一些包含我們所需方法的javadocs。可定位的物體可以是這四個中的任何一個（英雄，蠕變，消耗品，裝備）。我基本上可以得到一個可定位的x和y位置，通過將其設置爲目標屬性，然後使用bfs（）獲取路徑，然後移動字符（在這種情況下，我創建了go方法，它具有包含在javadoc中的moveUp（），moveDown（），moveRight（），moveLeft（）方法，並且完全按照它們的名字所示）。動作方法包含角色所做的所有事情。我的問題是，當我激活遊戲的jar文件時，角色沒有移動。代碼有問題嗎？如果有，有人可以告訴我在哪裏？我基本上在這個問題上停留了3天。任何幫助/建議將非常感激。謝謝:)

注意： WorldState w = getWorld（）;返回我的角色所處的世界的副本。w.isPassable（int x，int y）如果我可以遍歷（x，y）則返回true，否則返回false。

import com.th.*; 
import java.util.*; 


public class LyannaMormont extends HeroBot{ 
    ArrayList<Node> way = new ArrayList<Node>(); 
    private Locatable destination; 
    private int count = 0; 
    private boolean where = false; 
    private final int counter = 0; 

    public class Node implements Comparable<Node>{ 
     private int xPosition; 
     private int yPosition; 
     private Node parentNode; 
     private double minDist; 

     public Node(int x, int y, Node p, double n){ 
      this.xPosition = x; 
      this.yPosition = y; 
      this.parentNode = p; 
      this.minDist = n; 
     } 

     public int getXPosition(){ 
      return this.xPosition; 
     } 

     public int getYPosition(){ 
      return this.yPosition; 
     } 

     public void setXPosition(int x){ 
      this.xPosition = x; 
     } 

     public void setYPosition(int y){ 
      this.yPosition = y; 
     } 

     public Node getParentNode(){ 
      return this.parentNode; 
     } 

     public void setParentNode(Node p){ 
      this.parentNode = p; 
     } 

     public double getMinDist(){ 
      return this.minDist; 
     } 

     public void setMinDist(double m){ 
      this.minDist = m; 
     } 

     public int compareTo(Node otherNode){ 
      return Double.compare(this.minDist, otherNode.getMinDist()); 
     } 

     public boolean equals(Node node){ 
      if((this.xPosition == node.getXPosition())&&(this.yPosition == node.getYPosition())){ 
       return true; 
      } 
      else{ 
       return false; 
      } 
     } 
    } 

    public void bfs(){ 
     WorldState w = getWorld(); 
     ArrayList<Node> found = new ArrayList<Node>(); 
     Queue<Node> queue = new LinkedList<Node>(); 
     Node source = new Node(this.getXLocation(), this.getYLocation(), null, 0.0); 
     queue.add(source); 
     found.add(source); 
     ArrayList<Node> path = new ArrayList<Node>(); 

     outerloop: 
     while(queue.peek()!=null){ 
      Node node = queue.poll(); 
      if((node.getXPosition() == this.destination.getXLocation())&&(node.getYPosition() == this.destination.getYLocation())){ 
       path.add(node); 
       queue.clear(); 
       found.clear(); 
       break outerloop; 
      } 

      int x = node.getXPosition(); 
      int y = node.getYPosition(); 
      if(w.isPassable(x-1, y)){ 
       Node newNode = new Node(x-1, y, node, node.getMinDist() + 1.0); 
       if(!found.contains(newNode)){ 
        queue.add(newNode); 
        found.add(newNode); 
       } 
      } 
      if(w.isPassable(x, y-1)){ 
       Node newNode = new Node(x, y-1, node, node.getMinDist() + 1.0); 
       if(!found.contains(newNode)){ 
        queue.add(newNode); 
        found.add(newNode); 
       } 
      } 
      if(w.isPassable(x+1, y)){ 
       Node newNode = new Node(x+1, y, node, node.getMinDist() + 1.0); 
       if(!found.contains(newNode)){ 
        queue.add(newNode); 
        found.add(newNode); 
       } 
      } 
      if(w.isPassable(x, y+1)){ 
       Node newNode = new Node(x, y+1, node, node.getMinDist() + 1.0); 
       if(!found.contains(newNode)){ 
        queue.add(newNode); 
        found.add(newNode); 
       } 
      } 
     } 
     Node goal = path.get(0); 
     this.way = new ArrayList<Node>(); 
     while(goal.getParentNode()!=null){ 
      this.way.add(0, goal); 
      goal = goal.getParentNode(); 
     } 
     if (goal.getParentNode() == null){ 
      this.way.add(0, goal); 
     } 
     Collections.sort(this.way); 
     this.destination = null; 
     this.where = false; 
    } 

Answer 1

除非你對progress變量有一些特殊的理由，那麼你想完全消除它。當你不需要它時，它正在消耗Node。基本上你想要測試每次迭代時你的目標是否在你的目標，如果你發現它，就打破它。否則，你分支出去。

outerloop: 
while(queue.peek()!=null){ 
    Node node = queue.poll(); 
    if((node.getXPosition() == this.destination.getXLocation())&&(node.getYPosition() == this.destination.getYLocation())){ 
     path.add(node); 
     queue.clear(); 
     found.clear(); 
     break outerloop; 
    } 

    int x = node.getXPosition(); 
    int y = node.getYPosition(); 
    if(w.isPassable(x-1, y)){ 
     Node newNode = new Node(x-1, y, node, node.getMinDist() + 1.0); 
     if(!found.contains(newNode)){ 
      queue.add(newNode); 
      found.add(newNode); 
     } 
    } 
    if(w.isPassable(x, y-1)){ 
     Node newNode = new Node(x, y-1, node, node.getMinDist() + 1.0); 
     if(!found.contains(newNode)){ 
      queue.add(newNode); 
      found.add(newNode); 
     } 
    } 
    if(w.isPassable(x+1, y)){ 
     Node newNode = new Node(x+1, y, node, node.getMinDist() + 1.0); 
     if(!found.contains(newNode)){ 
      queue.add(newNode); 
      found.add(newNode); 
     } 
    } 
    if(w.isPassable(x, y+1)){ 
     Node newNode = new Node(x, y+1, node, node.getMinDist() + 1.0); 
     if(!found.contains(newNode)){ 
      queue.add(newNode); 
      found.add(newNode); 
     } 
    } 
}