Dont know how to fix A* pathfinding algorithm

Question

I'm trying the A* outline from GeeksforGeeks. I followed most of the steps in the grey box until I hit a roadblock on dii and diii. Here is the section of the pathfinding:

def pathfind(grid):
    sx, sy = 0, 0
    # find start point and end point cood
    for y in range(len(grid)):
        for x in range(len(grid[y])):
            if grid[y][x] == "S":
                sx = x
                sy = y
            elif grid[y][x] == "E":
                ex = x
                ey = y

    opensq = []
    closedsq = []
    successor = []

    #add starting point to closed
    opensq.append([sx, sy, gcost(sx, sy, sx, sy), hcost(sx, sy, ex, ey)])
    grid[sy][sx] = "O"

    while opensq:
        # find the node with lowest fcost
        q = opensq[0]
        if len(opensq) == 1:
            pass
        else:
            for sq in range(len(opensq)):
                if sq == len(opensq) - 1:
                    pass
                else:
                    if q[2] + q[3] < opensq[sq + 1][2] + opensq[sq + 1][3]:
                        pass
                    elif q[2] + q[3] == opensq[sq + 1][2] + opensq[sq + 1][3]:
                        # if f is same, check hcost
                        if q[3] < opensq[sq + 1][3]:
                            pass
                        elif q[3] == opensq[sq + 1][3]:
                            pass
                        else:
                            q = opensq[sq + 1]
                    else:
                        q = opensq[sq + 1]
        opensq.pop(opensq.index(q))
        # pick successors to q
        successors = []
        successors.append([q[0] + 1, q[1], gcost(q[0] + 1, q[1], sx, sy), hcost(q[0] + 1, q[1], ex, ey)])
        successors.append([q[0] - 1, q[1], gcost(q[0] - 1, q[1], sx, sy), hcost(q[0] - 1, q[1], ex, ey)])
        successors.append([q[0], q[1] + 1, gcost(q[0], q[1] + 1, sx, sy), hcost(q[0], q[1] + 1, ex, ey)])
        successors.append([q[0], q[1] - 1, gcost(q[0], q[1] - 1, sx, sy), hcost(q[0], q[1] - 1, ex, ey)])
        for s in successors:
        #     if successor is the goal, stop search
            if s[0] == ex and s[1] == ey:
                pass
#            if a node with the same position as
#            successor is in the OPEN list which has a
#            lower f than successor, skip this successor
            for sq in opensq:
                if sq[2] + sq[3] < s[2] + s[3]:
                    successors.pop(successors.index(s))
            # if a node with the same position as
            # successor  is in the CLOSED list which has
            # a lower f than successor, skip this successor
            # otherwise, add  the node to the open list
            for sq in closedsq:
                if sq[2] + sq[3] < s[2] + s[3]:
                    successors.pop(successors.index(s))
        for s in successors:
            opensq.append(s)
            grid[s[1]][s[0]] = "O"
        closedsq.append(q)
        grid[q[1]][q[0]] = "C"

sx and sy being start point and ex ey being endpoint. I used letters to determine if a node is open or closed or start or end, with their first letter. This error pops up when I run it:

Traceback (most recent call last):
  File "D:/Bruh/Desktop/Codes and Scripts/AI/A_Pathfinding/Code.py", line 287, in <module>
    main()
  File "D:/Bruh/Desktop/Codes and Scripts/AI/A_Pathfinding/Code.py", line 274, in main
    pathfind(grid)
  File "D:/Bruh/Desktop/Codes and Scripts/AI/A_Pathfinding/Code.py", line 98, in pathfind
    successors.pop(successors.index(s))
ValueError: [5, 12, 3, 14] is not in list

here is the whole script, I used pygame for the visualization but just focus on the pathfind method, it currently kinda works but 1. the closed nodes become open nodes again after each loop for some reason and 2. it will get stuck in a loop if I skip the successor when it faces a wall. https://pastebin.com/yZfcPkq8

edit: finally finished the code! I'll put it up there, the only problem being that..I dont know hwo to show the path.. https://pastebin.com/EYSxFzpe

Answer 1

The error occurs in the following part:

for s in successors:
    if s[0] == ex and s[1] == ey:
        pass

    for sq in opensq:
        if sq[2] + sq[3] < s[2] + s[3]:
            successors.pop(successors.index(s))  # line 1

    for sq in closedsq:
        if sq[2] + sq[3] < s[2] + s[3]:
            successors.pop(successors.index(s))  # line 2

On "line 1" and "line 2", successors.index(s) can be called after the s is already popped in the previous cycle in the for loop. Then, the error occurs.

And, more significantly, your code does not perform A* search algorithm properly. You should only check "a node with the same position as successor" as you commented on your code. You can try the following code instead of the part mentioned above to fix the problems.

# Iterate over a copy of the list,
# since we are popping elements in the original list.
for s in list(successors):
    if s[0] == ex and s[1] == ey:
        pass

    for sq in opensq + closedsq:
        if sq[0] == s[0] and sq[1] == s[1] and sq[2] + sq[3] <= s[2] + s[3]:
            successors.pop(successors.index(s))
            break

And still, the code above is not that neat. You can see that sq[3] == s[3] always holds on the if statement above since they are hcost for the same position. So, you can just compare sq[2] to s[2], i.e. gcost. (In other words, since sq[3] == s[3] holds, you can just do sq[2] <= s[2] instead of sq[2] + sq[3] <= s[2] + s[3] on the if statement above.) I think the A* search algorithm described in the grey box on GeeksforGeeks is not that neat.

---

gcost is "the movement cost to move from the starting point to a given square on the grid, following the path generated to get there." So you should fix your code:

• Remove gcost function

• Fix the lines gcost used to

opensq.append([sx, sy, 0, hcost(sx, sy, ex, ey)])

successors.append([q[0] + 1, q[1], q[2] + 1, hcost(q[0] + 1, q[1], ex, ey)])

successors.append([q[0] - 1, q[1], q[2] + 1, hcost(q[0] - 1, q[1], ex, ey)])

successors.append([q[0], q[1] + 1, q[2] + 1, hcost(q[0], q[1] + 1, ex, ey)])

successors.append([q[0], q[1] - 1, q[2] + 1, hcost(q[0], q[1] - 1, ex, ey)])

---

With the fixes above, it seems your code works. But I think you can still improve your code. One thing we can imporve is separating the node and the gcost of the node. Now opensq in your code is saving the node coordinate and gcost together, and a node can be added to opensq more than once if the calculated gcost's are different.

You can also refer A* pseudocode on Wikipedia. I think it is more neat and clean than on GeeksForGeeks which you already referred.

For the closed list, you can refer the "Remark" after the pseudocode on Wikipedia:

Remark: In this pseudocode, if a node is reached by one path, removed from openSet, and subsequently reached by a cheaper path, it will be added to openSet again. This is essential to guarantee that the path returned is optimal if the heuristic function is admissible but not consistent. If the heuristic is consistent, when a node is removed from openSet the path to it is guaranteed to be optimal so the test ‘tentative_gScore < gScore[neighbor]’ will always fail if the node is reached again.

The closed list on GeeksForGeeks is really closed only if the heuristic function is consistent.