I was wondering what kind of technologies were used in FPS games to move bots around the level. I know the pathfinding is done using waypoints or navigation meshes but how do the bots actually rotate and move over those paths? Is something like opensteer used for that, if so, which particular parts?


1 Answer 1


(Optional) The navigation mesh approach is just an extension of the waypoints approach, that allows "wandering". In other words, you can use your navigation mesh to get back to a waypoint graph, by taking the centroid of each polygon in the navigation mesh. (If you are pre-generating the navigation mesh, you can just store the original source points; this way you don't have to recalculate the centroids later).

(Mandatory) Now once you have nothing but a waypoint graph, you need to do a search for the shortest path between A and Z. A is where the entity in question is; it wants to know how to fulfill some goal, and that goal generally has a physical location associated with it, which is Z. Now apply something like the A* algorithm for shortest-path search, to that waypoint graph. The output will be a single linear list of nodes indicating the shortest path to your destination, {A..Z}. Now move your entity: This should be a simple matter of moving your entity along a straight line betwen A->B, B->C etc. to Z. Each time you reach another node in the path, fire off an event (or whatever) and then start moving to the next one until Z is reached.

Rotation? Well just like in real life, you turn around to face where you're going, don't you? So have the entity rotate before she heads off toward the next node. You can even begin her moving slowly at first while she's rotating, to look more fluid.

  • \$\begingroup\$ Interesting answer, however the rotation (the maths for example) is not entirely clear. The simple approach would be to move from point A to B, rotate and move from point B to C. Is there some math that could make this more smooth? Maybe the way a rounded corner is calculated when you draw a rectangle with rounded corners is related to this? \$\endgroup\$ Aug 31, 2011 at 17:59
  • 1
    \$\begingroup\$ When we turn corners in real life, it's obvious that we move linearly, then make a small semi-circular turn once we approach the corner, and then cease turning once we're on our new target vector. Draw it out, as you would perform it, and you'll see that it's a simple problem in geometry that is based on what the entity's minimum turn radius is while walking at a given speed -- just like turn vectors for aircraft. Then you just need to iterate over that in real-time. The actual math used for rotation of data in 3D space typically involves matrices and quaternions for rotation. \$\endgroup\$
    – Engineer
    Aug 31, 2011 at 18:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .