Pathfinder + Fog of War

[Hvilela]

I would like to understand how you guys deal with the portion of the map data that the user do not know yet or is outside his view (fog of war) to calculate paths.
I'm thinking to to the most simple approach, the unknown tiles are considered blocked so they can't even be selected as goal.

Are you guys using a more clever idea?

[Leaf]

I think you may have to make the pathfinder consider the fogged areas impassable too, otherwise the player could use it to find cheat paths to areas that seem inaccessable. :3

[Omnomnom]

I haven't done/tested this yet so this is just my plan, but hopefully it will help to share the idea.

You can't calculate a path directly to the target tile with the information the player has, but you can calculate a path to a known passable nearby tile. As you get closer to that tile and reveal more map you will hopefully be able to calculate a new path to an even closer tile and finally the target tile itself will come into view and you'll be able to calculate a path to it directly.

The trick is deciding which tile nearer the target to use as a temporary target each turn. It isn't as simple as the nearest tile. The distance from the player matters too.

I think it involves minimizing this:
Cost of moving to temporary target tile + Estimated cost of moving from temporary target tile to actual target tile.

Unfortunately the second term is hard to estimate, not just because it involves picking some heuristic for the cost of crossing unseen tiles, but also because there can be patches of known tiles on the route requiring breaking out into proper path finding. The whole thing scared me off.

What I do instead is use the autoexplore method mentioned here:
http://roguebasin.roguelikedevelopment.org/index.php/The_Incredible_Power_of_Dijkstra_Maps
See section 2) Autoexplore

Use the target tile as the only goal and radiate out the echo/Dijkstra Map from there, treating each unseen tile as passable. Then from the player tile take the route towards the source. When new map info is revealed recalculate the map. Effectively this does the "hard" cost estimation mentioned above for free.

The downside is that it calculates a path to the target from lots of tiles on the map when we really only want the path from the player, so it's a little inefficient. Still it should make reasonably good intuitive guesses about where the closest path will be and if it finds it's a dead end it'll try another route.

I plan to add some constraints anyway like if the target is too far into unseen territory then don't allow it to be selected as a goal.

[wire_hall_medic]

I prefer a time-based system (nicely described on the DoomRL wiki), so for PCs it isn't an issue.  However, for NPCs, they get to use the whole map, as they should know the area.  The times I have done D&D style turns (a move distance and an attack), I've let the PCs use a whole map; never really bothered me.