honzaap / pathfinding Goto Github PK

What I will be doing -

• Based on recent paper on Q*, I will apply the algorithm to find the shortest path
• I will add links to relevant articles which mentions the working of algorithm

Hi,

I'm working on a version to specifically visualise the A star algorithm with similar data and noticed that the results where sometimes very different, even when I removed the additional weights I added based on maxSpeed & disregarded one way edges.

That's when I realised you are currently using the Math.hypot() on the difference in longitude and latitude between two nodes. The thing is that the distance in meters between the latitude lines is always the same, the distance in longitude changes.

Around the equator, 1 degree longitude and latitude is basically the same in distance, for which Math.hypot() will give you the correct distance between two points.
In Finland on the other hand, moving 1 degree left or right (east or west) we only move half the distance of moving 1 degree up or down (north or south).

=>
This is why the A* algorithm will heavily favour any movement left or right.
Using current Math.hypot() for the distance from Point A(Lat 0, Lon 0) & Point B(Lat 0, Lon 1) is the same as the distance between Point A(Lat 88, Lon 88) & Point B(Lat 88, Lon 89), although the actual distance is 348 times bigger.

To fix this you should scale by the cosine of the latitude

Hey, very cool project btw!
I think your project is using OSM, right?
Don't forget to add a little text box in the bottom right to make it clear that the tiles (and I assume the map data for the routing as well?) is OpenStreetMap

(I think you're using mapbox, which uses Openstreetmap and usually automatically puts a textbox there, so not sure what you need to do to make it appear correctly)

Basically everything work, but the map just does not load in Firefox

Trying the url with Chromium works, so I assume its a Browser compatibility problem.

hi,
@gboeing in osmnx enables a choice of different street networks when query overpass api:
https://github.com/gboeing/osmnx/blob/9fd590117d459d74065f32de9d64a6abffe2e3f0/osmnx/_overpass.py
I think that enabling geoff's queries in
https://github.com/honzaap/Pathfinding/blob/a38314553f89018a1c3c2f79d65611702996c6b1/src/api.js#L7C1-L7C1
will help users to visualize different usecases.