[bug] A* pathfinding will sometimes go through diagonal wall

[clay-arras]

description: in certain scenarios, the A* pathfinding algorithm incorrectly suggests traveling through a diagonal where walls meet e.g:

##_
__#
__#

in this layout, the pathfinding algorithm will propose an invalid route that effectively crosses the blocked diagonal.

criteria:

• the A* algorithm must only produce routes that are physically navigable by the robot.
• diagonal or corner passages should be skipped.

notes:

• the A* pathfinding algorithm is in util/astar_search.py
• I implemented it based off of this video: https://www.youtube.com/watch?v=i0x5fj4PqP4
• I'm guessing it has to do with this section of the code (line 155), maybe you can check if the diagonal is blocked by walls before saying its a valid path, not sure though

    dirs = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
    while len(to_search):
        last_dist, (x, y) = heapq.heappop(to_search)
        if last_dist > dist[(x, y)]:
            continue

        for dir in dirs:
            nx, ny = x + dir[0], y + dir[1]
            edge = 10 if dir[0] * dir[1] == 0 else 14

[clay-arras]

Ansh