RFC - Features I am working on

[MikeDX]

Once the current dev (or master) branch is working properly again (at the moment, the dev branch seems to just skip pokemon, and master has the session token expire after an hour, so I'm currently stuck on my own branch), I will be working on the following for possible submission:

• [ ] Remote control - this will allow the creation of a simple file with a list of locations you can populate for the bot to "hunt". useful for providing a list of pokemon locations containing pokemon you want to catch. Instead of the bot looking for the next pokestop, it will head towards the next in the list. (waiting for websocket remote, the maybe change to a predetermined list of locations to visit)
• [ ] Transfer limit - Instead of keeping the best one of each type, this will be configurable so you can keep your best two of each type (like I do)
• [ ] Evolve before transfer - At present, the bot starts up, transfers all but one of each type (if specified) and then each loop checks for any evolutions. It would make much more sense to evolve first, and then discard any lower CP dupes and not have this run in each step. Possible re-running this evolve and transfer when the pokemon storage is full.
• [ ] Travelling salesman algorithm - Given a list of pokestops, have the bot calculate the best route between them to maximise farming in a given area.
• [ ] Command line args override - This one drives me bonkers having to edit the config every time I want to run the bot! It would be better I think to have the bot read the config file and then check the args for any overrides.
• [ ] Keep pokemon of any type if none in bag! - Currently if you come across a pokemon and it doesnt meet your CP / IV requirements, it gets discarded regardless! This is not good, I've "lost" various pokemon not yet in my collection due to the bot discarding even though I have none of that type. Should probably be kept the same way as the transfer limit as above so if you come across something youve not seen before, you still get to keep it.

I am not expecting any of these to be done by any others, these are not feature requests, but things I am currently working on to try to make the bot better for us all.

[ghost]

+1. Whoever pushed the changes to requiring a lame JSON file should be shot.

[Dekryptid]

My main gripe with the farming of the bot currently is that it doesn't farm all the pokestops in an area (watching the web map submodule). The Traveling Salesman algorithm would be an amazing addition to the bot and seem more "human-like" (hopefully not walk across water either. See below).

[Skeyelab]

(hopefully not walk across water either)

You don't carry a boat with you when you walk around?

[Skeyelab]

Evolve before transfer make a ton of sense.

[alexejw]

The traveling salesman problem is np hard. I would suggest to use the prim algorith to compute a minimal spanning tree with the bots location and the pokestops location as nodes. Then the bot can visit each node from the resulting tree in preorder.

[Dekryptid]

The evolve feature should be smarter. Based on the type of Pokemon, transfer certain amount, use lucky egg (if available), then evolve. Maximize XP gain.

[MikeDX]

@alexejw - It is NP hard but we can use an existing algorithm (pytsp comes to mind) to get a "good enough" solution. We don't want perfection, we just want something a bit better than randomly hitting pokestops all over town.

[MikeDX]

@Nurvx I agree, if the lucky egg flag is set then we should save all evolves to do at once.

Maybe a pidgey mode...

[douglascamata]

@MikeDX my thoughts about it: do your features as modular as possible.

About Travelling salesman algorithm: one guy on working on walking with Google Directions, I think his work is better than a raw salesman algorithm because it calculates the best REAL walking route from point to point. If you still want to work on this, please try to follow the separation we did between Navigator (calculates final destination, can be Spiral farming, Square farming, something to walk from one city to another, etc) and Walker (walk step by step to final destination, this is where your travelling salesman algorithm would go, IMHO)

[douglascamata]

@MikeDX remote control will be implemented later through web sockets. So I kindly ask you to wait for this. We already agreed on doing it with web sockets, but there are much more important refactorings and features that have higher priority.

[alexejw]

@MikeDX I agree that you can approximate the tsp. The suggestion with the prim-algorithm and then traversing the resulting tree in preorder will give us a tour, that is maximal double of the length of the minimum tour.

[MikeDX]

@douglascamata Don't worry, I have learned from the login issue :)

A best "real" route may not be "better" in some respects though, if we are just looking to farm all pokestops in a given area as quickly as possible. There was talk about having multiple navigation options, so I guess that would just be a decision made in the config as to which pokenav to use when deciding where to go.

I'm not going to work on anything in particular at the moment, as I said, the current dev and master branches are a mess as it is - hence this being an RFC and nothing more for the time being.

The command args vs config thing though really does drive me crazy...

[MikeDX]

@alexejw pytsp pre-calculates the list of pokestops to visit too - am I missing something?

[douglascamata]

@MikeDX yes yes, but remember that Navigators just tell Walkers in what direction to go. So a travel salesman algorithm is a Walker, not a Navigator. Google Direction algorithm is also a Walker, not Navigator. They seem a bit overlapping, but are very different. I hope you understood.

[MikeDX]

@douglascamata That seems backwards to me, I would have thought the navigator gives the walker the new location to head to, which it does until it reaches that point and then moves to the next? Why would a navigator tell the TSA which way to go? Shouldn't the TSA tell the walker where the new point is?

[alexejw]

@MikeDX the problem with pytsp is, that it is a interface to external solvers you can install. But the two listed solvers are only for academic use. We must implement a solver ourselves or use an open source solver with the right licence.

[MikeDX]

@alexejw Ah yes, I forgot about that issue...

[douglascamata]

@MikeDX did you check the Navigator examples that I gave? The navigator decides which place you want to reach from the current location at long term. The walker traces and walk (slowly) the route from current location to final destination, stopping at every small step for interaction with cells nearby (that doesn't require more movements).

[MikeDX]

@douglascamata That seems to work well for a google navigation walker since it only wants to go from A to B but a TSA would have a list of A B C D etc to tell the walker where to go, so that's where the confusion lies. Your google direction algorithm makes sense to "walk" from pokestop A to B using the roads, but the TSA would want to just tell the walker where the next one is on its list of locations (in this case the walker would just be a straight line or whatever)

[douglascamata]

@MikeDX oh shit, now I understand. But there is a workaround. Let's say TSA walker works like this: given an array of N-points, it applies the algorithm as expected and walk the route. Then it's the navigator responsibility to give as much points as possible to have the best route. In the worst situation it gets the best route between 2 points (a straight-line).

[douglascamata]

@MikeDX this ways it works perfectly for farming, because you know where all the pokestops you want to go are. You can even add pokestops that you don't know at runtime and reapply TSA to increase you farming route.

[alexejw]

@douglascamata @MikeDX if we reapply TSA with added pokestops we must exclude the pokestops with cool-down for 5 minutes.

[MikeDX]

This I why I love RFC (I get to ask questions without feeling like a dumbass)

@douglascamata So the TSA walker also needs a TSA navigator? Assuming the standard navigator only supplies 2 points (or one!). I am guessing that is what currently happens.

If we exclude the pokestops with the 5 minute cooldown we need to factor in how long it will take to get to that pokestop on the given route.. But I agree it needs to be taken into consideration - at present I have seen the bot bounce between two stops

[douglascamata]

@MikeDX The TSA walker works with any navigator. But to really take advantage of TSA the navigator needs to provide a good amount of points. As I already said, IMHO, perfect for farming. Did you have any objective with TSA before suggesting it? I would like to know.

[MikeDX]

@douglascamata The only real objective was to make the bot more efficient in a small area, just to maximize the stops visited and minimise steps taken - given that we need to travel at a (relatively) slow pace, it seems like a sensible option.

[alexejw]

@MikeDX we could make two groups of pokestops. One with cooldown. One without. Calculate for both the tsp approximation. Start visiting the pokestops without cooldown and at the end go to the start point of the tsp with cooldown. Of course with the shortest cooldown. It is just a idea and I do not know how good the idea is.

[th3w4y]

in the context of above...

if navigator wants to take a decision when/where to send a walker... i expect naturally it will use the distance to take that decision...

thus each walker should implement their own distance calculator method that will be callled by the navigator...

does this make sense? (in the polylinewalker i implemented such a method because the walk is not in a straight line...)

[MikeDX]

Why is this closed?

[douglascamata]

Lots of things in this PR were implemented already, we only miss TSA. I guess there is some issue cleanup going on.

[MikeDX]

@douglascamata I think that's a fair reason :)