Configuration variables for the various path optimizations

[tzaeru]

Hi,

Currently, the thing I struggle the most with in the game is -- you guessed it! -- pathfinding. The problem isn't really that pathfinding was bad or stupid, as it is neither. Instead what I find is that the pathfinding is a little too optimized. There are two behaviours manifesting in particular that are hard to deal with in tight spots and lead to a lot of units lost for no real reason other than being unable to do what you wanted to do with them.

Firstly, large groups of units over long distances tend to lock to the same paths. This causes your units to flock together and at some point, you have to stop them, set them into a formation and use this formation with relatively short waypoints to keep them spread out in a line.

Secondly, when you order your unit to move to a spot, they rarely take a direct, straight line there. Instead, they tend to try to find the most optimal path. Unfortunately, this path is only so-often the actual path you want and may cause your unit to turn to a different direction than you were planning for it, which in the worst case scenario, blocks it from even firing at the target you intended for it.

For example of the latter case, consider you've a bunch of LLT set uphill. You drive your Janus down to one-strike the opponent LLT and plan to immediatelly retreat to the range of your LLT which would threaten any units planning to take retribution upon your Janus. You order the Janus to back up the hill and.. ..To your astonishment, it drives down a little, heads left for a while, then turns more to left and starts to go uphill.. And gets killed by the units tailing it, that never come to your LLTs range.

I am not fully sure if the two described issues are really a manifestation of the exact same optimization, but what I do still wish is that there were more configuration options for the path optimizations.

In practice, I would like to be able to play games where my units take very close-to straight lines when I order them to. If I'm not planning to have thousands of units, I don't need groups sharing their paths. If I want to micro my crucial units, I don't want them to take anything but the straight line exactly where I told them to.

Thank you for reading. ^_^ I understand that these are really decently complicated issues, that have no trivial fixes to them, but I hope that these issues can still be given consideration to. I really think the pathfinding system is quite well-made in the end and when comparing to commercial RTS games. Sometimes, it's merely.. Too well made!

[Kloot]

1) ask your game dev(s) to add support for a custom CMD_RAW_MOVE with a gadget that calls Spring.SetUnitMoveGoal to give units "raw" move instructions (https://springrts.com/wiki/Lua_SyncedCtrl#Unit_Control) whenever such commands arrive
2) write a widget that reads your mind and issues those commands instead of regular CMD_MOVE's exactly when you want it to
3) ???
4) profit (or watch your units get stuck)

[tzaeru]

1) ask your game dev(s) to add support for a custom CMD_RAW_MOVE with a gadget that calls Spring.SetUnitMoveGoal to give units "raw" move instructions (https://springrts.com/wiki/Lua_SyncedCtrl#Unit_Control) whenever such commands arrive

That sounds actually very useful and potentially something that can be hugely redeeming here, thanks! :) There's a lot to like in 0.98 (and, by the looks of it, in the upcoming 0.99).

The thing there is that the "get to point I clicked as fast as possible" is really only so-often a desired feature; It makes the units prone to pick same paths and makes it hard to reason about where, exactly, unit will turn towards to after a move command etc, which is actually quite crucial in games with more focus on unit tactics than economy. I do think that it'd be ideal if there'd be somekind of a treshold for "if the path with lowest cost has only a marginally lower cost than the shortest path, pick the shortest path"; I guess this would be a bit heavy performance wise though, as often two paths would need to be calculated..

2) write a widget that reads your mind and issues those commands instead of regular CMD_MOVE's exactly when you want it to

Well, my first thought was somekind of a modifier key for it, but if mind-reading is really what you think is the best approach, I'll give it a shot!

[Anarchid]

What with units now capable of pushing each other and flowing in fields, i think the real oppression is that pathfinder finds paths "on maps" (by movetype) but doesn't find paths "for units". What i mean by this is:
1) The pathfinder doesn't know that units are not points. Units with footprint greater than a certain narrow passage will experience issues.
2) The pathfinder doesn't know about unit maneuverability limits. It expects slow-turning low-acceleration tanks to be able to turn on a dime and move at constant speed.

Both are typically experienced with tanks and ships, which tend to be bigger and pounderouser than other standard unit archetypes.

Corollary: games that avoid these issues (small units with starcraft-esque movement) have the least reasons to complain.

This post is just observation. I have no suggestions, solutions, or ideas to offer.

[tzaeru]

I think the ability to issue raw move commands is really a great fix for small games where optimal play requires a great deal of unit microing. I like it it a lot! Huge thanks to whoever implemented it.

With tanks and ships in larger games, yes, there's a bit more trouble with movement. But I know from months of trying to get complicated pathfinding scenarios with Newtonian physics to work, that these issues are insanely complicated and often computationally heavy to solve. Would have no idea about how to fix these things.

[Kloot]

I did.

Newtonian-aware pathfinding is conceptually easy (just recursively sample the possible future physical states of a unit from your simulation, discretized over space and time) but computationally infeasible for RTS or any other 'RT' genre.

The Starcraft movement model works best (as I have explained many times before) because it least violates the assumptions and simplifications made by a typical PFS like Spring's. More complex models deviate further and therefore unsurprisingly run into more problems. This happens whenever two dependent systems are not in alignment, it's unfortunate but old news.

[tzaeru]

Yeah, I know it's old news, but I do believe that while making it - or really, almost any system - perfect would be not only impossible but potentially a huge waste of effort, once in a while there can still be an idea or two that let the state of affairs take a step closer to optimal. No need to make it perfect; making it a little better now and then is good enough, as you've done with the raw movement functionality.

Newtonian-aware pathfinding is conceptually easy (just recursively sample the possible future physical states of a unit from your simulation, discretized over space and time) but computationally infeasible for RTS or any other 'RT' genre.

Mmhm yeah.. When I was working with such systems, I first tried a kind of a recursive approach that, if it finds a movement plan to be too crappy, will start gradual, small changes to it based on a bunch of different heuristics. Eventually it did work... ...With 2 units and maybe half a dozen obstacles, while the code was way too complicated when it tried to optimize things.

EDIT: Fixed sentences and typos, too much coffee, can't write..

[Kloot]

of course, we all love useful little hacks so be sure to send in any you have

[Anarchid]

Ok i got interested enough and there's this, which claims to not be utterly inefficient.

[Google_Frog]

Don't get too excited about CMD_RAW_MOVE. You're all forgetting how sarcastically the solution was suggested.

1) ask your game dev(s) to add support for a custom CMD_RAW_MOVE with a gadget that calls Spring.SetUnitMoveGoal to give units "raw" move instructions (https://springrts.com/wiki/Lua_SyncedCtrl#Unit_Control) whenever such commands arrive
2) write a widget that reads your mind and issues those commands instead of regular CMD_MOVE's exactly when you want it to
3) ???
4) profit (or watch your units get stuck)

This issue is, of course, with step 2. Exactly zero pathfinding complaints would be fixed by implementing a separate command which lets players choose whether they raw move. The command would be

• So obscure that few people know it exists.
• Awkward to issue compared to just right clicking.

so a mindreading widget is the only option. I may have suggested to the Gravitas people that they should use raw move for within-room travel but that was only because their maps were simple concave rooms with doors between them. Anything more complicated and you are effectively rewriting the pathfinder in lua just to figure out when raw move is reasonable.

In practice, I would like to be able to play games where my units take very close-to straight lines when I order them to. If I'm not planning to have thousands of units, I don't need groups sharing their paths. If I want to micro my crucial units, I don't want them to take anything but the straight line exactly where I told them to.

I stated my solution in a recent thread on pathfinding: viewtopic.php?f=1&t=33334&start=20#p568318 . I will restate it for this context.

Our movedefs have a slopeMod entry which defines two things about units which use the movedef:

• How their speed will be affected by moving up hill.
• How the pathfinder and pathfollower thinks their speed will be affected by moving up hill.

My solution is to simply split slopeMod into two variables. One that controls the actual cost of going up hills and another which controls the pathfinder and followers perceived cost of going up hills. Then gamedevs can set a low perceivedSlopeMod and cause exactly the type of unoptimal paths that players are suggesting.

[tzaeru]

Yeah, I was thinking something very similar in the morning while contemplating if getting up to work at all is a good idea or if I just should stay sleeping. I succumbed to getting up, eventually, as can be seen.

Aside of a modifier to slope cost, I think there should also be a per-unit treshold. I.e. it should both be possible to simply ignore slope costs between 0.9..1.1 and also lower a cost of 2.0 to 1.5 (assuming 1.0 was the cost of smooth terrain). These variables being possible to be set mod-wide could also be handy, I think.

Depending on how the pathfinding is set up, an addition like this could be a decently elegant solution and solve a few issues. I'm currently looking into the pathfinder code. "flowCost" inside CPathEstimator::TestBlock() seems to.. ..End up unimplemented in the develop code but implemented in master as PathFlowMap::GetFlowCost() is commented out in the former?

[Google_Frog]

A per-unit threshold is impossible for the way pathfinding is currently set up. The pathfinder does not know that units exist, it only knows that movedefs exist. It is inadvisable to have many movedefs.

[tzaeru]

A per-unit threshold is impossible for the way pathfinding is currently set up. The pathfinder does not know that units exist, it only knows that movedefs exist. It is inadvisable to have many movedefs.

Mmh, but wouldn't having multiple MoveClass tags be a non-issue? Right now there's 4 if I read the doc right. Adding some more for units that would benefit from their own, customized modifiers and tresholds for slope costs could be quite handy.

I'm very eager to test this kind of code addition out right now, but seems that the flow costs are not used at all in the develop code? Seems only the node size and special terrain modifier for velocity is taken into account. So.. Is there something that is going to be used as a replacement, or is the flow code all-around waiting a full rewrite?

[Silentwings]

Mmh, but wouldn't having multiple MoveClass tags be a non-issue?

I guess it would be a performance issue.

may have suggested to the Gravitas people that they should use raw move for within-room travel but that was only because their maps were simple concave rooms with doors between them.

We thought about it, but QTPFS solved the problem perfectly for Gravitas.

[Kloot]

I stated my solution...

You either missed or ignored the relevant part about player desires for (cost-)suboptimal paths being context-dependent.

Splitting slopeMod (which, for the sake of consistency, also implies splitting depthMod) would affect unit movement in all situations and introduce other pathfinding complaints.

[tzaeru]

Splitting slopeMod would affect unit movement in all situations and introduce other pathfinding complaints.

Shouldn't the decision of using or not using slopeMod (and, I'd like to imagine, a treshold) be up to the game domain rather than Spring domain? For games with units with slow'ish acceleration and turn rates, a slopeMod value (and perhaps, an associated treshold value) somwhere in the middle of 0.0 and 1.0 could really be more optimal in vast majority of pathfinding cases than zero or 1.0.

Another thing that could actually be super great for fast-paced matches focused more on small-group unit tactics than unit spam through economical supremacy, could be having the possibility of sending movement commands with assumed slopeMod 0.0. It wouldn't "fix" things for newbies, but I doubt newbies are that concerned with these issues anyway. Anyway, the idea would be to get the unit to take shortest possible non-blocked path instead of presumed fastest non-blocking path. But even with such a command, I still think that a middle ground between shortest and fastest is generally more desired for most games than simply the assumed fastest, as the assumed fastest is A) not even nearly always the actual fastest due to turn rates and accelerations and whatever and B) radically diverting paths often lead the units to undesired places, like straight into enemy.

[Google_Frog]

I stated my solution...

You either missed or ignored the relevant part about player desires for (cost-)suboptimal paths being context-dependent.

Splitting slopeMod (which, for the sake of consistency, also implies splitting depthMod) would affect unit movement in all situations and introduce other pathfinding complaints.

I think that players want suboptimal paths most of the time as long as the paths were not too suboptimal. The main two complaints that I hear are:

• Units drive into terrain/structures and become stuck (much less common in 98.0+dev).
• Units don't go in the direction they are told to go.

The second complaint often stems from the player underestimating the cost of the straight line path. The outcomes of simple player actions should match the players expectations which is why I think the pathfinder should also underestimate the cost of straight lines when hills are involved.

I am not even suggesting a change to the default behaviour and I do not think ignoring the terrain slope completely is a good idea. I would like to experiment with a lower path slope mod and find a middle ground. I have had a look at the movement related code and these tags look easy enough to add so I will try to do that.

[Anarchid]

It seems that people have thought about that zigzag thing astar (and similar) does, and whoa, solutions exist.

Dunno if added cost really makes this viable in a "economical spam RTS", but "quick tactical games" likely wouldn't have issue.

[Google_Frog]

It would be good to fix the zig zag problem. It sounds like a nice task which can be attempted by someone interested in engine development. They would probably have to communicate with jK because he has worked on pathfinding recently.

Spring has three pathfinding resolutions so implementing zig zag removal would be more complicated than suggested by your article. Perhaps as a partial solution the pathfinder could be slightly encouraged to make 45 degree turns which would then be smoothed by the higher resolution path finders. This smoothing would occur on the fly as the unit invokes pathfinding of higher resolution to find a path through the next few nodes. This system may not even require explicit smoothing code. The result of this change would be to effectively give units 16 directions of movement.

[tzaeru]

QTPFS sparked my interest again and I found myself digging a bit into its code.

From what I understand, there are two main issues with it:
1) Huge memory footprint. I suppose this is due to the amount of Path struct instances that get generated when hundreds of units move at once?
2) Command latency. It takes a while to get the path, during which units don't move at all. This sounds quite difficult to fix. Needs a low-res mesh that can be used for initial path I guess? Or more caching? (= would kill some advantages of the system though)

Are there other known, big issues in it? How does it compare with unit clumping right now to vanilla system? Is there some general description of how the code works on the object level? And is the FlowMap solution actually used in Spring 0.99 for default PFS? It's commented out in the master branch..

/me is sometimes a little confused about these things!