Implement route() method of the Router class

[ethanjweiner]

Task Title

Task: Implement route() method of the Router class

Task Description

This Task will...

• Give Routers a way to find the next router to route to
• Recursively route the rest of the path
• Involve some contemplating, and possibly research

Epic Parent

Feature: Awesome Feature Title

[ethanjweiner]

Ideas:

We have access to a list of all the routers, the destination, and the path travelled so far. How can we move one step closer to the destination?

• Think about it as a singular step
• Think about it recursively

Use some searching algorithm to help with this (e.g. BFS?)

[ethanjweiner]

Idea:

• Randomly try paths
• Use a heuristic (distance from the destination) to give the choice a "rating"
• Once a path reaches a certain length, disregard that path

Research search algorithms for disconnected graphs

[ethanjweiner]

Spatial indices: Ways to arrange geometric data for efficient search -- e.g. find all the routers in this area

e.g. Organizing all the points into boxes such that we can use a tree-like data structure to recursively zoom in on boxes that touch the point of interest.

We will not be using spatial indices, since we aren't dealing with a ton of data -- we can use the more naive approaches of looping through all points.

However, we can maybe create something similar in practice. At the very least, we could label the continent that each router is located in.

[ethanjweiner]

Idea: Use a BFS (breadth-first-search like algorithm):

Heuristic: Distance from destination

• Create a circle of radius r around the origin
• Determine all routers within that circle: routers_candidates
• Sort the routers by the heuristic (least->most distance from destination)
• Starting with the best heuristic (least distance), run BFS find a path -> destination
• If the path becomes too large (> 30 routers), return false and try the next router candidate

We can tweak this algorithm (e.g. add more randomness; change router cap) as we go. But this seems like a good starting point. I'd rather introduce randomness/chaos, than start with chaos in the beginning.

[ethanjweiner]

Consider setting up a playground for testing these routing functions . . .

[ethanjweiner]

Potential edge case: The destination is isolated from other routers. Problem: The routers will simply keep jumping back and forth between each one. Solution: Avoiding circular cases --- at first, the algorithm will jump to the closest neighbors. But once those neighbors become part of the path, they can no longer be added to the path --- and so the algorithm will instead search in a further radius --- and try to find the destination.