What is the most efficient way to represent edge weights for Dijkstra's algorithm

Question

I'm making a little game where I'm going to have a character on a grid that moves around. I was going to use Dijkstra's algorithm for the pathing as they move around. Only problem being is I want to make thin walls(instead of just removing nodes) like so: http://i.gyazo.com/85d110c17cf027d3ad0219fa26938305.png

I was thinking the best way to do it was just edit the edge weights between 2 squares to be so high that it would never be crossed. Anyway, onto the question:

What is the most efficient way to assign edge weights to each connection in the grid?

I've thought about using an adjacency matrix, but for a 15x6 grid, that's a 90x90 matrix which seems... excessive. Any help would be nice, thanks (:

Answer 1

You only need to store edges between the rectilinear squares and a square can have at most 4 neighbors, once for each direction. Store the edge accessed by node as up to 4 entries of the enumeration {up, down, left, right}. That's is less than 90 x 4.

Answer 2

Some pointers that can help you decide what you should do:

1. It seems your graph is unweighted, so you could use a BFS, which is both simpler to implement and more efficient than Dijkstra's algorithm in this case.
2. 90x90 matrix is hardly an issue for a modern machine (unless you are going to use the pathfinding algorithm in a very tight loop)
3. If you are using double as weights, a lot of languages got infinity value that you could use. In java that's Double.POSITIVE_INFINITY. Beauty about infinity - as much as you add to it, it stays infinity (and does not overflow like integers).
4. You can always use adjacency lists, which can be thought of as a sparsed implementation of a matrix - where most edges have some constant predefined weight (infinity for example, for non existing edge).
5. Note that using adjacency matrix rather than adjacency lists for very sparsed graph (like yours) makes the time complexity of BFS O(V^2) instead of O(V+E) (which is actually O(V) in your case), and O(V^2) for Dijkstra's algorithm instead of O(E + VlogV) (which is O(VlogV) for your graph)

Answer 3

I agree with rocky's answer - just store the weights for the four directions for each square in an array (each array element will be a struct/tuple which contains the four weights). To look up an edge between two arbitrary squares, you first check if they are adjacent, and if so use the appropriate weight from the array. Not sure why anyone mentioned adjacency lists or matrix, which are redundant here.

Answer 4

Try code below to create you game.

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

Use this code to initialize the game board for large arrays. Then add nulls for location of walls making sure you add the walls to two cells.

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

                }
            }
        }
    }
}