Enemy Pathfinding

2:21pm, Sat 30th July, 2016
3382 Hits

Enemy Pathfinding

Update: Enemy Pathfinding
We've been trying to wrap up the Enemy AI so that we can break out the polish and fine-tune the user-experience. We can't quite remember the official name of this simple grid-based pathfinding technique, maybe someone can help me out with that. It's definitely not A*, or maybe a variation. Here's how we approached it:

1.) You identify free grids (green) and occupied grids (red). Occupied grids are grids occupied with assets like houses or illegal terrain like cliffs as shown in the pic.
2.) You identify your start grid and your destination grid (must be free) and work backwards from destination to start.
3.) You assign a value of 0 to the destination grid, then a value of 1 to all adjacent grids that aren't occupied and push them into an array to be checked later.
4.) You then check all adjacent grids to the grids in the check array, assigning to them a value of 2, etc.
5.) You keep going till you've exhausted all grids (no path found) or you encounter the start grid (path found).
6.) From the start grid you follow the path of grids with a value -1 of the current grid till you arrive at the grid with value 0 (destination grid).
7.) This will give you the shortest possible path between the start and destination grids (blue grids in the pic).

The technique has some constraints and there's still room for optimization but it works pretty well. In-game pathfinding operations are handled concurrently so the player doesn't experience any lag even while enemies are plotting complicated paths. When the enemies need to go somewhere (e.g. pick up an asset, call for help, etc), they make a pathfinding request and carry on doing whatever it was they were doing. When the request is ready and successful they enter a finite-state that guides them through the path. To make their behavior more realistic, should they encounter you while in this finite-state they'll still follow the path but face you and fire at you at the same time.

Add Comment

*Required Fields

Please enter the text you see in the image to the left into the space below:
*Characters are case-sensitive