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 performance for large number of portals #17

Closed pwiecz closed 6 years ago

pwiecz commented 7 years ago

I was playing recently with maxfield for a large number of portals (150) and found out that it was extremely slow. The slow part was generating a feasible triangulation. I've found a way to change the triangulate method to work quickly on my set of portals, but as I don't understand the existing algorithm well enough, I don't know if I don't break some property of the solution.

Right now the algorithm produces the triangulations of the perimeter portals such that the "final" portal for each triangle is never shared between two triangles. If I dropped this requirement and tried all the possible positions of the "final" portal when I split off a Triangle from the perimeter, the algorithm finds a triangulation of the 150 portals within a second. Actually, if I use another triangulation strategy which also don't care about the position of the final portal on the perimeter, I am able to triangulate even faster and usually generate solutions with shorter expected walk time, but that's beside the point.

My question is, where does this requirement about positions of the final vertices on the perimeter come from? I think it's worth having an option to ignore this requirement at least behind a flag, so that we can feasibly run maxfield for large portal sets.

What are your thought?

ghost commented 7 years ago

I also used maxfield to plan a multifield of 104 portals. It's current process. 44% (44/100 iterations) : 39h 15m 05.47s
Xeon(R) CPU E5-26xx 2.3GHz,DDR3

tvwenger commented 7 years ago

@pwiecz Can you confirm that your method creates the same number of fields as the current method? This algorithm was designed by @jpeterbaker to be optimal.

pwiecz commented 7 years ago

It creates the same number of fields. I just don't understand the current algorithm well enough, to tell if it creates the correct link order (e.g. maybe edge dependency depends on the current triangulation algorithm). I'm now trying to understand the code better (but I currently don't have much spare time :/ ).

mvinni commented 7 years ago

When I was developing the improveEdgeOrderMore stuff, I found automated validation of the generated plans very useful. To that end, you may find the last commit on this branch useful: https://github.com/mvinni/maxfield-1/tree/verify

This is the commit message:

add an option to validate the linking plan

    Use --check (or -c) to verify that the plan produced
    by the program does not contain some obvious errors.
    The checks are:
     - the source portal of a link should not be inside a field
     - a link can generate at most one field on each side
mvinni commented 7 years ago

I have been testing with an input of 119 portals, and managed to get the running time down from about 2 minutes to 22 seconds with the exact same settings. I don't want to send a pull request before testing with even bigger inputs, but the current patches can be seen at https://github.com/mvinni/maxfield-1/commits/speedup

Maybe these are useful for others as well.