4 ms·
> 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 larg
by munificent 7y ago
> 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.
- castratikron 7y agoDijkstra's is actually a special case of A-star where the heuristic is zero.
- setr 7y agoReally what you want is a flow field, since this is mainly a problem of many actors with a few shared goals: pathfinding can be computed once every turn and reused by everyone
- munificent 7y agoThe actors have to pathfind around each other, though, so I don't think you can easily reuse the pathfinding data.
- setr 7y agoyou're recomputing it every turn, so you can treat actors as obstacles; simply make tiles that are taken non-traversable (same as you'd make a boundary wall). When moving each actor, by flowing downwards, if they collide then undo the move and select the next best downward tile. In the case he's surrounded at the start of the turn, the flowfield will simply not allow him to move (he'll be surrounded by obstacles). If he's surrounded by newly moved actors, he'll bump into people in all directions, and not move. 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/continuum-crowds.pdf http://grail.cs.washington.edu/projects/crowd-flows/continuu... [1] http://www2.cs.uregina.ca/~anima/408/Notes/Crowds/HybridVectorFieldPathfinding.htm http://www2.cs.uregina.ca/~anima/408/Notes/Crowds/HybridVect...
- erikbern 7y agoI wrote the code and you're wrong :) 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!
- munificent 7y ago> A* doesn't work because the heuristic becomes pretty useless when you have moves that are very "cheap" 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.