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

Speedup parts of the triangulation #20

Closed mvinni closed 4 years ago

mvinni commented 7 years ago

Avoid using some NetworkX functions in hot code paths. Some functions, like Graph.size() to get the number of edges in a graph, were showing up taking surprising amounts of time.

Don't split triangles unnecessarily early, because the results of the split are often discarded as soon as the triangulation hits a dead-end.

This works best with #18. Otherwise the time taken in improveEdgeOrderMore shadows these improvements. With these two pull requests the program has produced plans for up to 500 portals in less than 70 seconds most of the time (--attempts 1 --skipplot, on a mediocre laptop). Without this, it was very hard to get results even for 100 portals.

tvwenger commented 4 years ago

Rendered irrelevant due to new version. Have a look at the new version and let me know if you can find any ways to improve it!