Oil generator tweaks

[JohnyDL]

I've gone ahead and done the hard work for myself on my oil field but I have a feeling that there should be some tweaks to the generator.

Allow other entities to be on the BP as obstacles to be avoided by piping (if they're power poles take that into account with needing to power the pumpjacks) Have a 'connect all pump jacks' option that doesn't require a train track in the BP and just connects all the pump jacks with as little pipe as possible Allow the generator to use the pump jacks as locators for the oil spots and rotate them if necessary Beacons. I wouldn't mind a "this program will run for about 5 minutes and will return the best BP it can find in that time" option rather than a "right this instant anything will do" ;)

The BP I provided failed several times because I didn't understand how to use the tool and then finally for being unable to connect all pipes which lead me to make my own and this post: 0eNqVl9tugkAQht9lr9GwJ06v0jQN6sZuq0gAmxrjuxfQXdrKhH+vFAOfs8w3s7NXtjmcTd3YqmPFldntqWpZ8XJlrd1X5WH4rbvUhhXMdubIIlaVx+GqPh/rj3L7yW4Rs9XOfLOC314jZqrOdtbcGePF5a06Hzem6W94fjpi9antHzhVwz/1kJVQax2xy/AtXuvbLXrCCAQjY4fh2TxGQtFwj0nnMQrBTMH0q+vf2M42Znu/Qc0wNcBUU2R6PrIEiWxY1gMj5zEpgBETRcxTMoAi1VIsOZT63GMIg3gMcJJFCuLzr2A4gYF8Ht7InZMTGBkUTfbfQzHHhOT2IiZEZIjOK597wmY+6dx2TWn3792q/zg8o3j2CGcWkwYtibCZQzr7qids5ojO2kGoboi4zCeZCQrUm5XTh6JAKosHJEYUFFCbdsUhIaQKqRQidwKT2imgCArUo31fJEpDIE6rZAGSQblzjZ7YDUUekq4ESZcMEpyISyJ+e72JRiYRvV3GiTYtEZ/91EGNLpDBeiESyGDpEk7tgjIJSQ+1CUpoysiXKFBb9isimruEHJ6CIWpbxUHjLonhIbsnNQsqRF3+J5bFwlQyxMIxsmUmNHEI10DIoVwHLTeFQsPm6cxBibJT0ACSLFGyoEMQdZRSedAhSIx115/yxrNg8evoGLEv07TjM0mWilgLLXk/gP0AeZ2Tgg==

[demipixel]

1) I could add an option to avoid unknown items in the blueprint.

2) Right now it works by having all pumpjacks trying to connect to a "target". What happens if no station is included?

3) Rotating the pumpjacks means you'd have to remove the existing ones before placing the blueprint again, right? How would you even figure out what the "best way to rotate" them would be?

4) On a 30x30 blueprint, that's 2^900 possible combinations of pipes, at 1000 tries per second would be 10^260 years (the heat death of the universe is in 10^103 years). What is the system currently doing poorly that you believe could be improved in a 5 minute time range?

5) Typically pipes can't be generated if a pumpjack is running into another pumpjack. In this case, it might be a bug because a pumpjack is facing upwards towards the top of the blueprint? I'm not completely sure...

[JohnyDL]

1 that would be cool

2 chose one oil pump stick a regular pipe to it use this pipe as the target for the first pump to connect to then additional oil pumps target the existing pipe network

3 I agree there's no easy 'best way to rotate' algorithm (PvsNP) but make an attempt to connect then any that don't/can't rotate 90degrees and reattempt, failure only when a pump rotates 4 times and still fails (also you can BP ghosts so I ghost all the pumpjacks to make the initial BP for your program no ripping them out and I think in 0.16 placing a BP ontop of existing structures can rotate them and even if you can't then you can manually rotate without picking them up by hovering over them and pressing R) Beacons: eliminate any areas smaller than 2x2, fill in dead ends with beacons (3x3 areas with 3/4 restricted edges, if conflicts then chose the beacon that serves the most pump jacks if conflict chose the one that conflicts least with other potential 3x3 areas if conflict leave for next pass) first then repeat each time you add beacons you add dead ends eventually some will create conflicts or remove conflicts from other pairs just repeat until all conflicts are resolved or until a pass doesn't change the conflicts (at which point it doesn't matter which of a conflicting pair is chosen they both are equal)

4 generate BP as I suggested in 2 and combine with the rotating idea of 3, put pump jacks in an order rotate pump jacks one at a time recalculate it's connection (remove pipes from old connection point until network would be disconnected then attempt a shortest path for the new connection point) to the pipe network after each rotation iff pipes foot print is smaller it's a 'better' BP once all 4 rotations have been tested move onto next pump jack in sequence, continue until 5 mins or until every pumpjack has been cycled through 4 rotations and no better BP has been found. You'll only find a local minimum but local minimum is better than not, to me at least.

5 I'm not sure what caused the final error I quoted but I did get one or two where I was inputting to the back of other pump jacks and when I didn't have a train track or when I included my sub stations I thought by the final time I'd jumped through all the hoops and I just thought it was a problem BP worth reporting while I was here with ideas.

[Chronial]

These are some interesting optimization problems :)

Right now it works by having all pumpjacks trying to connect to a "target". What happens if no station is included?

I looks to me like you need to find the minimum spanning tree https://en.wikipedia.org/wiki/Minimum_spanning_tree. Unless I'm missing something, it's also a MST if the station is included.

Rotating the pumpjacks means you'd have to remove the existing ones before placing the blueprint again, right? How would you even figure out what the "best way to rotate" them would be?

You are already using A to find the paths, right? Instead of starting at the output, you could start the search at a virtual point inside the pumpjack that is connected to all 4 output possibilities with a path of distance 0. Then A will do the right thing :).

I think @JohnyDL's request should be doable like this:

1. Calculate the shortest path between any two pumpjacks, For example via A*.
2. Find the MST over all of this.

Both steps can be done in quadratic time (for n pumpjacks, there will be n² operations), so given the low number of pumpjacks in an oilfield, a modern computer should be able do this in way under a second.

This algorithm would not find the perfect solution, because it might make sense to just connect all pumpjacks to the center instead of to each other. This could be improved by adding a few points between the pumpjacks into the mix and calculating the Steiner Tree instead of an MST. There even seem to be js packages for that ^^.

To be clear: I'm not implying that any of that is easy. I just thought you might be interested in how these issues could actually be solved.

[demipixel]

Definitely a good idea. I think MST is enough, since if there is a space between two lines of pumpjacks, it will just connect somewhere.

It does beg the question, what is the best way to find the shortest path between any two pumpjacks (A* works but the shortest path isn't always the best solution, e.g. diagonal is extremely annoying, and a long straight where you can have undergrounds may be preferable to a bunch of pipes connected and turning).

[Chronial]

It does beg the question, what is the best way to find the shortest path between any two pumpjacks (A* works but the shortest path isn't always the best solution, e.g. diagonal is extremely annoying, and a long straight where you can have undergrounds may be preferable to a bunch of pipes connected and turning).

It is up to you to define what "shortest" means for the A* – you do it here: https://github.com/demipixel/factorio-generators/blob/ca180f9a082a376b177c0ade8094804f34ce91e2/tools/oilOutpost.js#L224

It's not that trivial in this case, because where you can go depends on how you got there (you can't turn left on an underground pipe exit that came from the top). I gave this some thinking and came up with this solution: Only have the non-underground-pipe pieces of the path as nodes. At the moment, you tell A that only neighboring cells are connected. In addition to that, connect a cell also to all the ones that are reachable via a straight path. The direct neighbors have a distance of 1, Anything else has a distance of number of underground pipe pieces needed. That would be `ceil(cell-distance/11) 2`.

Then you can also enable the heuristic again and your algorithm should be a lot faster. But you will have to weaken the heuristic, as in it's current (the comment) form, it would break A*, because it might overestimate the distance, which is forbidden.