# 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

### Part 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.

### Part 2: Find nodes connected to those nodes

The next step branches out to nodes connected 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" of the node used along the route. This is the total distance to the destination from each of the new nodes.

When there is more than one route to a node, only the route with the shortest cumulative distance is saved. For example, starting at node 8, the destination 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 |

### Part 3: The next connected nodes

The process continues, branching out to the next set of nodes that are connected to ones already checked (5, 9, 13, 14, 15, 16, 19, 20, 22).

**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. The algorithm does not need to keep track of the sequence of nodes used for a given route.

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 |

### Part 4: Add connected nodes again

Once again the algorithm continues to add connected 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 |

### Part 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

### Part 6: 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 (the yellow area), the all the algorithm has to do is the following:

- Get a list of nodes that are in range (13 tiles) of the current position
- Determine which of those nodes has the lowest index in the sorted table above

So now the algorithm simply tells the object seeking a path to move directly to that node. Once at the destination it again finds all nodes in range and whichever one has the lowest index in the sorted table is the new target. Repeat until at final destination.

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 that new destination. But if there are multiple objects seeking a path to the same destination, then they can all use the same mapping table (provided all those objects are located somewhere in the yellow area).

### 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; go to node 20
- Once arriving at Node 20, Node 10 becomes the best node in range at a total distance of 16.6 tiles; go to node 10
- Then node 2 at 5 tiles; go to node 2
- Once arriving at node 2, the final destination will be in range. Proceed directly to the destination.

The following image shows these 4 steps along the route: