[TheLoneWolfling]

Not 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]

Flood 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]

Why 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.

[ajuc]

But you can just write for each cell the index of component it belongs to. It can't belong to many, right?

So it is O(N) in space?

I'm not sure we're talking about the same thing. I mean space requirements for the results of preprocessing.

Preprocessign itself may require computing cluster for all I care.

[TheLoneWolfling]

> I'm not sure we're talking about the same thing.

We are.

> But you can just write for each cell the index of component it belongs to. It can't belong to many, right?

Right. Each cell belongs to 1 and only 1 connected component.

However, there can be O(n) connected components overall. Think of a grid of cells all blocked off from each other, for instance.

As such, storing which connected component a cell belongs to technically requires O(log n) space, worst-case. Which means have overall you have n cells each requiring O(log n) space, or O(n log n) space overall.

In practice you can treat this as effectively O(n), however.

[ajuc]

So you treat 1 integer as log n? That's very technical, but in that case OK.

[TheLoneWolfling]

Yes. Although, as I said, in practice you can treat the integer index as constant space.