I just finished that video and had much the same thought
The speed improvements he mentions are the result of stacking several different optimizations on top of each other. As he stated in the talk, the complete combination only applies when the map is static and you can pay the precomputation cost (10+ hours for a single 2D starcraft map; you could do that just before you ship the game but that's of no use for DF). Of course, there's no reason we can't look at the major pieces independently.
The JPS search strategy he mentions at 6:26 could very likely be used directly; you'd have to add so flags to each tile to hold the "forced neighbor" flags for each of the six cardinal directions. At 7:15 you can see the three types of forced neighbors you might have. When your search enters a node (the central ones in these three diagrams) from the west, you would normally only search the node to the east. In the first case you just passed a wall to the north so you have to search to the north and north-east so that you don't miss anything. Similarly for passing walls to the south, and for passing walls in both directions.
The goal-bounding stuff is heavily reliant on precomputation, but at 20:30 he makes a good suggestion. You can precompute the goal bounds only for certain nodes. He's got these nodes spaced out over the chokepoints of the map, but you could go even simpler just by spacing them out every 20 or 30 tiles, or along the 48x48 map tile boundaries or whatever. Most tiles would have no goal bound information, but eventually the search would hit a node that does have that information and it would be able to prune out a lot of the search space each time it did so.
Of course, he's also using at least one optimization that isn't mentioned in this talk, since it only applies to dynamic maps. It's a bit like goal bounds, except that he's eliminating nodes from the search that he knows are unreachable; if you wall off a room then pathing to the interior of the room will bail immediately, since the interior is in a different reachable subset than the exterior. This is a great boon when there's a sock in there, or an unfinished job, and you need to avoid paying for the pathing cost over and over. This can be combined with goal bounds; any time two of these subsets are joined (someone took down the wall, you broke into the caverns, etc) you just have to take a moment to compute the goal bounds for the tile that connects the two subsets. Actually, you'd probably want to compute a list of tiles just outside the surface of each subset, then compute the intersection of those lists. That intersection is all of the tiles which will be a bottleneck between the two subsets if they are later reconnected; any tile in this list should have goal bounds computed on it if it ever becomes passable. Or it might be good enough to just compute goal bounds for any tile which becomes passable and is adjacent to another tile with goal bounds; that'd certainly be simpler.
Anyway, this is a great talk, and while it's not all applicable to DF it does present many ideas which are adoptable.
Author
Topic: Pathfinding algorithm (Read 970 times)