Page MenuHomeWildfire Games

Long path improvements
Needs ReviewPublic

Authored by temple on Oct 11 2017, 4:56 AM.

Details

Reviewers
None
Group Reviewers
Restricted Owners Package(Owns No Changed Paths)
Summary

This is a bit of a work-in-progress, looking for feedback.

Long paths look rather bizarre:

Here's three changes:

  • Remove redundant diagonal waypoints
  • Remove ImprovePathWaypoints (it tries to smooth the path, but does a poor job)
  • At the end of a turn, remove the last waypoint if there's a straight path to the next one

Now the paths look relatively sane:

This doesn't result in perfect paths like with the short/vertex pathfinder, but they're much better.

I need to do some performance tests, but using dramatically fewer waypoints might be a good thing, and I think the straight path check is cheap.

I'm missing one part though, because when paths fail the current code typically removes the last long waypoint and tries again. Now with so few long waypoints, this approach won't work. We can easily interpolate to create new waypoints for short pathfinding goals, but it's a problem if we then remove them in the next step. So instead we'll need to do something like keep track of the number of pathfinding attempts, rather than using the number of long waypoints as a proxy for how stuck we are.

I guess it wouldn't be too much work to do that, but there's lots of known issues about compatibility of the two pathfinders, so it might get annoying trying to make everything work perfectly when that might not be possible. After reading threads and tickets and patches over the last week, I think I'd rather work towards adding something like steering behavior, possibly even replacing the short pathfinder. (Of course I'm sure steering will have its own issues.) But I'd appreciate advice about this.

(If you move a group of units they currently have very different behaviors depending on if you go vertically/horizontally where they all try to walk on the same path, or diagonally where everyone takes their own parallel path. With the patch, they'll mostly behave the same whichever direction you tell them to move because they're usually all headed towards the same distant waypoint, but they'll still slowly crowd together which causes traffic jams in the back. With steering behavior we can take into account the movement of neighbors rather than treating them as static objects, so units can avoid colliding into units walking next to them and they can walk behind other units that are moving in the same direction. Hopefully that would smooth out the traffic jams a little. And I think it would make formation movement nicer too.)

Test Plan

Let me know what you think about the new long paths. The pictures might not do it justice, so rebuild and try it yourself, with and without the overlays.

I probably need to add in the missing part before doing performance tests.

(When we don't use diagonal gaps, the long waypoints can't go from one diagonal direction to another, so the collinearity check becomes simpler. It's possible to have three waypoints in a row horizontally or vertically, but that's rarer and not really a big problem.)

(I just noticed that I probably want to do a first check of straight paths before sending in the path, otherwise units will always start moving at 0/45/90/etc. degrees since I do the check at the end of a turn.)

Diff Detail

Lint
Lint Skipped
Unit
Unit Tests Skipped

Event Timeline

temple created this revision.Oct 11 2017, 4:56 AM
fatherbushido added a subscriber: fatherbushido.EditedOct 11 2017, 8:12 AM

After reading threads and tickets and patches over the last week,

You're a fast reader.

I think I'd rather work towards adding something like steering behavior, possibly even replacing the short pathfinder.

That's what was/is planned, and was always in mind (already in 2010). (explictily or not)

(Of course I'm sure steering will have its own issues.)

As you know Steering is broad.

But I'd appreciate advice about this.

Those things are 'easy' outside 0ad. In that specific context, you will need a global view on what do we mean by group walking, by formation and things like that.

And I think it would make formation movement nicer too.

Depending of what we mean by formation, I'd say replace?

At last you ll add to look if your work doesn t conflict with curent ones (with Wraitii plan for example)

After reading threads and tickets and patches over the last week,

You're a fast reader.

It's usually hard for me to tell what you mean, if you're making fun of me or something else. :)
But I did read quite a lot because I'm still new to this game and want to know the context and history. Philip documenting his work on the pathfinder was amazing, for example.

And I think it would make formation movement nicer too.

Depending of what we mean by formation, I'd say replace?

Not sure exactly what you're saying, but I mean formation = battalion or whatever you want to call it. That's actually what I was looking at first (e.g. fixing promoted units losing their formation position) before I started looking at movement. With group walking we don't care about them being in a certain position or walking at the same speed, but we do want that with formations. Some formations should be able to pack units more tightly than individual units (currently it's the opposite case) and prevent other units from running through them, and some should get attacking bonuses or penalties, and so on. There's a lot of possibilities there so I'd really like to see them work.

At last you ll add to look if your work doesn t conflict with curent ones (with Wraitii plan for example)

That's part of my reading. He didn't touch the long-range pathfinder but obviously he did change unit motion, and that's part of why I was hesitant to go further.

You're a fast reader.

It's usually hard for me to tell what you mean, if you're making fun of me or something else. :)

I was making fun. I spent month to read those things :p (I am a slow reader ;-))

Not sure exactly what you're saying, but I mean formation = battalion or whatever you want to call it. That's actually what I was looking at first (e.g. fixing promoted units losing their formation position) before I started looking at movement. With group walking we don't care about them being in a certain position or walking at the same speed, but we do want that with formations. Some formations should be able to pack units more tightly than individual units (currently it's the opposite case) and prevent other units from running through them, and some should get attacking bonuses or penalties, and so on. There's a lot of possibilities there so I'd really like to see them work.

You are clever so you know we can't speak of anything without defining thing. The matter is that here I am unable to define things (not that I didn't think about those things :/)
For example:

  • rigid formation selectable as an own thing.
  • group walking of a group of unit just selected together (which then need a good natural behavior - see steering)
  • group walking of a group of unit selected together and include in a group (ctrl + number stuff)

...

Well, anyway out of the scope of that diff.

That's part of my reading. He didn't touch the long-range pathfinder but obviously he did change unit motion, and that's part of why I was hesitant to go further.

Yes

This comment was removed by wraitii.
wraitii added a comment.EditedOct 12 2017, 4:51 PM

@temple : I would encourage you to review and possibly take over the unitMotion patches then, because I'm not certain I can finish them entirely.

Generally speaking, changing pathfinders is very risky business because there are a lot of unexpected edge cases, particularly with regards to short and long term pathfinder compatibility, and you might want to read through my differentials' comments to understand them better.

You are however right that the LR pathfinder needs improvements.

I'm missing one part though, because when paths fail the current code typically removes the last long waypoint and tries again. Now with so few long waypoints, this approach won't work. We can easily interpolate to create new waypoints for short pathfinding goals, but it's a problem if we then remove them in the next step. So instead we'll need to do something like keep track of the number of pathfinding attempts, rather than using the number of long waypoints as a proxy for how stuck we are.

I believe that's a change I do in D13.

Re

(Of course I'm sure steering will have its own issues.)

The main one is that you may want to take a non-direct path to avoid units, unless you can sanely push them away, and you risk ending up stuck in wrong places unless you're really really careful to stick with the long-range paths.

Regarding formations, I've changed them for the unit motion patches (https://code.wildfiregames.com/D444). I believe that's the only sane way forward under the current system for group-walk

I need to do some performance tests, but using dramatically fewer waypoints might be a good thing, and I think the straight path check is cheap.

Do test this as I believe the opposite can be true. The longer the straight line, the more objects we are pulling through the range manager (because we're using dumb square - this could be improved, mind you), and the check is not actually all that cheap.

In D956#37348, @wraitii wrote:

@temple : I would encourage you to review and possibly take over the unitMotion patches then, because I'm not certain I can finish them entirely.

That's probably too much for me! But I can try to review some of the parts later.

I think in the bigger picture I'm not yet convinced by the short pathfinder. Partly because of all the compatability issues you know too well, but also it seems to me that steering (including pushing) would be a better fit for 0ad. We usually have a large open map with small or tiny units, so there shouldn't be a lot of complicated collision. Either the units are all going in a similar direction, or they're two armies colliding in which case they want to go straight through each other rather than path around them (which we can always do by shift-clicking anyway). So I'd like to try to implement this first.

Do test this as I believe the opposite can be true. The longer the straight line, the more objects we are pulling through the range manager (because we're using dumb square - this could be improved, mind you), and the check is not actually all that cheap.

I'm not using CCmpPathfinder::CheckMovement() but instead Pathfinding::CheckLineMovement() which only uses the passability grid.

I'm not using CCmpPathfinder::CheckMovement() but instead Pathfinding::CheckLineMovement() which only uses the passability grid.

Ah, right, nevermind then.

There's been some attempts to remove the short range pathfinder in the past but nothing too serious. Pushing/steering is definitely one of the main ideas there, but I don't think it would be that easy to implement without D13, so I guess i'll just have to rebase all of that :p

(We start digressing but there is a patch lying somewhere since years with the ground base for nuking the short pathfinder and for simple steering behaviors).

(We'll need to decrease the turn length, at least for movement. Otherwise it's too hard to predict where units will be in order to steer around them or slow down before crashing into them. For example, Starcraft II does 16 simulation updates per second on normal speed, but in multiplayer we only do 2 updates per second.)

In practice the best we could do right now is about 50ms in SP and 200ms in MP, otherwise it lags too much. That might be improved by steering a bit but there's a hard limit there.

In D956#37500, @temple wrote:

(We'll need to decrease the turn length, at least for movement. Otherwise it's too hard to predict where units will be in order to steer around them or slow down before crashing into them. For example, Starcraft II does 16 simulation updates per second on normal speed, but in multiplayer we only do 2 updates per second.)

(I was working on rewriting the turn manager, am currently quite busy with other things, but may return to this in a few weeks)

(I've been working on this, but it's challenging, of course. I wanted to say generally that I think we'll need something like a collision manager. Currently we move one unit at a time, but this leads to unnecessary traffic jams when a group of units are moving in the same direction, for example. So I think it would be better to break movement into two parts, first moving units to their ideal position, flagging potential collisions as we go, and second going through all the potential collisions to see if the units actually collided, and if so try to resolve the collision by pushing or requesting another path or something.)

wraitii added a comment.EditedOct 23 2017, 8:24 AM

(I've been working on this, but it's challenging, of course. I wanted to say generally that I think we'll need something like a collision manager. Currently we move one unit at a time, but this leads to unnecessary traffic jams when a group of units are moving in the same direction, for example. So I think it would be better to break movement into two parts, first moving units to their ideal position, flagging potential collisions as we go, and second going through all the potential collisions to see if the units actually collided, and if so try to resolve the collision by pushing or requesting another path or something.)

Agreed, I came to the same conclusion during my unitMotion rewrite (didn't do it yet though)
In my opinion it's the only way to make formations work OK too, otherwise units bump into each other a ton.

(It looks like an evidence in the second decade of the 21st century).
But the word 'formation' has to be well redefined (as it's used to mention different things).

vladislavbelov added a comment.EditedOct 25 2017, 10:28 PM

I've tested it for different long paths, and it seems helpful in some cases, but still needs more tests.

free - no static obstructions.
big - big static obstructions.
grouped - 500 units splitted on groups by 50 units each moving near.

I wrote a script to run the game and automatically collect profiler's stats for different replays. And I think we need to make auto performance tests for commits/patches for the path finder.

temple updated this revision to Diff 3981.Oct 26 2017, 3:41 AM

Fixed this:

(I just noticed that I probably want to do a first check of straight paths before sending in the path, otherwise units will always start moving at 0/45/90/etc. degrees since I do the check at the end of a turn.)

wraitii added a reviewer: Restricted Owners Package.May 14 2018, 4:39 PM

(I've been working on this, but it's challenging, of course. I wanted to say generally that I think we'll need something like a collision manager. Currently we move one unit at a time, but this leads to unnecessary traffic jams when a group of units are moving in the same direction, for example. So I think it would be better to break movement into two parts, first moving units to their ideal position, flagging potential collisions as we go, and second going through all the potential collisions to see if the units actually collided, and if so try to resolve the collision by pushing or requesting another path or something.)

I've actually done that in D13 / D1490. Units first move, without regard for unit-unit collision, then we push. SO units moving in formation no longer "collide" all the time. It's not extremely clever but it seems to work well.

Stan added a subscriber: Stan.Nov 5 2018, 12:22 PM

@wraitii @vladislavbelov any review on this ?

source/simulation2/helpers/LongPathfinder.cpp
994

Could that logic be made into a function with the one in the other file somehow ?

@wraitii any chance you can look at it?