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.

- Next step Continuing the theory

- Back Overview