Block change tracking: false positives with changing blocks (SurvivalFly, Passable, pistons, piston+slime, elevators, falling blocks, trap doors, placed/broken/changed blocks) [DBO 364]

[MyPictures]

All type of block changes can lead to trouble with the survivalfly and passable checks, due to latency. This involves false positives for most. Some redstone driven blocks have been made exempt from passable by the default configuration, in order to make them playable, resulting in doors and the like not being safe to keep others out of an area. The issue with these blocks still are false positives, because the blocks can be unplayable for players with high latency connections, once the workarounds are removed.

• Pistons (might cover extra momentum with slime blocks).
• Redstone driven in-place block changes (doors, trap doors).
• Minging/building.
• Falling blocks.
• (Indirect changes, with blocks that change shape based on other adjacent blocks, such as fences, iron bars, glass panes.)
• (Blocks changed by plugins.)

Essentially this is somewhat complicated to support, because...

• The on-ground estimation needs to account for past block changes.
• Passable checks need to account for block changes too (including ray-tracing).
• Scattered all over the code base could be places that check for what types of blocks there may have been.
  • E.g. checking for being in liquid/lava/slime blocks.
  • Some places might lead to the need for calculate several branches of possible past environments :). Rather
• Preventing false positives (fall damage where pistons have just closed the chimney/thing.
• Preventing abuse (Players might walk over the pit, optimized such, that they always make maximum use of where they can/want to go). Complex cheat, not too likely, but there might be simple attempts like freecam/blink/replay, which might work for some parkour stuff. This will probably lead to have us use a global latency estimate, based on location traces with fight checks, block change tracking, velocity use, certain other client responses towards packets the server sends to them.
• (Other plugins might not advertise their changing of blocks.)

Roadmap:

1. Make vertical push work. (Mostly survivalfly+onground+push-distances, possibly passable.) [Already started.]
2. Possibly more optimizations, and per-world configuration (memory saving by player tracking, exclude creative worlds, players?)
3. Horizontal pushing.
4. General compatibility for onground and passable (might be done with any earlier point), advanced concepts using global latency estimates.

See technical details/discussion/guessing, if interested: https://github.com/NoCheatPlus/Docs/wiki/Design#block-change-tracking-pistons-redstone-digging-other

(Removed past comments, having updated the description.)
Duplicated by: #66

[asofold]

Currently i'm working out concepts for pulling this through for pistons. Have a look at: https://github.com/NoCheatPlus/Docs/wiki/Design#block-change-tracking-pistons-redstone-digging-other (CURRENT CONCEPT: ...).

In short, it looks like i have enough ground sketched out, to start implementing opportunistic on-ground and passable checking just for the flying checks. Using the same or similar methods for interaction could also be interesting, however there keeping conistency with latency estimates will be more important in order to prevent abuse. That would demand having a latency estimate in the first place :p.

The roadmap roughly stays the same.

• Opportunistic passable checking.
• Opportunistic/heuristic on-ground checking, likely just after-failure near/at vdistrel at first.
• Thus have the y-move covered (find more edges, fix up where possible).
• EDIT: At this point, might consider piston + slime, otherwise do this last. EDIT2: A slime block flag could be added to push/pull entries already now, setting the bounce effect based on getting pushed/pulled - however there might be other side conditions that demand alterations with on-ground pre-conditions for using the bounce effect (technicalities), so this may stay an extra thing until here.
• Horizontal push.
• Find edges for the entire thing with passable and on-ground. Here it gets more shifty, as the vertical move is checked after the horizontal move, but we might need the on-ground properties during checking of the horizontal move, and similar things, oddities. Thus some refactoring might happen here and changes towards variable checking order, more heuristic pre-checks (e.g. a coarse might-there-be-block-changes check triggers heuristics for testing properties nearby).

More uncertainties:

• How to adjust the set-back, in case of being on ground just because of block changes? Considering falling sand, just keeping the old set-back is possible, but there will be differing views on when it's better to set back to last any-ground or last solid-ground.

[asofold]

Around build 1040 more work has been done towards "much more" piston compatibility.

• A few internals have been adapted to work with past-block-states.
• For efficiency, a block change activity check (32x32x32 chunks) has been implemented, so moving checks will not even attempt to query for past block changes, if nothing has happened earby+recently.
• Opportunistic passable checking has been implemented (from here it's a small step towards tracking doors too and get rid of ign_passable workarounds).

For opportunistic on-ground checking, a few things are still missing.

• Final decision for entry points, where in the code to put queries for past block states. (Pondering mixtures of after-failure/vdistrel and before even checking lost ground, likely the latter+heuristics).
• Optimized methods to efficiently determine pairs of node+nodeAbove for checking on-ground with one coordinate. It appears to make sense, to at least have this pair with overlapping intervals of validity, while we don't cross-check consistency between differing potential on-ground coordinates. The block above is typically needed to prevent spider hacks in a more efficient way.
• In terms of efficiency it would be good to have some kind of query/aggregator/delegate that temporarily stores iterators for per-coordinate lists of BlockChangeTracker internals, otherwise there is a risk of quadratic checking runtime with positions that have one or more block changes per tick.
• Algorithmically, the checking routine will have a similar structure like BlockProperties.isOnGround, however we will have to potentially repeatedly test for fitting pairs of node+nodeAbove inside the y-loop. xyz-Iteration can't be stopped with one successful find, because that might invalidate timing with having a very recently created block change (more recent than latency makes possible). Thus this could become heavier than the ordinary on-ground checking.

On the long run...

• We might need a more complex data structure to query past states both in a more consistent and in a more efficient way. It'll be necessary to keep track of all used nodes, and be able to re-check previously used nodes with the side conditions of whatever check has used them (...), because the intervals of validity don't overlap with the latest of added nodes. It'll be hard to tell, which check actually failed :p.
• It could also be "interesting" to evaluate, if we should run the entire block based checking based on assumed validity intervals for latency, e.g. because the latest block changes have not even arrived at the client (...). Thus we could decide for running the checks with a preferred (past-) map state, and then upon inconsistencies, determine if we can find a similar set of blocks within the allowed regions of a latency window (advance the window towards sooner or later).
• I'd prefer to not have to do all that, though :p.

Forgot to mention:

• The BlockChangeTracker is now activated by default (might need altering the setting for existing configurations), so opportunistic passable checking is live. This might help with decreasing the opening interval for piuston-driven entries. (Doors are not covered yet.)

[asofold]

Vertical piston (+slime) support will be better soon, though there still can be a million edges.

Expectable issues even for the next build (~ 28 hours perhaops) will be around:

• Friction envelope (ascending, typically). Due to estimating past-ground to be there, the friction mechanics are not recognized. Possibly easy to mend by skipping setting ground, if the move is fairly large and within a typical friction envelope, can't tell if we're dealing with again increased lost-past-ground issues then :).
• Invalidation issues with (larger) setups where pistons extend/retract with a tick or more difference. Since we can't tell from which side a player will come, invalidation by the exact tick time will prevent using the ground, if the blocks get invalidated due to the player moving from the "younger" side. Possibly we can use differing invalidation mechanisms for push+pull vs. on-ground vs. passable (push+pull always is excluding using it again, once you have left the block). Perhaps we'll have to remember what blocks we used what for and do per-issue invalidation, still accunting for the interval of validity per-block.
• Fall damage is dealt too often.
• Random edge cases.
• (I didn't test with any jump effects yet.)
• (Lost-past-ground issues. Some of the workarounds we use for ordinary moving may also be necessary with handling past states. It's thinkable that if the stuff works too good at first, people will rely on larger setups, laying open these kind of issues.)
• (A little bit of exploitation with sneaking, if i forget to check for it. Think of similar side-conditions.)
• (The horizontal push/pull part is not yet implemented.)

Making ordinary redstone and piston driven setups work with latency will be quite a good thing already (piston driven doors, ), also piston traps are of higher priority here.

Currently i am shifting the already sketched out approach to do as much as possible within the MovingListener, with the checks at the position where the classic bounce-checks have been.

[asofold]

Much of vertical is done, except for moving with the side of the bounding box onto a just/next extended slime block.

Horizontal is missing, last attempt had to be aborted due to other incoming issues. An insertion point had been tried, but it did not fully work.

Then .,.. with vehicles.