Re:PathFinding.js
by TheLoneWolfling on Thursday May 28, 2015 @01:21AM
(#9616198)
You 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.
[ Parent
| on HN ]
Re:PathFinding.js
by TheLoneWolfling on Thursday May 28, 2015 @01:31PM
(#9619697)
Whoops, 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.