Path finding in Eternal Lands

In this post I will describe some investigations I did to try and improve the path finding code in the Eternal Lands game. This will actually be part of a two- (maybe three-) post series, introducing the algorithm used, and what I think the problems with the current implementation are. The other parts will look further into speeding up the code, and trying to improve the generated paths.

Some parts of this post may be a bit technical, but I have included them to be able to explain how certain problems with the path finder may arise, and how we can fix them.

Path finding in … what?

Eternal Lands. A 3D massively multiplayer online role playing game,¹Alright, “massively” may be a bit overstated in the case of EL, and sadly the role playing has gone down a bit over the years, but it is the best description I have 🙂 that I have been playing and coding for, for quite a few years now. No, I am not telling how many years, that will just make me feel old. The game is free to play, multi-platform, has a friendly community, and the client code is open source. Go ahead, install the game, and play for a bit. This post can wait a little while.

So what about path finding?

Path finding, in the context of this post, deals with trying to find a series of moves that brings the player’s in-game character from its current position to the position the player wants to move to. In the olden days, all path finding was done on the server only. Since path finding can be quite resource-intensive, and the server has to deal with other things as well (like, say, relaying text messages to the other players in my guild, or keeping track of who is fighting who, etc.), movement was restricted to a few tiles at a time. This model has later been replaced by a hybrid model where the client precomputes a path, and sends the individual moves to the server for verification. The server then only needs to check if the tile the player wants to move to is reachable and not occupied by another actor. This change allowed players to plan far longer walks, all across a game map if they want to, and moved most of computational cost of computing the paths to the clients.²There was a slight disadvantage (from a map designer’s perspective) as well which newer players may not appreciate: mazes on the game map lost most of their function, as the new path finder was able to simply plan a path through them.

The path finder code that is currently in the client is actually pretty good. It is fast, clear, and concise. It uses the A* algorithm to compute its paths, which is more or less the gold standard in path finding algorithms (or at least I have not been able to find a better algorithm, if you know of one please let me know). On my laptop, it manages to plan a path right across on of the the largest maps in the game in about 20 milliseconds, which compared to the time it actually takes to perform such a walk is essentially nothing. What then, is the problem?

There are actually three problems, and they are all related. The first is that with the current settings, the paths generated are not necessarily the shortest. This is arguably not a huge problem, but it does look rather silly when your character is moving in a certain direction, and at the very last moment before it encounters an obstacle decides to veer around it. Secondly, the pathfinder is very happy to insert turns in the path. This, combined with the first problem, results in the actor walking around like it drank too much ale in Pula’s tavern.³On Isla Prima. If you actually installed the game earlier, you have probably been there already. And finally, even though the code has measures in place to randomize the paths taken, this does not work out too well in practice, and often-times actors will walk more or less the same path going from A to B.

The algorithm

As said, the client uses the A* path finding algorithm to compute its paths. This is in essence a rather simple algorithm. We keep two lists of tiles, called open and closed. The open list constitutes the “frontier” of our search space, these are tiles that are currently candidates to extend our path from. The closed list contains tiles that have already been examined and are either currently part of our best guess for the path, or have been rejected altogether. Each tile t in the lists has the following fields:

• The actual cost g of getting to that tile from the start position,
• A heuristic (informed guess or estimate) h of getting from that tile to the destination, and
• A reference p to the “parent” tile from which the tile was reached in the path.

A* then simply boils down to:

1. Initialize the open list with the start tile, and empty the closed list.
2. Remove the tile t with the lowest total cost estimate f=g+h from the open list.
3. If this tile is the destination, we have successfully found a path and follow the chain of parent tiles p to generate it. If not, then
4. Examine all neighbour tiles of t. For each neighbour:
   • If the neighbour is in the closed list, ignore it and continue with next neighbour.
   • Determine the actual cost g for the neighbour by adding the step size to the g value of t, and calculate its heuristic cost h of getting to the destination.
   • If the neighbour tile is already in the open list:
     • If the new total cost estimate f=g+h is higher than the existing estimate, ignore it and continue with the next neighbour.
     • Otherwise update the neighbour tile’s g and h values, and set its p value to t.
   • If the neighbour is not already in the list, add a new tile to the open list with the calculated g and h values and parent t.
5. Put tile t on the closed list.
6. If the open list is now empty, there is no path from the source tile to the destination, so give up. Otherwise
7. Go to step 2.

A more detailed explanation can be found on Wikipedia.

If the heuristic values h for tile t never exceed the actual cost of getting from t to the destination, this algorithm is guaranteed to find a path with the lowest possible total cost of getting from the source to the destination tile. So you could choose one extreme, and pick h=0 for all tiles. You then end up with what is known as Dijkstra’s algorithm, which works, but is usually less efficient then using A* with a better informed heuristic. On the other extreme end, if you had a perfect heuristic that could predict the remaining cost exactly, you could just follow the path of tiles with the lowest estimated total cost, and would not need much of a path finding algorithm at all. Alas, such a heuristic is generally unavailable.

So, all is well?

Well, not all. And the attentive reader will probably already have deduced that this is due to the choice of heuristic in the game. Eternal Lands uses an eight-directional grid: from each tile you can move along the grid in either of directions, or diagonally (again, in four directions). The grid aligned moves have a cost of 10, and the diagonal moves a cost of 14.⁴This is an approximation of 10×√2. We will call this the octile cost function. The problem is that the heuristic function does not take diagonal moves into account, and uses what is called a Manhattan cost function, where the cost of a move of dx steps in the x direction and dy steps in the y direction is simply 10*(dx+dy).

Imagine planning a path from the tile at position (0,0) to (2,2), without any obstacles, as in Fig. 1. The total cost is simply the cost of two diagonal moves (the green arrows), so 14+14=28. Yet the heuristic function will only consider aligned moves, and so returns 4*10=40.

Whys is this problematic? Well, for one thing, it drastically reduces the randomisation the client tries to introduce. The client tries to randomise paths by adding a random cost between 0 and 3 to each step when it expands the neighbour nodes of a tile. But with the Manhattan heuristic, the effect of that extra cost is nullified. Let us plan a new path, this time from (0,0) to (4,2):

Bot the green and the blue path have minimal cost (disregarding randomization cost), containing two grid-aligned moves and two diagonal moves for a total cost of 2*10+2*14=48. In a properly randomized sample, these two paths should occur more or less equally often. But after the expansion of the source tile at (0,0), the total cost estimate for the neighbour tile at (1,0) is 10+50=60, whereas the estimate for the diagonal tile at (1,1) is 14+40=54. Even when the diagonal move incurs a randomization cost of 3, and the horizontal move none, the total cost estimate for the diagonal move is lower. Now remember that the A* algorithm always chooses the tile with the lowest total cost estimate from the open list to continue its search with. As a result, the tile at (1,1)is always chosen as the next tile to expand. And this holds in fact at every step: everywhere a diagonal move in the direction of the target tile is an option, it will lower the total cost estimate and will be preferred over a grid aligned move. As a result, alternative paths only become an option when the current path incurs enough randomisation cost along grid-aligned moves to offset the cost reductions by the diagonal moves.

And we see this back in the generated paths. Below is a heat map of a simulation of 1,000 runs of finding a path for a simple walk on the Isla Prima map, from (126,130) to (117,135). There are no obstacles in this path. The colours indicate in how many runs a tile is part of the returned path, dark blue meaning not visited at all, and bright yellow meaning visited in all runs.

As you can see, the pathfinder basically returns the same path on every run, where there are many different paths with the same total cost.⁵126 of them, in fact. On rare occasions, the randomisation error on the straight part of the the path becomes large enough for an alternative route to be taken. We can see this if we remove the main path from the figure:

So, the randomiser works somewhat, but its effect is drowned out in 98.5% of the cases by the overestimation of the total cost.

The Manhattan heuristic ruins the randomiser, but at least when there are no obstacles, it returns an optimal (lowest cost) path. Things are different when there are obstacles in the way. For a simple case, consider plotting a path from (0,0) to (3,2), with the tile at (1,1) being inaccessible:

The optimal path goes below the obstacle, for a total cost of 10+2*14=38. And indeed, the pathfinder can find this path using the Manhattan heuristic. But it can also fail. Let us expand the source tile, and write the calculated and estimated costs of the tiles inside them:

We see that both neighbour tiles at (1,0) and (0,1) have a total cost estimate of 50. At this point, the pathfinder does not have enough information to decide between the two possible paths. So it could get lucky and choose the tile at at (1,0) to expand next and find the lowest cost path. However, when it chooses the other tile, the mistake is never corrected. Let us expand one tile further:

Now the total cost estimate of the tile at (1,2) becomes less than that of (0,1), meaning that it definitely will be chosen next for expansion. This is a situation from which the pathfinder never recovers, as from here on the actual step costs will be the same as estimated. Filling in the costs of the remaining expansions, we see that it finds the wrong path:

Now this small example relies on the pathfinder choosing the wrong node to expand by accident, which should only happen half the time. In other cases, the heuristic will certainly lead to the wrong path. An example is given in Fig. 8, where the cumulative reduction in estimated total cost, due to the diagonal moves, is enough to make the pathfinder always choose a longer path than is optimal, introducing an extra turn in the process as well.

And finally, speaking about turns, there is no cost associated with turning the actor. Combine this with path randomisation (in places where it does have an effect), and you may well end up with your character moving into a different direction every other step, which is visually very distracting.

In the next post, we will look further into how to fix these problems (beyond merely replacing the heuristic), and speeding up the code. Stay tuned.