Paths

Table of Contentst

Differential D1871

Make rasterisation strictly more permissive than real static obstruction shapes (alternative take on D1869)
Changes PlannedPublic
Actions

Authored by wraitii on May 8 2019, 6:21 PM.

Details

Reviewers

None

Group Reviewers

Restricted Owners Package

(Owns No Changed Paths)

Summary

This is an alternative take on making the short and long-range pathfinder consistent.
In this differential, I simply make the pathfinder grid the reference for static obstruction. Movement is never checked against static shapes, only against unit shapes. The vertex pathfinder should be more permissive than the long-range pathfinder, thus we won't get stuck.

The positive of this diff is that trees, for example, have a much smaller long-range footprint, which will improve pathfinding in forests and such drastically.

Test Plan

Test the new behaviour.

Diff Detail

Repository

rP 0 A.D. Public Repository

Branch

D13_outtakes

Lint

Lint OK

Unit

No Unit Test Coverage

Build Status

Buildable 7389
Build 12039: Vulcan Build	Jenkins
Build 12038: arc lint + arc unit

Event Timeline

wraitii created this revision.May 8 2019, 6:21 PM

@Itms Do you remember a reason why this wasn't done in 2015/16? I feel like this is a strictly better approach than our current one, and it can be combined with D1869 for maximal safety.

I agree that this looks nice at first sight. I just followed Philip's concept regarding clearance, and then did some tuning to reduce the number of stuck units... This should be tested a lot but I don't see any conceptual issues with this.

Stan added a subscriber: Stan.May 8 2019, 6:51 PM

This comment was removed by Stan.

Successful build - Chance fights ever on the side of the prudent.

Linter detected issues:
Executing section Source...

source/simulation2/helpers/Rasterize.cpp
|   1| /*·Copyright·(C)·2015·Wildfire·Games.
|    | [NORMAL] LicenseYearBear:
|    | License should have "2019" year instead of "2015"

source/simulation2/components/ICmpObstructionManager.h
|   1| /*·Copyright·(C)·2018·Wildfire·Games.
|    | [NORMAL] LicenseYearBear:
|    | License should have "2019" year instead of "2018"

source/simulation2/components/CCmpObstructionManager.cpp
|   1| /*·Copyright·(C)·2018·Wildfire·Games.
|    | [NORMAL] LicenseYearBear:
|    | License should have "2019" year instead of "2018"

source/simulation2/components/CCmpObstruction.cpp
|   1| /*·Copyright·(C)·2018·Wildfire·Games.
|    | [NORMAL] LicenseYearBear:
|    | License should have "2019" year instead of "2018"
Executing section JS...
Executing section cli...

Link to build: https://jenkins.wildfiregames.com/job/differential/1345/display/redirect

Harbormaster completed remote builds in B7389: Diff 7937.May 8 2019, 6:53 PM

Make this usable on svn.

Freagarach mentioned this in rP22275: Fix move speed not correctly reset when chasing a unit.May 13 2019, 9:20 PM

Successful build - Chance fights ever on the side of the prudent.

Linter detected issues:
Executing section Source...

source/simulation2/helpers/Rasterize.cpp
|   1| /*·Copyright·(C)·2015·Wildfire·Games.
|    | [NORMAL] LicenseYearBear:
|    | License should have "2019" year instead of "2015"

source/simulation2/components/CCmpObstruction.cpp
|   1| /*·Copyright·(C)·2018·Wildfire·Games.
|    | [NORMAL] LicenseYearBear:
|    | License should have "2019" year instead of "2018"

source/simulation2/components/CCmpObstructionManager.cpp
|   1| /*·Copyright·(C)·2018·Wildfire·Games.
|    | [NORMAL] LicenseYearBear:
|    | License should have "2019" year instead of "2018"

source/simulation2/components/ICmpObstructionManager.h
|   1| /*·Copyright·(C)·2018·Wildfire·Games.
|    | [NORMAL] LicenseYearBear:
|    | License should have "2019" year instead of "2018"
Executing section JS...
Executing section cli...

Link to build: https://jenkins.wildfiregames.com/job/differential/1391/display/redirect

Harbormaster completed remote builds in B7469: Diff 8005.May 13 2019, 9:40 PM

Seems all units are causing considerable lag if they try to/want to go to the same position (with time the lag increases even more).

Some units go to the destination point but at collision go randomly (opposite way?) somewhere and return (inthe end all go and stay in the circle)

Replay: look at the houses for stuck units

2019-05-13_0003.zip20 KBDownload

This patch unfortunately negatively impacts the AI's ability to place structures.

When the AI looks to place a structure, it works out where it can place it by creating and consulting an "Obstruction Map" (ai/petra/mapModule.js:9). The following is an extract of such an "Obstruction Map", both before (left) and after (right) the application of this revision:

Those small black marks on the left side of the image that are missing on the right? Trees.

Yes: this revision means the AI cannot tell where trees are when it's trying to work out where to build stuff.

Why? From what I can tell (I'm no expert by any means):

The "Obstruction Map" is derived in part from a map of Passibility that is handed to it every update by the AIManager.
The AIManager gets it from the Pathfinder (CCmpAIManager.cpp:1042).
The Pathfinder doesn't (always) generate it from fresh, but instead hands over a copy of its most current one. When it did last generate a passibility map, it ran it through the ObstructionManager's Rasterize method (CCmpPathfinder:539 -> CCmpObstructionManager:858).
This calls the ObstructionManager's RasterizeHelper...
...which in turn calls RasterizeRectWithClearance in helpers/Rasterize.cpp.

The AI, when deriving its "Obstruction Map" from the passibility map, is looking for one thing: whether or not a navcell is passable to the building-land passibility-class. (Or building-shore if the AI's wanting to build something on the shore.)

When processing navcells, the RasterizeRectWithClearance function will, and I quote:

// Rasterise only navcells which are strictly inside the shape (+ clearance)

Now, the building-land passibility-class has no clearance set in pathfinder.xml. (And even if it did, it would be ignored for the most part.) So the clearance defaults to 0. And trees have such a small obstruction size that it is very rare that a navcell will ever be "strictly inside the shape".

This didn't matter before this revision, as the rasterisation code added on the value of Pathfinding::CLEARANCE_EXTENSION_RADIUS, bumping the clearance to 1. That no longer occurs; meaning that as they are usually too small to have a navcell entirely inside its obstruction shape, trees typically don't mark a navcell as building-land impassable.

So... we now get the AI trying to build Storehouses on top of the trees it wants to collect from. And wondering why it can't place a Barracks when there's clearly enough space.

(Oh, and when a player wishes to place a structure, the ObstructionManager's TestStaticShape method is used to check for current obstructions. A rasterised passibility map is consulted - should this check pass - but apparently for checking terrain.)

I've never reacted, @s0600204 , but thanks for reporting this which I had indeed initially missed.
I'll have to think of a way to fix this - perhaps motion and construction possibility classes will have to be made different? Dunno...