I've just been thinking about ways that pathfinding could be made more realistic, in theory. I havn't really thought out how to implement this, they are just ideas. Anyway, the main concept is that pathfinding, ideally, should replicate how real people pathfind. Given that real people can remember the way to lots of locations, it would be unrealistic for a game with lots of computer bots (like on an RPG such as Fable or Morrowind) to have each remember directions to the next city, to the post office, and to the tavern. So, instead, what I've been thinking about is, how would people navigate a map if they were dropped right into it? I've also been observing how people move out on the street in America (cultural tendencies change from country to country - in India, people are much less fussy about being close to each other, while in America we tend to walk on opposite sides of the sidewalk.) First, a basic overview of the ideal process as I see it: Real people, when they are exploring a new location, go by what they can see. So should bots; I think that when they navigate, their path should not be determined by a big overarching process, but by their individual sensory perceptions. Halo 2 is supposed to have used this in their pathfinding (I thought it was a great experiance). Also, assuming we know the general direction of our destination (like to the north of my present location), we move along a path that moves towards it, given no other information on its direction. If we entered an unknown house and wanted to exit through the back door, we would move through halls and rooms that pointed in that general direction, keeping faith that the back door is actually in the farthest wall from the front door; if that is false, then we start searching in another random direction. Given these, you can start to see the beginnings of how idela pathfinding should probably be, for the most realistic impression, anyway. Environmental factors come into play, as well. If a whitewater river blocks the road, then we try and find a way around it. Also, we would rather walk on a sidewalk than down the middle of a busy road. I suppose in a tile-based map, certain tiles could just be correlated to "road levels" which describe how good they are for foot travel. Also, maybe some tiles could be tagged as "water tiles", again with road levels representing the speed of the current, how deep it is, etc. The bots, like real people, will want to prefer in most cases to walk down the best available nearby road. Property is another issue. If you wanted to enter the alley across the street from you, you wouldn't walk through your neighbor's yard and through their garden, or through their house. These are private property, and you could be arrested. Also, if a military base forms a large detour, then a real person would go around it anyway. There might be something like a "tresspass level", correlated with either a group of characters (the house with the NPC "John Q. Smith", so that he wouldn't have a problem moving through it, but others would, and the base with "American Military", so that marines would enter and exit freely, but others wouldn't). Based on these two factors, the distance that would be saved by cutting through them (you wouldn't go three blocks down to find a crosswalk, unless you were physically disabled), and how much the character cares about cutting through them (bandits don't care if they are moving through someone else's home; they are raping the populace, dammit!), the general path should be fairly clear. Finally, the ideal impression comes down to details. In America, we tend to give others a wide buffer area; from observation, I noticed that people coming opposite directions tend to take opposite sides of the sidewalk, and people don't walk right behind someone else, out of courtesy. This is different in other cultures. Also, provided nothing blocks the path, we tend to stay away from the walls of buildings and the edge of the street. This would be another buffer area, which probably has less importance that giving others their "buffer space". When people walk, they tend to naturally form two streams, one going one way, and one going the other. NPCs should be able to form unfocused groups. Observe any high school. Periodically, they "circle up" and chat about stuff. This tends to happen before the group splits up. Some buffer distance should also be in effect to keep people from lagging behind their group. In real life, people will even walk on the edge of the street to keep in line with their buddies. Whew! Anyway, these are my initial thoughts on this subject which has been obsessing me for several days. I would love a reality check on this; and on other people's observations. Happy coding!

As far as I see it, your thoughts have being indirectly used in common path finding algorithms like A*. As follow:

You point that if a human want to move to a north location it first try to move in that direction or as near that direction as possible. If that path failed then it goes a bit back and tries another direction as similar as possible. That behavior is used by the A*, because as you know it heuristically expand the most promissing of the ways (The one that gets closer to the destination point) which in most situations is the one that follows the more similar direction.

About trying to not enter a military base or your neighbor backyard is easy but not covered by the standard A*. I implement it by using Cost Zones. They are shapes that add cost to a path when it passes through them. That way the A* will avoid processing that path until no other way is available.

You also point the way that people move: in opposite sides of the sidewalk, as far as possible from edge and walls, etc. All that is post path find tasks. Once the path has being found a filter is applied. That way is possible to smooth the path, make round turns, simulate human behavior, etc.

Either way; that’s just my point. I like to hear others as well.