RTS template pathfinding :(

Discussion and feedback on Construct 2

Post » Wed Jun 11, 2014 3:41 pm

@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?

Ashley wrote: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...
B
26
S
11
G
2
Posts: 669
Reputation: 5,038

Post » Wed Jun 11, 2014 4:25 pm

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.
Scirra Founder
B
395
S
232
G
88
Posts: 24,371
Reputation: 193,772

Post » Wed Jun 11, 2014 5:41 pm

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 request-regenerate-portion-of-obstacle-map_p671110?#p671110 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.
Moderator
B
94
S
33
G
33
Posts: 3,006
Reputation: 27,749

Post » Wed Jun 11, 2014 7:03 pm

@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?

Ashley wrote: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!
B
26
S
11
G
2
Posts: 669
Reputation: 5,038

Post » Wed Jun 11, 2014 7:39 pm

irina wrote:@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.
Moderator
B
94
S
33
G
33
Posts: 3,006
Reputation: 27,749

Post » Thu Jun 12, 2014 7:05 am

@Ashley

How about to atleest implement soft colision checks like explained here?

https://www.youtube.com/watch?v=VMI2nLC7i5w#t=126

http://www.adityaravishankar.com/2011/1 ... avascript/
B
26
S
11
G
2
Posts: 669
Reputation: 5,038

Post » Thu Jun 12, 2014 10:12 pm

@Ashley

Ok, so basicly... current pathfinding breaks every other logic that we try to implement... physics colision, other form of solids or any formulas that prevent units overlaping and you still dont se this as a problem???

Thanks.
B
26
S
11
G
2
Posts: 669
Reputation: 5,038

Post » Thu Jun 12, 2014 10:47 pm

I found this paper that might be interesting/useful to Ashley if you don't know it already.

Its written by a David Silver from The university of Alberta and called "Cooperative pathfinding", and seems to offer an alternative to A*, I don't really know a lot about it or whether it will be useful at all, to be honest, but it seems to cause some interest around the internet.

Anyway here it is, its only 14 pages.
http://www0.cs.ucl.ac.uk/staff/D.Silver/web/Applications_files/coop-path-AIWisdom.pdf

Here is an example of someone who have implemented it, and supplied the source code in Java as well.
http://www.jkilavuz.com/whca/
B
44
S
11
G
2
Posts: 1,182
Reputation: 6,838

Post » Thu Jun 12, 2014 10:59 pm

B
26
S
11
G
2
Posts: 669
Reputation: 5,038

Post » Thu Jun 12, 2014 11:29 pm

this is the best iw managed to fix it so far:
https://dl.dropboxusercontent.com/u/169 ... e-RTS.capx
B
26
S
11
G
2
Posts: 669
Reputation: 5,038

Previous

Return to Construct 2 General

Who is online

Users browsing this forum: Yahoo [Bot] and 34 guests