multimax does not maximize the number of layers

[le-jeu]

The heuristic used in multimax.js is

at each step, select the portal that covers the most portals.

In some real cases, this does not maximize the number of layers.

In this example, the current algorithm will select the red multi layers instead of the orange one.

[crystalwizard]

how are 3 small layers better than 2 big ones covering more area?

I'd rather see options to multimax - one for max layers, one for max space - than to just change the math to always go for the most layers at the expensive of area covered

[le-jeu]

Th heuristic does not care of the field size but the number of portal under the field, assuming that it will find more layer this way. I guess the previous figure is not relevant enough

[crystalwizard]

I still think it would be better to have 2 options - max number layers, max layer size (in mu) - instead of forcing one or the other. I will deliberately pick less layers if the fields go over a more population dense area than several layers going over an area with lower population.

[cloudkucooland]

But that heuristic is only HALF the algo. The Partially-ordered-set (buildPOS) step should still pick the orange route, not the red.

@QPotato

[cloudkucooland]

The PR looks good, but it will need to go through testing. Please cancel it and re-do it on the 017_FEATURES branch.

[cloudkucooland]

I still think it would be better to have 2 options - max number layers, max layer size (in mu) - instead of forcing one or the other. I will deliberately pick less layers if the fields go over a more population dense area than several layers going over an area with lower population.

MM should get maximum layers. If that set fails to maximize MU, take care of that by zooming in on the proper area or using exclude markers to force it. MM cannot know about a regions MU and makes no assumptions about field size; it is only concerned with # of layers. If my implementation of @QPotato 's algo was wrong (and it appears to have been) then it ought to be fixed.

[le-jeu]

I still think it would be better to have 2 options - max number layers, max layer size (in mu) - instead of forcing one or the other. I will deliberately pick less layers if the fields go over a more population dense area than several layers going over an area with lower population.

On huge field, the max number of layers should also maximized the amount of MU captured.

[QPotato]

Hi! A lot of stuff to cover here.

1. In depth explanation of the algorithm here.

2. The heuristic used in multimax.js is

   at each step, select the portal that covers the most portals.

The comment in the code is wrong. It would be more clear to say "at each step, select the portal that covers the longest chain of sequentially covering portals". The number of portals under a field is not used as heuristic.

3. On number of layers vs MU count: yes, indeed in very rare edge cases, less layers can give you more MU. It happend to me in the Cordoba province in Argentina. Generally, in this cases the planner can use his field knowledge to just frame the viewport better and do the multimax in the area wanted. The intended use is (or was, when i first coded this) to multimax over zoomed in towns. The decision of wich town to choose is still a human planner decission.

That said, if you had a function from Field to MU count, you could just replace the comparing function in the algo to maximize MU in the chain at each recursive step. This would yield the best plan wether it's the longest sequence or not, but..

4. There is no current way to have a function from Field to MU count. I've discussed this before with other agents. The available options are: 4.1. A database of fields with it's actual MU output. Then you query recorded ones or do interpolation for missing ones. This is against the ToS. Be free to do this privately for scince and fun, but we can't add this. 4.2. Use a population density database as heuristic. Problem with this is that unless you know for sure the exact database used by Niantic, it will be inaccurate in some places. The database should be server-side and would dramatically increase server load.

Hope this helps. I'm happy to keep discussing this.

[le-jeu]

Your algorithm works. I have just look into the git log and I found that the implementation changed here to the current algorithm, breaking it https://github.com/wasabee-project/Wasabee-IITC/commit/763526cb0071f4a5386b0e8182953a8559196ee6#diff-29b4284d9bc6a6cf5c56e01c7e964549

https://github.com/wasabee-project/Wasabee-IITC/blob/c803c87cd263127fcb16caddbdd285d029050fb8/src/code/dialogs/multimaxDialog.js#L265-L308

But I guess the line 111 had side effect since an Array is a mutable object. https://github.com/wasabee-project/Wasabee-IITC/blob/f84a38fa2ef9b00f84e360fd832f8ed575d7a97c/src/code/multimax.js#L102-L119

Duplicate the array would probably solve the issue. I vouch for for your code that is really nice implementation.

[cloudkucooland]

calling this one fixed