Droid movement code improvement patch

[wzdev-ci]

keyword_movement_pathing_pathfinding resolution_later type_patch (an actual patch, not a request for one) | by Zarel

---

We all know that the droid movement code has Serious Problems.

This patch aims to address some of them.

First, it makes sure that the current waypoint (i.e. the direction the droid is currently moving in) is always the furthest waypoint on the list. In other words, if a droid doesn't have LOS to the current waypoint, it moves towards the previous waypoint. If it can't find a single waypoint it has LOS to, it will recalculate the path instantly.

This involves doing a LOS calculation about once per moving droid per update. Shouldn't be too much of an issue (the old code did it approximately that often), especially since I rewrote the LOS function (more on that later).

Second, it makes sure that the LOS raycasts are always from the tile the droid "logically" occupies. This mostly only happens to cyborgs. Think of it like this:

     W
*    Wc
     W

* is the destination, W is a wall, and c is a cyborg. The cyborg is close enough to the wall that the tile it's on is the same tile as the wall is done. So when the LOS raycast is done from the W tile, it thinks it has LOS to the destination, even though it really doesn't.

My fix is to cast the ray from the closest non-blocking (i.e. unoccupied) tile.

Third, it rewrites parts of the LOS raycasting routine to eliminate rounding errors, and improve its speed. This rewrite will be applied to other usages of the rayCast function in a future patch.

Fourth, it fixes a bug in which units did not rotate in place if they were angled more than 45 degrees more than their destination. We may wish to adjust these angles.

These changes seem to fix most of the movement problems we have.

---

Issue migrated from trac:1649 at 2022-04-15 21:10:37 -0700

[wzdev-ci]

Zarel uploaded file movement-v1.patch (12.3 KiB)

Improve droid movement

[wzdev-ci]

Zarel edited the issue description

[wzdev-ci]

Zarel commented

---

Forgot change number four.

[wzdev-ci]

Per commented

---

How come a droid is ever in a blocking tile?

I see you are fixing the cannot-turn-in-place bug, but I rather liked that bug :/ It may be unrealistic, but it looks nicer.

[wzdev-ci]

Per uploaded file strictwaypoint.diff (1.9 KiB)

This patch seems to fix quite a few issues by simply asking droids to walk the path they are given, instead of looking too much ahead of them. It will also help the AI when we get more intelligent paths in the future.

[wzdev-ci]

Zarel commented

---

The droid can be pushed into a blocking tile, or get pushed into it, or something like that.

I think looking ahead is really necessary - walking their exact path doesn't solve anything, except make their paths uglier.

[wzdev-ci]

Per commented

---

How about fixing the bugs that push droids into blocking tiles, instead of working around them?

The look-ahead design is clearly broken. It will turn a neat U-turn path around an enemy defensive position into a head-on kiss of death. More advanced forms of path-finding to avoid danger are largely pointless when the path-walking works like this.

Also see #305

[wzdev-ci]

Zarel commented

---

Why are they bugs? Droids will collide, they will slide, etc... it's a fact of life. Unless you plan on instantly teleporting them out or something.

I don't see how the look-ahead design is broken. What do you mean by "neat U-turn path"? afaik, all paths will be similar with or without look-ahead/fall-back, and with fall-back, I think it will be more reliable...

Anyway, testing pathfinding is simple. Start Rush, Full Bases, then move back and forth between your base and the right of your base. With the old movement code, it takes around three tries before someone gets stuck. Using ~10 cyborgs seems to maximize the chances of getting stuck.

[wzdev-ci]

Per uploaded file strictwaypoint2.diff (2.1 KiB)

Improved version that does not cause unnecessary stall in front of destinations.

[wzdev-ci]

Per uploaded file fpathclean.diff (2.0 KiB)

Seems like this piece of code is really unnecessary. A* code will deal with any unreachable targets.

[wzdev-ci]

Per commented

---

A droid that is on a tile where it should not and cannot be is surely a bug. Visually it looks crap, too, when droids clip into walls and buildings.

As to look-ahead, I mean the code that automatically skips all path nodes it thinks are unnecessary (by checking LoS). This may generate elegant looking turns, but it really is not the path walking code's business to so completely overrule the decisions of the path-finding code. Path-finding may intend for the path to be non-optimal from the limited point of view of the path-walking code, eg to avoid danger or detection.

You should try the strict waypoint patch. The driving is really not that bad, and I have yet to see droids that get stuck. I do not doubt that droids will still get stuck, because the horrible sliding code is still alive, but it seems much better. And it is leaner/faster.

[wzdev-ci]

Zarel commented

---

Have you tried the "10 cyborgs in Rush Advanced Bases" test?

I'll try it once I get home.

[wzdev-ci]

Per commented

---

Which base? I tried 10 cyborgs a few times and then 100 cyborgs in start location 0, and saw none getting stuck. Droids-vs-droid collision resolution is horrific, but you knew that already... :-)

[wzdev-ci]

enki uploaded file pathfinding-alt.diff (51.6 KiB)

Some experimental changes in the same area, needs to be simplified and merged with trunk

[wzdev-ci]

enki commented

---

I've been thinking along the same lines, figured I'd throw something up here too. Don't know if I'll get around to a finished patch anytime soon but I think there's some good ideas to be picked out of what I have.

The thing that really needs fixing IMHO is moveGetObstacleVector, it does the work needed to implement decent flocking behavior but completely screws it up. Takes some fiddling to get everything working nicely but I think I got close.

I'd agree with Zarel's approach to waypoint selection. Going 100% with A looks good next to broken code, but it's not dynamic enough. I tried backtracking instead of re-running A but even that isn't quite right, sometimes units go partway around obstacles on their own then pull back to the path.

As far as droids going on blocking tiles that definitely needs to be treated as a bug, causes lots of problems. Fortunately I'm pretty sure that's just moveCalcBlockingSlide failing to work, I added an assert to check for that and haven't seen it triggered with my changes there.

[wzdev-ci]

Zarel commented

---

Well, "droids going on blocking tiles" was just my guess for some weird raycasting behavior... I haven't really confirmed that it happens.

[wzdev-ci]

enki commented

---

Well droids drive onto blocking tiles all the time so go confirm it :)

I wrote some stuff up in [#305], it's not hard to reproduce all those issues once you know where to look. I like the hill where you find the sensor tech in the alpha campaign, I got a screenshot showing two of the issues I posted there right away (skipped waypoint and droid driving off a cliff due to moveGetObstacleVector suckage). Droids on blocking tiles is harder to demonstrate, but see [#1095], [#1076], etc. If you add an assert looking for that you're likely to see it triggered very quickly.

[wzdev-ci]

enki uploaded file bad pathfinding hill.jpg (132.0 KiB)

Screenshot of a good testing ground for single units, this is on the main base map in the alpha campaign

[wzdev-ci]

Per commented

---

Another good map for testing is MizaMaze. Start as player 0, then move both starting droids to the closest derrick, the one on the tall plateau just SE of the starting position. At least one droid will get stuck on the ramp, usually both will miss the ramp and try to drive up the hill side.

[wzdev-ci]

enki uploaded file pathfinding-v2.diff (25.5 KiB)

Smaller, cleaner patch against r10162. Compare moving large groups of droids with this, beats the pants off the old code. Droid vs. droid could easily be made better, just need to fix other parts of the AI to handle units not colliding constantly.

[wzdev-ci]

Per commented

---

Interesting patch, it appears to fix some problems, but it has some of the same problems as mine - when droid gets really close to target (one tile away), sometimes it starts crawling very slow toward it. Also, droid vs droid collisions appear to be worse. Try testing on the miza map, it is really good at showing problems with this code.

[wzdev-ci]

Per uploaded file strictwaypointandclean3.diff (10.8 KiB)

New version, with better precision at destination, and laxer path walking. Push endpoint closer to destination in A* code to discourage crawling. Remove now unused bounds code.

[wzdev-ci]

Zarel commented

---

"Starts crawling very slow toward it" was something I fixed in my patch. I don't remember what I did exactly, though...

[wzdev-ci]

enki commented

---

There are some weird issues with path endpoints, but make sure you're looking at debug info when you see crawling, pretty much everything I've seen looks like bad orders rather than path finding now.

If no one likes droid vs. droid in my last patch I'll give up for now. I still like that approach better, but I think getting it right will take a bigger patch than I want to do right now.

Do make sure you address moveCalcBlockingSlide somewhere, though. I don't know why it doesn't cause more problems than it does, but if you change the tx ## ntx && ty nty case to an assert you'll see it hit very quickly.

[wzdev-ci]

Buginator commented

---

just adding myself to this ticket, so I get updates. I didn't notice it before.

[wzdev-ci]

Zarel commented

---

I just played a game of trunk. Used TK Scorp hovers in Manhattan, and the movement were horrible - they kept on moving away from the direction they were supposed to go, and weaving back and forth and would take an extremely long time just to move to a target four tiles away. I saw similar (but less pronounced) problems with the MG Viper Wheels in the beginning of Cam Alpha I.

I'm pretty sure this is a regression, since 2.3's pathing was mostly fine the last time I tried it.

[21:35] [Per's exact path following] wouldn't've fixed it. [21:36] Since the issue was that the hovers would get off the path (since their momentum is much higher than their engine power), and then go back to an old waypoint even though it was further away from the target than they were. [21:36] Which is the kind of thing my patch fixes.

So I think we should reconsider Per's patch. I'm open to committing enki's, which afaik is the best at this point.

[wzdev-ci]

Per commented

---

1) Momentum being higher than engine power is a problem why? 2) I see some patches address multiple issues at once. I would propose that each issue is discussed and fixed separately. 3) A droid should never be in a position where it is illegal for it to be. The whole issue of "logical" positions should be fixed properly at its source, and adding a ton of code to work around the problem is the wrong way to address it. 4) Have you tried my strict path-walking patch yet? It cleans up the code a great deal, and in my opinion and of those others who have tested it, it really improves movement. I do not make any claim that it fixes all the problems, and other fixes will also be needed. I have not noticed any "strange" movement due to the strict adherence to the path, to me it looked fine. 5) IMHO, non-tracked droids should not spin turn on the spot. 6) See above for problems I found during testing of enki's patch. These need to be fixed before it can be committed. I prefer that it be split up into multiple patches to separate out each fixed issue. That will make it easier to isolate problems and get progress.

[wzdev-ci]

Per uploaded file strictwaypointandclean4.diff (8.3 KiB)

Strict path walking patch updated to latest trunk (no real changes)

[wzdev-ci]

Zarel commented

---

Per - Trac doesn't support newlines very well. ;) Should probably get in the habit of clicking "Preview" first.

Okay, I just tested your patch a bit.

Say we have:

 ....
Dx

where D is your droid, x is an obstacle, and . is the path.

The droid can be stuck in that situation. Overall, pathing seems to be improved, but not great.

[wzdev-ci]

Zarel commented

---

Okay, I tested enki's patch, and it seems a lot better. Let's commit that one.

[wzdev-ci]

Zarel commented

---

To be more specific: I spent around three hours testing enki's patch and didn't get any stuck droids, while I got a stuck droid within around ten minutes of testing per's patch.

[wzdev-ci]

enki commented

---

FWIW, I don't disagree with Per about this being multiple issues at all, I've just been focused on droids driving onto blocking tiles and getting stuck. To be clear, I say my patch fixes that at the source. The complicated part is how to fix that without making other issues appear much worse, I still think my patch improves the overall situation, and the remaining issues are independent bugs that the existing code doesn't entirely avoid either. I'm also not claiming it's perfect, though.

Short term Per's patch does indeed help and there's nothing wrong with focusing on fixing that specific problem, but I still disagree about strict A path following being the way to do it. It works as good as anything else while the rest of the code is as broken as it is, but there's some really good research out there about how to do collision avoidance and flocking behaviors in local movement code, if you restrict droids strictly to a precalculated A path you lose that.

As far as turning in place, for me that's not about 'realism', it's about the droid going in completely the wrong direction very fast. If anything hovercraft need that changed more than tracked vehicles. I do think some kind of velocity scaling would be better than a hard on-or-off, but fixing the 'bug' is easier.

[wzdev-ci]

Per commented

---

I do not think that strictly following an A path is a very good solution in the long term. We need flocking/swarming behavior where the droid can swerve from the path and make local changes based on changing conditions. The problem with the current path walking algorithm is that it tries to second guess the A path about where the optimal route is and tries to make local optimizations that always give worse results. The result will in theory always be worse because basic A* always gives optimal results. When the path finding deviates from the optimal route, there may be good reasons (eg attempts to evade dangers known in advance) and this information should not be completely discarded by path walking like it can be today (eg a U-shape path across an open plain will be cut short by path walking).

So I do not intend that droids should always be strictly following the A route, just that we should stop the second guessing of the optimality of the path. I do not actually think that was the intention of the original coders, they just wanted the droids to do nicer turns, but worse optimization is the result, while I cannot really tell the difference in terms of how nice the droids drive. Hence making it following the A path strictly would be a first step on the way, not the end point.

[wzdev-ci]

Zarel commented

---

The benefit of the current path walking is that it doesn't follow the A path, since the A path incorrectly assumes that the Warzone world is a Manhattan grid plus diagonals. There is at this point no benefit to strictly adhering to A - all your named advantages are a vague "sometime in the future" type thing. One day, if our pathfinding algorithm does become more accurate than our moving algorithm, we can switch to exact path walking then, but I see no reason to do it now*.

Regardless of whether or not we commit Per's strict path walking, I vote to commit enki's patch now.

[wzdev-ci]

Per commented

---

"There is at this point no benefit to strictly adhering to A* - all your named advantages are a vague "sometime in the future" type thing."

This is really frustrating. I made a patch and I claim it has short-term benefits now, I explain why, and you just ignore it and claim I have said the exact opposite?

As to enki's patch, it needs to be split up (and reworked to apply to current trunk). Most parts of it are fine, but there are also parts I would like to discuss independently, like the turn in place changes and the new raycasting function.

[wzdev-ci]

Zarel commented

---

Replying to [comment:25 Per]:

This is really frustrating. I made a patch and I claim it has short-term benefits now, I explain why, and you just ignore it and claim I have said the exact opposite?

I apologize. Could you repeat the short-term benefits? I re-skimmed the comments again and couldn't find them.

As to enki's patch, it needs to be split up (and reworked to apply to current trunk). Most parts of it are fine, but there are also parts I would like to discuss independently, like the turn in place changes and the new raycasting function.

No reason not to discuss it now.

The turn in place changes are fairly important. While playing, I don't notice units looking awkward, but I do notice that hovers no longer dash in the wrong direction for several tiles before managing to turn around and slowly make their way in the direction I clicked. There's nothing more frustrating than watching a unit move several tiles closer to the flamer I clicked in the opposite direction of, and I think that frustration outweighs any minor graphical concerns.

As for the new raycasting function, assuming that's the one I wrote, it's algorithmically only slightly faster, but the main thing is that it resolves a rounding error that can happen when casting to a destination more than 128 tiles away (or was it 256?).

[wzdev-ci]

enki commented

---

Per, it sounds to me like you might be badly misunderstanding the purpose of moving the waypoint ahead of the droid, it's not 'nicer turns'. Try the cyborgs on Rush test with your patch and that piece disabled, you'll notice they form a very tight line. With my patch they tend to spread to fill the available area, and waypoint skipping is the only way I know to do that without major changes to global pathfinding code.

My last patch uses Bresenham's algorithm because I happened to have a working version around, feel free to take it back out if you don't like it. Just a speculative performance optimization really.

[wzdev-ci]

Zarel commented

---

Oh, yeah, enki raises a good point. In addition to assuming that Warzone is played on a Manhattan grid plus diagonals, A* also assumes that the moving droid is the only droid that exists, and that its hitbox is exactly one tile, and probably several other assumptions that simply aren't true, and that it doesn't matter if the droid gets shot at along the way...

You argue that avoiding enemy fire is good, since that can be a factor in the A calculation, but I've already mentioned that that only works if nothing that could shoot at the droid could move, and if the player can see everything on the path to the destination, neither of which are true. And even then, it might still be simpler to do avoidance in the movement code (or both), since that's not subject to all the other assumptions A makes that I list above.

[wzdev-ci]

Per commented

---

This is not going anywhere. I think we should move this discussion over to the mailing list.

enki, can you post an updated patch (or preferably, patches)?

[wzdev-ci]

Per commented

---

I wanted to test the moveGetDirection piece of the patch by itself, to see whether the change is good. If we truly could just wipe out all those complicated checks and exceptios, and simplify the code that way, I would be very happy. However, what happens is that droids start moving in circles. I suppose that this problem is 'fixed' by making droids not make wide turns and turn in place instead?

[wzdev-ci]

Per uploaded file moveGetDirection.diff (10.2 KiB)

Only the moveGetDirection changes from enki's patch, and some extra dead code removal that resulted from it.

[wzdev-ci]

Per commented

---

Looks like the circling issue is in the changes to 'moveReachedWayPoint', not 'moveGetDirection'. However, narrowing down the changes to only the latter, I get droids park quite a bit off from where they should go (but in line of vision) and do strange manoeuvres to get into the path.

[wzdev-ci]

Per uploaded file moveGetDirection-smaller.diff (3.0 KiB)

Smaller patch

[wzdev-ci]

enki commented

---

Yeah, I'll break it up and post some updated patches in a little bit. I didn't want to get into maintaining lots of pieces, but it seems like something will get committed soon now and that'll probably demonstrate what the pieces do better.

The circling thing basically happens because currently droids always go full speed, so they can sort of go into orbit around the final waypoint if the collision avoidance vector nudges them the right way. Just thought of something that might help, if it works out I'll post in a bit.

[wzdev-ci]

Zarel commented

---

Feel free to comment your code, by the way. Especially if it's otherwise unclear.

[wzdev-ci]

enki commented

---

OK, bunch of patches coming, hopefully this will be helpful. These are all going to be in git format because that's easier for me, 'patch -p1' works so I assume no one will care much. I do have a few comments in there, if something is unclear just ask.

There are definitely still issues when multiple droids have the same endpoint in mind (creeping, circling around, turning in place, etc). I consider this a separate issue, I think the fix basically involves finding a reasonable stop condition other than 'the droid is an arbitrary distance from the last waypoint'.

[wzdev-ci]

enki uploaded file blockingtileassert.diff (2.2 KiB)

Assert if the droid ends up on a blocking tile. I don't recommend committing this now because I haven't addressed old savegames, but it's useful to test with this on.

[wzdev-ci]

enki uploaded file blockingtilefix.diff (4.4 KiB)

Actually fix droids moving onto blocking tiles. This also makes it a little more obvious that droids keep wanting to do that.

[wzdev-ci]

enki uploaded file reallystrictpathfinding.diff (10.6 KiB)

This is mostly Per's code, I think we agree on 90% of it, so I'm using this as the base. I removed the hack to avoid 'creeping' and added my simplified moveGetDirection.

[wzdev-ci]

enki uploaded file smooth-speed-adjustment.diff (9.8 KiB)

Another solution to the problem of droids driving the wrong way really fast. This adds a nice '3 point turn' effect and generally looks a little more natural to me. I also removed the 'slide direction' stuff because it was in the way and becomes useless later.