4 ms·
It never checks the target is actually reachable, meaning it just keeps going if you make reaching it impossible.
by TazeTSchnitzel 11y ago
It never checks the target is actually reachable, meaning it just keeps going if you make reaching it impossible.
- Buttons840 11y agoHow can you tell if the target is reachable other than finding a path?
- TazeTSchnitzel 11y agoCheck if either the source or destination are completely enclosed.
- kevan 11y agoUntil the algorithm runs out of nodes to explore it can't know that the destination is unreachable. Checking if a node is enclosed is determining if its graph is disjoint from the graph that the other node is on. The only way to prove the graphs are disjoint is to explore every node in the graph.
- jankassens 11y agoIn this case it's enough to set the algorithm to "bi-directional". If one side is enclosed it will stop. This only breaks if both disjoint parts are infinite (for example, an infinite wall between start and end.
- TheLoneWolfling 11y agoYou preprocess the grid into connected components, marking every grid cell with the CC it is in. Then before pathfinding check that the start and end are in the same component. This is an O(1) check, albeit with a potential of O(n log n) space required for storing the array of CC lookups.
- TheLoneWolfling 11y agoWhoops, make that an O(log n) check, technically speaking, as the index of which CC a cell belongs to may take O(log n) space worst-case. Though you can treat it as effectively O(1) time and O(n) space.
- zefei 11y agoI think checking whether target is reachable has the same complexity as reaching it
- TheLoneWolfling 11y agoNot really. Or rather, yes, sort of, but you only need to do it once (or once per update on a changing grid): You find the connected components of the grid. This is easy (loop over the entire grid. Any grid cell that has not been assigned a CC, assign the first free CC and floodfill from there.) Then to check if a is reachable from b, just check that a and b are in the same connected component. This is O(1) time (albeit with O(n log n) worst case spacial complexity for the CC structure required). The problem with the naive version of this is that updates can, in the worst case, require a scan and update of arbitrarily close to the full grid. There are better versions for when updates are frequent, but they take longer to query (although still sublinear time!) and are substantially more complex.
- ajuc 11y agoFlood fill is the hard part - A* is basicaly flood fill too, just with heuristic and quick stop condition. Preprocessing is cheating :). If you preprocess and floodfill the map anyway, you can go one step further, do Dijkstra, save the results using a trick, and you don't need run-time pathfinding at all. And you can store full paths from each cell to each cell using just O(N * N) memory, no matter the path lengths - that's a neat trick BTW: you store for each cell pair (P,Q) what is the next cell you should go from P if you want to eventually get to Q. that allows yu to reconstruct full path between each pair of cells quickly. EDIT to clarify - cheating is good, it's just I don't think O(N log N) is good tradeoff for the ability to return quicker, if you can do away with the whole pathfinding for O(N * N). EDIT 2: why O(N log N)? It seems you could write the resulting component for each cell, so worst case O(N) space?
- TheLoneWolfling 11y agoWhy O(n log n) space? Because you require O(n) connected components in the worst case, which means that you need O(log n) space per cell in the worst case. Although now that I think about it that pushes the amount of time to O(log n). In practice you can treat it as O(1) time and O(n) space, though. Also, that preprocessing with result saving is substantially slower than the connectivity alone. The connectivity alone is O(n) / O(n log n) preprocessing time - you check each cell a maximum of 5 / 9 times (depending on 4 or 8 way connectivity). Also, that preprocessing with result saving fails miserably when you do updates to the graph.
- nacs 11y agoThat's because it's meant to illustrate how each pathfinding algorithm/heuristic works and their search scope, not to do project-specific pathing.