Bunch of vehicle stucks themselves after astar calculation

TwistedMind

Hello, so here a practical example:
From the left to the right: 1 - 2 - 3 - 4

Number 1 goes, after his first path step, to the path of the number 2;
Number 2 does the same for number 3 but at the step 3 (in red);
Number 3 goes straight on;
Number 4 goes to the path of Number 3 after his step 4.

In this case, the units move at the same time and a the same speed.

I think, but i'm not sure, each of them must check, at the moment they reachs their own actual step, if someone around them will join they own path next, and if this is the case, someone of them must wait to let pass the other(s).

But what should determine who will pass first ? ID priority or distance between them or something else, like a correspondance of the next path with neighbors ? What is the best ?

TwistedMind

Ok, so i restored succefully the old system to push and move the unit but i still have the traffic jam issue. Whit the new Astar setup implemented, the problem is, the groups must goes from the checkpoint to the final destination.

I suppose they must "move as formation" but i don't understand how i must do it, did i need a "center leader" or something else ? I don't know.

Here a link of the code which manage the step 1 and 2 below

xyz

TwistedMind They actually don't need to move as a formation.

You should first define the features of your movement system more precisely. The most important question for choosing the way to resolve traffic jams is; can movement be stopped while unit is in the process of moving to target.

TwistedMind

Movements ### have to ### stop when another unit is near in condition of this unit, or more, goes to the same point. My test and research led me to use a cone sensor (like a inversed house, not a triangle) to detect near units.

For the step 1 and 2 it almost works, but i'm not sure it is the good way. Units with high ID == high priority but i have some difficult do manage when the highest priorities are behind lowest... so i wonder if i wouldn't think the bad way...

xyz

TwistedMind No, I was asking if player can stop the issued movement command in the midst of its execution. For example if an unit starts moving from A to B, can the player say "stop moving now", while unit is still halfway between A and B.

TwistedMind

an the player say "stop moving now", while unit is still halfway between A and B

Yes he can tell to stop moving. For this, i suppose i can just reassign the actual path's step as final destination... what the link with my problem and this fact ?

xyz

TwistedMind So this is how you can approach the whole traffic jam problem. Read carefully, I won't type this twice 😉

Movement interaction looks like this, right?:

Player selects N units that they want to move from their current positions to some target position.
Player then clicks on the target tile to order selected units to go there.
At any time during this movement, player can stop it, in which case units stay at positions they reached thus far.

To get tile paths for each selected unit:

Assign a priority value to each of N selected units.
Find N passable tiles nearest to target tile and assign each to one of the units as its final position. If you need units to finish in a formation, choose tiles that constitute wanted formation. If some tiles in that formation are non-passable, use nearest passable tile instead. If you don't need a formation, simply choose N free tiles nearest to the target tile, sort them by distance to target tile, and assign as targets to units by priority.
Now each unit has a distinct start and end tile for the movement
Let the A* setup calculate the tile path for each unit (our infamous step 2)

Now that each unit has its tile path you need to do a preliminary step before they can actually start moving:

Let each unit holds a reference to all other selected units whose tile path overlaps with its own path, and whose priority is larger than its own priority.
We'll call this list of units the right-of-way list.

Units can now start moving:

Each unit moves tile by tile in succession
When an unit needs to advance to the next tile, check if any of the units from its right-of-way list is currently moving to that tile. If yes, wait for some short time and try again later.
If there are no such units - move to the next tile

And that should be it.

Note that this will work even if units move at different speed. You can also issue new movement commands while previous movement is in progress, as long as all moving units are following the same protocol, and their right-of-way lists are properly updated.

TwistedMind

I think i'm close to solve this but one actual point is not clear:

xyz Let each unit holds a reference to all other selected units whose tile path overlaps with its own path, and whose priority is larger than its own priority.

If i have 3 units: ID 6, ID 9 and ID 12.

ID 12 will move freely and pass the others, than 9, than 6. But ID 9 has the positions in the crosspath, the positions between this crosspath and the last position. I just need the crosspath and the final position, but if i want ID 9 push ID12 at the final destination, did i need to use a ray sensors or i can use the reference list ?

Because ID 9 doesn't understand ID12 is front of him. It allowed to move but the next path where ID 12 goes make disallowed that.

Here the code which generate this reference list for each selected units:

# platoon is a empty list variable in each units

for index1 in range(0, listUnitToMove.size()):
		for index2 in range(index1, listUnitToMove.size()):
			if index1 != index2:
				var unit1 = listUnitToMove[index1]
				var unit2 = listUnitToMove[index2]
						
				for path in unit2.unitPath:
					if unit1.unitPath.has(path):
						unit1.platoon.append([unit2, path])

TwistedMind

Movement interaction looks like this, right?

Almost: When the player select one or more units, there are two configurations:

If the selected units aren't assigned to a group (as number X), they must go to the same position and push if necessary at this position (like you can see in the step 2 of my previous screen, where the unit 10 is actually, so units at Vector(-3, -6), Vector(-2, -6) and Vector(-1, -6), must go to the position(0, 0) ).
If the selected units are assigned to as group, they automatically must be in formation at the destination, like what you explain.

That will, and must be checked before moving the units, of course.

Assign a priority value to each of N selected units.

Not before ? What append if i have two groups and if i want to move one of then "on" the other, to merge them ? I mean, what append if ID 1 group 1 detect ID 1 group 2 ?

And if I have two unassigned "platoons" ? I will have two same ID, so duplicate ones.

xyz

TwistedMind Well, you can do with priorities whatever fits your system best. They can be permanent properties of units, or they can be assigned for each move based on some criteria like speed or importance... I assumed the latter but you can do anything as long as each moving unit has a distinct priority. That way the movement precedence between two clashing units can always be unambiguously resolved. Nuances in priority assignment mechanism don't really make much difference for the main algorithm.

xyz

TwistedMind You don't need to store any overlapping tiles, only references to other units whose path crosses with unit's path. The idea is to check on every move from tile to tile if any of higher priority units is currently occupying (or moving to) tile we want to step into next.

So if unit's tile path is for example: [ (0,0), (1,0), (2,0), (3,0) ]
When it wants to move from (0,0) to (1.0) it first needs to check if (1,0) is occupied by any of referenced higher priority units. If not then it can move to (1,0)
Same for the next move from (1,0) to (2,0) and so on. Each consecutive tile needs to be checked when the time comes to move to that tile.

You can optimize to check only at overlapping tiles, but that can be done later when you get the basic system working properly.

TwistedMind

it's not okay... something seems bad.

First, units need to have a reference of each units move on their own path, i'm agree. But what data should i must add ? The unit's main node only or the unit's node with the point crossing ?

Then, when at least 2 units reach a same point, the check system must be as map coordinates or world coordinates (i mean map_to_world / world_to_map) ?

When a unit detects another in the same path, what form the waiting must be ? A timer or something else ? I actually use a timer for the waiting sequence and i wonder if it's a bad idea.

xyz

TwistedMind
Every moving unit should keep its current and next tile coordinates as a part of its state. So you can check if unit is transitioning to a specified tile at any given time.

You can wait with timers. Again, this could be optimized later but timers are good enough for prototyping the system.

TwistedMind

I'm very, very close to solve the problem:

One part of the units move with fluidity, sometimes some units are moving but not detects other units because they aren't not in the next step so i'm forced to use a frontal sensors to stop some of them. This is because the ckecking is done when a unit reach his step. Doing this in loop, i think, will be a high cost of memory/performance but maybe you expected that and speak about later ?

One other pack of units seems to need a "deviation" because they block each other because of astar's checkpoints. For exemple, if i move only unit 24, it go where it is actually on the screenshot, them it must go to upperleft (so it goes back to one tile). Logically, it should go directly to the destination, but we didn't consider this.

Unit 24 is blocked by unit 17, unit 17 must go where 24 is and 24 must go were 17 is.

Another point we don't consider is the fact of one unit move through unselected units (so they are out of the reference list), it pass through if i disable the frontal sensors i made, it should push them instead.

TwistedMind

I have a idea: because of astar building, the unit follow stupidly the path, but if i make a comparison distance to the final point with the next checkpoint, if it's goes away, that's mean this point does not be added, or removed.

Does that seem logical or a better way to do it ?

edit: it seems to works as expected, except for some units who pass on invalid cells because they exclude one critical astar's checkpoint. Otherwise they go all in the position and with order, so maybe it's the best trick to do ?

TwistedMind

Is there a way to choose another "closest" astar's node when the start position is distant (the one in blue) ?

xyz

You should have a clear idea of exactly what model of movement you want to implement. Otherwise the new gotchas will pop over and over. I suggest you find an existing game that has the exact movement model you want to use, analyze how it handles various situations, and then try to implement that.

TwistedMind

This step is already done, xyz. But words is too complicated. Here the model i looking for to reproduce.

Please go to 2:06... If you need more informations ask me.

TwistedMind

That's it, I made it !

So, when it use Bresenham to determine the type of way (classic or astar), if is it astar, i must check what is the closest astar point at the current Bresenham list's point. If the astar node distance is too far in comparison of the position distance of the unit, to the mouse position, so we need to check another node. When this node founded and the first is more closer, we make the path from this node, i "change" the closest node to choice if you want.

But if we do a move in other direction, this doesn't works, except if we add as condition we found a non-passable cell too soon, in this case, we use the "normal" closest node. And the result is great ! Some of units goes directly to the mouse position, some others make a little "deviation" but no one blocks the others.

TwistedMind

@xyz , you have mentionned "optimisation" instead using timer, is there a difference between memory consumption and have you got something to say before i mark this topic as solved ?

xyz

TwistedMind There will be plenty of opportunities for further optimizations and you'll probably encounter some bugs and misbehaviors down the line. But all in due time. Optimize only if/when the performance starts suffering. I suggest you start new threads with any specific problems that pop up.

This thread should take a bit of rest. Entering a triple digit post count, I think it deserved it 😉.
Hopefully, you've got something useful out of it 🙂

« Previous Page Next Page »