rewrite the scanner

[ahicks92]

Pretty sure this isn't a duplicate but if it is then we can close the other. Everyone knows the scanner is slow. So much so that let's not bother with the background. @LevFendi strongly encouraged me to open this in order to make sure him and I are on the same page WRT the scanner must do. I do not expect the new one to be perfectly identical for things which aren't single entities.

1. What a Scanner Finds Today

This is supposed to be a complete list. If it isn't we should add some. I'm just assuming we can all agree that I know how to use the keys and leaving that out.

• For entities, you get one each aggregated by type and when relevant also recipe.
• For enemies they're grouped by the key (type, size) e.g. "small worm".
• Spawners are grouped by whether they're biter or spitter.
• Ore patches are found with a heuristic
• Forests are found with a heuristic
• Water is probably found with a heuristic but the new one will probably just use floodfill or something.

2. The Heuristic

This is one of the bigger open questions. I'll call it out with a heading because it's important. It's not easy to spot from the code. We need to fill this in with the old behavior.

The new behavior I propose is per-chunk entity searches. That is a chunk is a forest if you count >x number of trees, rather than whatever complicated thing we're trying to do today. Two adjacent forest chunks make the box for that forest larger. In the end you get a bounding box which is probably generally sort of right. Similar logic can apply to ore, but I have a better way of doing that contingent on us being okay with moving the cursor to the middle rather than the top left. Which imo we should be, for the very simple reason that the tutorial has a whole thing about cursor skipping to find it and most ore patches aren't squares anyway.

3. Sketching a Plan

I think we organize it like this:

• One central scanner module. It caches and knows how to call jout to submodules to find features.
• One module per feature to handle: entities, forests, ore, etc.
• One helper module primarily for sorters and things like aggregating ore/water.

We could apply a similar structure to warnings in future as well, which would let us add all the warnings all the people ask about.

Seems simple and it is, but the actual algos are what will take this project from simple organization to o my god wtf. Not really much design discussion to have beyond this unless someone less algo--savvy is going to take it. If it's not me then whoever does it needs to understand big-O because that's where today's problems appear to be.

[LevFendi]

The old heuristic for resource patches is that when a chunk gets charted, the mod runs an island builder function. An island refers to a collection of ore tiles that are all grouped together in the same area, and the same idea exists for water tiles and trees. The mod does this because a player is interested in a single ore patch in an area rather than 700 ore tiles.

Another part of the old heuristic is that every time the player runs a scan, the mod computes the nearest edge of each island and lists that as the position of the island. We recently found this to be the most time consuming aspect of the scanner and an idea was to massively simplify the nearest edge function so that the scanner runs faster.

[LevFendi]

I propose that we try to replace the existing nearest edge finder function with an O(1) dummy function that simply returns any point from the ore patch. Testing this out would let us know fixing the nearest edge function is all we need to do for fixing performance issues.

On the other hand, even if the performance is fixed, I suspect that you more importantly want a more organized scanner code. I think the current single module is not a nightmare to read, but it is difficult to modify beyond the few degrees of freedom that I have managed to add in the past. A rewrite with a better architecture may help us regarding future scanner changes.

[ahicks92]

Yes, I want more organized scanner code. I think it's only not a nightmare to you, though maybe you helped it out a lot since I last read it so I will look at it again and see if my opinion changes.

There's no way that 2.0 is going to let us get away without modifying it somehow or other. If it's still just new kinds of entities cool, but with the update as big as they claim I'm having trouble buying that. I can also think of possibly useful but possibly not ideas for things to put in it. For example it'd not be hard to actually expose factories as agregates and use that to let multiplayer people find each other, or expose "islands " of transport belts as a group, or who knows. Also earcons. So on.

The algorithmic problems are also--like maybe we fix that nearest edge thing but if we are talking about the same problem (which maybe we aren't) then okay we just pushed it back. Now we go fix up fast travel and diagonal cursor skipping and some other stuff that in general stops someone like me from megabasing. Now hold my beer, and prepare to punch the nearest wall when this just comes up again.

Plus our workaround to "there's invalid entities" is "run it twice" rather than fixing.

But in any case UI isn't ready to hatch yet exactly per discord discussions so I was going to explore this but I'm also open to short term wins wrt being what users care about. Maybe point me at the specific code you mean? The only one I'm thinking of is that thing where we pack positions into strings but the issue is that they're already packed when we get there. SO even if we return a constant we'd still have to untangle that. But if there is an easy short-term win then let's take it for the short term. On the other hand unless you want to do it, now's the time to deal with the bigger problem, because I've got time off and can deal with it after the fact when people inevitably find issues, being as they'd be my "fault" haha.

My optimization idea for the things like ore patches comes in two steps. Firstly given a list of ore entities what the player wants is the one that's the most, not the top left corner. Being consistent as a philosophy is good but I personally find it more trouble than it's worth because it just makes work for forests and patches, and even before that change the tutorial had to explain this. What I believe people really want is the "center of mass" if you will, and that's pretty easy to do and (if required for performance) pretty easy to approximate.

There's a few ways to abuse the above. I'm assuming that the case of individual entities is trivial. But for aggregates you can do binary searching based off the size of the search box (double it in size till it stops adding more; then binary search the size), or you can query chunk by chunk and say that any chunk over a certain percent of x is a x patch.

For water we can cache all the water forever until and unless we get told that a landfill tile is placed. I think there's an event for it. Nothing else vanilla changes water tiles. So that's a nice free thing to explore too.

For forests we can check destroyed trees and avoid rescanning forests we already know about by decreasing the count of trees attributed to that forest. That should also be a win if searching by chunks because vanilla never grows trees, though we should think about mods in this case.

[LevFendi]

Firstly given a list of ore entities what the player wants is the one that's the most, not the top left corner.

Not sure what this means. The scanner always first returns the nearest entity in a list. The top left corner is the part of the entity where the cursor lands when you index it. This does not apply to aggregate entities, which specifically return the nearest corner instead, with that high-time-complexity function that I want to remove.

[LevFendi]

I am on board with the new scanner plan, especially after hearing about your improvement ideas.

I assume the core module will be created first. We can talk about relevant questions as they get raised, such as what is the point of which precedence, what would be a better UX, et cetera.

Given your eagerness about this I am happy to let go of the old scanner when the new one is ready to replace it. It will definitely be a large technical debt being removed.

[ahicks92]

Right. As for ore/forests etc. What I'm saying is that the top left corner is more expensive to find than the thing the user wants and, indeed, sometimes the cursor doesn't even land on part of the patch. The flow for ore, at least for me, is:

• Scanner puts at top left corner.
• Spend a while figuring out the shape of it and where the center actually is, where center is defined as tile with most ore on it. That's in the tutorial and takes forever.
• Finally you can place rows of drills.

Forests are even more annoying because trees aren't "nice" about their layouts. So when you hit the top left of a forest half the time it's not a tree and skipping in straight lines will just happily go zipping through gaps. I hate forests for this reason.

My point being that consistency is great but in this particular case I'd almost go as far as saying that my experience is objective--you have to kinda undo what the scanner did if that makes sense. Obviously it's not literal, obviously the UX is actually doing extra. But if we have to teach players how to do this where the alternative is we just don't teach it anymore, and the "find nearest edge" stuff can just be dropped for everything but water...well, why not? It's both better and (at least compared to today) faster in terms of runtime.

Unfortunately wrt landing this kind of has to be done in one go so I'll have to test locally and then we'll have to get some adventurous people to, well, adventure. As for being eager I am powered by annoyance at code that annoys me but also this is very core. Like I could even maybe see a UI you can open one day and ctrl+f stuff or have a third level of some sort or something. I dunno what. But there's so many regular patterns in Factorio, surely we can easily recognize some. "This seems to be a bus" would not be hard to code at all. Hell, for the exceedingly ambitious maybe you could even hook AI of some sort up and be like AI-ify the important Factorio features or something. I dunno. But, imo, lots of room for innovation herein.

[ahicks92]

Dropping a few things we probably want to scan for today, rather than hypotheticals:

• Coal near water (steam)
• Uranium near water, iron, copper (mining uranium)
• Stone near iron (concrete)
• uranium near oil (also easier mining)
• water near oil (refineries)
• Places where the 4 basic resources are close enough together, AKA "alternative starting locations" (make your start a mall, then run off over there)
• Places without water maybe (tricky to represent and maybe another tool but man is water annoying). Also let's say without cliffs too.

Not sure how to factor those in, as the scanner is already a bit cluttered. I see a future with a full on search the map UI but that's out of scope for this ticket (e.g. find me a place with x y and z within 200 tiles without trees and...). Still, that list above is a list of useful things that's kind of hard to find any other way I've found. Usually the alternative is temporarily teleport and scan again. Mostly just dropping this here so they don't get forgotten.