AI, Pathfinding - Searching Behavior

Question

I'm developing a top-down 2D game mostly based off a tilemap/grid. The player will be able to build structures on this grid while other objects like vehicles will move around freely. I've been working on the AI for awhile and have struggled with coming up with a searching method.

The basic behavior I'm looking for is that of a dog barking at someone inside a house. When the person inside runs to the left out of view, the dog will run left and could very well run around the whole house trying to reach/see the person.

Standard pathfinding algorithms look for shortest paths or near shortest paths. But the behavior I'm looking for is more dynamic and isn't about finding a path as much as searching for a way in.

The example I'm working with currently, as seen below, depicts a zombie that has sight of a player inside a building through a window. The player then moves to the right out of view. The desired effect would be that the zombie runs to the right and all the way around the building until finding the player again or giving up. Note that I don't want the zombie to go left and in through the door (which would be the shortest path) to reach the player.

I've fiddled with ideas about using steering behavior, weighted tiles based on distance, wall-following, etc. and nothing has really made sense yet. I'm looking for any thoughts on ways to go about this kind of behavior driven searching.

Answer 1

Complete vs. incomplete information

What you are looking to do is path finding without complete information. The conceptually sound way to do this would require you to keep track of all of your non-playing character's information state (i.e., the parts of the map they already have discovered).

Local information

A more workable solution in your case might be to have complete information path finding (as you do now) for human-like enemies, and use local information (a type of incomplete information) to perform path finding for creatures of lower intelligence.

You could do this, for example, by only considering obstacles within 5 tiles of the creature and assuming all other tiles are passable. Your example above would like this to the path finding algorithm:

Because every NPC has to re-path anyway when it finds it is executing an invalid path this should result in the behavior you are looking for. So when the zombie realizes at the top right corner there's a wall in its path you'll feed this new bit of local information to the algorithm:

Oscillation

Looking at that last picture I realize this might lead to oscillatory behaviour, as re-pathing in general may do. This can be resolved by keeping track of where the NPC has been and assign those tiles a higher weight when re-pathing.

Specifically for the solution suggested in this answer, you could also:

• have the creature keep track of one or more earlier path finding iterations' information states, or
• allow it local information around the path it has recently walked instead of only its current location.