Skip to content
Advertisement

Python Trouble with matrix pathfinding (DFS)

I am having issues with dfs, probably from a RecursionError when facing a wall.

Instead of continuously running an attempt which can only lead to a wall, it is supposed to return to its previous position and try another path.

Also, it leans heavily on the order in which attempts are made (N,S,E,W or other combinations)

Thanks in advance

def portal(M,l,c):  # locates current portal and changes position (if entering portal 1, go to portal 2)
    for elem in D.keys():
        x = 1
        if elem == M[l][c]:
            if [l,c] == D[elem][0] and x: [l,c] = D[elem][1]; x -=1
            if [l,c] == D[elem][1] and x: [l,c] = D[elem][0]; x-=1
    return [l,c]
    
def dfs(Q,p):
    l, c = Q[-1]     # previous position
    if [l,c] == COORD: return True
    for dir in [(l-1, c,1), (l, c - 1,2), (l , c+1,3), (l+1 ,c,4)]:    # dir = (l,c,p) = next row, next column and a number that represents the direction taken (1 = north)
        j=1
        if p:
            if dir[2] == p:         # if passing through a portal, p should not update, or else it would attempt to move in a direction it's not intended to
                nextl,nextc = dir[:2]
                print(nextl,nextc,l,c)
            else:  j = 0           # p is not 0 and no move happens (j = 0)
        else:                      # if no portal has been used: try all possible directions
            nextl, nextc, p = dir
        if j:
            if len(M[0]) > c >= 0 and 0 <= l < len(M):    # if inbounds
                if M[nextl][nextc] in D:                  # if the next move lands in a portal, change coordinates using the function portal()
                    Q.append((nextl,nextc))
                    nextl,nextc = portal(M,nextl,nextc)
                if M[nextl][nextc] and ((nextl, nextc) not in Q) and (M[nextl][nextc] not in D):
                # if there is no wall on the next position and it has not been visited yet, call dfs again for the next position  
                    Q.append((nextl, nextc))
                    if dfs(Q,0):
                        return True
                    else:
                        Q.pop()
                elif M[nextl][nextc] and (M[nextl][nextc] in D) and ((nextl, nextc) not in Q):
               # if a portal has been used, the next move should keep previous p (direction). Therefore, the function call is different, to prevent it from attempting to move in all 4 directions.
                    Q.append((nextl,nextc))
                    if dfs(Q,p):
                        return True
                    else:
                        Q.pop()
                elif M[l][c] not in D: p = 0
             # resets p if no move is possible ( allows it to gain a new direction from the for loop above)
            else: p = 0
            
M = [];L = int(input())
for _ in range(L): M.append(input().split())     # Matrix input
for i in M:
    for h in i:
        if h == "#": M[M.index(i)][i.index(h)] = 0
        elif h == ".": M[M.index(i)][i.index(h)] = 1   # Replaces path with 1 (easier to write)

l0, c0 = (int(i) for i in input().split())
queue = [(l0, c0)]       # initial position

COORD = 0
D={};lineP=-1
for LINE in M:          # locates portals and assigns to the corresponding letter both coordinates
    colP = -1; lineP+=1
    for COL in LINE:
        colP+=1
        if COL not in ["*",0,1]:
            if COL in D: D[COL].append([lineP,colP])
            else: D[COL] = [[lineP,colP]]
        if COL == "*": COORD=[lineP,colP]    # locates the destination (marked with "*")

if dfs(queue,0):
    print("Success"
else:
    print("Failure")

Advertisement

Answer

I created a script that finds one path that can reach goal. If the path does not exists, it prints that the task is impossible.

Note: the algorithm does not seek for all possible paths. Once it finds one, it returns that path. Consequently, it does not return the shortest path to goal. It returns a path, if it exists. Otherwise, it returns an empty list.

The return of dfs_pathfinder is a boolean, telling if the path was found or not. To retrive the path, store a list to path, and let the function fill the list passed as parameter by reference.

I tried to explain every single line of the script using comments. If you didn’t understood something, or got an unexpected bug from it, feel free to post it on the comments of this answer.

# Swap rows by columns of a grid.
#
# Useful for printing on terminal only. Or, if you
# need to transpose the input grid.
def transpose(grid):
    tgrid = []

    ncols = range(len(grid[0]))
    nrows = range(len(grid))

    for j in ncols:
        tgrid.append([])
        for i in nrows:
            tgrid[-1].append(grid[i][j])

    return tgrid

# Handles the file input, loading:
# 1. The Character's starting position
# 2. The Grid itself
# 3. The Goal you want to reach 
# 4. The List of Portals
def handle_input(filename):
    portals = {}
    goal = (-1, -1)
    
    # Try to open the file and read all its lines
    try:
        file = open(filename, 'rt')
    except:
        print('Error: Couldn't open ' + filename)
    else:
        lines = file.readlines()
        file.close()

    # Get the number of rows
    nrows = int(lines[0][:-1])

    # Mount the grid based on the file data
    # Append all portals
    # Find the goal's position
    grid = []
    for nr in range(nrows):
        row = lines[nr+1][:-1].split(' ')

        for co in range(len(row)):
            if (row[co] != '.' and row[co] != '#' and row[co] != '*'):
                if (row[co] in portals):
                    if (len(portals[row[co]]) == 2):
                        print("Warning: There are 3 portals of same kind: ", row[co])

                    portals[row[co]].append((nr, co))
                else:
                    portals[row[co]] = [(nr, co)]
            elif (row[co] == '*'):
                goal = (nr, co)

        grid.append(row)

    # Retrieve the starting position
    pos = lines[nrows+1][:-1].split(' ')
    pos = (int(pos[0]), int(pos[1]))

    # Check if the goal exists
    if (goal[0] == -1 or goal[1] == -1):
        print('Warning: No goal * is set')

    return grid, pos, goal, portals

# Eases the way of retrieving the current tile character from the grid, given
# a position pos: (x, y)
#
# If a position outside of the grid is requested, return an empty character.
def get(grid, pos):
    if (pos[0] >= 0 and pos[1] >= 0 and pos[0] < len(grid) and pos[1] < len(grid[pos[0]])):
        return grid[pos[0]][pos[1]]
    else:
        return ''

# Each portal is a pair of positions: [(a, b), (c, d)]
#
# This means that portal1 is at (a, b)
# and portal2 is at (c, d)
#
# Calling enterPortal(portal, (a, b)) -> (c, d)
# Calling enterPortal(portal, (c, d)) -> (a, b)
def enterPortal(portal, pos):
    if (portal[0][0] == pos[0] and portal[0][1] == pos[1]):
        return portal[1]
    else:
        return portal[0]

# This function does not measures the best path. Nor, it searches all
# possible paths available to goal.
#
# It returns the first path to goal that is found. Otherwise, an empty
# path is returned, signalizing that the goal is unreachable.
def dfs_pathfinder(grid, pos, goal, portals, path, reached):
    char = get(grid, pos)
    reached.append(pos)

    # Still walking
    if (char == '.'):
        # Store all movement choices
        movement = [(-1, 0), (1, 0), (0, 1), (0, -1)]

        # Try all movement choices
        for mv in movement:
            # Get a hint of next position
            nextPos = (pos[0] + mv[0], pos[1] + mv[1])

            # If the next position is not reached yet, continue
            if (nextPos not in reached):

                # Append current position to path
                path.append(pos)

                # And check if you are in the correct path
                if (dfs_pathfinder(grid, nextPos, goal, portals, path, reached)):
                    # If you reached goal, signalize to other levels of recursion
                    # that you found it.
                    return True
                else:
                    # If you're not, pop current position from path and try again
                    path.pop()

        # Didn't found goal. Giving up.
        return False

    # Steped on portal
    elif (char in portals):
        # Portals are unreachable. They teleport the character.
        #
        # However, we do append their position into path list.
        reached.pop()

        # Get the other end of the current portal
        other = enterPortal(portals[char], pos)

        # Get previous position, which will be used to calculate
        # which direction the character should face when stepping
        # outside of the portal exit
        prev = path[-1]
        
        # Check which position you came from
        diff = (prev[0] - pos[0], prev[1] - pos[1])

        # Get position you will face when exiting the portal
        # @ -> P ... O -> .
        # . <- O ... P <- @
        move = (-diff[0], -diff[1])

        # Calculate a hint of next position on other side of the portal
        nextPos = (other[0] + move[0], other[1] + move[1])

        # If the hint position is not reached yet:
        if (nextPos not in reached):
            path.append(pos)   # Stepped on portal
            path.append(other) # Stepped on other side of portal

            # Check if you're on the correct path to goal
            if (dfs_pathfinder(grid, nextPos, goal, portals, path, reached)):
                # You are. Signalize to other levels of recursion that you
                # found the goal.
                return True
            else:
                path.pop() # pop other side of portal
                path.pop() # pop current portal
                # You're wrong. Try again.

        # Didn't found goal. Giving Up.
        return False

    # Reached goal
    elif (char == '*'):
        path.append(pos) # Append goal to path.

        # Signalize to other levels of recursion that you found goal.
        return True

    # Cannot reach goal anymore. You are on a non-walkable tile.
    else:
        # Giving Up.
        return False

if __name__ == '__main__':
    # Step 1: Extract data
    grid, pos, goal, portals = handle_input('file.txt')

    # Step 2: Call Pathfinder
    path = []
    if (dfs_pathfinder(grid, pos, goal, portals, path, [])):
        print("A Path was found: ", path)
    else:
        print("No Path was found. Task is impossible.")

    # Step 3: Show the path inside the grid using counters
    k = 0
    for pos in path:
        grid[pos[0]][pos[1]] = str(k)
        k += 1

    # Step 4: Print the grid and the path the character must
    # go through to reach the goal
    print()
    grid = transpose(grid)
    gout = ''
    for j in range(len(grid[0])):
        for i in range(len(grid)):
            gout += ((' ' + get(grid, (i, j)) + '  ') if (len(get(grid, (i, j))) == 1) else (' ' + get(grid, (i, j)) + ' '))
        gout += 'n'
    print('The Grid: ')
    print(gout)
    print()

The script gets input from a file. In this case, file.txt, which contents are:

7
# # * # # # # # #
. . . . T . . . .
# # # # # # # # .
. . . T . . . . .
Q . . . . # # # #
. . . . . Q . . .
. . . # # # . . .
5 1

After testing the script, I got this output:

A Path was found:  [(5, 1), (4, 1), (3, 1), (3, 2), (4, 2), (5, 2), (5, 3), (4, 3), (4, 4), (3, 4), (3, 3), (1, 4), (1, 3), (1, 2), (0, 2)]

The Grid:
 #   #   14  #   #   #   #   #   #
 .   .   13  12  11  .   .   .   .
 #   #   #   #   #   #   #   #   .
 .   2   3   10  9   .   .   .   .
 Q   1   4   7   8   #   #   #   #
 .   0   5   6   .   Q   .   .   .
 .   .   .   #   #   #   .   .   .

The starting position is at 0 position, and 14 is the goal. The tiles 10 and 11 are both ends of the portal T, which tells that the algorithm used the portal T to reach the goal.

User contributions licensed under: CC BY-SA
1 People found this is helpful
Advertisement