KeyError when pathfinding enough times

[Dan-megabyte]

Bug Description
I get a KeyError from the heap module when the a* pathfinding (haven't tried yet with other algorithms) repeats many times

To Reproduce

from pathfinding.core.grid import Grid
from pathfinding.finder.a_star import AStarFinder

import random

grid = []
with open("map.txt") as f:
    for line in f.readlines():
        row = []
        for char in line.strip():
            row.append(int(char))
        grid.append(row)
grid = Grid(matrix=grid)

def random_node(grid):
    return grid.node(random.randint(0, grid.width-1),
    random.randint(0, grid.height-1))
# initialize pathfinding
finder = AStarFinder()
runs_left = 500
print(f"starting {runs_left} runs")
while runs_left > 0:
    # redefine start points
    start = random_node(grid)
    while not start.walkable:
        start = random_node(grid)
    end = random_node(grid)
    while not end.walkable:
        end = random_node(grid)
    
    path, runs = finder.find_path(start, end, grid)
    runs_left -= 1

Expected behavior
No error, that the pathfinding just happens

Screenshots / Map / Log
Map: uploaded since it's 500x500
Log:

starting 500 runs
Traceback (most recent call last):
  File "/home/user/Documents/coding/extendedessay/bug.py", line 32, in <module>
    path, runs = finder.find_path(start, end, grid)
                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/usr/lib/python3.12/site-packages/pathfinding/finder/a_star.py", line 92, in find_path
    return super(AStarFinder, self).find_path(start, end, graph)
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/usr/lib/python3.12/site-packages/pathfinding/finder/finder.py", line 161, in find_path
    path = self.check_neighbors(start, end, grid, open_list)
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/usr/lib/python3.12/site-packages/pathfinding/finder/a_star.py", line 76, in check_neighbors
    self.process_node(
  File "/usr/lib/python3.12/site-packages/pathfinding/finder/finder.py", line 124, in process_node
    open_list.remove_node(node, old_f)
  File "/usr/lib/python3.12/site-packages/pathfinding/core/heap.py", line 87, in remove_node
    heap_order = self.heap_order[node_id]
                 ~~~~~~~~~~~~~~~^^^^^^^^^
KeyError: (399, 372)

Environment:

• Environment: Arch Linux
• Python version 3.12.5
• Pathfinding Version 1.0.10

Additional Info:
I have a working workaround which is to just edit the heap.py to ignore nonexistent keys, but it should be better just to assure that this case never happens

[andreyd41]

You should call grid.cleanup() after each iteration, otherwise find_path will not work correctly.

[brean]

Yes, @w9PcJLyb is right that grid.cleanup() at the end of your loop solves the issue however because your map does not change during the runs you might want to use some form of storage/caching instead for performance issues.
I think for now we should check the map at the beginning automatically if the algorithm has been run once, (mark it as "dirty" after the first run) and run "cleanup" automatically. And later look at a finder that could use some caching functionality.

[andreyd41]

I think for now we should check the map at the beginning automatically if the algorithm has been run once, (mark it as "dirty" after the first run) and run "cleanup" automatically

It's a good idea. Because without cleanup the behavior of find_path is very unpredictable:

• find_path can find an optimal solution
• find_path can find a solution that is close to optimal
• find_path may not find a solution at all, although a solution exists
• find_path may сrash

And user may not even notice that something is wrong, because the first three cases may look logical.