Jump to content
  • Advertisement
Sign in to follow this  
josh1billion

Executing a pathfinding algorithm in real-time in a 3D game

This topic is 3308 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have implemented the A* (A-star) pathfinding algorithm in my game. Now I face the problem of knowing when to deploy it most effectively. Here's the basic flow of my gameplay: It's a stealth game similar to Metal Gear Solid. The player tries to sneak past the enemy guards without crossing their line of sight. If a guard "sees" the player, he will chase the player; upon finally colliding with the player, the player will be required to restart the level. I have my code written, tested, and working to generate the path from "guard to player" properly and have the guard run along that path. All is well, but my question is this: when is the best time to call that path generation code, and how frequently should the path be updated (re-calling that path generation code)? Here's how I have it set up now. I'm using multithreading (without multithreading, the game takes a several hundred millisecond pause each time a path is generated-- not acceptable at all, obviously). All game logic occurs in the main thread, except for the path generation. I have a threaded function (called regularly by Windows's thread handler) which checks to see whether any guards "want" a path to be generated for them. If yes, the guard has his path generated and he is checked off as no longer wanting a new path (i.e., he is taken out of that "please generate my path for me" queue of guards). After that, the guard will re-insert himself into that queue every X milliseconds (currently set as 100 milliseconds). Note: I set the pathfinding priority to "below normal" (THREAD_PRIORITY_BELOW_NORMAL) and this is giving me the best results so far. Anything higher slows the framerate noticeably (even though I'm testing on a dual-core 2.5ghz CPU), while anything lower makes the pathfinding look more jittery than it already does. This configuration is generally working, but it looks very bad at times, and that's why I'm asking for advice on when/where would be the best time/place (and how frequently) to generate paths. Sometimes, as you can see in the videos below, the pathfinding sometimes look smooth and seamless, while other times the guards will freeze their movement briefly mid-path as they're recalculating their paths: Smooth:
">
Jittery:
">

Share this post


Link to post
Share on other sites
Advertisement
So #1, your pathfinding shouldn't be taking 100ms, I think 1-3ms is standard acceptable performance in an FPS (but I might be mis-remembering). So I'd optimize your code to start (use a profiler to tell you why). Are you using a memory pooled binary heap for the open list, are you using memory pools for your generated paths so they don't require allocation, are you a candidate for hierarchical A*, etc?

Re-planning a path every 100ms should be fine, you may just need to update your pathfollowing code so that it gently steers the bot onto the new path, rather than about facing and snapping to it. Since your logic is asynchronous currently your bot is probably overshooting the start node by the time the new path returns. So you perhaps need to also account for that: "where I originally started my search may not be where I am now".

-me

Share this post


Link to post
Share on other sites
Looking at your second video there. Why does the AI agent stop? Is he at the end of his path? If so, why are you creating such short paths? If he isnt, why hasn't he continued along his previous path while the new path is being calculated?

Also, if he is currently waiting on a path to be calculated, he could easily just run towards the player with some basic obstacle avoidance. I would suggest using the pathfinding only to get the agent in close proximity of the player, such as in the same room. But once he's in the same room, and or has direct line of sight, he should just be using pathless navigation to reach the player.

At no point should the agent be waiting on data and standing still. He should either be heading towards the player, on the previous path, or on the newest path, with some kind of blending between transitions.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

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

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!