sync-by-unito[bot]
commented
5 months ago ➤ Zdenek Plesek commented:
Specification process needs to be done with explicit interfaces (entry/exit points) defined.
Some high level guidance to implementation, accessing object called Map, should be provided.
Dependency: https://trello.com/c/YaRL5Tvm
To implement the pathfinding, we will use Floyd-Warshall algorithm to generate a list for each vertex which describes the shortest route to every other vertice on the graph. This allows us to read these tables to immeadiately know the optimal route. This route may change due to conditions or events that occur during the path.
Here are some resources to help during implementation:
https://www.geeksforgeeks.org/floyd-warshall-algorithm-dp-16/
https://brilliant.org/wiki/floyd-warshall-algorithm/
https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=video&cd=&cad=rja&uact=8&ved=2ahUKEwjD-enrj8aCAxWvUkEAHfy9D2IQtwJ6BAgQEAI&url=https%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3D4OQeCuLYj-4&usg=AOvVaw1PFm8HY-XzpjbV_IDL3jht&opi=89978449
It is important to note that this algorithm will have to be modified somewhat. Rather than storing a matrix of distances, we must store dictionary on each junction (dict{vertex1: distance, vertex2: distance,…}). Additionally, rather than simply storing the distance to the node, we must consider the next step. This is simply done by recording the next step to node X along with distance. Therefore, the dictionary should hold this form:
dict{vertex1: (distance, nextStep), vertex2: (distance, nextStep)}
This can be performed during the steps where the intermediate vertices are considered, and may require some backtracking, If assistance is needed please contact proctorted .
During the routing table generation period, the following functions will be very useful:
getEdgesOriginatingIterator
getEdgesTerminatingIterator
Public attributes:
The validation phase will require a test case / network. Please contact proctorted or zp235 if assistance is needed.
Specified by: Ted Proctor, Zdenek Plesek, Scott DeVerinne
Implemented by:
Validated by:
┆Issue is synchronized with this Trello card by Unito