Koji vs faster-routes

[kamieniarz]

Hey. I just wanted to leave my observations here. I'm using faster-routes https://github.com/ccev/faster-routes for months so I wanted to make test if koji is better in generating route. Below are my results from a 7.5 km^2 area with 5039 spawnpoints

-	Koji	faster-routes
Calculation time	~3 sec	~13 min
Route length	550	505

Koji settings:

faster-routes settings:

I set same last seen values so number of spawnpoints for both tools was the same

I ran similar tests with even 10x bigger areas and results were the same - faster-routes generates ~10% shorter route with the same coverage. Below are screenshots from these routes - koji one looks to me like bootstrap with excluded parts without spawnpoints when faster-routes seems to be more optimized.

Koji:

faster-routes:

So basically looks like I'm doing something wrong or maybe there's still more to be done ;) Anyway the speed is impressive tho

[TurtIeSocks]

Appreciate the head to head comparison! You're not doing anything wrong though, I think clustering results for pokestops and gyms are roughly matched/superior with Koji (though much faster), but spawnpoint clustering still needs some work.

Unfortunately, it needs an entirely different approach though as the current algorithm is spaghetti code. The current thought process is to make a new algorithm based around S2 cells, so I'm working on some groundwork in the meantime before I jump back into clustering hell.

Thanks!

[jfberry]

The honeycomb style that koji uses here means it will likely have better performance for event days where there are more spawnpoints. It’s a good comparison.

[kamieniarz]

I'm back with results after merging #132 ;)

Same area, 5009 spawnpoints
Faster-routes: 505 routepoints (still)
Koji (brute force, cluster split level 10): 542 routepoints
Koji (fast): 664 routepoints
Koji (balanced): 552 routepoints - seems pretty much the same as in first post where it was 550

Honestly no idea what cluster split level does tho. I changed it to 1 and result was the same but with 15 it was 593

Here's a screenshot of Koji's route (the first one, brute force) which looks more like faster-route's one, so it's not that regular as it was before (or as it still is now when using fast or balanced cluster method). But this time I see a lot of spawnpoints out of routepoints...

So yeah, brute force looks better but it's still not it, at least when it comes to same settings as in first post -> min points = 1. Basically from my point of view it's not better cause maybe route is shorter but it missed some spots which is not good. But visually route looks better so I hope that's a good sign ;)

[Jebula999]

Just adding on to this.
Can confirm "Brute Force" set to 1 "Min Points" leaving out quite a few points.

[TurtIeSocks]

@kamieniarz @Jebula999 can you test #200, please?

[kamieniarz]

Ok so I'm not quite sure if that's the same area but I guess it is: 5167 spawnpoints in it currently.
Basically same settings as in my first message here - also min points = 1 and on each tries from below all points are covered

-	Koji fastest	Koji fast	Koji balanced	Koji better	faster-routes
Calculation time	<1 sec	<2 sec	~2 sec	~21 sec	~17 min
Route length	687	547	508	484	518

So generally I see huge improvement here 💪 I checked all routepoints visually and looks like there's no spawnpoints left behind. What is different is route optimization - I see few long jumps (with red line and some with yellow line) but I guess it's not a bad thing anymore, right? At least not with Atlas I guess. If you're looking for more Koji improvements then that's the only thing I found here.
Anyway I guess I'll just update all my routes now and monitor how my TTH look like in general. If numbers are going to be not worse than they are now looks like we have like ~6-7% less routepoints (and way better calculation time) when compared Koji's better algorithm with faster-routes which was in my case the best routes tool by now 🎉

[TurtIeSocks]

Thanks for the tests, glad Koji is finally putting out some good numbers!

The routing algorithms shouldn't have changed. What do you have sort_by (or Sort By in UI) set to? You'll need to use TSP to take advantage of OR-Tools and get proper routing.

[kamieniarz]

O have geo-hash (proly default?). I'll play with that and see how it goes, lots of options I see there ;) Thanks a lot! Since I'm the OP I'm ready to close this issue but I'll leave it open for some time cause maybe others may have some observations