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:

">