When two units collide and there is no one arround scenario. If one unit tries to move in to a tile and that tile hosts another unit in movement the first unit will wait. If the first unit tries to move in to a tile and that tile hosts another unit that is waiting, the first unit will add the tile where the second unit is as obstacle in the pathfinding map and then will call the pathfinder to find a new route.
But how do you proceed when you have a bunch of units around you (right next to you )all waiting? Do you add all of them as obstacles to the pathfinder obstacle map?
Calin said: But how do you proceed when you have a bunch of units around you (right next to you )all waiting? Do you add all of them as obstacles to the pathfinder obstacle map?
If you do this, assuming all units eventually have the same goal, there will be always one first unit which is closest to the goal. This unit is not blocked and can move one cell. The second unit then can enter the empty cell and the crowd does not get stuck. After some time the cloud may organize in a way there is always one free cell between adjacent units, and they may move on at constant speed without much waiting.
This works, but a problem is that the quantization of grid cells becomes very visible. It now not only shows because units always move just one cell in 45 or 90 degrees angles, it also shows with other behaviors like waiting for a free cell, moving forth and back eventually, etc. So your units move in restricted (quantized) ways, like chess pieces do. For some games that's desired, e.g. if we want predictable movement. Factorio maybe is an example. But for most games it's not desired, and we may prefer natural smooth movement instead. To make it smooth, the grid and pathfinding would be only used to give a coarse direction. But the units are particels which can move to any position, ignoring the quantization of the grid. Collisions can be handled as particle collisions in a physical way, rather than a logical way requiring a strict order. Particle units can also smooth the given path, hiding the quantized corners and grid aligned path segments we see otherwise.
So, i can't tell what classic RTS games usually did, but i guess you need to make this decision first. You might want to look into simple simulations at this point, instead into graph algorithms ans strictly ordered priorities. With particles, eventually units would never mark a grid cell blocked, even if a larger crowd of units covers it. Related collisions would be resolved by physical collision resolution, or some smarter form of flock behavior, etc. Only very large units might mark grid calls as obstacles, if needed.
So what I said is not such a crazy idea. I don’t need anything fancy, making it past the viable RTS entry point is all I want.
>with particles, eventually units
and
>only very large units
I don’t have in mind units of different sizes for my current game. I’m only looking for basic RTS behavior at this point. I can’t provide you with useful feedback on your last idea even in a hypothetical discussion since I don’t have a clear idea how a feature like that would work
Calin said: I don’t have in mind units of different sizes.
Collision detection grows in complexity if you support variable size, because then you either need a multi level grid (larger units go into the grid with larger cells, so they still always fit into a square of 2x2 cells), or you add large units into multiple cells (which is not really easier, but usually slower). So to keep things simple, your units should be small enough so the fit into a single cell. This still allows some small variance on size ofc., which may be good enough. But if your unit count is small (<100), you don't need to worry about efficient collision detection initially. You can just collide each unit with each other, which is brute force and slow but has no need for spatial acceleration structures to find nearby units quickly.
For the simulation itself, support of variable size and mass is easy, so i would add this from the start. Let's say we have a tank unit and a soldier. If they collide, the tank is heavy and should not move as much as the soldier to resolve the collision. We can have that by giving the tank a mass of 9 and the soldier a mass of 1. Then the soldier will move 90%, and the tank only 10% of the required displacement. This way the tank will also be able to push multiple soldiers out of its way simply because it has a larger mass.
Imagine we have 100 soldiers in a single spot. They all collide with each other and should be separated. After many steps of simulation they will, and their distribution will look something like that:
That's actually a screenshot from some SPH fluid simulation i did. It's 3D, so some particles are on top of others and thus it looks like they would collide, but they don't. But you also see many particles are distributed well and maintain distance to nearby particles. That's what you can expect. Even if there would be some obstacles, e.g. mountains, the particles would spread out through the valley and still separate if there is enough space. And there is no need for logic, priorities, order, or AI. It's just simple laws of physics which resolves the problem. That's what i try to say, and why it's worth to consider working with simulations.
You should look into research on path planning for multi agent simulations. Reciprocal Velocity Obstacles is one such technique that does collision detection not on the agents themselves, but on a shape representing the forward-predicted velocity. AFAIK this approach was used in some high-profile RTS games.
RVO2 is a library that implements this, which was used in the game Warhammer 40,000: Space Marine.
I think the crux of your question is: How can I clear up a traffic jam?
The simple answers are already given. Pathfinding should generally not include transitory obstacles, and objects should include a type of steering behavior that will automatically queue up, along with a pushing priority behavior to help eventually clear itself up as units start to slide through. Bottlenecks and choke points will always throttle traffic.
More complex systems are complex. You could build systems that incorporate complex flow mechanics, travel lanes, routes of highways and byways and flow control, systems that predict and redirect for congestion, and more. Unless you're building a traffic simulation game those are probably overkill.
for seen it all guys like you and with todays standards in mind it is probably simple, in my case it’s much more than that, it took a year to figure it out, and I’m still shaky about it and probably don’t understand all the implications yet.
“Unit A is blocked by unit B” means “unit A should move after unit B” (hoping that unit B is able to move and gets out of the way, allowing unit A to move later).
This is a partial ordering of units, which can be the source of a topological sorting (computed from collision tests) that can be used in the movement phase to decide the order in which units move and to detect clusters of mutually blocking units
