Original Post: My Old Blog

Introduction:

Basic pathfinding methods such as A* provide a method of getting the optimal and shortest path from point A to B. However, the shortest path is not always the path that an AI wants to use. A bit of manipulation will provide a much better approach to optimal pathfinding. The answer we are looking for lies in the implementation of Tactical Pathfinding.

What Genres/Platforms are This Technique Useful for?:

This method of pathfinding is useful for almost any AI implementation ever, except if you are trying to make the most unsophisticated AI possible. Mainly, First Person Shooter AI benefits the most from this technique, because you do not want AI-controlled soldiers to just wander around aimlessly and shoot at the player until they die. You want the AI to take cover, reload, and flee to reinforcements when they are outnumbered. Real Time Strategy games don’t really benefit from this tactic very much, because the player is grouping and moving the AI however they deem as best fit for their strategy. Fighting games benefit from tactics in general, but there isn’t much waypoint moving and pathfinding really involved.

Nodes and Waypoints:

Pathfinding algorithms such as A* require a graph of nodes in order to traverse a map. The way we can add to the depth of a node is creating Waypoints. A waypoint, in terms of tactical pathfinding, is a destination or area that provides a tactical advantage over an enemy or obstacle. A waypoint can be a single node or group of nodes, depending on the implementation. The waypoint class should include tactical information regarding how the waypoint provides a tactical advantage.

Examples of tactics or tactical advantages include, but are not limited to:

• Sniper alcoves/cliffs
• Hiding locations (Bushes, shelters, tench, etc.)
• Ammo supplies
• Home bases
• Ambush points
• Access to any forms of reinforcements
• Cheats (?)

Waypoints do not have to be limited to a single tactic, in fact, having multiple tactics in one waypoint give it more value. Below is a crude representation of how a basic map, with tactical waypoints, can be represented.

Depending on how you structure your units, different waypoints can be considered more favorable to different units. For example, if you have a class-based system for your units, you can have classes like sniper, heavy soldier, stealth soldier, etc. A sniper would much rather have a sniper spot or a far away location than a close-quarters cover spot, which would be more favorable to a cqc unit or heavy soldier. These values must be put into consideration in order to properly pathfinding to a favorable waypoint.

AI Needs and Player Needs:

There won’t always be a constant or static need for a tactic or a waypoint for certain units. A unit or player will not always have full ammo or health, or even stay the same class for that matter. These and other factors must contribute to the pathfinding process as well. you can create a basic decision tree to determine what the player or unit needs the most and that can determine the most favorable waypoint to reach. Below is another crude representation of the process I just explained.

Of course, your decision tree can be more or less in depth than this concept of a tree. The beauty of programming is that you can implement something any way you want.

Implementation of Waypoints:

There are two apporaches to coding in your waypoints into the game

1.Generating all waypoints before the game starts

-In most 2D and room-based environments, generating all of your waypoints initially is a good way to approach it, because it allows for less calculations during run time. However, this restricts the waypoints from adapating later on and the waypoints will stay relatively static to where they are.

2. Calculating waypoints and positions on the fly

-Having your waypoints be generated when necessary will allow faster initial load time for your game, but more calculations will be processed during the actual gameplay. This benefits 3D environments and randomly generated environments, because you can determine waypoints once the levels are being generated and when a situation is presented. If an enemy or obstacle is presented to an AI or group of AI, this will allow you to generate all nearby tactical advantages, generate the waypoints, and then determine how to pathfind to them.

Squad Tactics and Multi-Tiered AI:

Having all of your units pathfind to one waypoint is not efficient, especially if you have a bunch of throw-away units. It is best to split up your units to multiple waypoints to spread your units and prevent one attack from destroying your entire squad. This is a small thing to consider for most genres, because there typically is a point to keep your units together or apart anyways.

Sources:

http://www.seas.upenn.edu/~cis568/presentations/tactical-path-finding.pdf

http://www.cse.scu.edu/~tschwarz/COEN196_13/PPT/Tactical%20and%20Strategical%20AI.pdf

Millington, Ian, and John David Funge. Artificial Intelligence for Games. Burlington, MA: Morgan Kaufmann/Elsevier, 2009. Print.