What’s most important in the game is the user. You want the user to have fun! You don’t want him (or her) to feel like the computer is cheating, or that the game units aren’t behaving properly.
Dumb movement#
If the pathfinding doesn’t work well, the user will end up moving the units manually. Avoid this! In Civilization, the rules for the game allowed for zero-cost movement along railroads. However, the pathfinder had a non-zero movement cost. The result was that users avoided using the pathfinder, and instead moved units manually on the railroads. In Command and Conquer, units could get stuck in “U” shaped traps so users would have to guide the units manually. A dumb pathfinder will annoy your users and make them move units themselves, so make your pathfinder decent!
Smart movement#
Making units too smart is almost as bad as making units too dumb. If the player has to deal with fog of war but the pathfinder has access to the entire map, the units will mysteriously know where to go even though the user does not. That’s a clear sign to the user that something odd is going on. On the other hand, it gives better paths. A compromise is to scale up the movement costs on unexplored areas. For example, if your normal movement costs are 1 for grass, 3 for forest, and 7 for mountains, set them differently on unexplored areas: 5 for grass, 6 for forest, 7 for mountains. The unit will take mountains vs. grass into account, but not too much; it’ll be a subtle hint. Raising costs for moving through unexplored areas will also tend to make the unit stay in explored territory as much as possible. You might want to do the opposite for “scout” units: they should prefer unexplored areas.
Try to keep your units balanced between too dumb and too smart. The goal should be to make it match what the user might have done to move the unit around.
Multithreading#
You can use multithreading to improve the user experience. When a unit needs a path, allow it to start moving in a straight line towards the goal, and add a request to a pathfinding queue. In another (low priority) thread, pull requests off the queue and find paths. Your units will start moving immediately, so the user won’t be left wondering if something is wrong, and you won’t have a high CPU load (which will slow down the rest of the game) while the path is being calculated.
Multiple units#
If your game allows multiple units in a group to move together, try to make the movement look interesting. You can find a single path for them all to follow, and then have them all follow the path individually, but this will lead to either a line of units or units trying to pass each other. Instead, vary the paths a little so that they can walk in parallel. Alternatively, pick one “leader” unit to move along the path and have the other units use a separately programmed “follow” behavior. This following could be as simple as moving towards the leader but stay some distance away, or it could be as involved as flocking[1].
Multiple waypoints#
Even given the optimal path, the player may prefer a different path. You may allow the player to mark waypoints on the path: instead of simply clicking on a destination, the player would click on two or three points along the way to the destination. (Many real-time strategy games use shift-click for this operation.) You now have three or four smaller paths to compute, and you save some time. The player also has some control over the overall path—for example, your pathfinder may have found a path to the west of some mountains, but for safety’s sake, the player wants to stay to the east of the mountains (near friendly guard towers).
The main change in unit movement code will be that instead of a single destination, you will have a list of destinations. Find a path to the first destination. Once you get there, remove it from the list and find a path to the next destination. This reduces latency and improves throughput as well.