*There aren’t individual dated entries, but this is basically a dev blog. I’m recording my thoughts and findings as I discover how MU is calculated in Ingress. Once I have a good theory and some kind of field planning tool as a result, I’ll write an article about it.*

The consensus among redditors (see KevinC for example) seems to be that MU is calculated by computing coverage of s2 cells with an s2 cell to population database. It’s claimed that portal data can’t explain observed MU numbers and in particular the rare case where a large field has less MU than a smaller field it completely encloses. To my thinking, such anomalies are better explained by using area of the triangle and per-portal weights than an s2-based database. Also, area as opposed to say leg lengths better explains the so-called Divide by Zero bug that once existed.

Unfortunately, nobody has shown their work to disprove portal weights. So here goes…

Assuming the formula is (p1+p2+p3)*area = MU, where pi is some population factor that gets baked in to the portal data when the portal is created, then a single field gives us one equation with three unknowns. If we add a 4th point and consider 4 triangles (abc,abd,acd,bcd), then we have 4 equations and 4 unknowns which will allow us to solve for the portal weights of those particular portals. Using a 5th portal with three of the previous portals will give us another system of 4 equations and 4 unknowns that can be used to verify the original computed weights.

There is one other unknown. We don’t know exact MU. If your field is worth 8.1425 MU, you’ll be awarded 8 MU or maybe 9 MU depending on whether they floor, ceil or round. So with the data collected from any 4 portals, we have a system of linear equations sort of.

p1 + p2 + p3 = MU123/area123 where i<MU123<i+2 for some integer i p1 + p2 + p4 = MU124/area124 where j<MU124<j+2 for some integer j p1 + p3 + p4 = MU134/area134 where k<MU134<k+2 for some integer k p2 + p3 + p4 = MU234/area234 where l<MU234<l+2 for some integer l

So, we can’t solve for exact p1,p2,p3,p4. We can solve for ranges for each. Adding more data will either refine those ranges or disprove the assumption that the formula is correct. If we disprove the formula, we can try line segment lengths. If line segments lengths can be similarly disproven, we can try to deduce the s2 levels and population data at those levels for the area spanned by these particular fields. Given the number of s2 levels, that seems pretty daunting.

# Data collection

In the first data collection outing, I made the mistake of making a layered field and got less data than intended.

The initial 4 portals are (p1) Metamorphosis in the Northwest, (p2) East Memorial Wall in the Northeast, (p3) Memorial Fountain in the center and (p4) South Lawn Memorial in the South.

For areas, we’ll want to use a spherical geometry area. The google maps geometry library had an area function that can be used.

let triangle = [new google.maps.LatLng(47.488078,-122.169664), new google.maps.LatLng(47.486942,-122.171348), new google.maps.LatLng(47.485165,-122.172433)]; let area = google.maps.geometry.spherical.computeArea(triangle); console.log(area);

p2,p3,p4 was 8 MU (so actual MU was greater than 7 and less than 9) and the area of the triangle 47.488078,-122.169664 to 47.486942,-122.171348 to 47.485165,-122.172433 is 7368.210755235674 (square meters)

p1,p2,p3 was 17 MU (so actual MU was greater than 16 and less than 18) and the area of the triangle 47.48793,-122.173166 to 47.488078,-122.169664 to 47.486942,-122.171348 is 15613.401138994961 (thank goodness it wasn’t between 16k and 18k. That first one had me nervous).

It took a while to get data for the other triangle and in the meantime I realized why MU can’t be computed just at the portals. If you make a very large field with 3 remote mountain portals, the MU is much higher if there’s a city in between than if there isn’t. While pondering this, I also realized that while we can never get the underlying population map used by Niantic, we can get a very good approximation by making small fields like this and using Voronoi regions around the portals. Collecting enough data to map a region would be tricky. Scraping comms, in addition to being unethical and a violation of the TOS, wouldn’t work because you have to guess which links are in the field unless you scrape so much data that you have every link created and every resonator destroyed. Anyway…

p1,p3,p4 is 17 MU. This triangle has an area of 18014.800858524974

The big triangle, p1,p2,p4 is 42 MU with an area of 40996.4127527556.

And as an added bonus, a new portal in the mix is p5, Jimi Hendrix Memorial

p1,p4,p5 is 13 MU. It has an area of 13387.71415. We’ll get back to Jimi in the next round of linear equations. With the original 4 portals, we now have 4 equations for the 4 unknowns. Excel has matrix multiplication, so we can paste the data into Excel and get the answer. Excel also has a “spin button” that lets you put in a field that can easily be limited to a range so we can do the ±1 thing with the MU values to get the range for the portal weights.

Today I learned that the spin button only supports integer values. No biggie. I also discovered that cranking all the MUs to their max and min does not give the max and min values of the variables being solved for. That was a naive hope. I’ll have to think more about solving systems Ax=b for x when it’s really solving Ax=b(range) for x(range). Here’s the Excel.

The formula in B8:B11 is {=MMULT(MINVERSE(A2:D5),E2:E5)}. The mid, min and max columns are the pasted values of the solutions when all of the MUs are at their min (reported MU – 1), their mid (reported MU), and their max (reported MU+1). The two unlabeled columns in the bottom right are the min and max of columns B through F. With all of the MU at max, I nudged the first MU value down from 18 to 17.9 and got a new min for p1. So how to find the ranges for p1, p2, p3 and p4? Linear programming doesn’t quite fit. Or I’m just not seeing how to construct the objective function.

We’re solving the wrong formula since the right formula is going to be intersecting the triangle with s2 cells of population data (or some other map layer with population data), but for the sake of completion, let’s plow on with the wrong approach.

(1) w + x + y = A (2) w + x + z = B (3) w + y + z = C (4) x + y + z = D A bunch of sloppy and error prone algebra later... (it seems like there should be more symmetry in the solution) w = (4A-5B-C-2D)/3 x = (A-4C+D+B)/3 y = (A+5C+D)/3 z = (D-2A+B-C)/3

So… in the Excel sheet, p1 should be maxed with the first range maxed and the other ranges at their minimum. And that seems to be the case. Yay!

Some subset of these portals is going to have the same underlying population constant, but it’s not uniform for all of the portals. We know that because two very different areas, 15k m^2 and 18k m^2 both produced 17 MU. p1,p2,p3 has a higher underlying population than p1,p3,p4. East Memorial Wall must be close enough to the neighborhood east of the graveyard to have a higher population. To find the population of the graveyard, we’ll have to gather MU numbers from lots of triangles within the graveyard that have consistent MU to area ratios.

The areas of the triangles for ~~all~~ the portals in the Greenwood Memorial Park (computed as above) are:

Area | MU | Area/MU | Area/(MU-1) | Area/(MU+1) | |

Metamorphosis – Memorial Fountain – South Lawn Memorial | 18014.80086 | 17 | 1059.694168 | 1125.925054 | 1000.82227 |

East Memorial Wall – Memorial Fountain – South Lawn Memorial | 7368.210755 | 8 | 921.0263444 | 1052.601536 | 818.6900839 |

Metamorphosis – East Memorial Wall – Memorial Fountain | 15613.40114 | 17 | 918.4353611 | 975.8375712 | 867.4111744 |

Metamorphosis – East Memorial Wall – South Lawn Memorial | 40996.41275 | 42 | 976.1050655 | 999.9125062 | 953.4049477 |

Metamorphosis – Jimi Hendrix Memorial – South Lawn Memorial | 13387.71415 | 13 | 1029.824165 | 1115.642846 | 956.2652962 |

Garden of Harmony – Love Forever Headstone – Fish Fountain | 2100.091108 | 2 | 1050.045554 | 2100.091108 | 700.0303692 |

Garden of Harmony – Iu-Mienh Community Memorial – Fish Fountain | 2475.688882 | 2 | 1237.844441 | 2475.688882 | 825.2296274 |

Iu-Mienh Community Memorial – Fish Fountain – Prisoner of War Memorial | 2119.202046 | 2 | 1059.601023 | 2119.202046 | 706.400682 |

Love Forever Headstone – Fish Fountain – Prisoner of War Memorial | 3727.706351 | 4 | 931.9265877 | 1242.568784 | 745.5412702 |

Garden of Harmony – Iu-Mienh Community Memorial – Fountain of Youth | 3235.965542 | 3 | 1078.655181 | 1617.982771 | 808.9913854 |

Garden of Harmony – Love Forever Headstone – Remembered Forever | 3271.658364 | 3 | 1090.552788 | 1635.829182 | 817.9145911 |

Garden of Harmony – Remembered Forever – Fountain of Youth | 3170.971246 | 3 | 1056.990415 | 1585.485623 | 792.7428115 |

Yeah Yeah Thanks Puddin – Remembered Forever – Fountain of Youth | 5989.928659 | 6 | 998.3214432 | 1197.985732 | 855.7040942 |

Iu-Mienh Community Memorial – South Lawn Memorial – Prisoner of War Memorial | 9797.498726 | 9 | 1088.61097 | 1224.687341 | 979.7498726 |

Lullabyland Memorial – South Lawn Memorial – Prisoner of War Memorial | 3368.271922 | 3 | 1122.757307 | 1684.135961 | 842.0679805 |

Lullabyland Memorial – Sun Dial – South Lawn Memorial | 3579.065871 | 3 | 1193.021957 | 1789.532936 | 894.7664678 |

Lullabyland Memorial – Love Forever Headstone – Prisoner of War Memorial | 3508.57649 | 3 | 1169.525497 | 1754.288245 | 877.1441224 |

Lullabyland Memorial – Renton Aerie No 1722 F.O.E. – Love Forever Headstone | 8879.929826 | 9 | 986.6588695 | 1109.991228 | 887.9929826 |

Lullabyland Memorial – Renton Aerie No 1722 F.O.E. – Sun Dial | 6078.770277 | 6 | 1013.12838 | 1215.754055 | 868.3957539 |

All to Myself I Think of You Memorial – Renton Aerie No 1722 F.O.E. – Sun Dial | 10618.79058 | 11 | 965.3445984 | 1061.879058 | 884.8992152 |

All to Myself I Think of You Memorial – Renton Aerie No 1722 F.O.E. – Cedar View Memorial | 13253.79664 | 17 | 779.6350964 | 828.3622899 | 736.3220355 |

The S2 region cover of Jimi looks like this:

The next step is to get the S2 cells and the portals on the same map to be able to determine which fields span which levels of S2 cell cover. I downloaded the S2 geometry library and tried to get it to spit out reasonable amounts of data about the S2 subdivisions in the area I play, NR13-ROMEO-08, in a format that can be used from javascript with the google maps API.

I had a clever idea that failed. The thinking goes like this… if you take the bounds of the level 6 S2 cell that you’re interested in and subdivide it into 4 cells, you’ll have the level 7 cells. My mistake was doing a linear subdivision (linear in terms of lat/lng values). I split the cell by using a parametric equation along the edge. Comparing the linear subdivision of the level 6 cell into 64 segments along each edge with the actual level 12 cells, it’s way off. Blue is correct. Red is linear subdivision.

The code for subdividing in javascript looks like this:

new google.maps.Polygon({ path: [{"lat":47.994058,"lng":-122.242468},{"lat":47.430873,"lng":-123.977276},{"lat":46.457519,"lng":-122.693956},{"lat":46.984342,"lng":-120.994610}], strokeColor: '#0000FF', strokeOpacity: 0.5, strokeWeight: 1, fillOpacity: 0, map: map }); // If that's the level 6 cell and we use a parametric line for subdivisions // level 7 is 0.5 // level 8 is 0.25, 0.5, 0.75 // level 9 is 1/8, 1/4, 3/8, 4/8, 5/8, 6/8 // level 10 is 16ths // level 11 is 32nds // level 12 is 64ths // So... 64ths in red let p0 = {"lat":47.994058,"lng":-122.242468}; let p1 = {"lat":47.430873,"lng":-123.977276}; let p2 = {"lat":46.457519,"lng":-122.693956}; let p3 = {"lat":46.984342,"lng":-120.994610}; for (let t = 0.0; t < 1.0; t += 1.0/64.0) { // Line from a point on p0-p1 to a point on p2-p3 let start = {"lat": t*p0.lat + (1-t)*p1.lat, "lng": t*p0.lng + (1-t)*p1.lng}; let end = {"lat": t*p3.lat + (1-t)*p2.lat, "lng": t*p3.lng + (1-t)*p2.lng}; new google.maps.Polyline({ path: [start, end], strokeColor: '#FF0000', strokeOpacity: 0.5, strokeWeight: 1, map: map }); // Line from a point on p1-p2 to a point on p3-p0 start = {"lat": t*p1.lat + (1-t)*p2.lat, "lng": t*p1.lng + (1-t)*p2.lng}; end = {"lat": t*p0.lat + (1-t)*p3.lat, "lng": t*p0.lng + (1-t)*p3.lng}; new google.maps.Polyline({ path: [start, end], strokeColor: '#FF0000', strokeOpacity: 0.5, strokeWeight: 1, map: map }); } }

The code for generating the actual cell coverage looks like this:

S2LatLngRect rect; S2LatLng point; point = S2LatLng::FromDegrees(47.416464, -121.874288).Normalized(); rect.AddPoint(point); point = S2LatLng::FromDegrees(47.859055, -121.705051).Normalized(); rect.AddPoint(point); point = S2LatLng::FromDegrees(47.661905, -122.436668).Normalized(); rect.AddPoint(point); point = S2LatLng::FromDegrees(47.373463, -122.395961).Normalized(); rect.AddPoint(point); std::FILE * outFile; outFile = std::fopen ("s2cells.json","w"); std::fprintf(outFile, "{"); char levelDelimiter[8]; std::strcpy(levelDelimiter,""); for (int level=12; level<17; level++) { S2RegionCoverer::Options options; options.set_max_cells(100000); options.set_min_level(level); options.set_max_level(level); S2RegionCoverer coverer(options); std::vector<S2CellId> cells; coverer.GetCovering(rect, &cells); std::printf("Level %d produced %lu cells\n", level, cells.size()); char cellDelimiter[8]; std::strcpy(cellDelimiter,""); std::fprintf(outFile, "%s\"l%d\":[", levelDelimiter, level); std::strcpy(levelDelimiter, ","); for (auto id : cells) { std::fprintf(outFile, "%s", cellDelimiter); std::strcpy(cellDelimiter, ","); S2Cell cell(id); char delimeter[8]; std::strcpy(delimeter, ""); std::fprintf(outFile, "["); for (int i=0; i<4; i++) { S2LatLng point(cell.GetVertex(i)); std::fprintf( outFile, "%s{\"lat\":%f,\"lng\":%f}", delimeter, point.lat().degrees(), point.lng().degrees() ); std::strcpy(delimeter, ","); } std::fprintf(outFile, "]"); } std::fprintf(outFile, "]"); } std::fprintf(outFile, "}"); std::fclose(outFile);

But… I think with the lat/lng points of the correct subdivisions along the edges, we can get a minimal amount of data out of the S2 library that can be used to quickly generate the tilings in the browser.

That subdivisions along the edges thing didn’t work out at all. Given one of the level 6 S2 cell edges, the region coverer generates cells for a very large area, the axis aligned bounding box perhaps. Maybe I should do an S2 geometry library to javascript Emscripten port. In the meantime, here’s how the portals in questions align with the S2 cell tilings.

Level 14:

Level 15:

Level 16:

Of the fields for which we already have data, one of them is entirely in level 14 cell 549067df, 14 are entirely in549067e1, and 6 span both cells. We’ll need more data for the northeast cell before we draw any conclusions about it or about the fields that span cells. For the 14 in the south west level 14 cell, a population weight of 1050 with area/1050 rounded to the nearest integer produces the observed MU values.

These fields are all entirely within 549067df and are consistent with MU = round(area/780).

Area | MU | |

Cedar View Memorial – Greenwood Memorial Geometrical Fountain – East Memorial Wall | 1400.730006 | 2 |

Little Free Library At Heritage Park – Greenwood Memorial Geometrical Fountain – East Memorial Wall | 13480.33324 | 17 |

Basketball Half-Court At Heritage Park – Cedar View Memorial – East Memorial Wall | 7843.978627 | 10 |

Little Free Library At Heritage Park – Basketball Half-Court At Heritage Park – East Memorial Wall | 23026.86693 | 30 |

All to Myself I Think of You Memorial – Cedar View Memorial – Renton Aerie No 1722 F.O.E. | 13253.79664 | 17 |

One of the fields that spans both cells is Metamorphosis – East Memorial Wall – Memorial Fountain. Using the s2 geometry library, we can find the polygon which represents the intersection of that field with the cell 549067e1. Using the google maps geometry library, we can compute the area of the intersection as 8200.853169199234. If we divide that by 1050, we get 7.810336351618318.

The intersection of that field with cell 549067df has an area of 7406.250730416166. Dividing that by 780 gives is 9.49519324412329.

The sum of these is 17.305529595741608. The actual MU that we observed for the field is 17. So far so good.

Applying this method to all of the portals, we confirm that the guesses of 1050 as a divisor for cell 549067e1 and 780 for cell 549067df works with all the sampled fields. So the next step will to be gathering data for adjoining cells to start filling out the local map of population factors.

Area | MU | 549067e1 area | 549067df area | 549067e1 MU | 549067df MU | Calculated MU | |

Metamorphosis – East Memorial Wall – Memorial Fountain | 15613.40 | 17 | 8200.85 | 7406.25 | 7.81 | 9.50 | 17 |

East Memorial Wall – Memorial Fountain – South Lawn Memorial | 7368.21 | 8 | 5374.66 | 2006.06 | 5.12 | 2.57 | 8 |

All to Myself I Think of You Memorial – Renton Aerie No 1722 F.O.E. – Sun Dial | 10618.79 | 11 | 7490.62 | 3128.51 | 7.13 | 4.01 | 11 |

Metamorphosis – East Memorial Wall – South Lawn Memorial | 40996.41 | 42 | 31590.68 | 9411.94 | 30.09 | 12.07 | 42 |

Lullabyland Memorial – Renton Aerie No 1722 F.O.E. – Love Forever Headstone | 8879.93 | 9 | 8432.42 | 445.28 | 8.03 | 0.57 | 9 |

Lullabyland Memorial – Renton Aerie No 1722 F.O.E. – Sun Dial | 6078.77 | 6 | 5796.84 | 283.38 | 5.52 | 0.36 | 6 |

All to Myself I Think of You Memorial – Renton Aerie No 1722 F.O.E. – Cedar View Memorial | 13253.80 | 17 | 0.00 | 13253.80 | 0.00 | 16.99 | 17 |

Love Forever Headstone – Fish Fountain – Prisoner of War Memorial | 3727.71 | 4 | 3727.71 | 0.00 | 3.55 | 0.00 | 4 |

Yeah Yeah Thanks Puddin – Remembered Forever – Fountain of Youth | 5989.93 | 6 | 5989.93 | 0.00 | 5.70 | 0.00 | 6 |

Metamorphosis – Jimi Hendrix Memorial – South Lawn Memorial | 13387.71 | 13 | 13387.71 | 0.00 | 12.75 | 0.00 | 13 |

Garden of Harmony – Love Forever Headstone – Fish Fountain | 2100.09 | 2 | 2100.09 | 0.00 | 2.00 | 0.00 | 2 |

Garden of Harmony – Remembered Forever – Fountain of Youth | 3170.97 | 3 | 3170.97 | 0.00 | 3.02 | 0.00 | 3 |

Iu-Mienh Community Memorial – Fish Fountain – Prisoner of War Memorial | 2119.20 | 2 | 2119.20 | 0.00 | 2.02 | 0.00 | 2 |

Metamorphosis – Memorial Fountain – South Lawn Memorial | 18014.80 | 17 | 18014.80 | 0.00 | 17.16 | 0.00 | 17 |

Garden of Harmony – Iu-Mienh Community Memorial – Fountain of Youth | 3235.97 | 3 | 3235.97 | 0.00 | 3.08 | 0.00 | 3 |

Iu-Mienh Community Memorial – South Lawn Memorial – Prisoner of War Memorial | 9797.50 | 9 | 9797.50 | 0.00 | 9.33 | 0.00 | 9 |

Garden of Harmony – Love Forever Headstone – Remembered Forever | 3271.66 | 3 | 3271.66 | 0.00 | 3.12 | 0.00 | 3 |

Lullabyland Memorial – South Lawn Memorial – Prisoner of War Memorial | 3368.27 | 3 | 3368.27 | 0.00 | 3.21 | 0.00 | 3 |

Lullabyland Memorial – Love Forever Headstone – Prisoner of War Memorial | 3508.58 | 3 | 3508.58 | 0.00 | 3.34 | 0.00 | 3 |

Lullabyland Memorial – Sun Dial – South Lawn Memorial | 3579.07 | 3 | 3579.07 | 0.00 | 3.41 | 0.00 | 3 |

Garden of Harmony – Iu-Mienh Community Memorial – Fish Fountain | 2475.69 | 2 | 2475.69 | 0.00 | 2.36 | 0.00 | 2 |

*Time passed*

The method for finding and verifying the cell weights was really painful because it involved looking at portals and fields in a browser, calculating areas in javascript in a browser, but computing cell coverings and finding the intersections of fields with cells in C++. So I took a break from data collection and analysis to write a web server in C++ that could do the s2geometry work of finding cell polygons and calculating intersections and serve the resulting data back to the javascript browser client. That work is here.

Now I’m deciding if I want to go back to data collection and analysis now or do the next programming task. If I go back to data, I’ll be typing field coordinates into an html file and I’ll be copy-pasting from the javascript console in chrome to Excel to find cell weights that work. The alternative is entering the fields with clicking on map markers and typing the MU values into a dialog box (for the data entry) and putting the output of the area calculations into a Google Sheets div. The “Excel” work could be done on the same page that has the map showing cell coverings and portals.

I think the answer is that I need to do some more data collection and analysis first. I haven’t yet determined if more than one s2 cell level is needed or what level it is if there’s only one. And there’s still the possibility that the population data actually used by Niantic is in some other form than s2 cells with per-cell weights. Once those questions are answered, it’ll make sense to invest in better tooling to eventually come up with an MU calculator for my play box.

And so level 12 cell 5490687. Is it all the same population value?

Things are happening!

It’s starting to look like something.

The try-numbers-in-Excel-until-it-seems-to-work method broke down, so I replaced it with an algorithm.

- For each field that intersects only one level 14 s2 cell, find a range of cell weights for that cell considering MU – 0.5 and MU + 0.5. If there is more than one field contained entirely within that cell, constrain the min/max weights using the max min and the min max.
- While something is found:
- For each field that hasn’t been “solved”
- If all but one of the intersecting cells has a range of weights, solve for that unknown cell weight using the known weight ranges.
- If all of the cells have ranges, constrain the largest range by solving for that cell weight.

- For each field that hasn’t been “solved”

In the above screen shot, dark blue represents more MU and light blue represents less MU. The missing pieces have ranges that are larger than 100. (Weights, remember, are MU = area in meters divided by weight. So they tend to be between 600 and 1000 in my neighborhood.)

I’ve got a few more fields for the missing chunk of 5490686c but it’s not solvable, ie the ranges of cell weights don’t overlap. This means that either some of the underlying population data is at a s2 cell level other than 14 or I made a data entry error. I’m going to assume the former and modify the algorithm so if it finds a cell that doesn’t have a solution, it subdivides just that cell into the higher s2 level and starts over. It looks like some of these are level 13. 54906874 for instance all seems to be the same shade of blue.

The current version of the code, in all its crufty hacked up glory, is on my s2geometry server github.

Same data with subdivision.

More data collection

The server in an docker container that almost works on S3:

docker pull gorlow/s2geometryserver

And I found this article that suggests a different way to calculate MU that is pretty compelling. It explains the rare but observable “bigger field has less MU than the smaller field it completely covers” phenomenon, whereas my approach doesn’t. It also is compelling because rather than finding weights to divide areas by, it uses a “how many people live in each level 13 cell” metric which is more concretely tied to the idea of “mind units.” So I’ll be changing the algorithm to try to solve that system of linear almost equations.