Phantom repeat structure

Question

Phantom repeat structure

Navigation

#1 by (1 votes)

1

maze = """\
##############
#            #
#            #
#   ##########
#   #       X#
#   ## ####  #
#   #     ####
#            #
##############
"""
EMPTY, BLOCK, STEP, END ,WALL=" ", "*", ".", "X", "#"
UP, DOWN, LEFT, RIGHT = "˄", "˅", "<", ">"
north, south, east, west=0, 1, 2, 3
movem = {
    north: (lambda x,y:(x, y-1)),
    south: (lambda x,y:(x, y+1)),
    east : (lambda x,y:(x-1, y)),
    west : (lambda x,y:(x+1, y))
    }

def solve(maze, x, y, move):
    found = False
    if 0 <= x < len(maze[0]) and 0 <= y < len(maze):
        if maze[y][x] == EMPTY:
            maze[y][x] = BLOCK

            if (solve(maze, x+1, y, RIGHT) or solve(maze, x, y+1, DOWN) or
                solve(maze, x-1, y, LEFT) or solve(maze, x, y-1, UP)):
                maze[y][x] = move
                found = True

        elif maze[y][x] == END:
            found = True 

    return found


if __name__ == "__main__":

    maze = [[char for char in line] for line in maze.splitlines()]
    solve(maze, 1, 4, EMPTY)

    for line in maze:      
        print("".join(line))

I saw this code on the internet in an older version, and I decided to improve it a bit, and that was the result (this cost me several months), now I'm applying that same code in AStar (which is almost costing me a year) to find the minimum path, but I still do not understand one thing, how does the solver () function execute multiple times ?, since I do not see any repetition structure. It would be the "working together" of the boolean found condition with the condition if __name__ == "__main __" ?

site where I found the old code: [ link

python

asked by anonymous 12.04.2018 / 15:49

1 answer

How do I get the given 'distance' in JSON in this example? Getting value inserted in asp.Net text field

score 1 · Accepted Answer

This code searches for brute force in the maze. He always tries to go first to the right; if it is not possible he tries to go down, but to the left and finally to the top. (Note that this is exactly a clockwise rotation.)

This is a brute force because he will walk blindly through the maze until he finds his goal. Depending on where the target is, it will walk through the entire maze before finding it. Basically it will test all positions until you find the goal.

You said that you do not understand how the solve function runs more than once. Read carefully: It is called several times within itself, in this passage here:

if (solve(maze, x+1, y, RIGHT) or solve(maze, x, y+1, DOWN) or
    solve(maze, x-1, y, LEFT) or solve(maze, x, y-1, UP)):
    maze[y][x] = move
    found = True

Notice that the solve function called itself by passing new parameters. That's the way she does to move. Notice that on the first attempt it passes x+1, y , ie, it moves to the right column (so I said it tries to go first right). If this call returns False it tries again by passing x, y+1 (ie, down), if it does not go back it tries x-1, y (to the left) and if it does not, it tries last x, y-1 (up).

Calling a function within itself is a technique known as recursion.

# link

To turn this code into an A-star you need to create a heuristic function (this is usually the absolute distance between the current coordinate and the target), then you apply heuristics to all neighboring coordinates and call solve first to the coordinate that generated the smallest value in the heuristic.