Floyd-warshallアルゴリズム

Question

私は現在、Javaの小さなtowerdefenseプロジェクトに取り組んでいます。私はpathfindingに悩まされています。 私はA * dijkstraなどについて多くのことを読んでいましたが、私はFloyd-Warshallを経路探索に使用するのが最善であると判断しました（少なくとも、すべてのペアの最短経路問題を解決するように思えます）。

私は自分でそれを実装しようとしましたが、正しく動作しません。 私はここで開始http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

としてウィキペディア上のコードを使用し私のコードです：私はすべてのものを作成して

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); 
      } 
     } 
    } 
} 

}

ワーシャル - フロイド法は、グラフ上で動作するように設計されていますノードはそのネイバー（それが接続されているノード）を知っています。

私は実際にどこが間違っているのか、どういうわけかここではありません。 少なくとも、それは隣接行列の初期化のように見えます。

floydwarshall関数では、次の[] []で次のノードのインデックスを取得したいと考えていますが、NULLまたは10/11しか取得できません。

私の質問は何が間違っているのですか、私のアプローチが間違っていますか？ 誰かが私を助けてくれることを願っています。 さらに詳しい情報が必要な場合は

p.S.にお問い合わせください。私の悪い英語のために申し訳ありません;）

Answer 1

私はJavaを利用できませんが、あなたのinitAdjacency（）関数に欠陥があるようです。あなたが[CELL_X] [CELL_Y]である地図の寸法を反復している間、[[CELL_X * CELLS_Y] [CELLS_X * CELLS_Y]の寸法です。 1000年の値と、彼らはinitAdjacency（）関数の先頭に

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

を追加0

試しになってしまうが、あなたのループの前に、それを適切に初期化します。

また、私は、これはアルゴリズムに影響を与えわからないんだけど、念のその後

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

を行うことをお勧めします。