What we need now is a way to find the shortest path from point A to point B without wasting much performance. There's many ways to perform really fast path finding but most of these methods fail in certain situations. Path finding really is a performance-eating task but we can do some tricks to use it even in games. The algorithm we're going to use is called A* (a-star) and it's probably the best and easiest algorithm you can get. In it's basics A* is quite easy to understand and you can simply extend it by further algorithms to perform more advanced path finding as you need it.
Before we start coding let's have a look at the following picture. It shows a quite simple situation where we want to find the shortest way from A to B:
You hopefully agree that the blue way is a little shorter than the red one (it's a proven fact, you don't have to measure). Note that we use a 8-way system here so you can even move diagonally. So how can we find out which way is shorter before we calculated both? The trick is to simply estimate the remaining distance from each tile we're going to check. Imagine the system arriving at the critical point where it has to decide which way is shorter. The situation is shown below; the purple path is what we've done already and the yellow tiles are next to check:
The red and blue lines show the distance to the target and here you can clearly see that the blue line is shorter. Does this mean we can we leave out the red way from now on? No we can't because the code doesn't yet know if the blue way really is shorter. It's not even sure that we can even reach the target from there. But knowing the shortest remaining distance helps us deciding which tile to proceed with. We'll get back to this later, let's try something first:
In the next picture I calculated the correct distance from each critical tile to the target. This is done by using the well-known formula of Phytagoras d = Sqr( (x ^ 2) + (y ^ 2) ):
As you can see this works perfectly fine. Any distance of the way below is less than those of the other way. This means that we don't even waste time calculating that way! But does this work in any case? see the following picture:
Still the way below contains quite low distances but surely the top-way is shorter now! To solve this problem we have to score the tiles we already processed. Basically we just add a certain value to those tiles. Check out the next picture to see the generated scores:
For straight movement I added 10 points in each step and for diagonal movement 14. Why 14? When calculating the correct diagonal distance from one tile to another we get Sqr(1+1) = 1.4121... (square-root of 2). But we don't want to use floating-point numbers because of performance reasons. The trick is to multiply everything by 10 (or more) to simulate more precise values than integers are. Besides, 14 instead of 14.121 is quite a good match.
Now what the heck are the scores good for? Follow both ways again regarding the scores now. You'll go from 50 to 60, 64, 70, 78, 84, 92, ... and finally reach 146 at the end of the top way. That was quite good already because we found out the bottom way is longer before finishing the way below.
Adding both values, scores and the estimated distance, we get the final estimated distance for a step regarding the way we already passed. Since we used factor 10 for the scores we have to apply the factor to the estimated distance, too. The formula will look something like this (pseudo code):
'Get estimated distance Dist = Score + Sqr( (DeltaX ^ 2) + (DeltaY ^ 2) ) * 10
Now this is a situation where we have to optimize code for speed. Instead of using the correct formula above which contains square roots and squares we could use something like this:
'Get underestimated distance Dist = ( DeltaX + DeltaY ) * 10
This is called the Manhattan method and it simply calculates the number of tiles we have to move horizontally and vertically to reach the target, ignoring diagonal movement completely. The result will be a underestimated distance to the target or the correct distance in the best case. There's a number of methods you can use instead but this one is quite good. Note that we have to multiply the result by 10 so we can compare the scores later.
Using a cheaper formula to estimate the distance won't affect the path-finding. As long as we underestimate the distance A* is guaranteed to find the shortest path from A to B. If we overestimated the distance A* would still find a path but probably not the shortest.
However in both cases the function will check more tiles than necessary, therefore running slower as when using the correct distance we get from Pythagoras. On the other hand this complex formula will already eat performance to even calculate the distance. It's your turn to decide which one is better.