> Writing the simulation in Python was probably a bad idea in retrospect: it turns out to be incredibly slow to run Dijkstra’s shortest path algorithm on a large grid.
Dijkstra's algorithm is the completely wrong approach for this problem. First of all, the cost to enter any grid square is the same, so Dijkstra's priority queue is needless overhead. When all edges have the same weight Dijkstra's behaves identically to breadth-first search.
BFS is obviously a poor approach for a mostly open grid like you have here. It will explore every single open vertex whose distance is less than the distance to the goal. Imagine the person standing in the center of a circular room with the food at the edge. With DFS, the pathfinder will look at every single vertex in that room.
What you want is A-star, which is no harder to implement than Dijkstra's. Even better would be something like jump-point search that handles open spaces better. But just A-star alone will yield a massive improvement for problems like this.
Dijkstra's algorithm is the completely wrong approach for this problem. First of all, the cost to enter any grid square is the same, so Dijkstra's priority queue is needless overhead. When all edges have the same weight Dijkstra's behaves identically to breadth-first search.
BFS is obviously a poor approach for a mostly open grid like you have here. It will explore every single open vertex whose distance is less than the distance to the goal. Imagine the person standing in the center of a circular room with the food at the edge. With DFS, the pathfinder will look at every single vertex in that room.
What you want is A-star, which is no harder to implement than Dijkstra's. Even better would be something like jump-point search that handles open spaces better. But just A-star alone will yield a massive improvement for problems like this.