Adding Pathfinding to mapthis!

[andreq]

I've been using map this for the last weeks and I still think it defenatly need a "goto" button (find the route form A to B)

My idea :

Step 1

Generate a node.dat and links.dat from geodata.dat with relative info on how each node interconnect with the links. Also, info on the links (one way, road, highway, etc...)

This will minimise the calculation on the PSP and enable a faster search

Step 2



Use a Breadth-first pathfinding algorythme to calculate the road from node 1 (nearest node from current GPS position for exemple) to node N (nearest node from destination position)

SEE :
http://en.wikipedia.org/wiki/Breadth-first_search


I throw my idea as I've not done any psp dev (for now)

I know it's not as easy as it sound, but I'm sure someone clever here can figure out something


I love the work Nieko did on the get route from the psp browser... but doing this without internet would be really a great advancment for mapthis! (and would defenatly push some people use it instead of GoExplore!)

[Nieko]

Breadth-first search is exponential in time and space, that really won`t cut it on any map of decent size I`m afraid.

Dijkstra`s shortest path algorithm may work well, but as you said, someone needs to implement it, and we need the data (nodes, vertices and ideally weights). Both seem to be lacking at the moment for most countries (for the Netherlands we might be able to do something using using OSM data though).

[andreq]

Couldn't "we" create the data from the existing Geodata... we have the road info or im wrong ?

I'm far from being able to do this... but I'll try to give any idea that I could think :)

[Nieko]

Deniska and I talked about it a while ago (it should still be somewhere in the forums, search for geoline.dat), and the main problems are, at least for OSM data (Netherlands mainly): no street numbers, no max. allowed speeds, perhaps something else.

Personally, I'd love it if this were to work :), but I'm afraid we won't see this happen for the majority of countries any time soon...