search

tvwenger / maxfield

An Ingress Linking and Fielding Strategy Generator
http://www.ingress-maxfield.com/
GNU General Public License v3.0
107 stars 58 forks source link

Improve path length by more than 50 % #2

Closed mvinni closed 8 years ago

mvinni commented 8 years ago

Here is a suggestion to improve the output of maxfield to be much shorter. For example, for the courtsquare.portals example input, for one agent, the suggested route is:

Total time estimate: 17 minutes
Agent distance:   1008 m
Agent experience: 43140 AP

compared with the

Total time estimate: 28 minutes
Agent distance:   2294 m
Agent experience: 43140 AP

of the unmodified code.

In my tests the length improvement of the route for one agent has been typically more than 50 %, but naturally it depends on the randomization. For more agents the benefit may be smaller, but I don't have any figures for that.

There probably are still easy improvements to be made to the algorithm. The most common error result for a bad modification is two (or more) triangles forming on the same side of a link at the same time (getting a field and AP only for the largest). So, anybody experimenting with the code should keep an eye open for those. I have run the code through automatic tests some hundreds of times, and this version so far has not failed.

(originally I submitted a pull request to the "upstream" at https://github.com/jpeterbaker/maxfield/pull/34, but so far received no response there; perhaps the website users would benefit of these changes)

tvwenger commented 8 years ago

Thanks! I have some other changes to incorporate soon as well. I'll work on this as soon as I can!

tvwenger commented 8 years ago

Hi, I've just updated the code with some of jpterbaker's changes and they significantly improve the agent walk time. Feel free to submit another pull request if you notice any other changes that could be made to make it more efficient.