search

pszufe / OpenStreetMapX.jl

OpenStreetMap (*.osm) support for Julia 1.0 and up
MIT License
123 stars 24 forks source link

Added A* search algorithm implementation #8

Closed bartoszpankratz closed 5 years ago

pszufe commented 5 years ago

@bartoszpankratz - build failed:

ERROR: LoadError: ArgumentError: Package OpenStreetMapX does not have DataStructures in its dependencies:

Do you know how to add the dependency or need help?

bartoszpankratz commented 5 years ago

@bartoszpankratz - build failed:

ERROR: LoadError: ArgumentError: Package OpenStreetMapX does not have DataStructures in its dependencies:

Do you know how to add the dependency or need help?

Nope, any help will be very appreciated.

pszufe commented 5 years ago

@bartoszpankratz I have fixed the dependencies. However what is missing:

  1. add the a_star routing to shortest_route and fastest_route methods. a_star should be used by default. I propose adding a new parameter to those methods ; routing = :astar and the user should be able to change ; routing = :dijkstra if they wanted the classic Dijkstra.
  2. Once (1) is done add the following tests in the runtests.jl file: 
     @test shortest_route(m, pointA, pointB; routing = :astar) == shortest_route(m, pointA, pointB; routing = :dijkstra)
 @test fastest_route(m, pointA, pointB; routing = :astar) == fastest_route(m, pointA, pointB; routing = :dijkstra)

    I assume that those tests should pass.

bartoszpankratz commented 5 years ago

Done

pszufe commented 5 years ago

@bartoszpankratz tests now are failing for the fastest_route we need to adjust the heuristic function for a_start to calculate in this case the shortest theoretical travel time. Probably now it is still calculating distance - so for fastest_route we it needs to be divided by the travel speed.

bartoszpankratz commented 5 years ago

@pszufe I know it. An it was one of the reasons why I insisting on keeping the zeros heuristic during the phone call. It is the only universal one, and If you need something more sophisticated declaring new one is easy and absolutely basic. Straight Line heurisic is proper only for the shortest path searching, for the driving time you need to create another large matrix (speeds matrix) and it still will be sometimes unnefective (for segments faster than average speed the heuristic value might be larger than the value of the route, so algorithm will return unoptimal path).

bartoszpankratz commented 5 years ago

I have modified this heuristic, now it is dividing not by not average but maximum possible speed. IMHO it is quite unnatural but works - it will never overestimate the cost of the route. I guess case is done.

bkamins commented 5 years ago

This PR is becoming unmanageably large (almost 300 LOC). @bartoszpankratz - is it possible to split it into two parts: