OpenRa trees edition #16698

teinarss · 2019-06-15T09:55:30Z

Adding a new trait, "Static" to mark actors that we can cache for the blocking check in the Pathfinder.

Benchmark 1

Map

256x256
Over 8000 trees

Results

Benchmark 2

Map

128x128
More similar to a normal game with a lot of moving actors and some static

Results

And without log scale

GraionDilach · 2019-06-15T11:09:48Z

Should be named PermanentPathfinderBlock or something along that line. In the current modding environment, a Static trait name has no meaning.

teinarss · 2019-06-15T11:13:52Z

StaticPathfinderBlock? Imo the problem with using "permanent" is that we are using it to also mark buildings that are not permement. So static would suit better.

…

On Sat, Jun 15, 2019, 13:10 Zimmermann Gyula ***@***.***> wrote: Should be named "PermanentPathfinderBlock" or something along that line. In the current modding environment, a "Static" trait name has no meaning. — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#16698?email_source=notifications&email_token=AESI7GHGXOA67KH6ARBETPLP2TEYXA5CNFSM4HYOWNZKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODXYV35I#issuecomment-502357493>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AESI7GDQKNNDFJ5TUT2UK3DP2TEYXANCNFSM4HYOWNZA> .

abcdefg30

👍 to StaticPathfinderBlocker. I can see the static vs. permanent argument, but agree that permanent makes less sense here.

mods/ra/rules/defaults.yaml

OpenRA.Mods.Common/Traits/World/Locomotor.cs

OpenRA.Mods.Common/Traits/BotModules/HarvesterBotModule.cs

OpenRA.Mods.Common/Pathfinder/PathGraph.cs

OpenRA.Mods.Common/Traits/Mobile.cs

teinarss · 2019-06-15T17:06:56Z

Updated!

pchote · 2019-06-15T23:18:46Z

Wouldn't it make more sense to add this as an interface that Building can implement?

teinarss · 2019-06-16T02:37:15Z

Then we would had to add the handling for crushing (because of walls) again and it was a bit messy. Or we would need to have a property on that interface.

…

On Sun, Jun 16, 2019, 01:19 Paul Chote ***@***.***> wrote: Wouldn't it make more sense to add this as an interface that Building can implement? — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#16698?email_source=notifications&email_token=AESI7GCYVWAKMQXA5HLB37DP2V2GPA5CNFSM4HYOWNZKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODXZBZ6Y#issuecomment-502406395>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AESI7GCIWIWJBUFXGKS5KF3P2V2GPANCNFSM4HYOWNZA> .

teinarss · 2019-06-20T22:19:36Z

[17:37:54] +pchote having a property doesnt seem too bad
[17:38:11] since that would just need to check if the crushable trait is defined
[17:39:07] but in principle it shouldnt matter at all - i will need to look at the pr in detail to comment further though
[17:39:35] the cache is per locomotor and crushing is too
[17:39:51] so in principle walls can still block for everything except mammoth tanks
[17:40:17] and that doesnt depend on Building at all
[17:40:49] the more important detail here is things that move vs things that dont
[17:41:31] but i may be missing something
[18:19:27] +pchote Mesacer_: thinking out loud here, so bear with me and then feel free to point out the fatal flaw
[18:20:19] 1) #16698 is a very scaled back version of the generalized crushability cache, which was sunk by the complications around crates/mines
[18:20:19] @orabot Pull request #16698 (open) by teinarss: OpenRa trees edition | http://bugs.openra.net/16698
[18:21:18] +pchote 2) #16408 is fundamantally sunk by not having the generalized crushability cache, or something similar to it
[18:21:19] @orabot Pull request #16408 (open) by tovl: Prevent harvesters getting stuck in gridlock by allowing units to give way. | http://bugs.openra.net/16408
[18:23:11] +pchote I don't remember the specifics about what caused problems with your general cache, but what is stopping us from having two BitSets for blocking - transient and static for each player?
[18:23:46] instead of saying "cell is blocked by player x" and then resolving owners at query time, have it as "cell is blocked for player X"
[18:24:10] and then update that whenever an actor moves or is added/removed from the world
[18:25:08] where IOccupySpace exposes the crush types to the actor map, which are then passed to the locomotor
[18:25:35] the special case logic for crates, mines, etc then shouldn't matter at all
[18:25:50] and we get #16698 and enable #16408 for free
[18:25:50] @orabot Pull request #16698 (open) by teinarss: OpenRa trees edition | http://bugs.openra.net/16698
[18:25:51] Pull request #16408 (open) by tovl: Prevent harvesters getting stuck in gridlock by allowing units to give way. | http://bugs.openra.net/16408
[19:24:05] Mesacer_ pchote i will need some time to digest this :P
[19:26:05] @orabot New pull request #16716 by RoosterDragon: Silence some doc errors in VS2019. | http://bugs.openra.net/16716
[19:26:29] Mesacer_ #16698 was sunk in complications around the crush feature, not for the crate?mines which we had removed from the icrushable interface
[19:26:29] @orabot Pull request #16698 (open) by teinarss: OpenRa trees edition | http://bugs.openra.net/16698
[19:27:28] Mesacer_ not that pr but the one that we closed
[19:29:55] +pchote ah right that one was actually caching cost, not crushability
[19:31:25] Mesacer_ the one we closed cached crush, moving, static if i remember correctly

RoosterDragon · 2019-06-26T19:20:37Z

If I'm following this right, when the PathGraph asks GetCostToNode for a blocked cell, we can return a cached "yes it's blocked" result rather than having to calculate CanMoveFreelyInto? Is that the main idea here?

A few high-level questions:

Is there a reason/benefit to cache the path cost, rather than just the "is blocked" nature of the cell?
Why is there a cache per locomotor (as opposed to a single cache for the world)?
Why a marker trait? Since Locomotor owns the IsBlockedBy implementation can't it use the knowledge of that implementation to determine immobile actors that always block and determine that automatically? (at a glance, immobile, non-temporary-blocker and non-crushable) - perhaps there is some subtly in the previous discussion about crushing that answers this (or maybe I'm barking up the wrong tree entirely... not sure)

GraionDilach · 2019-06-26T20:13:42Z

@RoosterDragon Regarding your last point - you're assuming too much there. For example, in RA, tree husks (charred trees) are separate actors. This means that while the tree itself can be killed, it's cell won't be freed up due to the charred husk. Cases like these require actual use-case insight and the code cannot determinate/would take a lot of edge-case-based assumptions to figure this out on his own. A marker trait poses less burden for maintenance for the developers and more exact setups for the modders.

teinarss · 2019-06-26T20:15:18Z

If I'm following this right, when the PathGraph asks GetCostToNode for a blocked cell, we can return a cached "yes it's blocked" result rather than having to calculate CanMoveFreelyInto? Is that the main idea here?

A few high-level questions:
* Is there a reason/benefit to cache the path cost, rather than just the "is blocked" nature of the cell?

We cache both the cell cost and "is blocked". The gain caching the cell cost is arguable.

* Why is there a cache per locomotor (as opposed to a single cache for the world)?

Mostly because its based on a previous PR that we closed that also cached crushing. And also for the cell cost which is dependent on the locomotor. If we gonna do the crushing type again as suggested by pchote above we need it for each locomotor.

* Why a marker trait? Since `Locomotor` owns the `IsBlockedBy` implementation can't it use the knowledge of that implementation to determine immobile actors that always block and determine that automatically? (at a glance, immobile, non-temporary-blocker and non-crushable) - perhaps there is some subtly in the previous discussion about crushing that answers this (or maybe I'm barking up the wrong tree entirely... not sure)

That was my first idea:ish but https://logs.openra.net/?year=2019&month=05&day=25#20:37:57

teinarss · 2019-07-02T15:46:56Z

Updated.
"Struct with flag opti" is this PR

teinarss · 2019-07-02T17:28:58Z

For benchmark 1

pchote

Some initial comments. I haven't yet looked at the meat of the cost/blocking cache logic.

OpenRA.Game/Player.cs

OpenRA.Mods.Common/Traits/World/CreateMPPlayers.cs

OpenRA.Game/Traits/TraitsInterfaces.cs

OpenRA.Mods.Common/Traits/World/ActorMap.cs

OpenRA.Game/Primitives/LongBitSet.cs

OpenRA.Mods.Common/Traits/World/Locomotor.cs

teinarss · 2019-07-07T17:58:20Z

Updated!

teinarss · 2019-07-09T19:57:00Z

Updated with the things discussed.

OpenRA.Mods.Common/Traits/Crushable.cs

OpenRA.Mods.Common/Traits/World/CreateMPPlayers.cs

OpenRA.Mods.Common/Traits/World/Locomotor.cs

reaperrr · 2019-07-26T12:45:57Z

OpenRA.Mods.Common/Pathfinder/PathGraph.cs

@@ -84,6 +84,7 @@ sealed class PathGraph : IGraph<CellInfo>

 		readonly CellConditions checkConditions;
 		readonly LocomotorInfo locomotorInfo;


I doubt caching locomotorInfo separately is worth it now. Can you remove this and use locomotor.Info directly instead?

reaperrr · 2019-07-26T12:46:26Z

OpenRA.Mods.Common/Traits/BotModules/HarvesterBotModule.cs

@@ -45,13 +45,16 @@ class HarvesterTraitWrapper
 			public readonly Harvester Harvester;
 			public readonly Parachutable Parachutable;
 			public readonly LocomotorInfo LocomotorInfo;


reaperrr · 2019-07-26T12:47:23Z

OpenRA.Mods.Common/Traits/Harvester.cs

-			var li = self.Info.TraitInfo<MobileInfo>().LocomotorInfo;
-			using (var search = PathSearch.FromPoints(self.World, li, self, refs.Values.Select(r => r.Location), self.Location, false)
+
+			var locomotor = mobile.Locomotor;


The old var was mostly about reducing line length of the using, I think we can drop this now and use mobile.Locomotor directly below.

reaperrr · 2019-07-26T12:50:39Z

OpenRA.Mods.Common/Traits/World/PathFinder.cs

@@ -64,7 +64,10 @@ public PathFinder(World world)

 		public List<CPos> FindUnitPath(CPos source, CPos target, Actor self, Actor ignoreActor)
 		{
-			var li = self.Info.TraitInfo<MobileInfo>().LocomotorInfo;
+			var mobile = self.Trait<Mobile>();
+			var li = mobile.Info.LocomotorInfo;


I'd either drop this (likely no real benefit) and use locomotor.Info directly, or at least move it below locomotor so you can just populate it by locomotor.Info.

reaperrr · 2019-07-26T12:51:55Z

OpenRA.Mods.Common/Traits/World/PathFinder.cs

-			var li = mi.LocomotorInfo;
+			var mobile = self.Trait<Mobile>();
+			var li = mobile.Info.LocomotorInfo;
+			var mi = mobile.Info;


If you switch order of these two, you can populate li through mi.LocomotorInfo.

reaperrr · 2019-07-26T12:59:52Z

LGTM after those final nits 👍

reaperrr · 2019-07-26T13:56:26Z

https://github.com/OpenRA/OpenRA/wiki/Changelog-(bleed)/_compare/c3e751ce5653b67b5e53ac89d5aebeefc157d553...1c3ba302bc0e23670992b70f9dacf4830d75624c

RoosterDragon · 2019-07-26T19:01:59Z

This appears to have caused tick times to increase on the RA shellmap from ~10ms to ~14ms on my machine. Can anybody else reproduce? Profiling suggests Locomotor.UpdateCellBlocking is responsible for the increase.

pchote · 2019-07-26T20:31:30Z

Confirmed (~6 → 9ms in my case), and derp at the massive blind spot that we had in testing/profiling this.

reaperrr · 2019-07-26T20:32:31Z

Yeah. Last commit seems to be the culprit.

pchote · 2019-07-26T20:39:03Z

We can save this by changing Locomotor.CellsUpdated to be lazy - mark the cells as dirty, but defer calling UpdateCellBlocking and UpdateCellCost until a pathfind actually needs to know the value.

At this point its probably going to be better to revert this, and aim an improved version for Next + 1.

teinarss · 2019-07-26T20:55:10Z

Or go parallel?

teinarss · 2019-07-27T05:46:47Z

pchote · 2019-07-27T09:19:54Z

The perf regression was caused by a silly bug rather than any fundamental algorithm issue - fixed in #16846.

abcdefg30 reviewed Jun 15, 2019

View reviewed changes

reaperrr reviewed Jun 15, 2019

View reviewed changes

OpenRA.Mods.Common/Traits/Mobile.cs Outdated Show resolved Hide resolved

teinarss force-pushed the priority_queue branch from 760d8fb to e8b3a08 Compare June 15, 2019 17:06

teinarss mentioned this pull request Jun 28, 2019

Prevent harvesters getting stuck in gridlock by allowing units to give way. #16408

Merged

teinarss force-pushed the priority_queue branch 2 times, most recently from b9ec2e4 to e1baa4e Compare July 2, 2019 15:44

pchote added this to the Next Release milestone Jul 3, 2019

pchote reviewed Jul 7, 2019

View reviewed changes

teinarss force-pushed the priority_queue branch from e5444f4 to d137a3d Compare July 7, 2019 17:58

teinarss force-pushed the priority_queue branch from d137a3d to ddb05d2 Compare July 9, 2019 19:56

teinarss commented Jul 19, 2019

View reviewed changes

OpenRA.Mods.Common/Traits/Crushable.cs Outdated Show resolved Hide resolved

OpenRA.Mods.Common/Traits/World/CreateMPPlayers.cs Outdated Show resolved Hide resolved

pchote reviewed Jul 19, 2019

View reviewed changes

OpenRA.Mods.Common/Traits/World/Locomotor.cs Outdated Show resolved Hide resolved

reaperrr mentioned this pull request Jul 20, 2019

Use Actor.OccupiesSpace to save Mobile trait look-ups #16808

Closed

teinarss force-pushed the priority_queue branch 4 times, most recently from 63b854c to 0ebc455 Compare July 20, 2019 10:28

teinarss removed the PR: Fixup requested label Jul 22, 2019

pchote previously approved these changes Jul 22, 2019

View reviewed changes

reaperrr reviewed Jul 26, 2019

View reviewed changes

teinarss added 5 commits July 26, 2019 15:29

Using Locomotor instead of Info for pathfinding

6fb75f0

Creating PlayerMask

a6e8339

Added CellUpdated event to ActorMap

5858356

Updated TerrainInfo cost to use short

124978e

Added cache for cell cost and blocking

1641161

teinarss dismissed pchote’s stale review via 1641161 July 26, 2019 13:30

teinarss force-pushed the priority_queue branch from c304949 to 1641161 Compare July 26, 2019 13:30

reaperrr approved these changes Jul 26, 2019

View reviewed changes

reaperrr merged commit cc84daa into OpenRA:bleed Jul 26, 2019

reaperrr mentioned this pull request Jul 26, 2019

Cache IMove in Actor #16804

Closed

reaperrr mentioned this pull request Jul 27, 2019

Unloading actors ignore passability (and sometimes infantry) #16848

Closed

tovl mentioned this pull request Jul 29, 2019

Move-undeploy no longer works on MCVs #16862

Closed

pchote mentioned this pull request Aug 5, 2019

Starting units can overlap in the same cell #16880

Closed

teinarss deleted the priority_queue branch April 15, 2021 16:48

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

OpenRa trees edition #16698

OpenRa trees edition #16698

teinarss commented Jun 15, 2019

GraionDilach commented Jun 15, 2019 •

edited

teinarss commented Jun 15, 2019 via email

abcdefg30 left a comment •

edited

teinarss commented Jun 15, 2019

pchote commented Jun 15, 2019

teinarss commented Jun 16, 2019 via email

teinarss commented Jun 20, 2019

RoosterDragon commented Jun 26, 2019

GraionDilach commented Jun 26, 2019 •

edited

teinarss commented Jun 26, 2019

teinarss commented Jul 2, 2019

teinarss commented Jul 2, 2019

pchote left a comment

teinarss commented Jul 7, 2019

teinarss commented Jul 9, 2019

reaperrr Jul 26, 2019

reaperrr Jul 26, 2019

reaperrr Jul 26, 2019

reaperrr Jul 26, 2019

reaperrr Jul 26, 2019 •

edited

reaperrr commented Jul 26, 2019

reaperrr commented Jul 26, 2019

RoosterDragon commented Jul 26, 2019

pchote commented Jul 26, 2019

reaperrr commented Jul 26, 2019

pchote commented Jul 26, 2019

teinarss commented Jul 26, 2019

teinarss commented Jul 27, 2019

pchote commented Jul 27, 2019

		@@ -84,6 +84,7 @@ sealed class PathGraph : IGraph<CellInfo>

		readonly CellConditions checkConditions;
		readonly LocomotorInfo locomotorInfo;

OpenRa trees edition #16698

OpenRa trees edition #16698

Conversation

teinarss commented Jun 15, 2019

Benchmark 1

Map

Results

Benchmark 2

Map

Results

GraionDilach commented Jun 15, 2019 • edited

teinarss commented Jun 15, 2019 via email

abcdefg30 left a comment • edited

Choose a reason for hiding this comment

teinarss commented Jun 15, 2019

pchote commented Jun 15, 2019

teinarss commented Jun 16, 2019 via email

teinarss commented Jun 20, 2019

RoosterDragon commented Jun 26, 2019

GraionDilach commented Jun 26, 2019 • edited

teinarss commented Jun 26, 2019

teinarss commented Jul 2, 2019

teinarss commented Jul 2, 2019

pchote left a comment

Choose a reason for hiding this comment

teinarss commented Jul 7, 2019

teinarss commented Jul 9, 2019

reaperrr Jul 26, 2019

Choose a reason for hiding this comment

reaperrr Jul 26, 2019

Choose a reason for hiding this comment

reaperrr Jul 26, 2019

Choose a reason for hiding this comment

reaperrr Jul 26, 2019

Choose a reason for hiding this comment

reaperrr Jul 26, 2019 • edited

Choose a reason for hiding this comment

reaperrr commented Jul 26, 2019

reaperrr commented Jul 26, 2019

RoosterDragon commented Jul 26, 2019

pchote commented Jul 26, 2019

reaperrr commented Jul 26, 2019

pchote commented Jul 26, 2019

teinarss commented Jul 26, 2019

teinarss commented Jul 27, 2019

pchote commented Jul 27, 2019

GraionDilach commented Jun 15, 2019 •

edited

abcdefg30 left a comment •

edited

GraionDilach commented Jun 26, 2019 •

edited

reaperrr Jul 26, 2019 •

edited