Friday Facts #200 - Plans for 0.16

[mrvn]

I do agree with you that mrvn's table of waypoints idea sounds a lot like a n^2 problem.

That's just space. Computationally, it's travelling salesman, which is NP.

I'd hazard it's probably cheaper computationally and more effective to route within the coverage area instead of between explicit roboports. Then only if the bot determines it does not have enough charge for its intended path, it can schedule to detour via a convenient roboport near its path.

Really though, though NP problems are not solved as such, there is certainly plenty of reading material.

First of this is not traveling salesman. You are not trying to find a path that visits all roboports in the shortest total distance. It's a simple graph problem. Given a network where each roboport has a shortest route to every other adding a roboport is simple. You take the table from each roboport in reach (usually no more than 4), add the distance to that roboport and then build your own table taking the shortest entry from the tables. Now I reaslize that removing a roboport is expensive though and needs a full table rebuild. The network may even split in two.

As for having 1000 roboports and therefor the table needing a million entries. So what? That would be 4Mib of memory where each cell holds a 32bit ID of the next roboport. Compared to the GiB of memory already used that is negible. But I totally agree that a lot of the time just picking the roboport thats in the general direction of the destination will be the right thing. So the table could be made sparse to save space.

Or just do an A* search every time you plan a path. It's 1000 roboports for a big base and most of that will cover the whole area on the inside. Unless you have a very long U shaped base A* will include nearly no wrong roboports.

The point is that no matter how hard you try, you (probably) won't be able to find a solution less computationally intensive than creating a straight line and occasionally checking "if charge < x then charging logic". Changing it would also require a lot of work and could create a lot of bugs. There is also the problem of regenerating tables if you use that method, with lag spikes or wacky behavior, and possibly bugs. Bot pathing during that time could also be an issue.

The simplest and least intrusive change would also be totally fix the problem and would not cost any more time in the long run, just move some calculations to earlier:

- Plan your straight line just like now.
- Compute point where you run out of charge (cheaper than checking every tick for sure)
- If destination is too far away find recharging station from where you would run out of juice. (this part is just done earlier)
- Fly there directly. (this will actually save time since the distance will generally shorter)
- If already there send a signal that the bot is stuck. (better than constantly flying back and forth)

[Zavian]

@mrvn Is your "solution" going to actually make the challenge of laying out your factory more or less interesting/engaging for the player. Note I'm deliberately not asking if it will make it easier for a player to build an efficient factory. Instead I'm asking if this change would make laying out a factory more or less interesting/engaging/challenging for players? Because if it makes the gameplay less interesting, (and in my opinion I think it probably would), then the devs shouldn't implement it, because it detracts rather than enhances the gameplay.

As an alternative that also shouldn't be implemented, the devs could make it so that roboports continuously broadcast power to all bots in their range, and bots never leave a roboport's range. Hence bots never need to stop to recharge, and never run out of charge. I think that would also solve your issue, and is probably even easier to implement.

As I have said before Factorio's core gameplay comes from laying out and designing your factory. Managing the interactions between the game's entities is a large part of that. If you want an efficient factory, then it is up to you as the factory's designer to properly design your factory. And managing bot recharge is one of those challenges. As such making bots smarter can simply the game's challenges and detract from the gameplay.

[mrvn]

It changes nothing really on the design of your factory. It just makes the gameplay way less annoying. I don't know how often I stood somewhere waiting for some logistic robots. Then you see them comming and comming and 2m before you they turn around and head back to recharge. Hours later, it fells like, they finally come back and deliver.

In game character must be like: Seriously, we can build a rocket to go to another star but robots don't check their battery before flying somewhere? Is that why we crashed? Didn't take enough fuel?

[Jap2.0]

It changes nothing really on the design of your factory. It just makes the gameplay way less annoying. I don't know how often I stood somewhere waiting for some logistic robots. Then you see them comming and comming and 2m before you they turn around and head back to recharge. Hours later, it fells like, they finally come back and deliver.

In game character must be like: Seriously, we can build a rocket to go to another star but robots don't check their battery before flying somewhere? Is that why we crashed? Didn't take enough fuel?

Two things you might be missing:

Computing where they will run out of charge is more complicated than you'd think, as you have to factor in speed bonuses and either change all the paths when a new speed bonus comes along or keep the paths and make bots charge earlier than is perhaps necessary. Furthermore, robots appear to do some logic about which roboport to use based on distance and wait times, and using your idea either bots would not do this logic, and therefore sometimes no spread out between roboports (which would be worse than the "problem" you are trying to solve) or would do the logic when they created their path, which would lead to wierd charging cycles where one roboport is overused and another is underused, and then they flip, and so on. Either way, players would complain, and perhaps label it as a bug. So you see, it wouldn't really help the problem and it would probably be a waste of the developers' time.

[vanatteveldt]

Maybe an easier "solution" would be to special case logistic deliveries to the player to let bots go deeper into the red when near the player. Then after delivery they can take the slow boat to the charging station, but why would we care after we got the stuff?

[mrvn]

It changes nothing really on the design of your factory. It just makes the gameplay way less annoying. I don't know how often I stood somewhere waiting for some logistic robots. Then you see them comming and comming and 2m before you they turn around and head back to recharge. Hours later, it fells like, they finally come back and deliver.

In game character must be like: Seriously, we can build a rocket to go to another star but robots don't check their battery before flying somewhere? Is that why we crashed? Didn't take enough fuel?

Two things you might be missing:

Computing where they will run out of charge is more complicated than you'd think, as you have to factor in speed bonuses and either change all the paths when a new speed bonus comes along or keep the paths and make bots charge earlier than is perhaps necessary. Furthermore, robots appear to do some logic about which roboport to use based on distance and wait times, and using your idea either bots would not do this logic, and therefore sometimes no spread out between roboports (which would be worse than the "problem" you are trying to solve) or would do the logic when they created their path, which would lead to wierd charging cycles where one roboport is overused and another is underused, and then they flip, and so on. Either way, players would complain, and perhaps label it as a bug. So you see, it wouldn't really help the problem and it would probably be a waste of the developers' time.

I grant you that updating for new speed bonuses would be tricky. But I doubt simply ignoring that would have any noticeable effect. So what if bots recharge a bit too early because with the new bonus they could have gotten 5m further. It probably wouldn't have changed the fact that they need to recharge and probably at the same recharging station. And even if not then after the bot recharged at maybe the wrong charging point all will be well again. You could think of it like the bot only gets the upgrade when it next hits a charging point. I think we can safely ignore this.

As for the logic about which roboport to use. Keep that logic. It is possible that you get an oscilating use pattern out of it like you describe but then it already is possible as is. I'm assuming bots "reserve" a charging port when they route to a charging station. So the station not only knows how many bots are at the station but also how many are on the way. Because otherwise all bots would go to the same station till the first arrives and changes the metric. My idea might change when the bots reserve the charging port. Might be earlier now or later. When the flight path is near a charging station it will be earlier but when the direct flight is far from a charging station the current code will fly into wilderness and then very slowly fly back to a charging station. In that case flying direct will be quicker and the reservation will be for a shorter time and thus better.

So I'm unsure if my idea would make the balancing better, worse or have no noticeable effect. Personally my roboports tend to be near maximum distance in a nice grid pattern. I don't think there is much balancing going on at all since usually one roboport has a clear distance advantage over all the others.

[Muche]

@mrvn, since bots would compute their path beforehand, similar to how trains do, does this proposal have the potential to trade current efficiency bottlenecks (with best-practice ways how to solve them) for currently unknown ones (but in a way similar to train ones)?

[featherwinglove]

The simplest and least intrusive change would also be totally fix the problem and would not cost any more time in the long run, just move some calculations to earlier:

- Plan your straight line just like now.
- Compute point where you run out of charge (cheaper than checking every tick for sure)
- If destination is too far away find recharging station from where you would run out of juice. (this part is just done earlier)
- Fly there directly. (this will actually save time since the distance will generally shorter)
- If already there send a signal that the bot is stuck. (better than constantly flying back and forth)

These would be the "simple rules" I referred to in my earlier post talking about a table of paths where such simple rules don't work, such as when the simple rules would path over enemy territory (quite likely in those few bases where biters are being deliberately farmed.)

[mrvn]

@mrvn, since bots would compute their path beforehand, similar to how trains do, does this proposal have the potential to trade current efficiency bottlenecks (with best-practice ways how to solve them) for currently unknown ones (but in a way similar to train ones)?

Obviously they would change things and probably unpredictably prior to testing it. You have some simple rules but predicting the emergent behaviour of swarms following those rules and their interaction can be very hard.

[mrvn]

The simplest and least intrusive change would also be totally fix the problem and would not cost any more time in the long run, just move some calculations to earlier:

- Plan your straight line just like now.
- Compute point where you run out of charge (cheaper than checking every tick for sure)
- If destination is too far away find recharging station from where you would run out of juice. (this part is just done earlier)
- Fly there directly. (this will actually save time since the distance will generally shorter)
- If already there send a signal that the bot is stuck. (better than constantly flying back and forth)

These would be the "simple rules" I referred to in my earlier post talking about a table of paths where such simple rules don't work, such as when the simple rules would path over enemy territory (quite likely in those few bases where biters are being deliberately farmed.)

I don't think anything can help you with bots flying over your alien farms. Except to keep all roboports far away from it. Leave a hole in the network larger than twice the charge and the bots will fly around instead of across.

Some time ago I started a game with natural evolution mod, where you can build and farm aliens. I haven't progressed enough yet to actually do that but aren't those aliens then friendly and won't attack bots?