1. Diagonal moves have a slightly higher weight. 2. I have an edge weight of 100 to go through another person. This makes it possible to go _towards_ the right direction even though there is no path 3. For the perpendicular lines method, the distance is modified to 1e-3 4. A* doesn't work because the heuristic becomes pretty useless when you have moves that are very "cheap": you need a lower bound that's pretty much zero
So for all those reasons, I just went with plain old Dijkstra!
I don't see where you have cheap moves. If your move costs are unit for straight lines, slightly longer for diagonal (i.e. probably close to sqrt(2)), and much longer for obstacle, then A* will work fine. The lower bound is just the usual Cartesian or Manhattan (depending on your diagonal cost) distance.
Assuming the crowd keeps moving, the problem will naturally resolve itself eventually (and the results are the same as if you'd done direct pathfinding -- a traffic jam is a traffic jam).
There's also the possibility an actor gets stuck holding the door: He's the last to move, so by the time he takes his turn, he's surrounded again; The gamey solution would be to cheat and let him phase through or temporarily merge with an actor.. alternatively increase his iteration priority if he doesn't get to move, so he gets the first move next turn.
But in the case of this simulation, such extreme crowding is an unnecessary edge-case to care about, since the goal really is to simulate to the point when crowding just starts to occur, so just "bump and undo" collision logic is probably more than sufficient.
If you want to go way too far, you end up with potential fields like [0] or [1] but I don't think a buffet line really necessitates that level of intelligent behavior
[0] http://grail.cs.washington.edu/projects/crowd-flows/continuu... [1] http://www2.cs.uregina.ca/~anima/408/Notes/Crowds/HybridVect...
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.