Hello everybody.
Today, a very … uncomfortable problem i met some time ago and that follow me since then.
I am not talking here about A*, Djikstra or whatever algorithm of this kind. It’s a more high-level problem.
First, have a look at that picture: 
There is three place named [A], [B] and [C]. Units CAN cross in the place.
The path between two places is written with the pipe glyph (for example, the path between [A] and [B] is |AB|). Unit CAN’T cross in a path.
There is two units, (a) and (b).
Tip: [] is like a box, it’s a place, || is like a pipe it’s a path and () is like a ball, it’s a unit.
Distance of |AB| + |AC| is < to distance of |BC|
For all paths the order between letters is not important (i.e. I write |AB| or |BA| to design the same thing).
(a) starts in [A], (b) starts in [B]
We can use :
- Calculation per frame or only when we initiate the movement.
- Path locking, i.e. we acquire a path and nobody else can use it.
- :
(a) wants to go to [B], (b) wants to go to [C]
1.1 : we use: calculation when we initiate the movement and no path locking.
(a) looks for the best way (=shortest) to go to [B] and find |AB|.
(b) looks for the best way to go to [C] and find |AB| too.
(b) enters in |AB|, then (a) enter in |AB|. They collide, they can’t reach theirs destinations.
1.2 : we use: calculation per frame and no path locking.
Step 1:
(a) looks for the best way (=shortest) to go to [B] and find |AB|.
(b) looks for the best way to go to [C] and find |AB| too (he plans to do |BA| then |AC|).
Step 2:
(b) enters in |AB|
(a) detects that the |AB| is no longer an option, so he decides to switch and go |AC| then |CB|.
So, (a) enters |AC|
Step 3:
(b) detects that he can no longer do |BA| then |AC|. So, he looks for the shortest way and finds |BC|.
So, (b) leaves the |AB| (he goes back).
Step 4:
(a) (who is currently in |AC|) detect a shortest path to go to [B]: |AB|
So, (a) go back and return to [A] (he plans to go to |AB|)
(b) detects a shortest path to go to [C] : |BA| + |AC|.
[Go to step 2]
1.3 :
If we use path locking, I’ll introduce a new scenario: (b) wants to go to [C] and (a) wants to go to [C] too.
So, if (b) lock the whole path (i.e. |BA| and |AC|), (a) will wait a lot of time for nothing.
However, if (b) doesn’t lock the whole path, if he just lock |AB|, we can imagine that when (a) and (b) are in |AC|, (a) just receives the order to go back to [A]. So, if (a) goes back he will collide with (b) but if (a) doesn’t move it will also collide with (b). Actually for these case we can imagine specific comportments like “I can’t receive orders while I am not in a place” but it will lead to some unwanted behaviours.
Plus, if we imagine that (a) and (b) don’t belong to the same player (like in starcraft where players are fighting with each others), it would be strange to have (a) that waits kindly to let (b) pass. If (a) has the order “attack on sight” the situation is clear, but if (a) has the order “move to [B]” then (a) and (b) will just dumbly collide forever. What I mean is: path locking can be (maybe) a solution if the two units belong to the same players but it’s obviously not a solution otherwise.
Plus, with path locking I have this image in my head:
About this problem, I can easily create bigger version of it with (a), (b) and © (or more) taking different road and “looping” (going back and forth) forever.
Also, remember that in most rts game you’ll give orders to a lot of units in the same time. So, if each unit locks the path for itself it’s not gonna anywhere.
So, do you have any idea? I think that the root of the problem is close to the limit of algorithms, i.e. decidability. A perfect solution would be to have a program that analyse each path of each unit, understand (predict the comportment in the future) it and decides what to do. However, we don’t have an analysable (not Turing complete) language to code our a.i. and theirs movements so we use the all-mighty-dirty Turing completes languages.
It’s also close to problems about concurrency (which in root suffers too from the same problem of non-analysable languages)
What I mean is : I can detect the very specific case I gave to you with only 2 unit and 3 place, but I want a solution to handle bigger cases of the same type.
Any idea ?