Determine use of JSP vs DIJEKSTRA

[SonOfTheStars]

We have to determine the usage of the 2 routing algorithms that have been devised by @Borimino and Me.

First of all big thanks to Bori for adding Dijkstra to the table.

We need to compare JSP and Dijekstra under different conditions on different real life applicable networks here. Here are some metrics(Both algorithms ran on an internal Delay of 120ms):

1. Normal network, 6 connections, long straight lines: 1.1 JSP took 15s to find all routes from the activated Pipe 1.2 DJK took 11s to find all routes from the activated Pipe
2. Crafting Wall(Length 9, Height 5), 45 connections, no straight lines: 2.1 JSP took 52s to find all routes from the activated Pipe 2.2 DJK took 2:18 min to find all routes from the activated Pipe

Ive tested delayless in both scenarios. Both take <1s to complete.

I then build a very large network and ran both delayless. Dijekstra reached a runtime of >1s quite a lot earlier than JSP

I conclude: For networks with long straight runs of pipe, dijekstra is more ideal. For networks with a shitload of junctions/destinations, JSP is more ideal.

[saulrh]

Suggestions for future dev-work if routing starts to hurt:

• A* with Reach is extremely good for networks with "highways". If I remember the intuition correctly, a preprocessing stage on the graph identifies nodes which are useful for moving long distances quickly, encoding this information in "reaches". Original publication, later publications with enhancements.
• Variants on Lifelong Planning A, most importantly [D-lite](http://idm-lab.org/bib/abstracts/papers/aaai02b.pdf), are particularly relevant for this use case because they remember information from request to request and efficiently tolerate changes to the graph. These typically build up partial policies about the graph along with enough information to invalidate appropriate chunks of the policy when edge weights are changed.

[SonOfTheStars]

Dijekstra has been determined as best practice use for us and will be used from this point onward.

This issue is hereby closed.