Announcement: Be excellent to each other.


Caravel Forum : DROD Boards : Bugs : Briar bug (Briar has connection between detached patchs.)
New Topic New Poll Post Reply
Poster Message
lsyddg
Level: Roachling
Rank Points: 14
Registered: 07-22-2014
IP: Logged

File: Briar bug.hold (907 bytes)
Downloaded 15 times.
License: Public Domain
icon Briar bug (+2)  
As shown in the attached hold, a patch of briar is split by a bomb, but has connection through another patch of briar. Then the ‘pass’ briar is destroyed, but they are still connected.
07-26-2014 at 06:32 PM
View Profile Send Private Message to User Show all user's posts Quote Reply
skell
Level: Legendary Smitemaster
Avatar
Rank Points: 3500
Registered: 12-28-2004
IP: Logged
icon Re: Briar bug (+1)  
I can't get over the fact no one has freaked out like mad about this.

____________________________
My website | Facebook | Twitter
09-30-2020 at 01:59 PM
View Profile Send Private Message to User Send Email to User Visit Homepage Show all user's posts High Scores This architect's holds Quote Reply
skell
Level: Legendary Smitemaster
Avatar
Rank Points: 3500
Registered: 12-28-2004
IP: Logged

File: BUG REPORT Briar Magic.hold (970 bytes)
Downloaded 3 times.
License: Public Domain
icon Re: Briar bug (+1)  
Here is a bit more minimal example hold with the bug.



____________________________
My website | Facebook | Twitter
09-30-2020 at 03:00 PM
View Profile Send Private Message to User Send Email to User Visit Homepage Show all user's posts High Scores This architect's holds Quote Reply
skell
Level: Legendary Smitemaster
Avatar
Rank Points: 3500
Registered: 12-28-2004
IP: Logged

File: BriarBug.jpg (209 KB)
Downloaded 235 times.
License: Public Domain
icon Re: Briar bug (+4)  
The image used in the explanation:
Click here to view the secret text


Understanding this bug requires understanding some of the internals of how DROD handles briar, so sit tight and read if you're curious.

Each connected section of briar in DROD can be assigned to one of two types:
- Briar Component, which requires a section to have at least one briar root
- Freefloating briar which is almost completely ignored by any and all processing

By "Connected section" I mean like if there is a path between two tiles through briar then they form one section - there are some tiny exceptions but that's the gist of it. If a briar tile stands next to any other brair tile they are the same section.

Looking at A. you can see there is one Briar Component, encircled in yellow, and a freefloating section. It's not part of any component but it will be crucial to understanding the problem.

Okay, we wait one turn and see B. What has happened so far? Our Briar Component got larger, but the freefloating section IS NOT part of the Component. Nothing complicated is happening right now, until we wait another turn and...

On C. the bomb explodes splitting our Briar Component in two. Are the two bits still connected? They shouldn't be, because as I said a moment ago the freefloating briar is not part of this Component. But they are actually still connected. Why? Here is where the complexity starts.
When a briar that is part of a Briar Component is destroyed, game takes note and when it's time for briar processing the components are recalculated. The way it works on the high-level is that it removes all of the stored information about briar components. Then it checks every briar root, and using a "flood fill" method gets a list of all briar tiles connected to the root. Let's call it NEW_BRIARS.
Then it looks at the old data, at the component this briar root was part of, takes a list of all the tiles and calls it OLD_BRIARS.
Finally, it creates a new component that is made out of tiles from NEW_BRIARS that also exist in OLD_BRIARS, basically an intersections of two sets if you're into math.

It might not be obvious yet but that's the problem. You see, the "flood fill" method I talked about, it's a function called "GetConnected8NeighborTiles" and it does just that. If it neighbors a tile orthogonally or diagonally, it's part of the list and it then looks for that tile's neighbors. Which means, when regenerating the component at step C, the code manages to reach the separated part on the East through the freefloating briar, even though that briar is not part of its group.

But normally it would kind of make sense - if the top briar was left alone it'd almost look as if the briars are connected. The problem is, when the next turn the freefloating briar is removed by anothere explosion, the component remains untouched. Because, as established earlier, recalculation only happens when the removed briar is part of a component.

I hope it's more or less understandable.

The fix consisted of modifying the call to "GetConnected8NeighborTiles" so that it only looked at the tiles that were part of the component in the past.
Essentially it changed from "Hey give me all neighbors and they neighbors" to "Hey give me all neighbors and they neighbors but skip the neighbors that are not on this fancy list".

I worry this might break some arcane behavior I was not aware of, let's hope not!


____________________________
My website | Facebook | Twitter
09-30-2020 at 09:14 PM
View Profile Send Private Message to User Send Email to User Visit Homepage Show all user's posts High Scores This architect's holds Quote Reply
skell
Level: Legendary Smitemaster
Avatar
Rank Points: 3500
Registered: 12-28-2004
IP: Logged
icon Re: Briar bug (+4)  
And the Pull Request

____________________________
My website | Facebook | Twitter
09-30-2020 at 09:17 PM
View Profile Send Private Message to User Send Email to User Visit Homepage Show all user's posts High Scores This architect's holds Quote Reply
Kalin
Level: Delver
Avatar
Rank Points: 64
Registered: 01-25-2016
IP: Logged
icon Re: Briar bug (0)  
skell wrote:
Okay, we wait one turn and see B. What has happened so far? Our Briar Component got larger, but the freefloating section IS NOT part of the Component. Nothing complicated is happening right now, until we wait another turn and...
Why didn't the freefloating section connect? Is it because the adjacent briar is all new growth?

If the explosions had been delayed, would the freefloating section connect the turn after B and again after C?
09-30-2020 at 11:52 PM
View Profile Send Private Message to User Show all user's posts Quote Reply
skell
Level: Legendary Smitemaster
Avatar
Rank Points: 3500
Registered: 12-28-2004
IP: Logged
icon Re: Briar bug (+1)  
> Why didn't the freefloating section connect? Is it because the adjacent briar is all new growth?

Because briar only connects with stuff it grows into, not things that are next to it after it finishes growing. It's a bit inconsistent though, because when there is freefloating briar next to an existing component and the component grows, it'll grow as if the freefloating briar was part of it (assuming it's withered briar, not live briar).

Let my try to pseudocodify what I see a little bit (might be worth to update the ruleset document too).

E 1. Take a list of all tiles that make the component, then for every tile (FROM_TILE) do the following.
E 2. For every direction, starting with orthogonal and then diagonal (DIR will be the direction we check and TO_TILE is the position into which we're trying to grow)...
E 3. If DIR is diagonal and there was already a pit in any previous DIR for this tile, skip processing this direction.
E 4. If TO_TILE is outside room edges, skip processing
E 5. Then there is a lot of logic for checking if briar can actually grow onto TO_TILE, the most interesting of which are...
E  5.1.    If TO_TILE is pit, store a flag used in #3
E  5.2.    If TO_TILE is fluff, then FROM_TILE will become live briar, meaning Fluff is treated like a pit
E  5.3.    If TO_TILE is briar...
E   5.3.1. Freefloating withered briar, then add this briar to NEW_DEAD_BRIAR
E   5.3.2. Freefloating live briar, then add this briar to NEW_LIVE_BRIAR
E   5.3.3. Part of a different component, then add this briar to MERGE_LATER
E  5.4.    If TO_TILE is powder keg, then store it in EXPLODED_POWDER_KEGS
E  5.5.    If TO_TILE is pressure plate, store it in HELD_PLATES
E  5.6.    If TO_TILE contains a Puff, store it in KILLED_PUFFS
E 6. Cleanup time!
E  6.1. Newly grown briar, NEW_DEAD_BRIAR and NEW_LIVE_BRIAR are added to the component
E  6.2. If NEW_DEAD_BRIAR is not empty, then go back to #2 but use NEW_DEAD_BRIAR as the list of briar tiles to use

E 7. Then, when the briar component has finally stopped growing:
E  7.1. For every puff in KILLED_PUFFS, damage the briar there and kill the puff

That marks the end of single briar expansion. From the code perspective there is some more cleanup that happens later, so let me show you the overview of the whole briar processing:

P 1. If briar that's part of a component was damaged this turn, rebuild the components.
P 2. Process the briars in a way that imitates things happening simultaneously for all the briars. Essentially repeat the following:
P   2.1. For each briar source (root) try to grow its component. If there are no more live briars to grow and there is space to grow, do nothing but return information "My component wants to grow".
P   2.2. If no briar source reported growth, leave this loop and go to P#3.
P   2.3. For every briar root, do the expansion logic I outlined above
P   2.4. Iterate over MERGE_LATER from E#5.4 and merge the components at this stage. 
P 3. For every EXPLODED_POWDER KEGS from E#5.4, do the explosion now
P 4. Convert unstable tar to tar babies
P 5. For every pressure plate that was held previously and was added to HELD_PLATES in E#5.5, either activate it if it was not held down or release it if it's no longer held down


I realize that's a lot to take in, so let me point out the interesting bits:
1. Kegs explode after ALL BRIARS have finished growing
2. Puffs damage briar only once a single growth of a component has finished
3. When briar grows onto a freefloating WITHER BRIAR, it'll act as if it was part of its component and grow out of it in the same cycle
4. Pressure plate interactions happen after ALL BRIARS have finished growing
5. Briar interacts with fluff identical to how it interacts with pit

Last but not least - there is a strange consequence to how P#2 works which is easy to miss. Each component can only expand once per iteration of P#2. That's because the "convert Briar Growth to Withered Briar" step is in P#2.1 and the actual expansion is in P#2.2.

Imagine a situation where you have a 1-tile-wide maze and 10 briar roots next to each other in one corner and 10 briar roots next to each other in the other corner. That gives us two components, let's call them A and B. When running the processing, that's how it would look:
1. A converts its briar growths to withered briar
2. B converts its briar growths to withered briar
3. A expands by one tile (creating a new briar growth which prevents it from growing again in this iteration)
4. B expands by one tile (creating a new briar growth which prevents it from growing again in this iteration)
5. Do the merging (assume it doesn't happen in our case)
6. Go back to 1

And I think that's it. Briar is pretty darn good at being intuitively understandable while playing the game, but the code that powers it has a lot of going on. Sorry for no images in this post, I'd love one day to make a video about how briar works internally just like the one I made for gentryii, minus the angry part.

____________________________
My website | Facebook | Twitter

[Last edited by skell at 10-01-2020 10:15 AM]
10-01-2020 at 08:22 AM
View Profile Send Private Message to User Send Email to User Visit Homepage Show all user's posts High Scores This architect's holds Quote Reply
mauvebutterfly
Level: Smitemaster
Rank Points: 542
Registered: 05-03-2015
IP: Logged
icon Re: Briar bug (0)  
skell wrote:
5. Briar interacts with fluff similar to how it interacts with pits, except orthogonally-adjacent fluff DOES NOT prevent diagonal growth from that tile

Are you sure about this? Fluff definitely prevents briar from growing diagonally. Maybe I'm not sure what you're trying to say here.

____________________________
106th Skywatcher
10-01-2020 at 09:40 AM
View Profile Send Private Message to User Show all user's posts High Scores This architect's holds Quote Reply
mauvebutterfly
Level: Smitemaster
Rank Points: 542
Registered: 05-03-2015
IP: Logged

File: Briar Growth and Connectivity.hold (953 bytes)
Downloaded 4 times.
License: Public Domain
icon Re: Briar bug (0)  
Also on the topic of briar, the fact that briar is sometimes connected and sometimes disconnected based on room history rather than current state of room might be something to discuss. Not sure if this is something that we want to (or can) change at this point since I'm sure some rooms would be broken by it.

Basically, the issue is that pit (or fluff) prevents briar from growing diagonally, but doesn't prevent it from being connected diagonally.

I've thrown together a room to demonstrate this. Both sections of the room look identical (close enough), but they continue differently. Also doubled this again to show that pit and fluff function identically here.

What you'll see is that after the door closes the briar in the left chambers still continues growing past the door, but briar in the right chambers does not.

____________________________
106th Skywatcher
10-01-2020 at 09:54 AM
View Profile Send Private Message to User Show all user's posts High Scores This architect's holds Quote Reply
skell
Level: Legendary Smitemaster
Avatar
Rank Points: 3500
Registered: 12-28-2004
IP: Logged
icon Re: Briar bug (+1)  
mauvebutterfly wrote:
Are you sure about this? Fluff definitely prevents briar from growing diagonally. Maybe I'm not sure what you're trying to say here.
You're right, fixed. Suits me for making such a writeup the first thing in the morning.

As for the example you posted, I am afraid modifying this behavior would break way too many demos and rooms. I think we could make it just the tiniest bit more reasonable by adding a way to highlight all of the tiles that a given briar root is connected to. Perhaps double clicking the root?

____________________________
My website | Facebook | Twitter

[Last edited by skell at 10-01-2020 10:19 AM]
10-01-2020 at 10:17 AM
View Profile Send Private Message to User Send Email to User Visit Homepage Show all user's posts High Scores This architect's holds Quote Reply
kieranmillar
Level: Smitemaster
Rank Points: 2272
Registered: 07-11-2014
IP: Logged
icon Re: Briar bug (+1)  
Can confirm in 5.1.1.alpha.2020-10-16 that skell's example hold no longer demonstrates the bug, the two patches of briar are considered unconnected after both bombs have exploded.
10-17-2020 at 03:25 PM
View Profile Send Private Message to User Show all user's posts High Scores This architect's holds Quote Reply
Kalin
Level: Delver
Avatar
Rank Points: 64
Registered: 01-25-2016
IP: Logged
icon Re: Briar bug (0)  
skell wrote:
E 5.3. If TO_TILE is briar...
E 5.3.1. Freefloating withered briar, then add this briar to NEW_DEAD_BRIAR
E 5.3.2. Freefloating live briar, then add this briar to NEW_LIVE_BRIAR
E 5.3.3. Part of a different component, then add this briar to MERGE_LATER
I'm trying to understand what is happening here and apply it to The Goblin: The Briar Patch 2S1E.

And I think something is still bugged in this step. Component A has 2 roots and 1 tile of new growth. Component B has 0 roots and lots and lots of new growth. It appears that the first root of A withers its new growth, then the second root expands it into B. Then for some reason B also expands even though it has new growth and all the roots were already processed.

Some diagrams:
Click here to view the secret text

It's looking like A expanding into B caused B to be added to NEW_DEAD_BRIAR instead of MERGE_LATER.

It occurs to me that I don't if "free-floating" means single tile briar patch or a patch without roots. If the latter is intended, you need to check all its tiles for new growth. (Though that still won't help this room much since the ashes will still be destroyed.)

How big a change would it be to diagonally connect briar during room initialization even if there are orthogonal pits? This room has large briar patches that never connect (the islands the Fegundo flies around), and this would at least give the player more time.

[Last edited by Kalin at 11-15-2020 06:35 PM]
11-15-2020 at 06:19 PM
View Profile Send Private Message to User Show all user's posts Quote Reply
Dragon Fogel
Level: Smitemaster
Rank Points: 1634
Registered: 06-21-2014
IP: Logged
icon Re: Briar bug (+1)  
Briar always withers one tile after expanding. Changing that would affect every room with briar.
11-15-2020 at 06:38 PM
View Profile Send Private Message to User Show all user's posts High Scores This architect's holds Quote Reply
Kalin
Level: Delver
Avatar
Rank Points: 64
Registered: 01-25-2016
IP: Logged

File: Briar testing.hold (794 bytes)
Downloaded 0 times.
License: Public Domain
icon Re: Briar bug (0)  
Dragon Fogel wrote:
Briar always withers one tile after expanding.
I did not know that. Thank you.

skell wrote:
Last but not least - there is a strange consequence to how P#2 works which is easy to miss. Each component can only expand once per iteration of P#2. That's because the "convert Briar Growth to Withered Briar" step is in P#2.1 and the actual expansion is in P#2.2.
This isn't true. (Unless I'm misunderstanding what you mean by "iteration".) Briar patches can expand once per root per turn. See attached hold.

I think this is because the "wither one tile after expanding" happens before the next root is processed.
11-15-2020 at 08:25 PM
View Profile Send Private Message to User Show all user's posts Quote Reply
skell
Level: Legendary Smitemaster
Avatar
Rank Points: 3500
Registered: 12-28-2004
IP: Logged
icon Re: Briar bug (0)  
Kalin wrote:
skell wrote:
Last but not least - there is a strange consequence to how P#2 works which is easy to miss. Each component can only expand once per iteration of P#2. That's because the "convert Briar Growth to Withered Briar" step is in P#2.1 and the actual expansion is in P#2.2.
This isn't true. (Unless I'm misunderstanding what you mean by "iteration".) Briar patches can expand once per root per turn. See attached hold.

You misunderstand but that's okay because it's not simple and I wrote the whole thing in the morning :).

Essentially a single iteration in P#2:
1. Goes through every briar root
2. Allows each briar component to grow once
3. If a briar root attempts to grow a component that already grew this iteration, it will make it do nothing until the next iteration
4. The iterations continue until either all roots have used up their "moves", or all roots are stuck and can't grow.

Or to put it differently:

Repeat this until all roots have moved or are stuck:
    For every briar root -> Do P#2.1 and P#2.2 on that root
    For every briar root -> Do P#2.3
    Do P#2.4


So it's a nested loop.

____________________________
My website | Facebook | Twitter
11-15-2020 at 09:02 PM
View Profile Send Private Message to User Send Email to User Visit Homepage Show all user's posts High Scores This architect's holds Quote Reply
Kalin
Level: Delver
Avatar
Rank Points: 64
Registered: 01-25-2016
IP: Logged

File: Briar testing.hold (859 bytes)
Downloaded 0 times.
License: Public Domain
icon Re: Briar bug (0)  
Kalin wrote:
And I think something is still bugged in this step. Component A has 2 roots and 1 tile of new growth. Component B has 0 roots and lots and lots of new growth. It appears that the first root of A withers its new growth, then the second root expands it into B. Then for some reason B also expands even though it has new growth and all the roots were already processed.
I looked into this some more (since no one else did), and what is happening is this:

If component A expands into component B, all the withered briar in B will also expand this turn, even if B still has new growth. New growth in B does not expand. See attached hold.

Edit: I'm guessing the problem is that when you build components, you first checked for roots, and if there weren't any you assumed there was no new growth. Note that left-clicking a component without roots will not highlight its new growth.

[Last edited by Kalin at 11-23-2020 05:37 PM]
11-23-2020 at 05:18 PM
View Profile Send Private Message to User Show all user's posts Quote Reply
Dragon Fogel
Level: Smitemaster
Rank Points: 1634
Registered: 06-21-2014
IP: Logged
icon Re: Briar bug (+3)  
This is known behavior, and has been used in puzzles.

But while this is weird, it makes sense - briar can't expand from new growth because it has to mature first.

What's actually happening is that withered briar in the new patch is expanding, destroying the briar growth, and replacing it with new briar growth.

To see this more clearly, try making a 2-by-2 patch with only red briar in it, and let a root grow into one of the corners. The rest of the growth will separate from the corner, and will not highlight if you click on the growing patch.
11-23-2020 at 06:04 PM
View Profile Send Private Message to User Show all user's posts High Scores This architect's holds Quote Reply
New Topic New Poll Post Reply
Caravel Forum : DROD Boards : Bugs : Briar bug (Briar has connection between detached patchs.)
Surf To:


Forum Rules:
Can I post a new topic? No
Can I reply? No
Can I read? Yes
HTML Enabled? No
UBBC Enabled? Yes
Words Filter Enable? No

Contact Us | CaravelGames.com

Powered by: tForum tForumHacks Edition b0.98.8
Originally created by Toan Huynh (Copyright © 2000)
Enhanced by the tForumHacks team and the Caravel team.