Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

Zombie searching for the player after it moves

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.

share|improve this question

1 Answer 1

up vote 7 down vote accepted

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:

enter image description here

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:

enter image description here

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.
share|improve this answer
    
This is brilliant. Being able to adjust the local information of each NPC based on intelligence will also fit perfectly with what I had in mind. Tyvm –  Saliken Jul 22 at 16:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.