One of my earlier projects involved the development of a pathfinding algorithm for NPCs in games. The project was aimed to overcome the unfairness of NPCs in games, the unfairness of them knowing everything about the environment and you (the player) having to explore.
So I took a well known pathfinding algorithm (A*) and combined it with a mapping technique uses in mobile robotics (Occupancy Grids). The end results is a NPC that knows nothing about the environment and has to plot paths in unknown areas of the map, then update its path as the NPC reveals more of the map.
It’s a little like a fog of war, except this is a genuine fog of war, not pretend.
I produced a conference paper on this, I will release it here soon.