A * Pathfinding - Arrêter de déplacer la diagonale à travers les carreaux

Question

J'essaie de comprendre l'algorithme de recherche A * et j'ai un carré qui traverse un labyrinthe, mais le carré traverse deux carreaux qui touchent aux coins. Voici un exemple:

Image - Click here

est-il de toute façon d'arrêter l'algorithme d'ajouter ceci au chemin

public List<Node> findPath(Vector2i start, Vector2i goal){ 

    List<Node> openList = new ArrayList<Node>(); 
    List<Node> closeList = new ArrayList<Node>(); 

    Node current = new Node(start, null, 0, getDistance(start, goal)); 
    openList.add(current); 
    while(openList.size() > 0){ 
     Collections.sort(openList, nodeSorter); 
     current = openList.get(0); 
     if(current.tile.equals(goal)){ 
      List<Node> path = new ArrayList<Node>(); 
      while(current.parent != null){ 
       path.add(current); 
       current = current.parent; 
      } 
      openList.clear(); 
      closeList.clear(); 
      return path; 
     } 
     openList.remove(current); 
     closeList.add(current); 
     for(int i = 0; i < 9; i++){ 
      if(i == 4) continue; 
      int x = current.tile.getX(); 
      int y = current.tile.getY(); 
      int xi = (i % 3) - 1; 
      int yi = (i/3) - 1; 
      Tile at = getTile(x + xi, y + yi); 
      if(at == null || at == Tile.voidTile) continue; 
      if(at.isSolid()) continue; 

      Vector2i a = new Vector2i(x + xi, y + yi); 
      double gCost = current.gCost + getDistance(current.tile, a); 
      double hCost = getDistance(a, goal); 
      Node node = new Node(a, current, gCost, hCost); 
      if(vecInList(closeList, a) && gCost >= current.gCost) continue; 
      if(!vecInList(openList, a) || gCost < node.gCost) openList.add(node); 
     } 
    } 
    closeList.clear(); 
    return null; 
} 

Answer 1

Petit hors sujet: Si vous ne voulez pas ajouter ces tuiles pour ouvrir liste, alors ils ne doivent pas être considérés comme des voisins. Donc, la question de base que vous devez répondre en créant un algorithme pathfinding - quels nœuds sont considérés comme voisins dans mon graphique.

Dans votre cas, votre tuile actuelle n'est pas voisin de tuile diagonalesi leursles deux communes voisines ne sont pas passable. Par exemple, pour le pavé {+1, +1}, ces voisins seront {0, +1} et {+1, 0}. Etc. Donc, permet de vérifier qu'il:

// code here... 
if(at.isSolid()) continue; 

if (Math.abs(xi * yi) == 1) { 
    // this is true if we're checking diagonal tile 
    if (!isPassable(getTile(x + xi, y)) && !isPassable(getTile(x, y + yi)) { 
    // Both common neigbors are not passable 
    // So we won't add this tile as neighbor 
    continue; 
    } 
} 

Et méthode isPassable:

private boolean isPassable(Tile tile) { 
    return tile != Tile.voidTile && !tile.isSolid(); 
} 

neigbors communs existent toujours, si vous traitez avec des carreaux en diagonale, de sorte que vous ne devriez pas les vérifier null.