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.)