Results 1 to 4 of 4

Thread: Adding Pathfinding to mapthis!

                  
   
  1. #1
    DCEmu Newbie
    Join Date
    Mar 2008
    Posts
    35
    Rep Power
    0

    Default Adding Pathfinding to mapthis!

    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!)

  2. #2
    DCEmu Pro
    Join Date
    Feb 2007
    Location
    Netherlands
    Posts
    539
    Rep Power
    29

    Default

    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).

  3. #3
    DCEmu Newbie
    Join Date
    Mar 2008
    Posts
    35
    Rep Power
    0

    Default

    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

  4. #4
    DCEmu Pro
    Join Date
    Feb 2007
    Location
    Netherlands
    Posts
    539
    Rep Power
    29

    Default

    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...

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Tags for this Thread

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •