# Pathfinding Demystified (Part II): Search Strategies

## Introduction

The first article in this series presented the generic pathfinding algorithm. If you didn’t fully understand it, please go back and re-read it, because it’s essential to understand what follows. Once you get it, A* will be the most natural thing in the world.

## The Secret Sauce

I left two open questions at the end of the previous article: if every pathfinding algorithm uses the same code, what makes A* behave like A*? And why did the demo find different paths sometimes?

The answers to both questions are quite related. Even though the algorithm is well defined, there’s one aspect that I left purposely vague, and which as it turns out, it’s the key to explain how search algorithms behave:

`node = choose_node(reachable)`

That innocent-looking line is what makes each search algorithm different to the others. The choice of what `choose_node` does makes all the difference in the world.

So why did the demo find different paths? Because its `choose_node` method picked a node randomly.

## Length Does Matter

Before diving into the different behaviors of the `choose_node` function, we need to fix a slight oversight of the algorithm as explained before.

Whenever we considered the nodes adjacent to the current one, we ignored those we already knew how to reach:

```if adjacent not in reachable:
adjacent.previous = node  # Remember how we got there.

This is a mistake: what if we have just discovered a better way to reach it? In that case, we should adjust the node’s `previous` link to reflect this shorter path.

In order to do this, we need to know the length of the path from the start node to any reachable node. We’ll call this the `cost` of the path. For now let’s assume moving from a node to one of its adjacent nodes has a fixed cost of `1`.

Before starting the search, we set the `cost` of each node to `infinity`; this makes any path shorter than that. We also set the `cost` of the `start_node` to `0`.

So here’s how the code looks now:

```if adjacent not in reachable:

# If this is a new path, or a shorter path than what we have, keep it.
if node.cost + 1 < adjacent.cost:
adjacent.cost = node.cost + 1```

Let’s now focus on the `choose_node` method. Choosing a node at random clearly isn’t a good idea if we’re trying to get the shortest possible path.

A better idea is to choose the node we can reach from the start node with the shortest path; this will generally choose shorter paths over longer ones. This doesn’t mean longer paths won’t be considered, just that shorter paths will be considered first. Since the algorithm stops as soon as a valid path is found, this should get us short paths.

Here’s a possible `choose_node` function:

```function choose_node (reachable):
best_node = None

for node in reachable:
if best_node == None or best_node.cost > node.cost:
best_node = node

return best_node```

Intuitively, this algorithm’s search expands “radially” from the start node until it reaches the end node. Here’s a live demo of this behavior:

 reachable = [] explored = []

## Conclusion

A very simple change in the way we choose what node to consider next gives us a pretty good search algorithm: it does find the shortest path from the start node to the goal node.

But this is still a dumb algorithm, in a way. It keeps looking everywhere until it stumbles upon the goal node. In the example above, what’s the point of looking in the direction of A when we’re obviously getting farther away from the goal?

Can we make `choose_node` smarter? Can we make it steer the search towards the goal, even without knowing the right way beforehand?

It turns out we can - in the next article, we’ll finally arrive at the `choose_node` which makes the general pathfinding algorithm become A*.

Found this interesting?