Dijkstra algorithm helping find new space

[1bumcheek]

Hello people I am kind of new to coding and I am making a robot that moves through a maze that is 5 by 5. I am writing dijkstras algorithm to help me, or at least trying to, I think the problem with my code is the part where it detects a new space. However there is probably more to change.

This is my code so far...

import time
import numpy as np

Maze = np.array([
    "X", "_", "_", "_", "_",
    "_", "Z", "Z", "Z", "_",
    "_", "Z", "_", "_", "_",
    "_", "_", "_", "_", "_",
    "_", "_", "Z", "_", "Y", 

])

# Reshape the 1D array into a 2D 7x7 grid
Maze = Maze.reshape((5, 5))

def X():
  CurrentValue = str(input("CurrentValue"))
  if CurrentValue:
    print ("currentCoords" + str(CurrentValue))
  else:
    print("currentCoords") 
  return

CurrentValue = "Y"
i = 0

# Check for obstacles represented as -1
def check_next_coordinates(X, Y):
    if 0 <= X < 5 and 0 <= Y < 5:
        return Maze[X, Y] != -1
    return False

# Stop when it reaches the Y
while CurrentValue != X:
    currentCoords = np.argwhere(Maze == CurrentValue)
    # Check if currentCoords array is empty
    if not currentCoords.any():
        break

    print("Current Coordinates:", currentCoords[-1])
    time.sleep(1)

    # Check for empty space
    if Maze[tuple(currentCoords[-1])] == -2:
        Maze[tuple(currentCoords[-1])] = int(CurrentValue) + 1
    elif Maze[tuple(currentCoords[-1])] == 0:
        print("Maze:", Maze)
        CurrentValue = 0

    X = currentCoords[-1][0]
    Y = currentCoords[-1][1] if currentCoords[-1].size > 1 else currentCoords[-1][0]

    # Check the left space
    left_x, left_y = X, Y - 1
    if check_next_coordinates(left_x, left_y):
        if Maze[left_x, left_y] == -2:
            Maze[left_x, left_y] = CurrentValue + 1
        elif Maze[left_x, left_y] == 0:
            print("Left space is available")
            CurrentValue = -2

    # Check the above space
    above_X, above_Y = X - 1, Y
    if check_next_coordinates(above_X, above_Y):
        if Maze[above_X, above_Y] == -2:
            Maze[above_X, above_Y] = CurrentValue + 1
        elif Maze[above_X, above_Y] == 0:
            print("Space above is available")
            CurrentValue = -2

    # Check the right space
    right_X, right_Y = X, Y +1
    if check_next_coordinates(right_X, right_Y):
        if Maze[right_X, right_Y] == -2:
            Maze[right_X, right_Y] = CurrentValue + 1
        elif Maze[right_X, right_Y] == 0:
            print("Right space is available")
            CurrentValue = -2

    # Adds 1 to the next space 
    i = i + 1

    # Print the updated Maze after each move
    print(Maze)

#print("Maze:", Maze)

So now the code prints the maze, the coordinates and then waits a second then prints the maze again so on and so on.
But I want it to check the spaces around it, update what it prints with a 1, then on the next print update it with the number 2 until it reaches the X.
Any help appreciated , thanks in advance :)

[deanhystad]

I think you solution will get stuck in the upper left corner of the maze (bouncing between (0, 0) and (1, 0). This solves your current maze, but would fail for a maze like this.

Output:
-----
-ZZZ-
-Z---
-----
-Z-YX

This does not look like Dijkstra's algorithm at all. Where is the shortest path tree? In Digkstra's algorithm you compute the distance to the goal for each node. Once you compute that, you have solutions for all starting positions. You would not blindly wander around, hoping to stumble upon the goal.

You will also have a hard time showing the path using digits if the number of moves exceeds 9. Could you mock up what you want the output to look like?

[1bumcheek]

The output looks like this

Output:
[currentCoords[6,6]]
[['X' '_' '_' '_' '_'] 
 ['_' 'Z' 'Z' 'Z' '_'] 
 ['_' 'Z' '_' '_' '_'] 
 ['_' '_' '_' '_' '_'] 
 ['_' '_' 'Z' '_' '0']]

once it reaches next to the X in the top left corner it should stop and this should be fine however what I need first it the "_" to update from a "_" to a "1" however I don't know how I would implement that with the code.
Thank you for the response

[Gribouillis]

I haven't tried to run the code but at line 34, X should most certainly be 'X'

Also CurrentValue is initialized as a string but later in the code it is assigned numerical values. This indicates an inconsistency in the design of the program.

[deanhystad]

To use Dijkstra's algorithm the first thing you would do is convert your maze from a map to a graph. Below is a graph for the map in you post. It is a dictionary of node: {n1:cost, n2:cost...} where n1, n2, ... are neighboring nodes and cost the cost to reach that node. You could add wall ("Z") nodes and give them an infinite cost (you can't go there), but I decided to prune the walls so the search algorithm has fewer paths to compute.

Output:
((0, 0), {(1, 0): 1, (0, 1): 1})
((1, 0), {(2, 0): 1, (0, 0): 1})
((2, 0), {(3, 0): 1, (1, 0): 1})
((3, 0), {(4, 0): 1, (2, 0): 1})
((4, 0), {(4, 1): 1, (3, 0): 1})
((0, 1), {(0, 2): 1, (0, 0): 1})
((4, 1), {(4, 2): 1, (4, 0): 1})
((0, 2), {(0, 3): 1, (0, 1): 1})
((2, 2), {(3, 2): 1, (2, 3): 1})
((3, 2), {(4, 2): 1, (3, 3): 1, (2, 2): 1})
((4, 2), {(4, 3): 1, (3, 2): 1, (4, 1): 1})
((0, 3), {(1, 3): 1, (0, 4): 1, (0, 2): 1})
((1, 3), {(2, 3): 1, (0, 3): 1})
((2, 3), {(3, 3): 1, (2, 4): 1, (1, 3): 1, (2, 2): 1})
((3, 3), {(4, 3): 1, (3, 4): 1, (2, 3): 1, (3, 2): 1})
((4, 3), {(4, 4): 1, (3, 3): 1, (4, 2): 1})
((0, 4), {(0, 3): 1})
((2, 4), {(3, 4): 1, (2, 3): 1})
((3, 4), {(4, 4): 1, (2, 4): 1, (3, 3): 1})
((4, 4), {(3, 4): 1, (4, 3): 1})

This entry: ((1, 0), {(2, 0): 1, (0, 0): 1}) says that nodes (0, 0) and (2, 0) are adjacent to node (1, 0), and the cost to reach each node is 1. Node (1, 1) is not in the list of adjacent nodes because it is a wall.

You could also do this: ((1, 0), {(2, 0): 1, (0, 0): 1, (1,1): inf}. Here (1, 1), a wall, shows up as a neighboring node, but the cost to go there is infinite. This will work, but it will take longer to solve the graph.

Most of the Dijkstra's algorithm's I've seen online work with a map like this. Where they tend to differ is the results they produce. Some algorithms just produce a cost map, which I find mostly useless. The cost map for your maze might look like this:

Output:
((0, 0), 0)
((1, 0), 1)
((0, 1), 1)
((0, 2), 2)
((2, 0), 2)
((0, 3), 3)
((3, 0), 3)
((1, 3), 4)
((0, 4), 4)
((4, 0), 4)
((2, 3), 5)
((4, 1), 5)
((3, 3), 6)
((2, 4), 6)
((2, 2), 6)
((4, 2), 6)
((3, 2), 7)
((3, 4), 7)
((4, 3), 7)
((4, 4), 8)

The cost to get from the starting node (3, 4) to reach the goal (0, 0) is 8. The cost map does not provide any information about the route.

Some algorithms produce a roadmap of how to efficiently navigate the graph. This is roadmap of your maze.

Output:
((1, 0), (0, 0))
((0, 1), (0, 0))
((0, 2), (0, 1))
((2, 0), (1, 0))
((0, 3), (0, 2))
((3, 0), (2, 0))
((1, 3), (0, 3))
((0, 4), (0, 3))
((4, 0), (3, 0))
((2, 3), (1, 3))
((4, 1), (4, 0))
((3, 3), (2, 3))
((2, 4), (2, 3))
((2, 2), (2, 3))
((4, 2), (4, 1))
((3, 2), (2, 2))
((3, 4), (2, 4))
((4, 3), (3, 3))
((4, 4), (3, 4))

Each entry in the map directs you to the next node on the most efficient path to the goal. Once you compute the solution you have a map for reaching the goal from any starting node. This roadmap says that starting at (3, 4) the first move is to (2, 4) and then to (2, 3), (1, 3), (0, 3), (0, 2), (0, 1) and finally (0, 0), the goal.

Your program looks more like the start of a recursive search. Start walking around until you either blunder into the goal or hit a dead end. When you hit a dead end you back up to where you can try a different path and blunder along the new path. This will get a solution, but you need to exhaustively test every possible path to find the most efficient.

[Gribouillis]

I once posted a class to run Dijkstra's algorithm. You can use it for the maze:

import numpy as np

Maze = np.array([
    "X", "_", "_", "_", "_",
    "_", "Z", "Z", "Z", "_",
    "_", "Z", "_", "_", "_",
    "_", "_", "_", "_", "_",
    "_", "_", "Z", "_", "Y",

])
# Reshape the 1D array into a 2D grid
Maze = Maze.reshape((5, 5))

directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

def neighbors(pair):
    x, y = pair
    for dx, dy in directions:
        xx, yy = x + dx, y + dy
        if ((0 <= xx < 5) and (0 <= yy < 5)
                and Maze[xx,yy] != 'Z'):
            yield (1, (xx, yy), None)

d = Dijkstra((4, 4), neighbors, target=(0,0))
print(list(d.rev_path_to((0,0)))[::-1])

Output:
[(4, 4), (3, 4), (2, 4), (1, 4), (0, 4), (0, 3), (0, 2), (0, 1), (0, 0)]

With a small modification, you can get a more interesting output

directions = [(1, 0, 'down'), (-1, 0, 'up'), (0, 1, 'right'), (0, -1, 'left')]

def neighbors(pair):
    x, y = pair
    for dx, dy, msg in directions:
        xx, yy = x + dx, y + dy
        if ((0 <= xx < 5) and (0 <= yy < 5)
                and Maze[xx,yy] != 'Z'):
            yield (1, (xx, yy), msg)

d = Dijkstra((4, 4), neighbors, target=(0,0))

for k in list(d.rev_path_to((0,0)))[::-1][1:]:
    print(f'{d[k].edge} -> {k}')

Output:
up -> (3, 4)
up -> (2, 4)
up -> (1, 4)
up -> (0, 4)
left -> (0, 3)
left -> (0, 2)
left -> (0, 1)
left -> (0, 0)

[deanhystad]

Or this:

Output:
X - - - -
^ Z Z Z -
^ Z - - -
^ < < - -
- Z ^ < -

[Gribouillis]

Or this:
Output:X - - - -^ Z Z Z -
^ Z - - -
^ < < - -
- Z ^ < -

or this

Output:
[['0' '1' '2' '3' '4']
 ['1' 'Z' 'Z' 'Z' '5']
 ['2' 'Z' '6' '7' '6']
 ['3' '4' '5' '6' '7']
 ['4' '5' 'Z' '7' '8']]

For this one, you need to run the Dijkstra starting from (0,0) and without target. The number is d[k].dist