Building adjacency graph out of chessboard (for dijkstra)

Question

I ran into a problem where I wanted to add a little feature to my homework and it turned out to be overwhelming for me (read bold sentences for question without context).

My program has a list of about 35 items in it, containing information about the map I'm supposed to work with. It can have the following elements:

• "Wall" with its coordinates (X, Y), in the dijkstra it is supposed to have weight 100.
• "Tree" with cords (X, Y), weight 3

I have a 10x10 map laid out like a chessboard, which means 100 tiles, and 35 items. "Nothing" in the list means weight 1 in dijkstra (it means a normal route)

To make the dijkstra work and be able to find a shortest path between two tiles, I have to build an adjacency graph. My problem here is, how to define tiles "around" the current tile, if all I have is that list?

Only adjacent tiles in the shape of "+" have edges in the graph between them, but I have to run through the list every time to check if there is something on it?

Any lead on the problem would be greatly appreciated, also if you can point me to a source with a code sample, that could also do. I only see really messy code with a lot of "if-elseif-elseif..." to solve that.

Thank you for your time!

Edit: I ended up using @kraskevich 's suggested way, and it works excellent, but all the answers and suggestions were really useful, thank you very much everyone!

Answer 1

You don't really need to build a graph. Just create a 10x10 table and put the weight of the corresponding items into it:

board = 10x10 array filled with 1
for item in list:
    if item is a tree:
         board[item.row][item.column] = 3
    else if item is a wall:
         board[item.row][item.column] = 100

After that, you can treat pairs (row, col) of coordinates as vertices and update the distance for 4 adjacent cells when you process a tile. That's it. Sure, you can also create a graph with 100 vertices and add edges explicitly from a tile to all 4 adjacent cells (the weight is the weight of the end of the edge tile) and use a standard implementation.

The most convenient way to iterate over adjacent cells is as follows:

delta_rows = [-1, 1, 0, 0]
delta_cols = [0, 0, -1, 1]
...
for direction = 0 .. 3
     new_row = row + delta_rows[direction]
     new_col = col + delta_cols[direction]
     if is_valid(new_row, new_col)
          // do something