Paths

Table of Contentst

Fix Pathgoal::RectContainsGoal family of function for SQUARE goals, reduce ambiguities, improve coherence among the different functions.
AbandonedPublic
Actions

Authored by wraitii on Apr 19 2019, 5:51 PM.

Details

Reviewers

Group Reviewers

Restricted Owners Package	(Owns No Changed Paths)
Restricted Owners Package	(Owns No Changed Paths)

Summary

The current code is broken for Square goals and can be ambiguous in certain situations, as well as the different functions returning incompatible results in rare edge (literally) cases.

This revision removes those incoherences.

Test Plan

Review.

Diff Detail

Repository

rP 0 A.D. Public Repository

Lint

Lint OK

Unit

No Unit Test Coverage

Build Status

Buildable 7236
Build 11795: Vulcan Build	Jenkins
Build 11794: arc lint + arc unit

Event Timeline

wraitii created this revision.Apr 19 2019, 5:51 PM

wraitii retitled this revision from Make Pathgoal::NavcellContainsSquare correct (D53 outtake) to Make Pathgoal::NavcellContainsSquare use only the top/left edge of the square (D53 outtake).

wraitii edited the summary of this revision. (Show Details)

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

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

Harbormaster completed remote builds in B7213: Diff 7773.Apr 19 2019, 5:55 PM

wraitii mentioned this in D1831: Some more pathfinder tests (D53 outtake).Apr 19 2019, 6:01 PM

wraitii mentioned this in D53: D13 prerequisite 8: Upgrade the hierarchical pathfinder.Apr 20 2019, 10:24 AM

bb added a subscriber: bb.Apr 20 2019, 6:55 PM

bb added inline comments.

source/simulation2/helpers/PathGoal.cpp
29–33	`left/upper edge of a circle`, sounds like a joke we tell about Belgians here. Do you mean something like upper circle half, or the left/upper side of the navcell?
30	Seeing this I assume the second possibility?
66–72	if so then the same comment here

wraitii added inline comments.Apr 20 2019, 7:35 PM

source/simulation2/helpers/PathGoal.cpp
29–33	I mean the latter indeed. Comment sorta makes sense for squares.

Hopefully clarify comments.

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

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

Harbormaster completed remote builds in B7233: Diff 7793.Apr 21 2019, 5:35 PM

bb added inline comments.Apr 21 2019, 5:51 PM

source/simulation2/helpers/PathGoal.cpp
29–34	Now the written condition is true for about every navcell: a navcell is not supposed to be empty, so it will always contain "a" point... When you change `navcell (i,j)` to `circle (x,z,r)` the comment looks more correct `side` => `edge` similar for the square below

Mhpf, you're right. Fix other whitespace in this file while I'm at it.

@bb Do you agree with the intent of this patch (beyond comment clarity issues)?

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

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

Harbormaster completed remote builds in B7236: Diff 7796.Apr 21 2019, 6:01 PM

Stan added a subscriber: Stan.Apr 27 2019, 1:06 PM

Stan added inline comments.

source/simulation2/helpers/PathGoal.cpp
29	Maybe this could be doxygen on the top of the function :)
66	Same here.

wraitii mentioned this in rP7690: Add fixed-point sin/cos, to fix OOS errors.May 2 2019, 9:59 PM

I've realised there is a much more fundamental problem in RectContainsGoal (and related functions): our case for square goals is not sufficient!

We were checking if the point on the rect closest to the center of the goal was inside the goal, but that's not enough since the goal can be rotated arbitrarily. Indeed we have to used the Separating Axis Theorem in full force, unless I've missed something.

@Itms @echotangoecho (and anyone else really) I think you're both much better at geometry than I am, so I would appreciate if you could give this a look. It passes the tests and fixes the one empirical edge case I noticed, so I'm relatively confident, but still.
Maybe my SAT implementation can be sped up.

Incidentally, I'm also changing the rules for 'strictly' to be coherent across all functions, and I am also removing the (insane, frankly) code duplication in this file.

Will affect performance (possibly slower, possibly faster, hard to say for sure), and will change hashes since the previous code was incorrect.

With this I can should be able to make at least the reachable case from D1834 (the 'fast' case) not change svn hashes, which will give me high confidence in committing that performance improvement.

wraitii retitled this revision from Make Pathgoal::NavcellContainsSquare use only the top/left edge of the square (D53 outtake) to Fix Pathgoal::RectContainsGoal family of function for SQUARE goals, reduce ambiguities, improve coherence among the different functions..May 2 2019, 10:45 PM

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

Linter detected issues:
Executing section Source...

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

source/simulation2/helpers/PathGoal.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/1321/display/redirect

Harbormaster completed remote builds in B7351: Diff 7900.May 2 2019, 10:51 PM

@temple might know as well if he is still around...

wraitii mentioned this in D1835: Hierarchical Pathfinder - Add Global Regions / Optimise MakeGoalReachable (D53 outtake).May 4 2019, 3:19 PM

@Itms If you want to review something :)

Itms added a reviewer: Itms.May 25 2019, 11:53 AM

pinging @Itms on this again, as I do believe we still have the underlying bug :)

Rereading, this seems somewhat incorrect & RectContainsGoal is actually unused except in that test, so I'm abandoning this for now.