I was recently introduced to the A* algorithm when I asked a friend about making AI/NPC's in video games move to certain points and it sounded very interesting. I am building an FPS and it has AI that must be able to move to certain points, so the A* algorithm sounds very appealing to me.

However, as I went through the Half-Life 2: Episode 1 Developer Commentary, I found another solution that the workers at Valve have been using: a line system. I couldn't find a screenshot and alas, I couldn't find the developer node to show the system. :(

Basically, there's a whole system drawn on the level map for AI to move along. If there happens to be an enemy that shows up in a certain section that might not be on the AI's line of sight, then the AI can break out of the line and attack said enemy.

I'm building the game in C# (XNA) and I wanted to know if it would be better to use the algorithm, the line system or even both to achieve pathfinding?

  • 2
    \$\begingroup\$ I can't see the picture but assuming you're talking about a system of waypoints and connections throughout the map, that works with A*; it's not an alternative to it. The waypoints and connections provide the graph that you do A* on. (You can also do A* on a grid, if you don't have a graph of waypoints.) \$\endgroup\$ Jun 28 '14 at 2:52
  • \$\begingroup\$ Yeah, I couldn't find a screenshot. :/ However, I don't really know if it uses waypoints. Maybe they do use the A* algorithm to help show how to get to a certain point, but I'm not really sure. :/ \$\endgroup\$
    – Gumptastic
    Jun 28 '14 at 3:01
  • \$\begingroup\$ For really large traveling waypoints and routing based on those makes it faster to get over there. And then you can do more local based planning for a region your in for pickups attacking etc. \$\endgroup\$ Jun 28 '14 at 6:04
  • \$\begingroup\$ A* is good at finding fastest path form A to B but FPS games the exact fastest path is not the highest objective. A* also has to be calculated for each step in a plan (when things change) so for 10+ bots A* all the time would cost to much CPU. \$\endgroup\$ Jun 28 '14 at 6:09

I think what Valve does is using a Navigation Mesh (source) together with a Visibility Graph. The navigation mesh covers all of the walkable space in (usually) convex regions. A* or Dijkstra's is used to plan paths between regions, while local movement techniques are used for moving agents inside regions. (This is very easy since regions are convex you can reach any place inside a region by following a straight line towards it).

The Visibility Graph models line-of-sight information, and is an alternative subdivision of the walkable space (from where in one region one can see someone in another region). The data from the Visibility Graph can be used to give the agent goals. Like: "find line of sight on an opponent" or "stay out of sight".

Navigation, especially in 3D environments, is a complex problem. Actually I'm writing my thesis on this very subject, comparing all these kinds of techniques.

Here are some links that you can use for ideas:


You must log in to answer this question.

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