[New Feature] Extended route search algorithm

[exodus4d]

There are some really cool features for the *Routes search" module in progress:

• The Routes search" module is no longer restricted to *K-Space systems. Routes can be searched from any system on the map, to any other system in New-Eden (this includes of course wormholes and Jumpbridges!)
• The new algorithm will also take care of multiple chains on a map (finding short cuts)
• Routes can no longer be static cached. Existing routes will auto-adjust if new systems were added to the map, which affect the length of a route. (Client-Side and Server-Side route cache refactoring)

Example

1. We are looking for a route from "J100820" (C5 WH, top-left chain) to "Jita"
2. The search algorithm found a valid route (first row)
3. The first 3 Jumps (red squares [-1.0 trueSec]) are W-Space jumps ( "J100820" -> "J105719" -> "J132721" -> "Uminas")
4. For demonstration purpose, I added a second Chain ("Olo" -> "J110823" -> "New Caldari"). This route is shorter than doing all the HS jumps to "Jita". Therefore the algorithm takes this into account and proposes a route through that WH (red square with active tooltip)

The Future

• Now it is super easy to enable multiple maps for route searching. Ill probably add some "filter" options, where users can add all their active maps and perform some kind of "meta search".
• I´m thinking about a way to filter some connections (e.g. Frigat Holes, or EOL Holes). -> If the character is currently in a Battleship it does not make much sense to add small wormholes which can not be entered.
• I´m also thinking about a zKillbaord API call fore each system in the root to find recent kills in any of those systems. -> Routes could be marked as "unsave"

[exodus4d]

[NEW] Extended route search. Features:

• "Live search". All systems/connections on a map are included for route search
• "Map meta search". Multiple maps can added to route search
• Routes can be refreshed and re-calculated (button added) e.g. when a map has changed (new systems/connections,..)
• "Filter Routes". Routes can be filtered/limited to search conditions:
  • Include/Exclude specific or multiple connection scopes from search (e.g. stargates, wormholes, jumpbridges)
  • Include/Exclude specific connection types from search (e.g reduced wormholes, critical wormholes)
• "Batch refresh". Refresh/reload multiple routes for a system with a single "click"
• Routes module is added to wormhole systems
• "Delete Route". Added button to delete specific routes from a system

Screenshot from new "Routes finder" dialog

[atkinsj]

This is awesome; much nicer than Siggy's actually I think. Thanks a heap for adding this.

Quick question -- it's extremely slow for me, taking 45-60 seconds to load after clicking each system. Is this a performance deal on my host or a known issue?

I'm also seeing this cause php-fpm worker processes to spike in CPU; sometimes as far as 100%.

[exodus4d]

That s interesting. The "Dijkstra algorithm" is indeed CPU intensive, that´s true. But even on long routes (> 40 jumps), the calculating was done in < 100ms on my dev system.

• Which PHP version are you running? - Switching vom v5.6 to v.7.x was a huge performance boost for me. The calculation time was reduced by more than 50% for me.
• In the past it was pretty easy to cache routes between k-Space systems (stargate connections never change :) ) From now on, It is a lot harder, any new system/connection, added to a map, may have impact on any route. Therefore routes are not auto-refreshing and I added a button for this.
• Nevertheless, routes are cached for 10s (client side [js]) (which is currently not working as expected) and 10s (server side [PHP)]. Due to the fact, server side caching is heavily used. If you relay on "file based caching" (default cache folder: /cache), running your web server on an SSD will reduce file reade/write timings furthermore.

Could you tell me the server specs you were testing at?

[atkinsj]

Interesting. I'm running on a VPS that has 2 CPU cores and 1GB of ram and even on my local development machine which is a 2.4Ghz i5 Quad core I'm still seeing routes take in excess of 10 seconds. This is to the point where php-fpm is killing the script as it becomes long running. A run through the xdebug profiler and throwing it QCacheGrind shows all the time is indeed in the graph_find_path method.

I'm running PHP 5.6, I'll try upgrading to 7 and see how we go. I'm using APC for caching.

[VivianMeally]

Hi, how difficult is it to implement Titan chains in this calculation?

BTW, awesome work

[exodus4d]

If they are mapped (e.g. you could use "jumpbridges" for them) they work out of the box.
There is no way to get those chains from the API.

If you want a complete new type of connection, it will probably take some time to implement them.
The basic requirement for the calculation is a source and a target system. If they are available, the calculation algorithm will take this in into account.

It works like:

1. get all static connections (Stargates) from the SDE
2. get all the dynamic connections from the map (or multiple maps)
3. merge everything together
4. perform a search over all connections

[VivianMeally]

Thanks, i think i can just map it as jumpbridges.
btw, i dont know if its belong to this ticket.
But Routes window dont show any routes
http://puu.sh/oF1z0/e35b89191e.png
Installed is the lates develop branch patchfinder.sql and sde are imported.

[exodus4d]

@VivianMeally have you imported pathfinder\export\sql\pathfinder.sql in your freshly generated DB (which is not documented on the wiki yet). If you have, clear your \cach dir.

[VivianMeally]

Nice, thank you. Clearing cache has done the job.
I am doing a rancher app ( http://rancher.com/rancher/ ) to install it more easy.

Do i am need to clear the chace after pathfinder.sql import? Or bevor i do my first cronjob?

[exodus4d]

After *.sql import. The "static" connections are cached for 24h. For some reason they were not up2date. :( Ill have look at this. Maybe I can automate this and/or fix it.