# Algorithm Explained

This page describes the algorithm used by the node_map.lua script in order to find an optimal route from point A to point B using a network of interconnected nodes.

### Topics

### Sample Node Map

The following image shows a sample node map that will be referenced in this example:

Red dots are nodes (numbered 1 to 25), and the green lines show the connections between nodes. Nodes are only connected if they are within 13 tiles (208 pixels) of each other on the map. Distances between nodes are shown as number of tiles (multiply by 16 to convert distances to pixels). The area highlighted in yellow is within range of at least one node (no more than 13 tiles away).

The destination is marked by the red X. The blue dashed lines show the distance (in tiles) from the destination to the nearest nodes.

## The Mapping Algorithm

### Segment 1: Find nodes within range of the destination

The first step is to find all the nodes within range (13 tiles) of the destination and calculate their distances.

**Node 1:** 8 tiles from destination

**Node 2:** 5 tiles from destination

**Node 3:** 7 tiles from destination

These distances are saved with each node. They are the shortest distance possible, so none of these nodes need to be checked again.

### Segment 2: Find nodes adjacent to those nodes

The next step branches out to nodes adjacent to the ones already checked. Node 1 is connected to nodes 6, 7 & 8 (ignore nodes 2 & 3 since they've already been checked); node 2 is connected to 8, 10 & 11; node 3 is 4, 11 & 12. Now the distance between the nodes is added to the distance away from the destination on the route used to reach the node.

When there is more than one route to a node, only the route with the shortest cumulative distance is saved. For example, node 8 can be reached by going through either node 1 or node 2.

**Node 4:**

- using node 3: 7 + 9.6 = 16.6

**Node 6:**

- using node 1: 8 + 11.0 = 19.0

**Node 7:**

- using node 1: 8 + 9.4 = 17.4

**Node 8:**

- using node 1: 8 + 9.9 = 17.9
- using node 2: 5 + 10.7 = 15.7
- route using node 2 is shorter

**Node 10:**

- using node 2: 5 + 11.6 = 16.6

**Node 11:**

- using node 2: 5 + 10.5 = 15.5
- using node 3: 7 + 12.5 = 19.5
- route using node 2 is shorter

**Node 12:**

- using node 3: 7 + 9.5 = 16.5

The node distances found thus far are:

Node | Total Distance | Node | Total Distance |
---|---|---|---|

1 | 8.0 | 7 | 17.4 |

2 | 5.0 | 8 | 15.7 |

3 | 7.0 | 10 | 16.6 |

4 | 16.6 | 11 | 15.5 |

6 | 19.0 | 12 | 16.5 |

### Segment 3: The next adjacent nodes

The process continues, branching out to the next adjacent nodes.

**Node 5:**

- using node 4: 16.6 + 12.4 = 29.0
- using node 6: 19 + 10 = 29.0
- routes are equal

**Node 9:**

- using node 8: 15.7 + 11.4 = 27.1
- using node 10: 16.6 + 12.3 = 28.9
- route using node 8 is shorter

**Node 13:**

- using node 4: 16.6 + 11.5 = 28.1

**Node 14:**

- using node 6: 19 + 9.3 = 28.3
- using node 7: 17.4 + 11.2 = 28.6
- route using node 6 is shorter

**Node 15:**

- using node 7: 17.4 + 11.7 = 29.1

**Node 16:**

- using node 8: 15.7 + 10.6 = 26.3

**Node 19:**

- using node 10: 16.6 + 11.1 = 27.7

**Node 20:**

- using node 10: 16.6 + 12.6 = 29.2

**Node 22:**

- using node 11: 15.5 + 12.7 = 28.2
- using node 12: 16.5 + 11.3 = 27.8
- route using node 12 is shorter

**Node 24:**

- using node 4: 16.6 + 12 = 28.6

Notice that the routes to node 5 through nodes 4 or 6 have the same total distance of 29 tiles. This is unimportant because the only value saved is the distance itself. It does not need to keep track of which sequence of nodes the route uses.

Adding the new node distances to the table gives:

Node | Total Distance | Node | Total Distance |
---|---|---|---|

1 | 8.0 | 11 | 15.5 |

2 | 5.0 | 12 | 16.5 |

3 | 7.0 | 13 | 28.1 |

4 | 16.6 | 14 | 28.3 |

5 | 29.0 | 15 | 29.1 |

6 | 19.0 | 16 | 26.3 |

7 | 17.4 | 19 | 27.7 |

8 | 15.7 | 20 | 29.2 |

9 | 27.1 | 22 | 27.8 |

10 | 16.6 | 24 | 28.6 |

### Segment 4: Add adjacent nodes again

Once again the algorithm continues to add adjacent nodes.

**Node 17:**

- using node 16: 26.3 + 9.1 = 35.4

**Node 18:**

- using node 9: 27.1 + 10.4 = 37.5

**Node 21:**

- using node 20: 29.2 + 12.1 = 41.3
- using node 22: 27.8 + 9.2 = 37.0
- route using node 22 is shorter

**Node 23:**

- using node 22: 27.8 + 13.0 = 40.8
- using node 24: 28.6 + 9.8 = 38.4
- route using node 24 is shorter

Here is the updated table of node distances:

Node | Total Distance | Node | Total Distance | Node | Total Distance |
---|---|---|---|---|---|

1 | 8.0 | 9 | 27.1 | 17 | 35.4 |

2 | 5.0 | 10 | 16.6 | 18 | 37.5 |

3 | 7.0 | 11 | 15.5 | 19 | 27.7 |

4 | 16.6 | 12 | 16.5 | 20 | 29.2 |

5 | 29.0 | 13 | 28.1 | 21 | 37.0 |

6 | 19.0 | 14 | 28.3 | 22 | 27.8 |

7 | 17.4 | 15 | 29.1 | 23 | 38.4 |

8 | 15.7 | 16 | 26.3 | 24 | 28.6 |

### Segment 5: Add last remaining nodes

Now node 25 is the only node that still needs to be added.

**Node 25:**

- using node 21: 37.0 + 12.2 = 39.2

### Sort the table by distance

The final step is to sort the table listing the total distance for each node to the destination. It is sorted in ascending order of total distance. Here is the sorted table:

Node | Total Distance |
---|---|

2 | 5.0 |

3 | 7.0 |

1 | 8.0 |

11 | 15.5 |

8 | 15.7 |

12 | 16.5 |

4 | 16.6 |

10 | 16.6 |

7 | 17.4 |

6 | 19.0 |

16 | 26.3 |

9 | 27.1 |

19 | 27.7 |

22 | 27.8 |

13 | 28.1 |

14 | 28.3 |

24 | 28.6 |

5 | 29.0 |

15 | 29.1 |

20 | 29.2 |

17 | 35.4 |

21 | 37.0 |

18 | 37.5 |

23 | 38.4 |

25 | 39.2 |

Now when starting anywhere that's in range of one of the nodes, all the algorithm has to do to find the best node to target for a route to the destination is get a list of nodes that are in range of the current position, and whichever of those nodes has the lowest index in the sorted list is the node to target.

Here's the map with the distances for each node displayed:

Of course, these distances are only applicable for finding a route ending at the red X. To find a route ending anywhere else, a new mapping of all the distances has to be generated that targets the new destination.

### Algorithm in Action

Now for an example. Let's say an entity is starting in the lower right corner with nodes 20, 21 & 25 in range.

The steps are as follows:

- Node 20 has the shorted total distance of 29.2 tiles.
- Once arriving at Node 20, Node 10 becomes the best node in range at a total distance of 16.6 tiles.
- Then node 2 at 5 tiles
- Once arriving at node 2, the final destination will be in range.

The following image shows these 4 steps along the route: