Pathfinding: What are the chances...

[Kloot]

I mean why is it than when i have a line of units facing right and i stretch a move line at a location to the left of my units all my units will get criss crossed...

a\ / a
b \ b
c/ \ c

Because the direction of the line is opposite to that of the unit iteration order if you draw it from "left" to "right" and the units happen to be sorted "right" to "left" or vice versa. There is almost no criss-crossing for a given group of units when you always draw lines with one consistent orientation.

CustomFormations works similarly for small groups.

I'm sure Custom Formations is relevant in some way though. It orders each unit a move command individually, so each unit has it's set move order to go to, each unit should have the most optimal path in terms of time it would take to get there, compared to any of the other units using that same path.

When there are N units (and N goal positions), you would need N*N path computations to find the optimal solution. Which gets expensive quickly, so it isn't done.

I agree the pathfinder has some issues

People say that a lot, yet never seem to be able to quantify them, hence why topics about Spring's PF usually aren't taken very seriously.

Also, the reactions to the FF algorithm on GPG's forums and elsewhere are far from universally positive, with insightful comments like

pathing is borderline broken

being no exception there either.

[Forboding Angel]

It is though!

Spring's pathfinding, whether it's better than other games or not doesn't matter, because it's still quite awful.

Everyone wants to advertise 500vs500 unit battles and blah blah blah, yeah we have it. We also have more units wrecking into each other than we have units shooting at one another. When the groups hit there is no orderly formation. It turns into one big snarl of chaos.

You don't see this happen often in commercial games for various reasons, but spring really needs some work done.

Anyone remember that game website's review of pure? Really liked the game but couldn't give it a decent score because of the pathfinder?

Or, we could just ignore it for another 5 years, I guess that option works too.

Edit: Btw that heat thing was showing some real promise from what I could tell. Any way of working that in to getting some more unit separation?

[Gota]

interesting...I just tested again and no matter how i drew the line i couldn't get them to criss cross...not sure how to recreate it but yesterday it did happen.

[Jazcash]

interesting...I just tested again and no matter how i drew the line i couldn't get them to criss cross...not sure how to recreate it but yesterday it did happen.

Yeh, as I said, it happened randomly.

http://springrts.com/phpbb/viewtopic.ph ... 42#p360242

[Jazcash]

There's also definitely something weird with the path system. I remember the first time I thought, "What the hell is this", was when I used to play SpeedMetal and when ordering units to go through the middle, they followed the edge of the circle which is a longer route than going straight through the centre.

Here, have another one of my wonderful diagrams:

[Tobi]

I can't reproduce criss-crossing units with custom formations widgets (and also IIRC it happens only seldomly in-game for me)

I can reproduce it only with the built-in line order, but 1) there is custom formations widget and 2) it will keep having that problem as long as it is capable of making rectangles of units instead of only lines.

I can't reproduce that speedmetal thing either, units move in a (relatively) straight line for me. (In other words, include more information (mod/game, unit, etc.) as apparently you applied an incorrect generalisation...)

[BrainDamage]

customformations has multiple algos, that get toggled according to unit size and some profiling of the pc capability to handle load, that's why it happends seldomly

there's the optimum algo, that produces the good result ( right pic ), the near- optimum with medium load ( left pic ), and the random algo

[Gota]

I understand.thx for the explanations.
I tried using the engine's bare formation movement using the alt key and criss corssing happened over and over again.
SA is now using this movement so that sux but obviously does not warrant any work on the engine since ONLY SA uses it.
This formation movement might come in handy later on though,if someone decided to make a game that uses formations extensively(total war anyone?).

Would be cool if Custom formation somehow integrated alt movement and ctrl movement into itself with some options you can modify to decide what you want to be used.

Of course the flow field used in Supcom,or something similar would also be cool to have as an option since its probably a better solution for a game with even bigger numbers of units than the ones we have ATM.

[Super Mario]

Of spring ever getting a system like this?

http://www.youtube.com/watch?v=jA2epda-RkM

One in a thousand if spring progress like this.

[very_bad_soldier]

I get really sad when watching those supcom2 vids

[Tribulex]

Crisscrossing has NOTHING to do with pathfinding. That is just a bug in whatever is giving the commands, whether its spring's sorting or customformations widget. Pathing is a completely different thing.

[Jazcash]

I can't reproduce criss-crossing units with custom formations widgets (and also IIRC it happens only seldomly in-game for me)

I can reproduce it only with the built-in line order, but 1) there is custom formations widget and 2) it will keep having that problem as long as it is capable of making rectangles of units instead of only lines.

I can't reproduce that speedmetal thing either, units move in a (relatively) straight line for me. (In other words, include more information (mod/game, unit, etc.) as apparently you applied an incorrect generalisation...)

Ah yeh sorry, the first pic is correct, the SM I labelled up wrong. Fixed it now.

The fail pathing happens randomly, it doesn't appear to depend upon how many units are being pathed, it sometimes happens with 2 units, sometimes 50. Most the time it works alright but every now and then a big hiccup occurs and I've got units flying all over the place.

[zerver]

I agree the pathfinder has some issues

People say that a lot, yet never seem to be able to quantify them, hence why topics about Spring's PF usually aren't taken very seriously.

This is not so strange. When you issue a move order and the pathfinder instantly fails, the replay will not help you prove your point.

Edit: or maybe it does? What happens to me is usually that I issue an order but the order is just silently ignored. Nothing happens, no move order seen when you hold shift. Network issues could probably cause the same thing, but I always tend to check my ping when something like this occurs and it is usually ok.