gda-routefrontend Routing algorithm improvements

[gregallensworth]

See the gda-routefrontend branch for the client/ folder. This contains a front-end-only application for calculating a route between two latlng-pairs. This basically works at present (16:00 on May 25) but has improvements to make:

• [x] Following wrong forks, will basically follow until a dead end (edge of the fetched universe, or a real dead end). For a large route that could in theory be some miles. Put in a check whether we're increasing our distance instead of decreasing it, see if we can detect wrong turns and abort before the dead end.

• [x] Choice of candidate path when candidates.length > 1 is always candidates[0] Manhattan heuristic would check the far endpoint of the next segments, pick the one that's closer to the target latlng, and thus take fewer wrong turns that it needs to resolve.

  • Example: findRoute(31.1811, -81.4993, 31.3640, -81.4193) Current data, the first step is a wrong turn which it follows for 7 steps. Examination of the candidates would have taken it on the correct path the first time.

• [x] Test with some larger distances.

• [x] Test some known unusual conditions, e.g. the ring around Boston, and the L shape of Fernandina Beach GA, to see if it's making smart choices..

[gregallensworth]

Manhattan alone, suffices that the thing won't follow a wrong fork indefinitely. It picks the right fork the first time, and the few dead ends have proven to be fairly short.