Announcement: Be excellent to each other.


Caravel Forum : Caravel Boards : General : A new theory on gel cutability (you too can eyeball it with no problem)
New Topic New Poll Post Reply
Poster Message
uncopy2002
Level: Smiter
Rank Points: 431
Registered: 07-28-2014
IP: Logged
icon A new theory on gel cutability (+25)  
I was solving that room in Abyssian Fortress this morning when a line of insight popped out of nowhere. I immediately picked it up and worked on it thoroughly, which by then I figured out it's actually a fully workable theory on dealing with gels.

(The pics in this thread are badly drawn. If anyone knows of good tools to draw these like the ones on the tarstuff page, feel free to suggest.)



As we know, tar cutability is simple: it's a tiling of 2x1 tiles for the enclosed corners. Mud is even simpler. Gel, however, is so viscous it resisted various angle of attack for years.
As a reminder, gel can only be cut on inside corners.

Before we begin, perhaps we can look at the situation in a different perspective: Tar cutability is easy to analyse because cutting tar is essentially a clean cut inside our analysis scheme: for each cut, we're taking away exactly one piece of 1x2 enclosed corners, and doesn't change anything else. This implies that the analysis doesn't depend on the order of evaluation.
It is important because if not so, things may happen differently just because one part is evaluated before another, and everyone knows that it's down the path of "so horrible I won't touch at all". An example would be horde movement order tracking, such as mass wraithwing manipulation.

In this sense, L-tromino tiling and enclosed corner analysis are both bad:
L-tromino tiling, even if it can be made to work, would be bad because the two side tiles of the L piece only get taken away some of the time, depending on the surrounding tile connectivity.
Enclosed corner analysis is bad for a different reason: the amount of cuttable enclosed corner formations could increase instead, so it fluctuates between being helpful and being unhelpful. We don't want to get more gel when we cut gel.




The new theory of gel cutability goes as follows:


Instead of using the old tar way (tiling and enclosed corners), we'll consider the tiles themselves instead, which we'll call them nodes:
Click here to view the secret text

I've marked the bright and dark tiles in red and green dots. They are in different colors because they are nodes of different parity.

Next, we'll connect two diagonally adjacent tile together, if this diagonal has both dots of opposite color present on the sides (Or, in other words, cross out all 2x2 blocks). This forms a network of diagonals. We'll call the connected lines links:
Click here to view the secret text

From this, we can immediately see that a tile is cutable if and only if that tile is at the center of an exposed straight line segments of the length of 3 nodes. It can be of T shape or I shape. The primitive gel formation for such T shape and I shape are the 8-tile and 7-tile gel, respectively, shown in the bottom right corner.

Cutting gel in this setup equates to this algorithm:

1. A node with the above-mentioned property (connected with adjacent nodes by T or I shape) is cut and destroyed.
2. Links connected with this node is destroyed.
3. All links of the opposite color, which cross over any links that was destroyed in step 2, is also destroyed.
And then we repeat the progress with the new, modified network, until nothing can be cut.

This is an improvement on the enclosed corner analysis: We've found a pair of quantities which is guarantee to decrease with each cut. This is also an improvement over the L-tromino tiling, because in this case it's exact: every step cuts specific nodes, and nothing else; it's similar to how tar are cut by taking away exactly 2 adjacent enclosed corners at a time.

Note that singled red/green nodes will be formed in the progress. We don't destroy them because they become gel babies. Singled nodes cannot have any stable form (for a 2x2 formation you need 2 red/green nodes which is connected). Incidentally, this provides a way to calculate the amount of gel babies produced by any particular sequences of cuts.


What about the deadly gel formation? We know that some gels are cutable, but Beethro can't cut the gel himself because it'll end up in a lethal situation. This analysis also gives the exact condition of such lethal cuts:

Click here to view the secret text

Basically, two gel babies form next to Beethro's sword if and only if these two corner (say, green) nodes are singled as a result of the central node of opposite color (red) being destroyed. In order to make this lethal, Beethro must have no space to retreat, which means there are another two corner (green) nodes blocking your way. This corresponds to one I-shaped empty node formation of the same color. The following example gives a clear view at the sufficient and necessary condition:

Click here to view the secret text





Onto gel cutability. Gel cutability problem with a single color only is simple, as the problem reduces to a graph traversing problem for that color.
Since cutting gel requires each step landing on a node with two existing nodes perpendicular to your direction of travel, this means all sections of a path cannot be directly adjacent from any other path segment of the same color, as that closes the path. It can't also be a piece adjacent to empty space. A rule of thumb is you need to stay at least 4 tiles (2 diagonals) away from any path you've drawn of the same color to continue your gel-cutting path.
Additionally, you can't begin from a node which is at the middle of a I-shaped empty node.

After all red links are destroyed, green links are destroyed as well, and so the gel is gone.
When the links are all destroyed, all remaining uncut nodes will become singled.

Example:

Click here to view the secret text


This also explains why a corner with different parity cannot be revealed:
Click here to view the secret text



Gel cutability problem with both colors involved only becomes slightly more complicated, because by our construction any two paths of different color cannot touch each other. They must stay at least 3 tiles away from all other paths of opposite color. (If the paths cuts all gel, they form 2 diagonal lines of gel babies.)
For a gel to be cuttable, the paths of opposite color must always stay 3 tiles away from each other. Otherwise there is a gap of 2x2 blob.
(By the way, once an entrance is selected, everything along the path opposite to the color of this entrance is suppressed, so you can safely ignore them as you extend this path.)

Click here to view the secret text

If you are evil enough, you can use this information to make a gel formation with 2 colored paths spiraling each other while only barely able to stay 3 tiles away from them. I can already see this coming.
EDIT: Now it's done:
Click here to view the secret text



Note that gel cut solutions are not unique!
In fact, in general, a larger gel blob gives you more possibility in walking the paths along the nodes.
The following is a recreation of an example from the threads linked above:
Click here to view the secret text


Also, note that because of the lethal cut condition, gel cutting paths cannot branch from a straight path. If you want to make a 3-way or 4-way branch, make the 90 degrees turn first.



Mimics breaks tar invariant when two swords stabs two adjacent tar, reducing the number of enclosed corners by 3 instead of 2 or 4.
Similarly, with mimic's help, some unbreakable gel formations are breakable. This is done via forcing the creation of two paths of opposite color to be exactly 1 tile from each other:

Click here to view the secret text





So, now you've mastered the theory of gel-cutting! Feel free to brag at your fellow delvers the ability of eyeball gel cutability just as easy as tar and mud.




(I might consider making a little gel cutability quiz level soon. Stay tuned in this thread.)

[Last edited by uncopy2002 at 02-05-2016 12:49 PM]
02-04-2016 at 07:49 PM
View Profile Send Private Message to User Show all user's posts Quote Reply
skell
Level: Legendary Smitemaster
Avatar
Rank Points: 3734
Registered: 12-28-2004
IP: Logged
icon Re: A new theory on gel cutability (0)  
I did not understand a single word from this but it is amazing. Can any certified smart2skell translator do something about me failing to grasp this?

____________________________
My website | Facebook | Twitter
02-04-2016 at 09:19 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
tempestadept
Level: Master Delver
Rank Points: 141
Registered: 12-23-2010
IP: Logged
icon Re: A new theory on gel cutability (0)  
And how exactly does this theory help with cutting-order-dependent situations?
02-04-2016 at 09:33 PM
View Profile Send Private Message to User Show all user's posts Quote Reply
uncopy2002
Level: Smiter
Rank Points: 431
Registered: 07-28-2014
IP: Logged
icon Re: A new theory on gel cutability (+1)  
tempestadept wrote:
And how exactly does this theory help with cutting-order-dependent situations?
Cutting order is now embedded into the nature of choosing the non-touching paths: All paths of the opposite color must be at least 3 tiles away from each other. Cutting order, in this context, is equivalent to the order you "evolve" the path chains to their desired formation, which you can always do in any order you want as each path is independent to each other.
Paths within another path are just branches to that particular path, so they really belong to a single path.

This all comes from the observation that after you cut a gel piece, the new cuttable gel pieces produced are always diagonally adjacent to it; moreover, a cut will only destroy existing inside corners of the opposite color if that inside corner is adjacent to the one you've just cut.

skell wrote:
I did not understand a single word from this but it is amazing. Can any certified smart2skell translator do something about me failing to grasp this?
I'd be glad too if someone helps me on clarifying this post. It's written in a haste, and I know my writing skill isn't that good either.

[Last edited by uncopy2002 at 02-05-2016 01:18 AM]
02-05-2016 at 01:11 AM
View Profile Send Private Message to User Show all user's posts Quote Reply
Kallor
Level: Master Delver
Rank Points: 277
Registered: 04-02-2007
IP: Logged
icon Re: A new theory on gel cutability (0)  
This was like super interesting. Did not understand though, and must sleep. Anyway, thanks.

____________________________
Kallor
02-14-2016 at 10:14 PM
View Profile Send Private Message to User Show all user's posts This architect's holds Quote Reply
Pearls
Level: Smitemaster
Avatar
Rank Points: 767
Registered: 12-21-2009
IP: Logged
icon Re: A new theory on gel cutability (+2)  
Anything interesting enough to rouse Kallor from his eldritch slumber is worthy of note.

____________________________
Hey, w-wait, that's the guy who shamelessly promotes his own...

Click here to view the secret text


[Last edited by Pearls at 02-17-2016 07:10 AM]
02-17-2016 at 06:58 AM
View Profile Send Private Message to User Show all user's posts High Scores This architect's holds Quote Reply
Jutt
Level: Smitemaster
Rank Points: 863
Registered: 06-29-2007
IP: Logged
icon Re: A new theory on gel cutability (+20)  
Based on the work of uncopy2002, I've tried to find a way to construct cutting patterns for gel blobs. I think I've found a set of necessary and sufficient conditions for a configuration of squares to cut to remove a gel blob. I'll use simple diagrams like the one below to mark the cutting squares in a gel blob
-OOO-  X = marked gel square
OXOXO  O = unmarked gel square
OOXOO  - = empty square
OXOXO
-OOO-
The conditions for marking a pattern are as follows:
C1 (Complete removal) – Each 2x2 area of gel must contain at least one marked square.

C2 (Access) – Each component of diagonally adjacent marked gel squares must contain at least one cuttable gel square, i.e. a gel square that is diagonally adjacent to an empty square.

C3 (Adjacency 1) – The four horizontal/vertical neighbours of a marked gel square must all be unmarked gel squares.

C4 (Adjacency 2) – An unmarked gel square must have at least one horizontal/vertical neighbour that is also an unmarked gel square.

C5 (Zigzag rule) – The following configurations (including rotations/reflections) of empty squares and marked gel squares may not occur:
- -
 X

- X
 X -

…

- X X X -
 X X X X

etc…
That is to say, any zigzag pattern of diagonally adjacent marked gel squares with empty squares at the ends.
We will now prove that these conditions are necessary and sufficient. For this we will use the following to properties of cuttable gel squares:
Property 1: A cuttable gel square is always horizontally and vertically surrounded by four other gel squares

Property 2: For a cuttable gel square, either the NE and SW neighbours, or the NW and SE neighbours are both covered with gel.
Proof that conditions are necessary:
Suppose a cutting pattern allows a gel blob to be completely removed, then we will show C1-C5 must hold.
C1: This follows from the requirement that to remove a blob, all squares must become cut or unstable, so there can be no 2x2 regions of gel where none of the 4 squares are cut.
C2: This follows from the fact that an uncuttable gel square may only become cuttable if a diagonally adjacent gel square is cut. If none of the marked gel squares in a diagonally connected component are cuttable, it is impossible remove the blob entirely.
C3: A marked gel square cannot be h/v adjacent to an empty square, because it will never be able to satisfy property 1 of cuttable gel squares, hence will never become cuttable. Two marked gel squares can never be h/v adjacent, since cutting one of them results in the other becoming adjacent to an empty square, hence unremovable. We conclude the h/v neighbours of a marked gel square must be unmarked gel squares.
C4: Suppose an unmarked gel square has no h/v neighbour that is also an unmarked gel square. Then the four h/v neighbours are all marked gel squares or empty squares, and not all empty because of gel stability reasons. But of these four, the last marked gel square to be removed will have two diagonally adjacent empty squares that always violate property 2 of cuttable gel squares. That means the last one could never become cuttable, which contradicts the fact that it was marked as a cutting square.
C5: Similarly the last marked gel square in a zigzag pattern to be removed will have two empty diagonal neighbours that violate property 2 in the same way. Therefore it would never be removable, so the zigzag patterns cannot occur. □

Proof that conditions are sufficient:
Suppose we have a pattern of marked gel squares that satisfies C1-C5. First we show that we can select a cuttable marked square, such that after cutting there, the reduced blob with remaining marked squares still satiesfies C5.

Choose any diagonally connected component of marked gel squares. By C2 it contains a cuttable marked square S. If cutting at S maintains C5, we have found a square that suffices. Suppose however that C5 does not hold after the cut at S. In this case there exists a zigzag pattern, and S must be the empty square at one end of the zigzag. But then the empty square at the other end of the zigzag gives access to another cuttable marked gel square T in the original blob:
- X X  …   X
 T X      X S
Now cut the original blob at T instead. Then this cut cannot create a zigzag pattern in the resulting blob: T must be an initial empty square of the zigzag, and placing the zigzag in any way starting at T in the above diagram always creates one of two possible configurations:
– A zigzag pattern, which violates C5
– An unmarked gel square surrounded by four marked gel squares/empty squares, which violates C4.
– (There is one exception, which will be covered below [*])
We conclude that T is in this case a square that suffices.

Next we show that after cutting at this square, the resulting blob + marked squares also satisfy C1-C4.
C1: This follows immediately from the fact that we only remove gel squares.
C2: The connected component we cut a marked gel square from will become smaller, and may fall apart into multiple components. All components still can be cut at squares adjacent to the gel square that was removed.
C3: The square we cut is surrounded by four unmarked gel squares, and has one empty square as diagonal neighbour:
 O    ?O
OXO  ?OXO
 O-   ?O-
       ?
If by cutting a square we destabilize an unmarked gel square that is the neighbour of another marked gel square, this marked gel square must be positioned on one of the question marks (symmetrical cases omitted). We will show however that this cut never destabilizes its neighbours, i.e. C3 remains true. We consider all four cases:
 O2
OXO
1OXO
  O-
Both 1 and 2 cannot be an empty square, because the cut would create a zigzag pattern, which it does not by assumption. This ensures that the unmarked gel squares will not destabilize.
 O1O
OXOXO
 O2O-
Either 1 or 2 must be a gel square, because the unmarked gel square between them is stable before the cut. Thus the unmarked square will not destabilize after the cut.
  O
1OXO
OXO-
 O2
Both 1 and 2 cannot be an empty square, because otherwise the original blob would contain a zigzag pattern, or an unmarked gel square without unmarked gel neighbours. This ensures that the unmarked gel squares will not destabilize.
  O
 OXO
 1O-
 OXO
  O
1 is a gel square, because the unmarked square east of it is stable before the cut. Thus the unmarked square will not destabilize after the cut.
C4: Suppose the reduced blob has an unmarked gel square that has no h/v neighbouring unmarked gel square. Then its surrounding squares must be either of the two following configurations:
 X    X
-OX  XOX
 -    -
Because C3 holds for the reduced blob, we can infer some additional squares to be unmarked gel squares:
OXO  OXO
-OX  XOX
 -O  O-O
In the original blob, one of the adjacent empty squares must have been an unmarked gel square. This means it must have become unstable after the cut and have disappeared. But in either configuration, it would have been part of a 2x2 segment of gel after the cut. Hence the gel square could not have destabilised, which is a contradiction. We conclude that C4 is satisfied.

Conclusion: we have shown it is possible to reduce the number of marked gel squares by cutting one while maintaining C1-C5. With induction it follows that we can thus remove all marked gel squares. Since every non-empty blob that satisfies C1 has at least one marked gel square, the entire blob is removable. □


[* Exception]
Click here to view the secret text

This is all I got for now. Hopefully the proof is correct. I have skipped over some minor details, but I think the idea is sound and the result gives some new insight in the gel removal problem. The downside is that there are five criteria to meet when creating a cutting pattern. They are however fairly intuitive, and not too hard to check. Perhaps someone can think of a better set of conditions? Or a way to convert them to an algorithm for finding solutions? Comments are welcome!

____________________________
Holds: An Architects Audition, Artful Architecture, Salamander, Elusive Exhibitions, Leftover Levels, Six Times Six
Collaborative: Way Forward, Advanced Concepts 2
Styles/Mods: Basalt, Sandstone, Garden, Clock using game elements
02-18-2016 at 05:23 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
New Topic New Poll Post Reply
Caravel Forum : Caravel Boards : General : A new theory on gel cutability (you too can eyeball it with no problem)
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.