jpeterbaker / maxfield

Code for maximizing the Ingress fields on a given set fo portals
GNU General Public License v3.0
165 stars 56 forks source link

use a greedy total path length optimizer to improve path length #34

Open mvinni opened 8 years ago

mvinni commented 8 years ago

This commit significantly reduces the length a single agent needs to move in order to complete a maxfield operation. Using the EXAMPLE.csv file, whereas the master version gives paths with lengths like: 33677 m, 25036 m, and 26641 m; this version gives: 13509 m, 11181 m, 13447 m.

This is implemented by recording which individual edges should be done before the final edge of each triangle, and greedily re-ordering edges within those limits as long as improvement is happening.

I have tested it quite a bit [*] and believe it works. However, while testing on top of 418afc7e93b2190e772828b24913c22aa6d5070f (master) one should be careful, since that version appears to produce bad results (source portals inside already completed fields) about half of the time with EXAMPLE.csv as the input (if this is not a known issue, I might report it properly).

Thoughts?

([*] mostly on top of the version by @tvwenger, where this patch applies as-is)

mvinni commented 8 years ago

Added a second commit to fix the bad output. This is necessary even without the length improvement code.

------------------------------- lib/Triangle.py -------------------------------
index a466a57e1f0d..fff3d05e873e 100644
@@ -19,7 +19,7 @@ def try_reduce_out_degree(a,p):
     # Reverse as many edges out-edges of p as possible
     toremove = []
     for q in a.edge[p]:
-        if a.out_degree(q) < 8:
+        if a.out_degree(q) < 8 and a.edge[p][q]['reversible']:
             a.add_edge(q,p)
             a.edge[q][p] = a.edge[p][q]
             toremove.append(q)