A-Star Algorithm: Adjacency List

Sometimes we can speed things up by providing nodes for "special" points on map, rather than "seeding" the entire map with regular grid's nodes. A good example is navigation along the existing road network: when planning such path, we simply do not have to consider points that are not located on the road.

In that case, the algorithm changes signifficantly: we choose neighbours from the list, we can use distances along the road, and instead of the keepout values of nodes, we use "quality of the road", provided with the graph edges.

Note that the algorithm below can be changed based on your task. For example, let's say your adjacency list contains a segment of a road that has quality of 128. But we want to additionally "punish" part of that segment, as it goes uphill. Something like that.

Let's take a look at the result. First, Let's "unblock" the straight road (which is 1-2-3-4). Note that keepout values for corresponding nodes are set to 255:

Now let's reduce quality of a 3-4 segment: