Pathfinding and group movement improvements

[Gabba]

A group of Spring units still seem to follow individual paths and move in a kind of "bumper cars" fashion, where they constantly collide with units of the same group heading for the same point - and it gets worse when they cross paths with units going in another direction.

The customs formation widget (the one with which you draw a line) kinda helps with this by having parallel paths instead of converging ones, but only if you have few units, and even then the "bumper cars" behavior tends to surface since the unit paths are so close.

I think a very good goal for Spring would be to integrate pathfinding of the quality found in Supreme Commander Forged Alliance (groups of units are handled intelligently and synchronize their movement, no bumper cars) and especially Supreme Commander 2 (use of flowfields, groups of units can collide and handle the situation elegantly; large units interact well with groups small units).

The first part of this video shows SupCom 1-level movement, observe units moving in formation without mutual hindrance. The second part shows SupCom 2 flowfield pathfinding, which is frankly pretty awesome.

The research is out there on the 'net, I'm posting this in the hope someone has the time and skills can implement those improvements (I might have the skills with a lot of research and effort, but definitely not the time). I think it would massively improve the professional aspect and mass appeal of Spring, and possibly bring performance improvements (bumper cars cause constant recalculations of paths, which can't be good for perf).

Edit: after posting this I found this happy, friendly, constructive and optimistic (so, typical of our amazing Spring community) discussion about the same video.

Edit3: Those impressions are still valid for Spring 87.0

[Kloot]

Yes, this has come up a few times before, though opinions from people who have actually played (GPG's) SC2 tend to be less positive.

Also, I implemented the flowfield / CC algorithm a while back (some surviving videos here) and found it lacking in performance, both on the "how well it works" front and on the "how much it costs" front, so a transplant to Spring was not in the cards.

[BaNa]

Yes, this has come up a few times before, though opinions from people who have actually played (GPG's) SC2 tend to be less positive.

Also, I implemented the flowfield / CC algorithm a while back (some surviving videos here) and found it lacking in performance, both on the "how well it works" front and on the "how much it costs" front, so a transplant to Spring was not in the cards.

awwww i thought that was going to happen$

[Gabba]

Yes, this has come up a few times before, though opinions from people who have actually played (GPG's) SC2 tend to be less positive.

Also, I implemented the flowfield / CC algorithm a while back (some surviving videos here) and found it lacking in performance, both on the "how well it works" front and on the "how much it costs" front, so a transplant to Spring was not in the cards.

Wow ok, I didn't know that you actually went and implemented it. I can imagine it's pretty costly, but too bad you couldn't get it to work satisfyingly. (I'm gonna fire up SupCom2 to see how well it worked in-game, pretty well from what I remember.)

Well, that still leaves the "group movement" part of my suggestion. Even Supcom 1 unit are good are getting automatically in a spaced formation and moving without any bumper cars effect. Of course bumper cars happen when the meet other groups or large experimental units, but it would already be a big improvement.

[luckywaldo7]

As I recall supcom 2 pathfinder was pretty good, but the flowfield-pathing didn't really work as advertised, especially in chokes and around obstacles like buildings. (Actually some people have theorized that this is why there are no wall structures like in supcom1/FA - the pathfinder wasn't able to handle them)

Here is a widget that does sort of what you want: http://springrts.com/phpbb/viewtopic.php?f=23&t=23773

It doesn't keep them in tight formations all the time, just spreads out the move command order so your units aren't all fighting for the same spot at the end. But that alone is a pretty big improvement to moving unit groups around, in my experience.

[Gabba]

Well I just started SupCom 2 and tried moving large groups of units through each other, around experimentals and through rows of buildings. Overall it works as advertised in the video. Obviously they presented the optimal case in that footage, and it doesn't always look that good, but it works.

Units do seem to react to buildings a bit at the last minute, and GPG cheated a bit by making small turrets pass-through for your units but otherwise the whole thing is incredibly smooth. The main point (which was already true in Supcom 1) is that you can order around your units while zoomed out without hassle, and that even a group of diverse units will move around without units lagging behind, and the whole group quickly stabilizes and stops any bumping when disturbed, whether stationary or in motion.

I'd like to find time to make a video, but anyways there are many videos of those games on youtube... including my favorite channel for commented Supcom:FA gameplay.

[Gabba]

Sorry for double-posting, but I wanted to share a separate idea: would you devs be able to separate the pathfinding code from the rest, just like the AI resides in separate DLLs?

This would allow several algorithms to exist separately and to compete, and would lower the barrier for outside people to contribute new ones. Said outside people (or past contributors like me who pay an occasional visit) are often afraid to dive into the whole codebase and to try go get their work accepted into the official build, because of the huge time and effort it represents. But if faced with a clear API and some code examples with other already implemented pathfinding DLLs, the barrier to contribution would be much lower.

I hope this is possible, and that the pathfinding code is not too entangled with the engine core to separate it neatly from the rest.

[Kloot]

I can imagine it's pretty costly, but too bad you couldn't get it to work satisfyingly.

To be fair, it works better if you are willing to give up realism in the motion model (in which units have limited turn- and acceleration-rates) and trade it for SC2's "inertialess" movement. The algorithm was really intended for pedestrian crowds, so any attempt to use it for other types of actors is going to be suboptimal.

Well, that still leaves the "group movement" part of my suggestion. Even Supcom 1 unit are good are getting automatically in a spaced formation and moving without any bumper cars effect. Of course bumper cars happen when the meet other groups or large experimental units, but it would already be a big improvement.

Spring's equivalents of those spaced formations are hidden behind ctrl+lmb and ctrl+alt+lmb, although over longer distances you still run into the problem of converging / intersecting paths. Solving that would get into backbone pathfinding territory.

Here is a widget that does sort of what you want: viewtopic.php?f=23&t=23773

It doesn't keep them in tight formations all the time, just spreads out the move command order so your units aren't all fighting for the same spot at the end.

That just does the same as ctrl+lmb afaics.

would you devs be able to separate the pathfinding code from the rest, just like the AI resides in separate DLLs?

Pathfinding code has already been unentangled (not quite to the point that it can live in a DLL, but that would not be a big step), however pathfollowing code has not. Unfortunately, more advanced algorithms like CC need control over both.

[smoth]

was going to give a nice long reply but these suggestions are frustrating to read.

Supcoms maps are EXTREMELY simplistic when compaired to springs maps and the path finding needed to navigate them.

Spring has units with variable speeds of acceleration and deceleration. Spring slopes are very complex with some pretty wide slowdown gradients.

you can always try this:
http://springrts.com/phpbb/viewtopic.php?f=14&t=27623

and use maps with relatively simple structure, aka speedmetal. Anything with fine details(aka my maps) will have some path difficulties due to the variable slopes and high hills.

Tl:dr: supcom has simple maps and simple unit movements when compared to what spring's pathfollower has to deal with. You are making a comparison of apples to oranges saying that apples should taste like oranges because apples are round to.

[zwzsg]

SupCom 1-level movement, observe units moving in formation without mutual hindrance.

SupCom 2 flowfield pathfinding, which is frankly pretty awesome.

Oh, you mean awesome pathfinding like in this Spring video: http://www.youtube.com/watch?v=_HcaumIB20Q ?

Now we just need Kloot secret recipe.

[Gabba]

It's all well and good to defend Spring and to say maps/units are more complex, but I don't think it's a good way to approach the situation. Fact is, it's been 4 years, and the overall perceived quality of unit movement has not improved for the player. That's bad.

Maybe Spring should shed some complexity that doesn't really amount to interesting gameplay. I think that the ridiculous unit movement is one of the things that holds the various games back and makes them look stupid to many people. I personally cringe everytime I check back, and I've been an fan of this project from the start.

But for a more immediate goal, most maps have a good amount of flat ground, and that's where players usually move large forces. If unit movement could at least be SupCom1-coherent on flat surfaces, it would be a huge improvement. You kinda expect formations to break up if you send units into broken terrain...

(Interesting points btw. I actually did not realize that SupCom 2 units are inertia-less, and the funny thing is that I think almost nobody noticed... complaints about this game weren't about that. It kinda suggests units with intertia are not that useful for gameplay.
On the other hand, according to this, SupCom1 units at least do have turn rate and max speed, so group movement in Spring similar to that game is perhaps not that far-fetched. I do realize that some maps are more complex than the SupCom ones, but those do still have slopes and slower terrain for land unit -- fordable water -- so I wouldn't dissmiss SupCom's pathfinding so easily.)

Pathfinding code has already been unentangled (not quite to the point that it can live in a DLL, but that would not be a big step), however pathfollowing code has not. Unfortunately, more advanced algorithms like CC need control over both.

I'd encourage you devs to unentangle the pathfollowing too, then. I think I could really bring healthy competition like with the lobbies and AIs.
People should also be able to implement intertia-less units in their games (if not already possible), so that if we can't get the most complex setup to look good, we can at least allow people to make, say, an open-source game technically equivalent to SupCom 2 with the economics and unit scale inspired by SupCom 1. Which would be an awesome achievement.

you can always try this:
http://springrts.com/phpbb/viewtopic.php?f=14&t=27623

Took a look, that's pretty interesting. Doesn't invalidate my suggestions above.

Oh, you mean awesome pathfinding like in this Spring video: http://www.youtube.com/watch?v=_HcaumIB20Q ?

Kloot already linked to his videos. Unit movement definitely isn't as smooth as Supcom 1 on that, but unit avoidance very good. Unfortunately I guess we'll never see that in Spring because of other technical problems like performance?

[Kloot]

Kloot secret recipe

squeamish ossifrage

If unit movement could at least be SupCom1-coherent on flat surfaces, it would be a huge improvement.

Like this?

People should also be able to implement intertia-less units in their games (if not already possible)

That has been supported for a long time, just not used by any project that I'm aware of.

Unfortunately I guess we'll never see that in Spring...?

Actually it is already in Spring, but being a recent addition still not seen much.

[Gabba]

Like this?

/me is impressed. It's almost as good as SupCom 1, only thing missing is that units don't get into formation while moving, only when they have reached their destination. At least, that's what I concluded from the footage.

People should also be able to implement intertia-less units in their games (if not already possible)

That has been supported for a long time, just not used by any project that I'm aware of.

The thread Smoth linked suggests that EvoRTS does it, actually. Good to know that it's possible.

Unfortunately I guess we'll never see that in Spring...?

Actually it is already in Spring, but being a recent addition still not seen much.

Well, I fired up latest BA in 87.0, and units still moved as a spastic blob. Is it something the games have to enable, and is it related to the much-decried (haven't followed that story much) heatmapping feature?

[Google_Frog]

It may be "already in spring" but no game devs have any idea how to set up the tags for the new functionality. If noone knows how to enable an improvement the improvement isn't quite finished.

[PicassoCT]

Hi, im a dev, and im shy! Peopl bitching all them time, make me hide my masterpiece.

[smoth]

It's all well and good to defend Spring

-1 respect for you.

I don't defend spring. I am just saying your are very ignorant, was trying to be nice.

[Gabba]

@smoth I was gonna write a vitriolic answer, but what's the point. Even though you're a rude individual whose respect I couldn't care less about, you contributed more to the project that I'll ever do, so I respect you for that.

If you bash anyone who tells you which aspects of Spring suck and are obstacles to the project's progress, though, you'll be responsible for its stagnation.

Of course I'm clueless about some of Spring's technical aspects, my point of view is from the gamer's perspective.

[smoth]

@smoth I was gonna write a vitriolic answer, but what's the point. Even though you're a rude individual whose respect I couldn't care less about, you contributed more to the project that I'll ever do, so I respect you for that.

PFFT what I have done only merits my words a little credence. I was trying to be nice and give you a direct to the point answer. You took it like:

"Took a look, that's pretty interesting. Doesn't invalidate my suggestions above"

never said it invalidated anything did. You took it that way.

I could post more bits but what's the point right, you already don't like me because of 1 thread. I might have stayed around and helped you shape out your idea but your defensive post and assertion that your idea was still the correct one sapped all of my will to continue.

If you bash anyone who tells you which aspects of Spring suck and are obstacles to the project's progress, though, you'll be responsible for its stagnation.

I could ACTUALLY bash you but I don't really see the point, to you a slap on the shoulder is a punch in the face.

Of course I'm clueless about some of Spring's technical aspects, my point of view is from the gamer's perspective.

Yes you are, and that is what I was <-[past tense] trying to help you fill in the gaps.

It's ok, you can tell the guy(kloot) who has spent years looking into different approaches for pathing your half thought out idea is better. You can rage at the content dev who tells you some of the extra stuff you are not really considering. You get answers like squeezing blood from a turnip.

[PicassoCT]

What actually would help is bundle huge groups with priority ("First Class Cannonfood for the Frontline.. dont stop those guys") into a metaUnit collisionwise, that collides (depending on groupsize) ahead of time with units who go into the other direction. It might not be that ellegant (there is a obvious gap, and still the unit circles around those cans ) and there would have to be a sizelimit (omg solid walls of units, i cant go anywhere effect could be exploited)

Still you know.. we have no clue of the code, we wont do any work, so if the Devine have no mercy upon us mortAlls this is just trouble for the next generation.

[zwzsg]

squeamish ossifrage

Nice nerd reference, but I'm also eager for a serious answer: I would really like to have units flow so smootly in KP, connections moving unimpeded through sea of packets like the gollies in your vid, but I'm not really sure where to start with. Does it require an experimental build of Spring? Do I have to enable special pathfinding options in the ModRules? Is it all about setting appropriate masses? Is it about the moveclasses, the unitdefs, or both? Are our games pathing broken because of missing tags or other silly mistake?

What is it that I have to do to have big and small units path like in your vid?