什么是最有效的方式来表示Dijkstra的算法的边权重

Question

我正在做一个小游戏，我要在网格中移动一个角色。当他们四处移动时，我将使用Dijkstra的路径算法。唯一的问题是我想制作薄壁（而不是仅仅删除节点），如下所示：http://i.gyazo.com/85d110c17cf027d3ad0219fa26938305.png

我在想最好的方法就是编辑2个方格之间的边缘重量，永远不会被越过。无论如何，在这个问题上：

什么是边缘权重分配给网格中的每个连接的最有效的方法是什么？

我想过使用一个邻接矩阵，但对于一个15x6的网格，这是一个90x90的矩阵，看起来......过度。任何帮助都会很好，谢谢（

Answer 1

你只需要在直线方块之间存储边缘，一个方块最多可以有4个邻居，每个方向一次，存储边缘访问的边缘最多4条。枚举{上，下，左，右}这是小于90×4

Answer 2

一些指针，可以帮助你决定你应该做的：

1. 看来你的图是不加权，所以你可以使用BFS，这是 在这种情况下比Dijkstra的算法更容易实现并且效率更高。
2. 90x90矩阵是很难成为一个现代化的机器的问题（除非您要使用的寻路算法在一个非常紧密的循环）
3. 如果您正在使用double作为权重，很多的语言得到了 无穷价值，你可以用。在java中，这是 Double.POSITIVE_INFINITY。关于无限的美 - 就像你添加它一样，它保持无穷（并且不像整数那样溢出）。
4. 您总是可以使用adjacency lists，这可以认为是矩阵的稀疏实现 - 其中大多数边具有某个恒定的预定义权重（例如对于非现有边的无穷大）。
5. 注意，使用邻接矩阵，而不是邻接表非常疏林图（像你这样）让BFS O(V^2)代替O(V+E)（实际上O(V)你的情况），以及O(V^2)的时间复杂度为Dijkstra算法而不是O(E + VlogV)（其是O(VlogV)你图）

Answer 3

我同意岩石的答案 - 只为四个方向各方的权重存放在数组（每个数组元素将是一个结构/元组包含四个权重）。要在两个任意方块之间查找边缘，首先检查它们是否相邻，如果是这样，请使用阵列中的适当权重。不知道为什么有人提到邻接表或矩阵，这在这里是多余的。

Answer 4

试试下面的代码来创建你的游戏。

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 

namespace ConsoleApplication1 
{ 
    class Program 
    { 
     static void Main(string[] args) 
     { 

      object[,] input = { 
           { 
            new object[] { 0, -1, -1, 1, 6}, //index, left, up, right, down 
            new object[] { 1, 0, -1, -1, 7}, //index, left, up, right, down 
            new object[] { 2, -1, -1, 3, 8}, //index, left, up, right, down 
            new object[] { 3, 2, -1, 4, 9}, //index, left, up, right, down 
            new object[] { 4, 3, -1, -1, 10}, //index, left, up, right, down 
            new object[] { 5, -1, -1, -1, 11} //index, left, up, right, down 
           }, 
           { 
            new object[] { 6, -1, 0, 7, -1}, //index, left, up, right, down 
            new object[] { 7, 6, 1, -1, 13}, //index, left, up, right, down 
            new object[] { 8, -1, 2, 9, 14}, //index, left, up, right, down 
            new object[] { 9, 8, 3, -1, -1}, //index, left, up, right, down 
            new object[] {10, -1, 4, 11, -1}, //index, left, up, right, down 
            new object[] {11, 10, 5, -1, 17} //index, left, up, right, down 
           }, 
           { 
            new object[] {12, -1, -1, 13, 19}, //index, left, up, right, down 
            new object[] {13, 12, 7, 14, 20}, //index, left, up, right, down 
            new object[] {14, 13, 8, 15, 21}, //index, left, up, right, down 
            new object[] {15, 14, -1, -1, 22}, //index, left, up, right, down 
            new object[] {16, -1, -1, 17, 23}, //index, left, up, right, down 
            new object[] {17, 16, 11, -1, 24} //index, left, up, right, down 
           }, 
           { 
            new object[] {18, -1, 12, 19, 24}, //index, left, up, right, down 
            new object[] {19, 18, 13, -1, 25}, //index, left, up, right, down 
            new object[] {20, -1, 14, 21, 26}, //index, left, up, right, down 
            new object[] {21, 20, 15, -1, 27}, //index, left, up, right, down 
            new object[] {22, -1, 16, 23, 28}, //index, left, up, right, down 
            new object[] {23, 22, 17, -1, 29} //index, left, up, right, down 
           }, 
           { 
            new object[] {24, -1, 18, 25, -1}, //index, left, up, right, down 
            new object[] {25, 24, 19, 26, -1}, //index, left, up, right, down 
            new object[] {26, -1, 20, 27, -1}, //index, left, up, right, down 
            new object[] {27, 26, 21, 28, -1}, //index, left, up, right, down 
            new object[] {28, 27, 22, 29, -1}, //index, left, up, right, down 
            new object[] {29, 28, 23, -1, -1} //index, left, up, right, down 
           }, 
          }; 

      cell game = new cell(input); 
     } 
    } 
    public class cell 
    { 
     public static cell[,] board = new cell[5, 6]; 

     public int index { get; set; } //row number * 6 + col 
     public int row { get; set;} 
     public int col { get; set;} 
     public cell up { get; set; } 
     public cell down { get; set; } 
     public cell left { get; set; } 
     public cell right { get; set; } 

     public cell() { } 

     public cell(object[,] input) 
     { 
      int cellNumber = 0; 
      int boardRow = 0; 
      int boardCol = 0; 
      int cellRow = 0; 
      int cellCol = 0; 

      for (int row = 0; row < 5; row++) 
      { 
       for (int col = 0; col < 6; col++) 
       { 
        board[row, col] = new cell(); 
       } 
      } 

      for (int row = 0; row < 5; row++) 
      { 
       for (int col = 0; col < 6; col++) 
       { 
        object[] items = (object[])input[row, col]; 
        cellNumber = (int)items[0]; 
        boardRow = cellNumber/6; 
        boardCol = cellNumber % 6; 

        board[boardRow, boardCol].index = cellNumber; 
        board[boardRow, boardCol].row = row; 
        board[boardRow, boardCol].col = col; 

        cellNumber = (int)items[1]; 
        cellRow = cellNumber/6; 
        cellCol = cellNumber % 6; 
        if (cellNumber == -1) 
        { 
         board[boardRow, boardCol].left = null; 
        } 
        else 
        { 
         board[boardRow, boardCol].left = board[cellRow, cellCol]; 
        }       

        cellNumber = (int)items[2]; 
        cellRow = cellNumber/6; 
        cellCol = cellNumber % 6; 

        if (cellNumber == -1) 
        { 
         board[boardRow, boardCol].up = null; 
        } 
        else 
        { 
         board[boardRow, boardCol].up = board[cellRow, cellCol]; 
        }       

        cellNumber = (int)items[3]; 
        cellRow = cellNumber/6; 
        cellCol = cellNumber % 6; 

        if (cellNumber == -1) 
        { 
         board[boardRow, boardCol].right = null; 
        } 
        else 
        { 
         board[boardRow, boardCol].right = board[cellRow, cellCol]; 
        }       

        cellNumber = (int)items[4]; 
        cellRow = cellNumber/6; 
        cellCol = cellNumber % 6; 

        if (cellNumber == -1) 
        { 
         board[boardRow, boardCol].down = null; 
        } 
        else 
        { 
         board[boardRow, boardCol].down = board[cellRow, cellCol]; 
        }       

       } 
      } 
     } 
    } 
} 
​ 

Answer 5

使用此代码初始化大型数组的游戏板。然后为墙的位置添加空值，确保将墙添加到两个单元格。

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 

namespace ConsoleApplication1 
{ 
    class Program 
    { 
     static void Main(string[] args) 
     { 
      cell game = new cell(90, 100); 
     } 
    } 
    public class cell 
    { 
     public static cell[,] board = null; 

     public int index { get; set; } //row number * 6 + col 
     public int row { get; set;} 
     public int col { get; set;} 
     public cell up { get; set; } 
     public cell down { get; set; } 
     public cell left { get; set; } 
     public cell right { get; set; } 
     public bool visited { get; set; } 

     public cell() { } 

     public cell(int rows, int cols) 
     { 
      board = new cell[rows, cols]; 
      int cellNumber = 0; 

      for (int row = 0; row < rows; row++) 
      { 
       for (int col = 0; col < cols; col++) 
       { 
        board[row, col] = new cell(); 
        board[row, col].visited = false; 

       } 
      } 

      for (int row = 0; row < rows; row++) 
      { 
       for (int col = 0; col < cols; col++) 
       { 
        cellNumber = (row * cols) + col; 

        board[row, col].index = cellNumber; 
        board[row, col].row = row; 
        board[row, col].col = col; 

        if (col == 0) 
        { 
         board[row, col].left = null; 
        } 
        else 
        { 
         board[row, col].left = board[row, col - 1]; 
        }       


        if (row == 0) 
        { 
         board[row, col].up = null; 
        } 
        else 
        { 
         board[row, col].up = board[row - 1, col]; 
        }       


        if (col == cols - 1) 
        { 
         board[row, col].right = null; 
        } 
        else 
        { 
         board[row, col].right = board[row, col + 1]; 
        }       

        if (row == rows - 1) 
        { 
         board[row, col].down = null; 
        } 
        else 
        { 
         board[row, col].down = board[row + 1, col]; 
        }       

       } 
      } 
     } 
    } 
}