Check out A* Pathfinding. It’s really simple to set up (Here’s a good tutorial). At the most basic level, it works like this:
Your enemy moves in a sequence of ‘steps’, where it moves to an an adjacent tile. Each tile you can ‘step into’ has a cost, and your enemy picks the one with the lowest cost to move into.
Each tile’s cost is the sum of 2 things:
-The cost to move into that tile (the tile cost)
-The estimated cost (called the heuristic) between that tile and the destination
Looking at the 8 tiles around you (4 if no diagonal movement), calculate the total cost for each, and move there.
The Tile Cost:
This is the simplest part of the cost, and the one that you will likely modify the most in your game. Obstacles will have a cost of infinity. Alternatively, you can simply check if it’s an obstacle and not evaluate cost, since you know you cannot move there. Other tiles will generally have a cost that is inherent to the tile. Walking on road tiles might cost less than walking on grass tiles, so your pathfinder will prefer to take the roads unless the grass is a big shortcut.
A very common part of the tile cost is simply distance. Moving horizontally or vertically is only 1 tile away, but diagonal moves might work better with a distance cost of 1.41 (sqrt 2). This will accurately weigh each tile with its distance, so your pathfinder won’t zigzag as much. Keep in mind that this is only to account for diagonal moves. Your pathfinder should only ever move 1 tile each step, and this cost does not account for tiles farther away than this.
The Heuristic:
This is the real meat of the algorithm, but in most cases its still very simple. The Heuristic represents the cost of moving from that tile to the goal. Ideally, calculating this doesn’t require any extra searching, and can be done just with the position of the tile and the position of the goal. This is just Euclidean distance, the square root of the sum of the squares. If your pathfinder can only move horizontally and vertically, you can use the (even faster) Manhattan distance, which is just the sum of the absolute values of the differences in X and Y. Other heuristics exist, but are a bit slower to calculate. These include summing the costs along the line to the goal, etc. You might be able to get away with these if you do it in a background thread in a turn-based game. Generally its not worth it, and if you want the most realistic pathfinding out there, there are better algorithms. A* is great for games though, and it’s very predictable.
Tiebreakers and backtracking:
Sometimes, two tiles might seem equally good choices. In this case, there’s not much to do other than to just pick one. This can be done either just as an inherent part of your loop (do you replace on < or <=), or can be chosen randomly. The random one is a bit less predictable, and can appear more interesting, however it also loses determinism. Two exact copies of the environment might be navigated differently. Additionally, sometimes these tiles are close together, or the pathfinder might want to loop back on itself and keep moving between the same few tiles. The solution to this problem is simply to add a cost to a tile that corresponds to whether or not you crossed it recently. Now, the pathfinder will prefer to take a contiguous path rather than double back on itself or flicker between options.
Putting it all together:
Consider your enemy having a speed that represents how many steps it can take in a given time (turn, second, whichever. I’m going to be using a turn-based example, it’s pretty similar for realtime). Each turn, your enemy finds the cost of all the tiles it can move into, then chooses the best one and moves there. Then, if it still has steps to do, it does it again. And again. This continues until the enemy has either reached its goal (the player), or the maximum number of steps it can take that turn (its speed).
The A* algorithm isn’t the most accurate in existence, but its really fast and it works quite well for stuff like this. It’s also a lot of fun to mess with the costs to create interesting effects. A ranged enemy, for instance, might actually cost more to get too close to the player (of course this results in the enemy ‘orbiting’, so you might want to avoid that too, unless you want it).