Page MenuHomeWildfire Games

Vision Blocking by Terrain while exploring
Needs ReviewPublic

Authored by Angen on May 17 2019, 9:58 PM.
This revision needs review, but there are no reviewers specified.

Details

Reviewers
None
Trac Tickets
#3634
Summary

Currently every entity has los given by range and reveals everything in that range. This patch is adding blocking of entity vision given by terrain (one from TODOs of range manager).
This blocking of vision applies only for visibility on the map. Not to the fact if entity see another entity.

Changed los update computation from stripes to squares starting from entity position and forming them to circle.
This way code can do multiple raycasts at one go and checks every tile in range only once.
To know if tile is visible it needs information at most from 2 neighbouring tiles.

There have been added two maps (both boolean) with the same structure as m_LosState (this holds if tile is visible/explored/hidden).
One map holds information which tiles are visible.
Second map holds information which tiles blocks vision. (tile blocking vision can be visible)

This has to remove incremental update as tile visibility will change every time entity moves and computation needs to always start from source.

Adding new experience from exploring map and increase importance of watch towers and scouting when playing on map with hills. And is removing ability for player to see through mountains.

(related forum topic: https://wildfiregames.com/forum/index.php?/topic/25975-vision-blocking-wip/)

Test Plan

Check incrementing logic for circle. Maybe could be done faster/nicer.
Test for performance (I believe not too much overhead was added as I did not notice big problems but maybe needs more testing)

Main test goal: moving group of entities with big los, building buildings with big los, removing group of buildings with big los or a bigger groups of buildungs with small los

Also there was gl error out of memory reported at forum topic, but might be just because of build I provided.
So please test with different OS.

Me: windows, intel graphic card- cannot reproduce gl out of memory error.

Diff Detail

Repository
rP 0 A.D. Public Repository
Branch
/ps/trunk
Lint
Lint OK
Unit
No Unit Test Coverage
Build Status
Buildable 7606
Build 12404: Vulcan BuildJenkins
Build 12403: arc lint + arc unit

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
Angen added inline comments.May 18 2019, 12:34 PM
source/simulation2/components/CCmpRangeManager.cpp
46

not used anymore

410

what do you mean ?

2049–2050

oh nice, did not realise it

2086

I plan it :)

2140

it returns float so yes :)

smiley added a subscriber: smiley.May 18 2019, 1:12 PM
smiley added inline comments.
source/simulation2/components/CCmpRangeManager.cpp
414

std::vector<bool>. That’s interesting.

smiley removed a subscriber: smiley.May 18 2019, 1:12 PM
Angen added inline comments.May 18 2019, 4:51 PM
source/simulation2/components/CCmpRangeManager.cpp
414

what is interesting about it?

elexis added a subscriber: elexis.May 18 2019, 8:36 PM
elexis added inline comments.
source/simulation2/components/CCmpRangeManager.cpp
414

According to Wiktionary, interesting = interest +‎ -ing, from Latin interesse = present active infinitive of intersum = inter- +‎ sum, where

inter:

From Proto-Italic *enter, from Proto-Indo-European *h₁entér (“between”). Cognates include Sanskrit अन्तर् (antár, “between, within, into”), Oscan 𐌀𐌍𐌕𐌄𐌓 (anter, “between”), Old Irish eter (“between”), Albanian ndër (“between, among, amid, throughout”), Old High German untar (“between”) and German unter (“among”).

sum:

The present stem is from Proto-Italic *ezom, from Proto-Indo-European *h₁ésmi (“I am, I exist”). Cognates include Ancient Greek εἰμί (eimí), Sanskrit अस्मि (ásmi), Old English eom (English am). The perfect stem is from Proto-Italic *(fe)fūai, from Proto-Indo-European *bʰúHt (“to become, be”) (whence also fīō (“to become, to be made”), and future and imperfect inflections -bō, -bam).

In other words he has a patch for it somewhere, see discussion in D1637.

Angen updated this revision to Diff 8058.May 18 2019, 9:14 PM

More complex tests for range manager (for now with flat terrain but it is something :) )

Build failure - The Moirai have given mortals hearts that can endure.

Linter detected issues:
Executing section Source...

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

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

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

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

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

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

source/simulation2/components/CCmpRangeManager.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/1435/display/redirect

Angen marked 2 inline comments as not done.May 18 2019, 9:20 PM
Angen updated this revision to Diff 8060.May 18 2019, 9:40 PM

fix debug build

Build failure - The Moirai have given mortals hearts that can endure.

Linter detected issues:
Executing section Source...

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

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

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

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

smiley added inline comments.May 18 2019, 10:04 PM
source/simulation2/components/CCmpRangeManager.cpp
414

No I do not have a patch anywhere related to this. If I am being more specific at what I am getting at, just see the differences of vector<notBoolT> vs vector<boolT>.
D1637 has nothing to do with this. (I did not need to go with cpp btw. Js was optimized to the point where it performed at the same speed). It’s more of low level details in this case.

smiley added inline comments.May 18 2019, 10:49 PM
source/simulation2/components/CCmpRangeManager.cpp
414

Just to clarify, I am not being vague here. I am just trying to avoid making a direct statement since I don't consider myself an expert in C++.

Stan added a comment.May 18 2019, 11:16 PM

Looks like my comments weren't submitted.

source/simulation2/components/CCmpRangeManager.cpp
46

Fair.

410

#include <vector>

Angen added inline comments.May 18 2019, 11:20 PM
source/simulation2/components/CCmpRangeManager.cpp
410

not needed include, used at lines 402, 384, 392

Stan added inline comments.May 18 2019, 11:22 PM
source/simulation2/components/CCmpRangeManager.cpp
410

I'm not sure I understand.

Forward declaration for STD types is undefined behavior so that wouldn't work + It doesn't work for members.
So why isn't the include needed ?

Angen updated this revision to Diff 8061.May 18 2019, 11:22 PM
Angen updated the Trac tickets for this revision.

added check against overflow when forming circle what was reason why debug tests failed

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

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

elexis added inline comments.May 19 2019, 10:55 AM
source/simulation2/components/CCmpRangeManager.cpp
414

I guess you mean that https://en.cppreference.com/w/cpp/container/vector_bool might or might not be worth reading

elexis added inline comments.May 19 2019, 11:25 AM
source/simulation2/components/CCmpRangeManager.cpp
414

(Also to clarify, I didn't want to imply that you were intentionally vague in that statement, I actually wanted to derive the statement from the etymology but failed the last steps of the deduction and it's useless indirection anyhow)

smiley added inline comments.May 19 2019, 11:52 AM
source/simulation2/components/CCmpRangeManager.cpp
414

Or tldr; It's not an STL container and therefore does not work like one (code which would compile for other T vector would not compile for this specific thing). And it's placement is widely regarded as a mistake in the standard. But despite the various attempts to remove or depreciate the thing, it still remains as part of the standard. For backwards compatibility I suppose.

I guess this is the part where I propose solutions. boost bitsets.

elexis added inline comments.May 19 2019, 12:21 PM
source/simulation2/components/CCmpRangeManager.cpp
414

refs https://stackoverflow.com/questions/17794569/why-is-vectorbool-not-a-stl-container

So the problem with it is it pretends to be an STL container but isn't one, which is arguably contradictory and thus a mistake, and thus can be assumed to be deprecated in the future and thus not using it now would mean that our code doesn't have to be changed in the future, even if one only uses those functions that compile fine now.

The question is whether there is also a plan for a successor, since the use case for bit arrays won't go away.

I thought it would be preferable to avoid making the code depend on boost libraries.

smiley added inline comments.May 19 2019, 12:46 PM
source/simulation2/components/CCmpRangeManager.cpp
414

Arguments for not using this and using boost.
https://www.boost.org/doc/libs/1_54_0/doc/html/container/Cpp11_conformance.html#container.Cpp11_conformance.Vector_bool

A bitset that is reasonably performant is not that difficult to implement. So that is an alternative too.

Or just keep this as is. As long as whoever will commit this is fine with it, this whole discussion can be safely ignored.

Just tried it it's pretty cool. I think though that the plateau reveal themselves too quickly for some reason, and it can be quite surprising for the user. I didn't notice any big performance drop, even on a giant map. But then I have a pretty good PC.

source/simulation2/components/CCmpRangeManager.cpp
405

calls

406

@vladislavbelov I wonder in which cases we should use smart pointers instead of raw ones.

414

@Angen can you try the boost bitesets and do some profiling ? :) You can usually do so in the tests, so that you have an easy sandbox.

1635

could be merged ?

1637

Missing spaces between operators, make this a helper function, and use it in both methods, with LOS_VISIBLE and explored as parameter ?

source/simulation2/components/tests/test_RangeManager.h
548

Don't think you need to check for both, do you ?

source/simulation2/system/ComponentTest.h
26 ↗(On Diff #8061)

whitespace

71 ↗(On Diff #8061)

delete

193 ↗(On Diff #8061)

m_UseTerrain also you could set it to false in the Init function.

208 ↗(On Diff #8061)

ternary ?

214 ↗(On Diff #8061)

m_useTerrain = true = m_Terrain ?

219 ↗(On Diff #8061)

ternary ?

239 ↗(On Diff #8061)

static_cast<int>(...) though probably no need to cast as there is a cast just after. One might want to cast to float otherwise.

245 ↗(On Diff #8061)

ternary ?

252 ↗(On Diff #8061)

ternary ?

259 ↗(On Diff #8061)

ternary ?

272 ↗(On Diff #8061)

One could use std::numeric_limits<short>::max()

286 ↗(On Diff #8061)

one could use std::numeric_limits<u16>::max()

293 ↗(On Diff #8061)

nullptr. Maybe ternary ?

303 ↗(On Diff #8061)

Any reason we are using i32 specifically instead of int ?

322 ↗(On Diff #8061)

static_cast<int>(...) spaces between operators.

323 ↗(On Diff #8061)

static_cast<int>(...) spaces between operators.

330 ↗(On Diff #8061)

static_cast<int>(...) spaces between operators.

331 ↗(On Diff #8061)

static_cast<int>(...) spaces between operators.

Angen added a comment.May 21 2019, 5:06 AM

well dont think I can do anything about pletau revealing. Terrain there is flat so. Unless you have some ideas.

source/simulation2/components/tests/test_RangeManager.h
548

yes I was just super cautious :)

source/simulation2/system/ComponentTest.h
239 ↗(On Diff #8061)

you cannot do fixed / float operation
it is well defined op fixed / int :) you are not loosing float information

and it is exactly what is in CCTerrain :)

303 ↗(On Diff #8061)

dont know, maybe just to be sure its 32 and not 64

Stan added a comment.May 21 2019, 8:35 AM

Maybe you could progressively increase the range depending on the height ? Or just slowly reveal it by increasing the view distance slowly when discovering a new plateau. Otherwise I think it really makes things interesting.

Angen added a comment.May 21 2019, 3:09 PM

Its not hidden because vision distance but because it is not higher than last visible point by entity which is blocking vision :)

Angen edited the test plan for this revision. (Show Details)May 21 2019, 3:18 PM
Angen updated this revision to Diff 8104.EditedMay 22 2019, 12:26 PM

cleanup and trying bitset, I did not found any significant performance loss or improvement switching from vector to bitset, changing position (with bitset) of entity 3000 times with step of 1 tile was done from 1000 to 2000 micro seconds

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

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

Stan added a comment.May 22 2019, 4:06 PM

Some more comments :)

source/simulation2/components/CCmpRangeManager.cpp
226

maybe name it height, and remove the comment ?

341

Nuke ?

422

Can't you just use the DEFINE Above instead of adding a new one ?

810

Anyway to check that they aren't the same to avoid useless assignation ?

877

Caps.

1635

Would be something like

return (!(LosIsOffWorld(i, j) ||
    !(i >= 0 && j >= 0 && i < m_TerrainVerticesPerSide && j < m_TerrainVerticesPerSide)) &&
    m_LosState[j*m_TerrainVerticesPerSide + i] & (state << (2 * (player - 1)))
2738

Range loop maybe.

Angen updated this revision to Diff 8144.May 25 2019, 9:03 PM

some comments

Angen added inline comments.May 25 2019, 9:08 PM
source/simulation2/components/CCmpRangeManager.cpp
1635

I dont know it would be too long

2738

here i am not sure

To be honest I'm not sure what to do with this. It's a huge gameplay change, with potentially complex performance implications (in the wrong direction, sadly). It's also C++, so you can't really get it as part of a mod.

Realistically, I don't think we'll commit this anytime soon even unless we end up deciding that this is a gameplay change we absolutely want for A24 - which is doubtful because we're still in the process of deciding how we move forward with game design.

On your side, going forward, what I would do is:

  • make it possible to disable this feature in-game.
  • run lots of performance tests using profiler2 (possibly comparing with the disabled feature, which should have the same simulation states).
Stan added inline comments.May 25 2019, 9:40 PM
source/simulation2/components/CCmpRangeManager.cpp
1635

Could be make clearer with functions maybe :)

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

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