Optimize Drone Movement

[dognose]

Currently, drones which should deliver a good from A to Z are taking "bee-line" to reach the target.
Meanwhile they need to return to Drone-Ports very often.

Drone-Movement can be improved as described bellow:

1.) Consider a Base build around a big Lake:



2.) Having a Drone which should deliver Goods from A to Z



3.) Currently this results in a behaviour like the following example shows:



4.) Rather than that: The Drone-Port-Connections should be utilized. The drone should start "moving" and as soon as it hits the Drone-Port-Area, it should change its direction right to the "center" of the NEXT drone-port area.

- A Drone from "Zone A" which should be deliver a good to "Zone Z" should first use a path-finding algorithm to detect the shortest way, based on drone-port-connections. (purple: Drone Port connections)
- gray: "Next" path, based on targeting the center of the next drone port area (the drone port itself).
- red: Actual path by changing direction as soon as the border of any drone port area has been hit.




This would ensure that drones are staying within range for recharge, but more important: Avoiding "dumb" movements in case of lakes and/or U-shapped bases...

[dognose]

Technical Example:

purple: Drone port connections
gray (thin): theoretical way, if the center would need to be reached.
red: actual way.



(Basically the "Movement-Model" applied by Blizzard for Warcraft II Map Designer)

[keyboardhack]

Assume a base has 20.000 robots in a network, they always have something to do and don't need to recharge. If we assume an average travel time for each robot to be 4sec then 20.000 / 4 = 5000 robots need to pathfind per second.

Factorio runs at 60UPS which means that factorio would have to process 5000 / 60 = 83,3 paths for each update(1 update = 16ms). With a graph consisting of >1000 nodes it would literally be impossible to do it in < 16ms.

Everyone agrees that it would be a good idea to add pathing to robots but no one knows how to do it in a way that is just as fast as how it works right now. Simulation speed is the main reason that robots are stupid.

[dognose]

Assume a base has 20.000 robots in a network, they always have something to do and don't need to recharge. If we assume an average travel time for each robot to be 4sec then 20.000 / 4 = 5000 robots need to pathfind per second.

Factorio runs at 60UPS which means that factorio would have to process 5000 / 60 = 83,3 paths for each update(1 update = 16ms). With a graph consisting of >1000 nodes it would literally be impossible to do it in < 16ms.

Everyone agrees that it would be a good idea to add pathing to robots but no one knows how to do it in a way that is just as fast as how it works right now. Simulation speed is the main reason that robots are stupid.

First, an efficent "pathfinding" algorithm doesnt require a huge amount of time. Pathfinding is basically "Kindergarden" for programers.

Second, the example I proposed does not need "One calculation per second":
- It calculates ONE path per drone - which should be a fraction of a second.
- It only re-calculates a new path as soon as a drone hits the "border" of a drone-port area.
- So, for a path taking 50 "hops" and maybe 5 minutes of travel time, that would be 6 calculations per minute (per drone)
(Improvements can be done, by aranging drones in batches or cache commonly used paths)

So, even with 20.000 drones moving around - it will come down to maybe 1000 or 2000 calculations a second.

Personally, I wouldn't mind, if a drone has a little "delay" while determining the next port to target. After all it would - at least in the scenario described above - be more efficent than
bouncing back and forward between drone-ports in order to recharge just because the "bee-line" is about 30 times the length one Battery-Charge of a drone could handle.

[dognose]

Maybe a more realistic example:

Consider a base like this, with a drone that should deliver something from "ORE-2" to "OIL-4":



Non-Path-Finding-Drones will do something like this:



While Path-Finding-Drones might do this:

[dognose]

ps.: I only use the Logistic Network for construction purpose and delivery of very very rare materials.

So, even if my network is made of 15.000 Drones, only a fraction is active.

Thus I expect the logistic network to be able do deliver a "stack inserter" anywhere within a reasonable amount of time,
even if produced at the "main-base" only.

I also saw "drones" bouncing back and forward between the very same drone-port just because they don't use pathfinding,
but retrying the same direct connection over and over again, leading to the case that the item never gets constructed, cause
the "job" is taken by a drone which never could fullfill its job.

[Adil]

Well, I guess it's safe to say, that examples here are way off the designed scope of usage of logibutts. On the distances like that you're supposed to set up the supply train. And those don't look like default generation settings either.

The thing with pathfinding bots is that

a path taking 50 "hops" and maybe 5 minutes of travel time

isn't most frequent one.
An average usecase of a robot is a hundred tiles at most with next task right away. Surely, the pathing won't take time up it worst-case at majority of the cases, but it is still way slower than a single direction calculation.

[Rseding91]

As I've said before: this is not likely to ever happen. It would increase the CPU cost of robots by massive amounts for incredibly miniscule gains.

There's already a simple answer: don't build L or U shaped logistic networks.

[dognose]

Well, I guess it's safe to say, that examples here are way off the designed scope of usage of logibutts. On the distances like that you're supposed to set up the supply train. And those don't look like default generation settings either.

In "my world" the logistic network is only used for building and supplying items to the player. Everything else is done with belts and trains. (I consider this a "valid" usecase...)

I'm a developer myself and I think that "technical issues" should not affect "users freedom" of doing stuff. If there is a design flaw, it should never ever be justified by saying "You are using it wrong / out of scope".
If the option to build it "this way" is given, it should also work... (But that's just my opinion)

I thought about this topic again today, and actually, it will be way less calculations possible with a small tradeoff:
A Drone could only do the pathfinding ONCE it starts to move. Drone-Ports added during movement could simply be ignored / considered for the "next" time.
(tbh: Drone-Network does not change that frequently)

Only a check on each "hop" if the next target port is still there (could have been removed) would be required.

[kingmob]

Is there no way to 'cache' the pathfinding between nodes? That way the bot can use basic pathfinding if the target is within a short range and use more advanced pathfinding if it is required. Other bots can then just re-use that path, reducing it to just a table lookup or something.
You might also want to have a slow background loop iterating over existing paths to update them once in a while and to remove dead paths etc.

I'm not familiar with game-programming, but wouldn't this cover all cases with little extra overhead? It might also open up the door to other more advanced behaviours, like bots handling multiple construction jobs more intelligently, although I would assume that's more challenging.

[ssilk]

Even if you cache paths and optimize whatever possible, this would be still slower than the current algorithm.

[vtx]

It's clear pathfinding is not the good idea in your example with 22 nodes there's ~ 64 possibles paths.

I guess the actual code is try to reach destination directly ( trace a direct line ).
Once low on energy or empty ( not sure at wich level it occur ) go to the nearest roboport to recharge.

Out of the box idea.

Instead of doing the scan for nearest roboport at low level energy.
Check when he leave roboport if it'll be in blank spot when low energy if yes alter the direction to be in valid spot.

Anyway this code is executed somewhere or is most of the time it's not executed at all ?

[greep]

This sounds like a hack. It'd be fixed if drones didn't have frequent recharges in the first place. I made a suggestion in the balance forum regarding this.

But alternatively, I don't see why bots need limited energy at all. They should just have essentially infinite energy, and make a recharge check on a completed delivery, and then have infinite energy on their way to a station, where they then take time to recharge proportional to their last recharge time.

It'd increase performance too. Unless current recharges are fixed time and somehow calculating the time to recharge is a performance hog, kind of doubt that, though. And they could then complete get rid of all energy checks during transit and slowdown state altogether.

[vtx]

This sounds like a hack. It'd be fixed if drones didn't have frequent recharges in the first place. I made a suggestion in the balance forum regarding this.

But alternatively, I don't see why bots need limited energy at all. They should just have essentially infinite energy, and make a recharge check on a completed delivery, and then have infinite energy on their way to a station, where they then take time to recharge proportional to their last recharge time.

It'd increase performance too. Unless current recharges are fixed time and somehow calculating the time to recharge is a performance hog, kind of doubt that, though. And they could then complete get rid of all energy checks during transit and slowdown state altogether.

I think it's to exactly to prevent bot to become too powerfull as a transport solution and obliterate train and transport belt. Because they have to recharge it's a good solution for small transit transportation inside their own roboport it's where they shine and lost their spark the further they have to travel.

[greep]

Well, with recharge time is proportional to flight time as per my comment, this basically changes nothing about bot productivity and wouldn't really affect a map where the whole map was one giant full network for instance. It would only affect U/L shaped network viability, and depending on current implementation, increase/decrease performance.

Edit: I like my idea better still, but altering this:

Instead of doing the scan for nearest roboport at low level energy.
Check when he leave roboport if it'll be in blank spot when low energy if yes alter the direction to be in valid spot.

To instead be "if would be in invalid spot, immediately set to recharge at the roboport it would've recharged at" would be pretty performant. Maybe?

[vtx]

Well, with recharge time is proportional to flight time as per my comment, this basically changes nothing about bot productivity and wouldn't really affect a map where the whole map was one giant full network for instance. It would only affect U/L shaped network viability, and depending on current implementation, increase/decrease performance.

Edit: I like my idea better still, but altering this:

Instead of doing the scan for nearest roboport at low level energy.
Check when he leave roboport if it'll be in blank spot when low energy if yes alter the direction to be in valid spot.

To instead be "if would be in invalid spot, immediately set to recharge at the roboport it would've recharged at" would be pretty performant. Maybe?

I guess both approach in this case are equivalent.

- Instead of calculating the nearest roboport at low energy point. Calculate that nearest roboport at low energy position when leaving roboport and then go directly to that roboport. ( Lead in useless calculation when bot travel within roboports range, but more accurate travel time )

- Let bot go directly to destination and then charge for longer time. ( less cpu usage and increase travel time of bot as he go directly to that point )

I think too your idea is better in term of cpu usage.

[TI-89]

Bot flight paths are actually probably very nearly optimal in the average case. The biggest thing to understand here is that the bot routing algorithm is not designed to optimize the flight path of an individual bot, but to avoid congestion in the network. This is very much in the spirit of Factorio as I understand it; which is summed up (at least for my point here) as simple components interacting based on simple rules, resulting in complex behavior. I've seen it said many times on these forums that lognet throughput is 'theoretically infinite,' but what does this truly mean? In essence, robot logistics is currently extremely powerful for transport of goods to arbitrary locations. In this, the essential thing which needs to be managed (not for logibots as they currently work, but for moving things in a random pattern in general) is average distance from the requested items. Another way of thinking about my game philosophy above is that 'components are stupid but you are smart.'
I've been working a lot on putting much of this into more precise terms; now is as good a time as any to start sharing my thoughts I suppose. So let's take a step back.
I have worked a lot with trying to push performance of robonet to its limits; along with this are a lot of thought on how things could be done differently, and a lot of reading this forum trying to get a sense of all the suggestions and discussion starting long before I had this game. The biggest problem with roboport network as it stands are the huge discrepancy between how it is 'supposed' to be used (short distance, high throughput, e.g. 'train station') and how players, especially when starting out, attempt to use it. But the design of the system (in particular the inclusion of congestion avoidance and equal request prioritization) leads to emergent behavior over large scales with many robots.

Essentially, Rseding91 is correct. You have two options: separate your network so that bots don't think a straight line path is a good idea, or make it a good idea. You can place ports at the narrowest parts of the lake, this will help keep performance reasonable, but does not necessarily make a straight line path viable. Or you can build an island. See my response to viewtopic.php?f=6&t=40527&p=244466#p244466.
Still hoping to set this up further as a test, get some hard numbers on throughput (it's a good test for dynamic scaling of a subnet too). But idk when it will happen. But for a basic comparison, it took about 1200 bots going straight over the lake to overwhelm the ~5500 in the network going around. Latency and buffer management are very real problems in scaling networks. Traveling in a straight line is a very naiive way to pathfind. But in most cases it leads to a near optimal path. When it does not, it is often because the player has chosen to transport things in a way that is inherently inefficient, or in quantities too large for the network to manage. I believe the choice should be left to the player: I have had immense fun designing a network capable of transmitting goods in a tremendously inefficient way. If you wish to follow my footsteps, build an island. Otherwise, build a train station that brings supplies closer to where you need them.

[TI-89]

When I said "let's take a step back" I meant to quantify performance a bit. Never did in that post. But essentially lognet is a truly shared medium, unlike belts and trains which require external solutions for managing mixed item types (filter inserters, circuit control, etc). So while a network has a maximum "link throughput" for any particular request, this is never really reached under normal circumstances. Especially just for restocking player. Which means latency is all you really have to manage.
Latency depends on a number of things however, and is very difficult to minimize for all resources. Thus the game requires you to make choices about how you distribute things based on how you use them. For example in a high bandwidth network, (in which it takes quite a bit of sustained demand to really build up contain) it doesn't matter too much where you put something like concrete, because generally the player doesn't mind waiting a bit for concrete to be placed. If you choose to have lognet perform a function like resupplying turrets however, response time becomes critical.
Basically, latency = time to item pick up + time to drop off. Each of these terms also varies probabilisticly based on network conditions. Distance traveled for a given delivery can be broken into two parts: straight line distance + distance deviated (when going to charge). Again this is probabilistic based on how much charge the bot has at pick up, which depends where it came from. In addition to distance, each bot spends some amount of time waiting in queue for charging.
To optimize performance then, it is necessary to decrease variability. For example, if you cache items at one edge of the lake, and keep some bots nearby, they can usually get most of the way straight across the lake (because they will consistently be near full charge when the items are picked up.
Of course, if you get to that level of optimization with log net you realize that really having a cache in the middle of the lake would be best for response time all around it. And now we're back to building islands.

[dognose]

Let's first think about what "pathfinding" actually means. It seems like a lot of people are expecting a "massive, complex" algorithm,
taking forever to determine a single path, cause each and every option needs to be evaluated.

While this ofc. would increase the CPU-Load to an unacceptable level - this is not true.

The point is: We are talking about PATHS - Not "Single-Drone-Movement-Instructions!"

Sidenode: I've done very complex pathfinding in the past, thus I know that it is not "magic".

----

When it comes down to performance, two numbers are important: Amount & Size i.e. "How much do I need to calculate" and "what is the individual size of each calculation"?
Right? Well... no.

The most important factor is the third - often negleted - component: How OFTEN do I need to calculate a new path.
And for "Factorio-Purposes" it would be a ridiculous low count.

I'm now switching to "technical talk", hoping it might give some devs some ideas, even if not everyone might be able to understand what I'm talking about.

-----

Imagine there are 100 Drone ports and upon "savegame load", an algorithm is detecting the shortest ways between two nodes.
let's think of them as a1 to a100. Figuring out the shortest path using some of the well known algorithms will not significantly impact the loading time.
(Re-Doing the paths would be a one-time-process, could be "saved" as well)

The detected "links" could be saved in a HashMap (or something similar) by creating all possible (!) combinations, i.e.

"a1-a2" = "a1-a10-a50-a90-a2"
"a1-a3" = "a1-a15-a3"
...

Keep in mind, that "possible" does not mean all. Only connected drone-ports.

This "map" would now be valid until a drone port is removed or added. And please take into account, that you don't remove or add drone-ports every second!!

A101 is added:
- Determine A101s Connections (as it currently happens - yellow dashed line)
- Imagine A1, A2, and A3 are now connected to A101 (new yellow dashed lines)
- Copy every Map-Entry ending at A1, A2, A3, add A101 to the end and store as "copy". (Map will "blow up", but hey, Hashmaps are O(1), leading to a little more memory-consumption, but who cares nowadays?)

A75 is removed/killed:
- Drop every path containing A75. (Start, End, Middle)

Drone-Movement-Starts:
If a single drone now starts to move - it is a query of a hashmap which is worth "nothing" in terms of performance:
Determine Source -> A8
Determine Target -> A56
Query HashMap for "A8-A56"
Receive "A8-A10-A12-A70-A50-A56" and "feed" the drone-movement-system accordingly, while ignoring everything that happes "from now on".

I think nobody would mind if any moving drone would:
- Hit a droneport that has been removed 3 minutes ago.
- Not utilizing a droneport that has been added 2 minutes ago.
(One could often see such a behaviour in games of popular companies)

[TI-89]

Right, but you misunderstand the way the robotic network functions. As did I when I started trying to use it effectively. One of my earlier thoughts involved a peer-to-peer path discovery algorithm. This would still be nice for things like routing around biter nests, rather than continually sending bots to their deaths, but can be managed with reasonable ease by careful planning of your networks and the interfaces between them.

The logistics network basically hides the location of individual resources. In this way it is totally unlike belts and trains, in that you deal with "connections" from provider to requester, and not more permanent stations. In reality you don't requester chest settings are basically permanent the way it is used, but my point is that it behaves in very complex ways that I don't think were factored into the initial design. So "connections" are an imaginary device that I will use to discuss network performance from the perspective of the network. So to the logistics network, the connection is closed when the request is filled, i.e. when the chest has at least the number of resources that it requested, and reopened when the number of items in the chest drops below the set amount.

This matters, because when you talk about connections you can talk about latency. "How long is the delay between a request being sent and the first item being delivered?" The other measure of a connection is throughput -- importantly, while high delay is bothersome to a player, it does not affect total throughput *at least not directly*. There is still a point at which performance is maximum for the given window size (the # of items that the network will put in flight at once for a request -- this is the request size). The higher the latency, the higher the window size must be to achieve a given throughput. And this window size is limited by the capacity of the requesting chest (and therefore the stack size of the item type requested). Also the maximum throughput on a chest is capped by inserter speed (lognet avoids this for storage, but to actually use resources they must be inserted into an assembler or onto a belt). Thus when it is said that possible throughput of lognet is infinite, it is an oversimplification. There is a limit, it is simply immense.

So, when I say that the network 'abstracts resource location' and 'paths are near optimal in aggregate' I mean that worrying about the path an individual bot takes is not only unnecessary but irrational. Latency scales directly with the distance an object must be moved; the path the bot takes is just jitter. Or to use an analogy, when your internet is performing poorly, do you start running traces to see if any packets went off course? If you want better response time you should build a cache, not try to route individual requests more precisely. The bots travel as they do to maximize the available performance of the network (don't overwhelm ports when avoidable) not to minimize the travel time of a single 'packet.'