Закрепление код Pathfinding

Question

У меня есть этот путь найти код, который делает первую часть находке лишь собирается один квадратный

public class PathFinding { 

    static Vector2 start; 

    static Vector2 end; 

    static Cell[][] cells; 

    static Node currentNode; 

    static Arena arena; 

    public static void calcPAth(Vector2 from, Vector2 to, 
      Cell[][] mapCells, Arena a) { 
     start = from; 
     end = to; 
     cells = mapCells; 
     arena = a; 

     List<Node> openList = new ArrayList<Node>(); 
     List<Node> closedList = new ArrayList<Node>(); 
     Gdx.app.log(PArena.LOG, "Lists Created"); 

     currentNode = new Node(null, start); 
     openList.add(currentNode); 
     Gdx.app.log(PArena.LOG, "Added start to openList"); 
     // check squares around this and add 

     int startPX = (int) currentNode.parentV.x/32; 
     Gdx.app.log(PArena.LOG, "Start X" + startPX); 
     int startPY = (int) currentNode.parentV.y/32; 
     Gdx.app.log(PArena.LOG, "Start Y" + startPY); 

     Gdx.app.log("", ""); 
     // 
     int MIN_X = startPX - 1; 
     int MIN_Y = startPY - 1; 
     int MAX_X = startPX + 1; 
     int MAX_Y = startPY + 1; 

     int startPosX = (startPX - 1 < MIN_X) ? startPX : startPX - 1; 
     int startPosY = (startPY - 1 < MIN_Y) ? startPY : startPY - 1; 
     int endPosX = (startPX + 1 > MAX_X) ? startPX : startPX + 1; 
     int endPosY = (startPY + 1 > MAX_Y) ? startPY : startPY + 1; 

     // Check boundaries on start cell 
     for (int rowNum = startPosX; rowNum <= endPosX; rowNum++) { 
      for (int colNum = startPosY; colNum <= endPosY; colNum++) { 
       // All the neighbors will be grid[rowNum][colNum] 

       if (!cells[rowNum][colNum].getTile().getProperties() 
         .containsKey("blocked")) { 
        Node node = new Node(currentNode, new Vector2(
          rowNum, colNum)); 
        if (rowNum != startPX && colNum != startPY) { 
         node.setMovementCost(14); 
        } else 
         node.setMovementCost(10); 
        openList.add(node); 

        System.out.print(node.getFValue() + "|"); 
       } else 
        System.out.print("B"); 

      } 
      System.out.println(""); 

     } 

     openList.remove(currentNode); 
     closedList.add(currentNode); 
     int n = openList.get(0).getFValue(); 
     int index = 0; 
     for (Node temp : openList) { 
      if (temp.getFValue() < n) { 
       n = temp.getFValue(); 
       index = openList.lastIndexOf(temp); 
       Gdx.app.log("n", "n = " + n); 
      } 
     } 
     currentNode = openList.get(index); 
     arena.colorSquare(currentNode.getVectorPos()); 

     // need to calc move cost; 

     // 

     Gdx.app.log("", ""); 
     openList.clear(); 
     closedList.clear(); 

    } 

Это мой класс Node

public static class Node { 

     int hVal; 

     int gVal; 

     int fVal; 

     Node parentNode; 

     Vector2 parentV; 

     private Node(Node node, Vector2 p) { 
      setParent(node); 
      this.parentV = p; 
      calcHValue(); 
     } 

     public void setMovementCost(int c) { 
      this.gVal = c; 
      calcFVal(); 
     } 

     private void calcFVal() { 
      fVal = gVal + hVal; 
      // Gdx.app.log("Node", "HVal = " + hVal); 
      // Gdx.app.log("Node", "GVal = " + gVal); 
      // Gdx.app.log("Node", "FVal = " + fVal); 
     } 

     private void calcHValue() { 
      int x = (int) (parentV.x - end.x); 
      if (x < 0) 
       x *= -1; 
      int y = (int) (parentV.y - end.y); 
      if (y < 0) 
       y *= -1; 

      hVal = (int) (x + y)/32; 
      // Gdx.app.log(PArena.LOG, "Heuristic Value" + hVal); 
     } 

     private void setParent(Node node) { 
      this.parentNode = node; 
     } 

     public int getFValue() { 
      return fVal; 
     } 

     public Vector2 getVectorPos() { 
      return parentV; 
     } 
    } 

Моя проблема заключается в том, что мой такие отладочные выходы, как этот

15|11|15| 
11|11|11| 
15|11|15| 

Так что в основном это не вычисление общей стоимости. Это просто добавляет стоимость движения, а не эвристику.

В чем проблема? Мне не хватает шага?

Answer 1

Вам не хватает списка преемников, я думаю. A * действительно есть Successorlist и в то время как openlist Isnt опорожнить вы делаете следующий материал:

while (openList.size() != 0) { 
      successor.clear(); 
      q = openList.remove(); //first element of the prio queue 
// generate your neighbornodes of q and add them to the successorlist 
//after this you iterate over the successor and check if its your goalnode. 
//If so you do return it else you add it to the openlist. (still inside of the while!) 
//Dont forget to check if the neighbor is inside of the close list! 
//if so you do not need to add it to the successorlist 



//Here is how it does look at mine A*. It also contains a check if there is a betterone 

// calc 

    for (Node suc : successor) { 
     if (suc.x == (int) this.screen.character.mapPos.x 
       && suc.y == (int) this.screen.character.mapPos.y) 
      return suc; //return the goalnode 
     boolean add = true; 
     if (betterIn(suc, openList)) 
      add = false; 
     if (betterIn(suc, closeList)) 
      add = false; 
     if (add) 
      openList.add(suc); 
    } 

Последний но не в последнюю очередь сделать удалить Q записку от openlist и добавить его в тесной ист.

  } 
      closeList.add(q); 
     }//end of while 

Некоторые более мелкие improvmements будет то, что вы делаете добавить compareable в узел ..

@Override 
public int compareTo(Node o) { 
    if ((this.g + this.h) < (o.g + o.h)) 
     return -1; 
    else if ((this.g + this.h) >= (o.g + o.h)) 
     return 1; 
    else 
     return 0; 
} 

также переопределить Равных и метод Hashcode для него, например, как это:

@Override 
    public boolean equals(Object o) { 
     // override for a different compare 
     return ((Node) o).x == this.x && ((Node) o).y == this.y; 
    } 

    @Override 
    public int hashCode() { 
     return x + y; 
    } 

После этого ваш openList может быть PriorityQueue<Node>, и первый объект, который вы получаете, всегда совпадает с наименьшим h.

Не забудьте вернуть наш окончательный узел, чтобы перебрать метод getparent, чтобы получить путь.

---

private boolean betterIn(Node n, Collection<Node> l) { 
    for (Node no : l) { 
     if (no.x == n.x && no.y == n.y && (no.g + no.h) <= (n.g + n.h)) 
      return true; 
    } 
    return false; 
}