RTS template pathfinding :(

Hello,

I see that pathfinding... (or more likely units moving along path) still suffer from terrible overlaping.

If you move them several times (a bit further path), they eventally all end up on top of each other...

I persume that this is never going to be fixed...

(maybe its not even considered as an issue)?

Does anybody know, is there some sucessfull solution for this?

Thank you!

If you give the units physics behavior, they will collide with each other and not overlap. Just set the world gravity to 0 else they fall off your layout. <img src="{SMILIES_PATH}/icon_e_wink.gif" alt=";)" title="Wink">

I believe Arima has done it.

Alternately, I've done it using Rex's SolidPushOut plugin: https://dl.dropboxusercontent.com/u/577 ... solid.html

Set your unit to that behavior and set them to Solid.

You will have to customize the obstacle to something else rather than Solid, trigger it via on startup etc.

This approach works too and uses very little CPU processing so its fine on mobiles. The only downside is they look like bump cars sometimes, they push out a bit too much. But honestly its just a minor issue, otherwise visually and gameplay wise, its fine.

—

Thank you for your advices but:

1st solution is not working as one would expect...

They are pushing each other over the solids... then glide, spin etc... lotsa wierd stuff...

2nd is not working either... they are solid and they dont move.

any other ideas?

glide and spin can be changed via setting the physics variables in the behavior.

2nd option works fine for me, i opened the default RTS template, add the behavior (after install Rex's plugin first!) and they move but wont ever overlap. They push each other out whenever they contact. You need to change the obstacle in Pathfind behavior to CUSTOM and not DEFAULT to SOLID. Then on start of layout, add an obstacle to your unit. ie. "Wall" or "Barrier" etc.

—

OK, i am opening template...

added to "firendly bases" pushout solid behavior

nothing happens... they overlap.

then i add regular solid behavior

they are solid now and i cant move them...

i am now changing obstacles in Pathfind behavior to CUSTOM

they can move now but they cant navigate proper path... (they seem to plot a straight line and just stop at obstacle)

and enemy tanks are now crazy going straight through walls (i did not even touch them yet)

and now im kinda lost...

I just added that pushout and solid to Tank1Base directly, without doing it via the Family. Custom obstacle so they move. The walls are set as solid so they do hit the walls and cannot go through it.

Not sure about enemy tanks, i havent look at that RTS code template in detail. But what you want: Pathfind AI to not overlap and bunch units together is possible.

I use it in my own RTS game, some big fights have heaps on each side and they don't overlap.

—

let me share what iw done... just select them all and click to move

https://dl.dropboxusercontent.com/u/169 ... B/RTS.capx

Maybe i am doing something wrong?

This is an extremely complicated problem and even designers of top commercial RTS games struggle with it. There is not a clear, easy solution that works well in all cases. It's something you're going to have to experiment with and come up with something that works reasonably well for your own game.

Ashley

May i make one sugestion?

Can you create one more event in pathfinding behaviour that might get called "path blocked"

where unit would on path that was once was clear and executed but in the meanwhile becomes blocked (by friendly units or maybe new solid obstacles) try to recalculate new path?

thanx.

irina - that in itself is a very difficult problem and doesn't necessarily help. If two objects drive in to each other head on, do they both go in to 'path blocked' mode? What if a whole traffic jam or gridlock forms? The whole essence of the problem is really determining that, it doesn't help reduce it much. Also pathfinding by default does not try to avoid any other objects, so recalculating the path will just return the same path it was already on.

Ashley

Yes i know it is pretty dificult but just heat me out on this...

If im not mistaking pathfinding is grid based?

Can we somehow for every grid block set boolean value of 0 or 1 depending is it currently populated with passable (tiles, undergorwth etc.) or impassable items (solids, owergrowth, units... etc.) and calculate or recalculate move acording to the currently empty grid blocks?

Units could have asociated traffic advantage values so that unit with lower traffic advantage moves (eg. 1 grid block at 90° to the right) if gets in contact with unit that has greater value of traffic advantage and that is in "path moving state"?

Multiple selected units move to exact came location, spot... and eventualy stack on single grid block...

but if it was "populated" they shud target closest empty grid block and find a path to there?

Maybe multiple selected units could start movement with small delay in time so that one closest to the target coordinate x,y first calculate path and move... then second one, then third and so on?

If two objects drive in to each other head on, do they both go in to 'path blocked' mode?

easy.. they both make 90° (maybe even 45° would be enough) turn to the right, move to 1st empty grid block and recalculate path again.

if we consider my traffic advantage values one could move for the other to pass...

That would only take in to account the state at the time the path was calculated, and changes while the object is moving along would be ignored. It also would not take in to account other object's plans to move through there, meaning sending 20 objects off at once will promptly traffic jam them all in the same place. Taking in to account dynamic changes and other object movements would probably have a high performance overhead, and is difficult to implement given actual pathfinding happens in a separate JS context on a web worker.

The RTS template already avoids stacking at the destination by maintaining formation. I don't think adding delays would make any difference.

Your solution to head-on blocking does not work in the general case: if two objects wedge together beside each other (e.g. both trying to squeeze through a gap), both turning the same way will continue to jam them even worse. So one blocked evasion strategy is not enough: you need to take in to account their relative orientations, and possibly even the other surrounding objects, to know if they do in fact have room to do anything. I mean consider two objects hitting head on down a narrow alley - there is no room to turn, so they must reverse instead. If it detects the wrong thing, it will likely jam itself in an even worse position and may even get permanently stuck. This is far from simple.

I have spent many hours on this in the past and it seems pretty intractable to solve in the general case. Depending on the cell size is also a bad idea, since you might want to adjust that for performance or detail reasons. That's not to say it could be better, and I will try to come back to this and figure out some ways of making it easier to deal with, but I think it is far, far more complex a problem than you appear to appreciate. Objects moving through each other looks wrong, but actually works really well, so there's that.

As Ashley said, this is a very difficult problem, especially to solve for everyone's games which behave differently. I've got units pushing out of each other in my game with physics, but not only was that difficult to get working, it doesn't solve a lot of problems like paths blocked by units (not to mention being quite CPU intensive).

Ashley - I hope my suggestion here hasn't been forgotten. If we could define the area to update for the pathfinding plugin it would really help us to be able to change the map without pauses from regenerating the whole layout, which is almost always unnecessary.

Ashley

Thank you for your insight.

...cant find original topic but iw found one sample that works with dynamic obstacles:

https://dl.dropboxusercontent.com/u/169 ... _nogl.capx

Maybe this can be usefull?

Maybe to atleest set priority of physics objects in the pathfinding?

Your solution to head-on blocking does not work in the general case: if two objects wedge together beside each other (e.g. both trying to squeeze through a gap), both turning the same way will continue to jam them even worse.

...to add multiple checks: at 45° (to the left, than to the right), than 90° (to the left, than to the right) than reverse ... + earlier mentioned unit priority value to pushout other units?

That shud solve any possible JAM, no?

Arima

Are you willing to share some simple example capx with your solution?

Thanx!

Arima

Are you willing to share some simple example capx with your solution?

Thanx!

No, because that's the point - the capx is not simple because the problem is not simple. Even if I did supply it, my method is far from comprehensive and I'm trying to come up with methods to fix the blocked paths problem too - and really, I'm probably going to just have to fake it somehow because of how complex it is.