Floyd-warshall algorithm

Question

ich arbeite gerade an einem kleinen towerdefense Projekt in Java und bin mit der Wegfindung festgefahren. Ich lese viel über A * Dijkstra und solche Dinge, aber ich entschied, dass es wahrscheinlich das Beste ist, Floyd-Warshall für die Pfadfindung zu verwenden (zumindest erscheint es mir als die Lösung des kürzesten Pfades).

Trotzdem habe ich versucht, es auf eigene Faust zu implementieren, aber es funktioniert nicht genau so, wie es sollte. verwendet ich den Code auf wikipedia als Start http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

Also hier ist mein Code:

public class MyMap { 
public class MyMapNode { 
    // list of neighbour nodes 
    public List<MyMapNode> neighbours; 
    // Currently no need for this :) 
    public int cellX, cellY; 
    // NodeIndex for pathreconstruction 
    public int index; 
    // this value is checked by units on map to decide wether path needs 
    // reconstruction 
    public boolean isFree = true; 

    public MyMapNode(int cellX, int cellY, int index) { 
     this.cellX = cellX; 
     this.cellY = cellY; 
     this.index = index; 
     neighbours = new ArrayList<MyMapNode>(); 
    } 

    public void addNeighbour(MyMapNode neighbour) { 
     neighbours.add(neighbour); 
    } 

    public void removeNeighbour(MyMapNode neighbour) { 
     neighbours.remove(neighbour); 
    } 

    public boolean isNeighbour(MyMapNode node) { 
     return neighbours.contains(node); 
    } 
} 
//MapSize 
public static final int CELLS_X = 10; 
public static final int CELLS_Y = 10; 

public MyMapNode[][] map; 

public MyMap() { 
    //Fill Map with Nodes 
    map = new MyMapNode[CELLS_X][CELLS_Y]; 
    for (int i = 0; i < CELLS_X; i++) { 
     for (int j = 0; j < CELLS_Y; j++) { 
      map[i][j] = new MyMapNode(i, j, j + i * CELLS_Y); 
     } 
    } 
    //------------------------------------------------- 
    initNeighbours(); 
    recalculatePath(); 
} 

public void initNeighbours() { 
    //init neighbourhood without diagonals 
    for (int i = 0; i < CELLS_X; i++) { 
     for (int j = 0; j < CELLS_Y; j++) { 
      int x, y;// untere Grenze 
      if (j == 0) 
       y = 0; 
      else 
       y = -1; 
      if (i == 0) 
       x = 0; 
      else 
       x = -1; 
      int v, w;// obere Grenze 
      if (j == CELLS_Y - 1) 
       w = 0; 
      else 
       w = 1; 
      if (i == CELLS_X - 1) 
       v = 0; 
      else 
       v = 1; 
      for (int h = x; h <= v; h++) { 
       if (h != 0) 
        map[i][j].addNeighbour(map[i + h][j]); 
      } 
      for (int g = y; g <= w; g++) { 
       if (g != 0) 
        map[i][j].addNeighbour(map[i][j + g]); 
      } 

     } 
    } 
} 
//AdjacencyMatrix 
public int[][] path = new int[CELLS_X * CELLS_Y][CELLS_X * CELLS_Y]; 
//for pathreconstruction 
public MyMapNode[][] next = new MyMapNode[CELLS_X * CELLS_Y][CELLS_X 
     * CELLS_Y]; 

public void initAdjacency() { 
    for (int i = 0; i < map.length; i++) { 
     for (int j = 0; j < map[0].length; j++) { 
      path[i][j] = 1000; 
      List<MyMapNode> tmp = map[i][j].neighbours; 
      for (MyMapNode m : tmp) { 
       path[m.index][map[i][j].index] = 1; 
       path[map[i][j].index][m.index] = 1; 
      } 
     } 
    } 
} 

public void floydWarshall() { 
    int n = CELLS_X * CELLS_Y; 
    for (int k = 0; k < n; k++) { 
     for (int i = 0; i < n; i++) { 
      for (int j = 0; j < n; j++) { 
       if (path[i][k] + path[k][j] < path[i][j]) { 
        path[i][j] = path[i][k] + path[k][j]; 
        next[i][j] = getNodeWithIndex(k); 
       } 
      } 
     } 
    } 
} 

public void recalculatePath() { 
    initAdjacency(); 
    floydWarshall(); 
} 

public MyMapNode getNextWayPoint(MyMapNode i, MyMapNode j) { 
    if (path[i.index][j.index] >=1000) 
     return null; 
    MyMapNode intermediate = next[i.index][j.index]; 
    if (intermediate == null) 
     return j; /* there is an edge from i to j, with no vertices between */ 
    else 
     return getNextWayPoint(i, intermediate); 
} 

public MyMapNode getNodeWithIndex(int k) { 
    //for testing purpose,this can be done faster 
    for (int i = 0; i < map.length; i++) { 
     for (int j = 0; j < map[0].length; j++) { 
      if (map[i][j].index == k) 
       return map[i][j]; 
     } 
    } 
    return null; 
} 

public void removeMapNode(MyMapNode m) { 
    //for testing purpose,this can be done faster 
    m.isFree = false; 
    for (int i = 0; i < map.length; i++) { 
     for (int j = 0; j < map[0].length; j++) { 
      if (map[i][j].neighbours.contains(m)) { 
       map[i][j].neighbours.remove(m); 
      } 
     } 
    } 
} 

}

der Floyd-Warshall-Algorithmus auf einem Graphen ausgelegt ist, zu arbeiten, so erstelle ich ein, wo jeder Knoten kennt seine Nachbarn (welche die Knoten sind, mit denen er verbunden ist).

Ich weiß eigentlich nicht, wo es schief geht, aber irgendwie. aber es sieht zumindest so aus, als ob die Initialisierung der Adjazenzmatrix funktioniert.

In der Floydwarshall-Funktion hoffte ich, den Index des nächsten Knotens im nächsten [] [] zu bekommen, aber ich bekomme nur null oder 10/11;

Also meine Frage ist, was mache ich falsch oder ist meine Vorgehensweise überhaupt falsch? ich hoffe jemand kann mir helfen. Wenn Sie weitere Informationen benötigen, fragen Sie bitte

p.S. Entschuldigung für mein schlechtes Englisch;)

Answer 1

Ich habe kein Java zur Verfügung, aber es scheint wie Ihre initAdjacency() -Funktion ist fehlerhaft. path [] [] hat die Dimension [CELL_X * CELLS_Y] [CELLS_X * CELLS_Y], während Sie über die Dimensionen der Map iterieren, die [CELL_X] [CELL_Y] sind, sodass Sie nicht alle Elemente ohne Kanten auf den Standardwert setzen Wert von 1000 und sie am Ende 0

VERSUCH,

for (int i = 0; i < CELLS_X * CELLS_Y; i++) 
    for (int j = 0; j < CELLS_X * CELLS_Y; j++) 
     path[i][j] = 1000; 

zu Beginn der initAdjacency() Funktion hinzugefügt, bevor die Schleife, um es richtig zu initialisieren.

Sie können auch

for (int i = 0; i < CELLS_X * CELLS_Y) path[i][i] = 0; 

danach nur für den Fall tun wollen, ich bin nicht sicher, dass dies den Algorithmus beeinflusst.