Bots with collision box and addressing the performance hit

[Jupiter]

After reading the FFF about belts vs bots I had an idea.

I always thought it was strange that you can have a thousand bots on the exact same spot. This, in essence, makes them so good.
My idea is twofold:

• 1. Give bots (only logistics bots) a small hitbox specific for airborne things (they cannot collide with things on the ground, only with eachother).
  This creates throughput problems when using lots and lots of bots on a narrow lane through the air.
  
  2. Give the player tools to manage flightpaths to cope with the bot throughput problems.
  One possibility is that the player can decide that when a bot should bring items from chest A to chest B it should ALWAYS follow a player-specified path consisting of a series of checkpoints which might be either roboports or separate buildings that solely act as checkpoints (which may be much smaller; maybe 1x1 tiles?). The path from chest B to chest A might even be different.
  This divides up the airspace above a factory into lanes to avoid too much clogging.

A sensible default, if no path is specified, might either be that the path is just a straight line which is the current behaviour or that the bot will find its own path using a path finding algorithm (A*?) without regard to current air traffic. It might also consider existing flight paths, if any, and use those as much as possible.

Now, this idea is also not without its issues and open questions. Here are some off the top of my head:

• - What to do with the flight path from the bot's starting roboport to the pick-up chest? Should it use the choosen sensible default when no path is specified (reuse of existing paths, go in a straight line or the bot should find a path by itself)? Will this interfere with existing flight paths if that is a problem at all?
  
  - What to do with flight paths from a chest to the player (= a moving chest so need to dynamically change choosen flight path) and back? Same considerations as above.
  
  - How to deal with flight paths that must necessarily cross? The player is essentially trying to solve the https://en.wikipedia.org/wiki/Three_utilities_problem problem. Do we allow for multiple layers of airspace so that paths can cross without problems? This also reduces the number of collision checks needed.
  
  - What to do when a bot is out of power in between 2 checkpoints? Just continue very slowly and recharge at the next roboport? Go to the closed roboport in its path? Should it consider ports just outside its path (this is a bad idea I believe as it interferes with those other paths)? What if its path doesn't contain roboports and only contains these smaller custom checkpoint buildings?
  
  - This adds major complexity and processing time to the bot's behaviour (it's number of decisions increases with path length). This can become problematic with many, many bots. What you might do is increase the carying capacity of bots so that fewer are needed and maybe make the collision box even a bit bigger so that the throughput problems and the accompanying challenges remain. You could also process the bot's decisions batch-wise. If many bots are following the same path and are on the same checkpoint then they are all making the same decision. No need to do this multiple times.
  
  - The actual collision check is also a performance hit. Besides reducing the number of bots you can also use a quad tree to counteract this.

Furter ideas building on this:

• - A player might define multiple paths to allow for more capacity. When multiple paths are specified the bots can choose. You can simply implement it so that bots choose a path randomly and all possible paths have an equal (or even biased?) chance of being choosen.
  
  - You might allow the player to build up paths hierarchically. For example, a player might want to specify a sort of 'high-way' that connects two regions of a base that will handle much traffic (it will have a lot of recharging capability) and then specify within a specific flightpath from chest A to B to use this predefined high-way.

[dood]

Has been suggested many times, not going to happen for performance reasons.

[Jupiter]

Has been suggested many times, not going to happen for performance reasons.

I added some suggestions for this as well in my post.

EDIT: ah, hahaha. I see what the major performance hit is. The actual collision check. Well then you might use things like quad-trees to speed this up.

[Zavian]

That is still much slower than no collision check.

[Jupiter]

That is still much slower than no collision check.

As long as it is not problematic... it has the potential to solve the entire bots vs belts issue so there is a lot to gain here.

[Zavian]

It is guaranteed to be problematic in megabases with lots of bots. Those bases are typically already limited by memory performance. It adds a lot more branchy code (that can cause cpu pipeline stalls if the branch predictor guesses wrong), plus a lot of extra memory accesses, to update and check that quadtree (or whatever type of algorithm/data structure you use), then do a comparison against every bot in the same quad (and since bots will be of measurable size, you might also need to check adjacent quads if the bot is too near the edge). Don't forget that that needs to happen every tick in a base that is probably already bottlenecked by memory performance.

[bobucles]

Arbitrary search algorithms are expensive. Every time a bot moves it has to check to see if it has collided with any other bot. It doesn't matter how fancy your algorithm gets. Every bot has to do this in some capacity, so no matter how clever you get that's a LOT of searching!

Collision gets very expensive very fast:
- Pick a bot
- Move it
- Did I hit bot 1? No.
- Did I hit bot 2? No.
...
- Did I hit bot 230301? yes!
- Well golly gee I guess I'll back up a bit
- wait a minute I hit another bot!
- Welp
Those CPU cycles add up fast.


No collision is very simple.
- Pick a bot.
- Move it
- Next bot
It's very simple and quick.

[MeduSalem]

Arbitrary search algorithms are expensive. Every time a bot moves it has to check to see if it has collided with any other bot. It doesn't matter how fancy your algorithm gets. Every bot has to do this in some capacity, so no matter how clever you get that's a LOT of searching!

Collision gets very expensive very fast:
- Pick a bot
- Move it
- Did I hit bot 1? No.
- Did I hit bot 2? No.
...
- Did I hit bot 230301? yes!
- Well golly gee I guess I'll back up a bit
- wait a minute I hit another bot!
- Welp
Those CPU cycles add up fast.

Seems like you haven't read about Quadtree-based collision detection in 2D Space (also works with Octrees in 3D space where it is commonly used for raytracing voxels). Reduces the amount of collision checks greatly because you can discard most of the participants very quickly when they aren't anywhere nearby.

Most implementations expect a performance of O(n log n) or something along the order if the participants are sparsely distributed.

That said even quadtrees eventually become expensive when the amount of bots exceeds a certain number where updating the tree becomes expensive. But it is something that hypothetically could be parallelized to run on multiple cores as well where each core checks a predefined part of the tree/bots but it isn't entirely conflict free because the threads would have to wait for each other each tick to resolve their possible collisions before they can advance with the next tick... and if one thread takes much longer than the other because of the stupid case that all the bots bound to the thread are bunched up and colliding with one another you are still screwed.



The bigger question is if it is worth the trouble gameplay wise to even have collision for bots at all and if it couldn't be just resolved by having limited access to the chests where only a limited number of bots can access a chest at a time.

[Jupiter]

Collision gets very expensive very fast:
- Pick a bot
- Move it
- Did I hit bot 1? No.
- Did I hit bot 2? No.
...
- Did I hit bot 230301? yes!
- Well golly gee I guess I'll back up a bit
- wait a minute I hit another bot!
- Welp
Those CPU cycles add up fast.

Seems like you haven't read about Quadtree-based collision detection in 2D Space (also works with Octrees in 3D space where it is commonly used for raytracing voxels). Reduces the amount of collision checks greatly because you can discard most of the participants very quickly when they aren't anywhere nearby.

Most implementations expect a performance of O(n log n) or something along the order if the participants are sparsely distributed.

That said even quadtrees eventually become expensive when the amount of bots exceeds a certain number where updating the tree becomes expensive. But it is something that hypothetically could be parallelized to run on multiple cores as well where each core checks a predefined part of the tree/bots but it isn't entirely conflict free because the threads would have to wait for each other each tick to resolve their possible collisions before they can advance with the next tick... and if one thread takes much longer than the other because of the stupid case that all the bots bound to the thread are bunched up and colliding with one another you are still screwed.



The bigger question is if it is worth the trouble gameplay wise to even have collision for bots at all and if it couldn't be just resolved by having limited access to the chests where only a limited number of bots can access a chest at a time.

I agree with everything. Also the last part. There indeed may be smarter ways. I thought about this too this afternoon but then I realized, we already have such a mechanic. Namely, limited charging capabilities. There already is such a limit as you suggest but implemented differently. Or do i miss something here maybe?

[AileTheAlien]

This creates throughput problems [for the player to solve]

Most implementations expect a performance of O(n log n) or something along the order if the participants are sparsely distributed.

log(n) is still a lot slower for a game pushing the limits of available hardware. If a base has a thousand bots, that's three times slower in base 10, and 10 times slower in base 2. We're missing the real numbers here, but whatever they are, it's likely going to be whole-number multiples slower than doing the simple thing we've already got in game. Furthermore, this pathing proposal includes changes to the game UI, just to have the player manage this new system (i.e. even more things to build and test for the devs). Making broad changes to the complexity of the robot pathing needs to be justified, by increased game enjoyment. There's already a throughput problem for players to deal with / have fun with, in fitting charging stations in the base, so the only thing adding complex pathing gives you is, at best, a differently-balanced version of the same problem. There's a much cheaper solution to try, which is to just re-balance the robot charging speed, charging cost, size of charging stations, flight speeds, cargo capacities, research costs, etc.

[MeduSalem]

log(n) is still a lot slower for a game pushing the limits of available hardware. If a base has a thousand bots, that's three times slower in base 10, and 10 times slower in base 2. We're missing the real numbers here, but whatever they are, it's likely going to be whole-number multiples slower than doing the simple thing we've already got in game.

What do people expect when talking about collision detection? Zero performance cost?

n*log(n) ... quasi-linear is most likely the best case achieveable in such a scenario.

Of course it is always going to be worse than no collision detection at all.



But like I wrote... it is rather questionable if it would benefit the game at all anyway when it comes to gameplay even without considering the performance costs.

I am not really a friend of the entire dumb bots vs belts topic anyway... because for the very reason that people can't even agree on why it even is an issue in the first place... even less about possible courses and actions to be taken, hence why it probably should be left alone.

[dood]

I am not really a friend of the entire dumb bots vs belts topic anyway... because for the very reason that people can't even agree on why it even is an issue in the first place... even less about possible courses and actions to be taken, hence why it probably should be left alone.

Yeah, it's like the good old turret creep "problem".
The best solution to this is giving belts a boost that makes bots look like throughput kindergarten the same way turret creep got solved by giving you options several times more effective and the game turned out better for it.

[MeduSalem]

Yeah, it's like the good old turret creep "problem".
The best solution to this is giving belts a boost that makes bots look like throughput kindergarten the same way turret creep got solved by giving you options several times more effective and the game turned out better for it.

Agreed. Buffing the belts in some form or another is probably the better solution (if any is required) than trying to find a non-existent sweet spot to use the nerf hammer on bots. The buff would be welcomed by everyone, the nerf hated by at least half the community.