Jump to content
  • Advertisement
sprotz

What is the most common pathfinding technique used?

Recommended Posts

What pathfinding technique is used for an enemy to find their way around when looking for the player, and also I'm curious... What pathfinding technique did Goldeneye 64 use when an enemy is alerted to the player's presence and begins to move through the level until they find the player?

Share this post


Link to post
Share on other sites
Advertisement

The one I most commonly hear people using some variation of A* which apparently has been around since 1968.

As far as goldeneye goes I don't think it is anything fancy but you're probably better off tracking down the devs and sending them a message if you really want to know.

Share this post


Link to post
Share on other sites

We have a good overview of commonly used techniques for game AI that briefly introduces a range of methods and what they're best used for.  It's a good read. :)

For actually finding paths through a level, the most common algorithm is A*.  The best guide I know to that is Amit Patel's Introduction to A* and the accompanying Implementation Guide.

For tracking an enemy, there are a range of techniques you could use. I recall one popular game had players regularly drop invisible "markers" that fade over time; AI could then path towards the nearest markers to pursue the player. A more sophisticated approach might involve the AI moving towards where the player was last detected and actually searching "hiding places" as they go.

I've no idea what specific techniques Goldeneye 64 might have used, but I don't remember it's AI being particularly impressive compared to other games, so likely nothing particularly special or novel.

 

Hope that helps to provide a starting point. :)

Share this post


Link to post
Share on other sites
7 hours ago, sprotz said:

enemy to find their way around when looking for the player

If you have many enemies and all look for the player, it could be faster to use just one Dijkstra shortest paths search from player to all enemies at once instead multiple A* searches from each enemy to the player.

(Dijkstra finds the shortest paths to ALL nodes in a graph. But it can terminate if all enemies have been found.)

On the other hand, in practice you may do only one search per frame for one enemy, as it is not necessary to update this very frequently, here A* becomes more attractive again.

 

 

Share this post


Link to post
Share on other sites

If the enemy doesn't know where the player is, this is a much more interesting problem. You can represent the agent's understanding of where the player might be as a probability distribution over the map. This probability distribution is updated whenever the enemy looks over some area and doesn't see the player (set the probability to the viewed area to 0 and rescale the rest so the total probability stays at 1), whenever some time elapses (making the probability distribution more diffuse), and whenever the player is spotted (accumulating the whole probability at that spot). You can then have the enemy simply go to the point with the highest probability, or perhaps the point from which the most probability would be visible.

I saw a video about a stealth game that makes the probability distribution visible to the player, but I can't find it now. Anyone?

 

Share this post


Link to post
Share on other sites
15 hours ago, alvaro said:

I saw a video about a stealth game that makes the probability distribution visible to the player, but I can't find it now. Anyone?

@alvaro The game you are thinking about is called "Third Eye Crime" (i may have just registered to tell you that :) )
I remember the developers mentioned that they were using visible occupancy maps as debug tools, and found them so fun that they decided to include them as a feature of the game.

Share this post


Link to post
Share on other sites

Yeah, that was based off of occupancy maps by Damian Isla. He thought it was so groovy that he and Christian Baekkelund made Third Eye Crime.

At about 11:40 of this, Damian shows off a demo of occupancy maps and describes how it is done. (His first 30 minutes of the lecture is about knowledge representation.)

https://gdcvault.com/play/1267/(307)-Beyond-Behavior-An-Introduction

Start at 30:30 of this for more about the design of the game, Third Eye Crime based on it:

https://gdcvault.com/play/1018057/From-the-Behavior-Up-When

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!