hexapipes
hexapipes copied to clipboard
gereleth
toward P3
Hi @gereleth!
Since a couple months after you released hexapipes, I've been wondering what it would be like to play this game on Penrose tiles.
In particular, it looks like P3 with two different sizes of rhombuses would be a good match for this game.
Weird things about P3:
- Every tile has four neighbors, but it's not a grid.
- It is rotationally 5-fold symmetric around exactly one point, and is aperiodic - it doesn't wrap.
- The number of tiles that meet at a corner is between 3 - 7.
I am hoping that gameplay will also be weird but not broken. It should work, just different maze walls right?
I can only work on this on nights and weekends, so it may take me a while to build this. So I will share my progress in this ticket, rebase regularly, and publish the results from my fork at penrosepipes.vercel.app.
I will of course contribute back once something works, assuming it's still maintainable and makes sense to you. I think it will still be comprehensible. There may be something like a graph abstraction above the grid, the game using the graph instead of the grid.
I've published the first change, which is subtle but important. To handle P3 and other tiles that are not rotationally symmetric, we can imagine arms of different lengths and different angles going to points on the edge of the tile which are on a straight line to the center of the neighboring tile. [^1]
Now instead of rotating the <g> using transform:rotate(...), we can bitwise rotate the tile, obtain its directions, and return the corresponding deltas.
We restore animation by applying the CSS transition to the path instead of the transform.
.pipe path {
transition: d 100ms;
}
If you look closely, the animation is not as good, and we might consider adding keyframes so that the arms don't get as short during the animation. But I think it maintains the illusion well enough.
The transition only works on Chrome and Firefox; on WebKit Safari/iOS it degrades to no transition. I am sure there are workarounds for WebKit but I haven't looked into it yet.
grid.getDirections(...) already has an optional rotate parameter, but there is a wrinkle: we need the arms to always be listed in the same order for the animation to make sense. So we also rotate grid.DIRECTIONS by the same amount before filtering.
At the current commit (ac09e1c72ca) I haven't yet implemented arm identity for the square grid, and you can see the bug that arises if arm directions are not returned in "original" order.
Here's a screen recording. Believe it or not, the tile is rotating clockwise, but the animation is deceptive: .
I'll publish the fix for this next week!
[^1]: I hope to find time to draw a diagram showing what arms will look like on P3. It will be weird, because the arms will rotate (and stretch) but the tile will not, but I think it will work.
Hi, Gordon! I'm really excited to see this.
It should work, just different maze walls right?
Absolutely! There's Penrose slitherlink, why not pipes)).
Regarding the rotations of rhombus tiles I thought of implementing them with some skew transform of a square tile. I made a REPL as a proof of concept that rotation transitions can look nice in this case. Of course the real difficulty is in figuring out correct transforms for different rhombus types and orientations. But maybe this is still less work than transitioning paths.
I also must confess that I changed a lot about grid implementations while working on "octagons + squares" grid. Basically I abstracted away a RegularPolygonTile that handles computing rotations, drawing tiles and pipes, detecting edgemark gestures - all the stuff that's local to the tile. So the grid delegates this local stuff to its polygon tile(s) and stays responsible for "global" questions like:
- where is tile number
ilocated (index_to_xy) - what's the number of tile located at
x, ypoint (which_tile_at) - what's the neighbour of tile
iin directiond(find_neighbour)
Maybe there could be a SkewedPolygonTile that "unskews" the coordinates it receives and then reuses regular polygon logic for all the local matters.
I've long wanted to have this "cubes" tiling - implementing this might be a way to try out rhombic tiles without the additional Penrose complications. Grid logic here can reuse the HexaGrid and further subdivide each hexagon into three parts.
I had the related thought of doing some kind of periodic rhombus tiles next week to test the variable length arms and different angles.
To make it easier I might do the simpler one-orientation rhombus first, even though it’s just squashed and rotated squares.
I had not considered a skew transform—will check out your REPL, thanks! That might be cleaner than the path transitions.
I have not looked at the octagon branch yet, but I will try to rebase on it before proceeding. It’s likely you will merge that before I finish this, and it sounds like you may have implemented some of the same abstractions I’ve been thinking about.
The disadvantage of skewing a square tile in order to make a rhombus tile is that the pipes will bend at tile boundaries, if the tiles are oriented in different directions. The advantage is that the pipes still land in the center of the tile boundaries.
Hard to say which looks better / clearer without trying.
The new abstractions look very helpful!
I am taking your advice and starting with cubes. This is... not working yet... but I think it's really close.
https://user-images.githubusercontent.com/1366709/230744040-06016e5b-d989-4d35-900c-f3cb495c8701.mov
FWIW the tiles need to be scaled as well as skewed, because otherwise the diagonals will be longer than 1. Here's a fork of your REPL. I think you scale first then skew, because that way the skew angle is correct.
I tried to solve one but my clicks land too unpredictably 😂. Individual tiles are looking great though 👍.
Display and gameplay mostly work for the cubes grid (demo).
There are many bugs, among them:
- The generated puzzles are impossible. I haven't looked at the generation code very much, so I'm not sure if it needs to change or if the grid is improperly specified. Generation occasionally crashes the browser (endless loop).
- Clicking on the border between tiles can cause the wrong tile to rotate.
- There is an off-by-one bug in
find_neighborwhere the rows wrap. - Smudges at tile boundaries are more visible because of the skew. I think the easiest thing to do is to clip each tile, although that may clutter the SVG with
<defs>. - I haven't yet tried to get marks to work / looked into
SkewedPolygonTile. It seemed simpler to start by defining the extra transforms in the grid without changing the polygons. - The naive non-wrapped grid might be too easy because the border is so bumpy.
Hope to continue this tomorrow.
It's really coming together!
Generation is currently messed up because opposite directions in the grid are inconsistent. The directions are defined like in this image (tile index in black, direction numbers in blue). See how the opposite of direction 2 is sometimes 4 and sometimes 8.
You could rotate your squares like this instead. Here directions 1 and 2 look inside the hexagon, and 4 and 8 look outside. This way the opposites are consistent and the generator should make something solvable =).
Or you could use the hexagonal directions... But then each of the three squares would have its own set of directions so I don't know if this idea is any good)).
Either way I'm also thinking that maybe we shouldn't rely on grid.OPPOSITE constant and instead return opposite direction as part of find_neighbour output. This seems like a good thing to hide away inside the grid but will require some slight changes to solver, generator and game logic.
For wrong tiles rotating and wrap errors I thought that maybe literally doing this.hexagrid = new HexaGrid(...) could be helpful. Then for example you can use this.hexagrid.which_tile_at(x, y) to find the hexagon index and only need to look at the angle to tell which rhombus it is. Same with finding neighbours - get neighbour hexagon index first and then figure out where we are inside it. I really don't wish the pain of debugging hexagonal wrapping on anyone =).
Boundary smudges may be fixed by setting stroke-linejoin="bevel"on pipe insides in Tile.svelte. I originally set it to round to avoid these small artifacts seen between connected pipes. But maybe this can be solved some other way.
Re bumpy borders we could always crank up the avoidObvious setting).
Excellent hints and feedback, thanks!
I agree it would be much better to reuse HexaGrid rather than duplicating all this code. I have been expedient to get things working, but I am glad to revise to make this maintainable.
Great point about the wrong opposites, knew I was missing something there.
With the rotation and direction numbering & opposites all consistent, the cube grid is now working perfectly in non-wrap mode. (It's playable but difficult to complete in wrap mode, because of the off-by-one bug.)
I think it's harder than squares but easier than hexagons. The false perspective is disorienting! 😱
Quite a lot still to fix and clean up - realistically probably won't do a PR until next week.
Wow, I just love solving buggy puzzles. Edge issues on wraps make things more challenging)).
Could you add a cubes option to the custom puzzle page? For experimenting with generator settings. I think that this puzzle would definitely benefit from bigger avoidObvious values. Maybe you can use the same generation settings as the square puzzles for now? Defined here.
It looks like the P3 tiling rules have the same notion of "opposite sides". From the wikipedia page, with binary annotation:
Hmm, no matter how you number it, the two rhombs will have directions in different order, though. So yeah, maybe opposites should be hidden away.
stroke-linejoin: bevel looks terrible on iOS but it's fine everywhere else, including Safari.
My apologies, I probably won’t be able to clean up my code and contribute for a few weeks. I’m traveling to see my parents next week, and need to clean and pack and so on.
I’ll be sure to rebase and continue the improvements we discussed.
Very eager to get this in good shape and contribute, just ran out of time for now.
Cubes are now completely working, including wrap and edge marks, although connecting marks do not work reliably on touchscreens (walls do). I also need to apply the transform for Orient / Lock mode, which I just tried for the first time.
I got wrap working last week. I was on vacation, so I didn't mention it here. Reusing HexaGrid as you suggested removed 70 lines of duplicated code, and fixed wrap and other issues.
Since then I've played more than 100 of the 5 x 5 cube wrap puzzles (which has 75 tiles). I find it quite fun. I think the corners where 3 tiles come together make it slightly easier than square grid, so I'm usually able to prove and auto-lock almost till the end. Best time under 2 minutes but it often takes 10.
I think the non-wrap should use the hexagon playing field shape so there aren't exposed corners. It's too easy with those.
I'm using transformation-matrix to invert the tile transformation and detect edge marks in the original coordinate system of the polygon. Hope the extra dependency is okay.
Needless to say, the transformation matrix approach is very general and will apply nicely to P3 tiles.
So neat how the maze generation code works perfectly with no changes for this grid. The only thing that "puzzles" me is that occasionally it draws a fully connected X - does it run out of other ideas? I think this only happens on the non-wrap.
I'll squash my commits into one and submit a PR tomorrow.
Happy to refactor further. I wasn't sure about the responsibility of controls vs grid for doing transformation - putting the code in the controls seemed less repetitive than adding the transformation matrix stuff to every grid, but maybe there's a better way.
Also the "grid tile" containing three actual tiles, each transformed its own way, is maybe not a good abstraction, just expedient.
I played some 5x5 wraps, they're nice! Quite refreshing after the confusing evilness of etrat grid that I've been working on).
It's neat how this grid has two distinct types of corners (with 3 and 6 squares meeting). All the others I've encountered so far have a constant number of tiles meeting in a corner (3 for hexagons and octagons, 4 for squares, 5 for etrat). Places where 3 tiles meet allow for some solver shortcuts but I don't yet know how to apply them to only some places in the grid. And imagine if each rhombus were a 2x2 square grid, then we'd have 3, 4 or 6 tiles meeting in different corners :exploding_head:
Re connection marks I think it would be cool if they could bend at the tile border like the pipes do. I drew a rough example on the pinkish pipe here. But this might be tricky to implement. Like each of the two tiles should draw its own half using its own transforms? Or maybe let's end the mark at tile border at least. The part that's hanging off doesn't look good to me.
I think the non-wrap should use the hexagon playing field shape
There's a helper for that in hexagrid code, something like grid.useShape('hexagon'). It makes the corners empty to get a hexagonal field shape. I use that for dailies sometimes). You could iterate over empty hexagons and empty some rhombs in turn.
The only thing that "puzzles" me is that occasionally it draws a fully connected X
Fully connected tiles can happen during pregeneration if there is no other way to complete a puzzle. Imagine the red part here is already visited, and the upper left green corner is not. Both neighbouring red tiles are already T-shaped. And the only way to connect to the green corner is to turn one of them into an X. I don't want to introduce backtracking into pregeneration so I just allow this. A less bumpy field shape (like a hexagon) should make X tiles less likely to appear.
I haven't reviewed how the transformations work yet, I'll be able to do that once I finish with etrat branch. That grid is forcing me to learn about web workers because ensuring uniqueness takes too long to just leave it in the UI thread =).
Etrat is tricky! I look forward to hours of figuring out proof patterns there.
I agree that the connection edge marks sticking out are ugly. Wrapping around the edge would be great. I haven't figured out how to get both EdgeMark tiles to draw while only one should record.
As an experiment, I added a flag to get_edgemark_line to shorten the mark, but this affected the walls as well, making them short and displaced.
I've run out of time this week, so I'll leave it like that for now.
I also reverted changes to the controls and created gridutils.js - so the grid has exclusive responsibility of the transform. This is needed for whichEdge for Orient / Lock mode and makes sense IMO. However, Orient / Lock still doesn't work, so I'll have to dig into that next week.
I want to fix everything before submitting a PR, so it's another week if not two.
etrat-wrap is too difficult for me, and now I'm scared P3 is going to be too. 😭
Oh well, can't stop now...
Penrose tiles can't wrap by design so they can't be too bad. I expect something around square or cube difficulty.
I don't quite understand yet what makes etrat so bad. It must be the triangular tiles? With square tiles if you have a turn and know one connection then at least you can say that the opposite side is a wall. That's often handy. With triangular tiles a turn + one its connection gives... mostly nothing. It's kinda similar to low branching hexagonal wraps that are hard too.
One other thing is that etrat puzzles tend to have hundreds and thousands of solutions at even moderate sizes. So even when a puzzle has a unique solution it likely has an obscene number of "almost solutions" that look very very plausible until one last part just doesn't connect. And lookups till you find a contradiction tend to be very long.
Interesting that etrat has so many solutions!
Yes I get stuck on “almost” solutions, even with the 10x10 non-wrap. There will be one extra piece or two closed components. I have no idea how to fix it so I start over or give up.
I think you’re right that P3 should be like cubes only irregular, with 3-7 tiles meeting at a corner.
I tried out the cubes code today and I think the transforms logic is currently a bit wasteful. On every click we compose a transform matrix, then invert it too... That's running a lot of the same computations again and again because we only have three distinct cube faces and so three distinct transforms. It should be enough to compute them only once!
I think a better way to go about this would be to do
TOP_FACE = new TransformedPolygonTile(SQUARE, transform_top)
RIGHT_FACE = new TransformedPolygonTile(SQUARE, transform_right)
LEFT_FACE = new TransformedPolygonTile(SQUARE, transform_left)
polygonAt(index) {
return [RIGHT_FACE, TOP_FACE, LEFT_FACE][index%3]
}
The TransformedPolygonTile computes transformation matrix, its inverse, and the transform style string in its constructor. And then it does pretty much the same stuff as regular polygon tiles taking care of its own coordinate conversions where necessary.
Then the cubegrid logic can look pretty much the same as other grids with this.polygonAt(index).doStuff...and forget that its polygons are weird =).
I would also remove the translate part of the transform and just give each rhombus its own center coordinates instead. This just seems easier to reason about. Not that it's easy! I tried to implement something along these lines but got bogged down trying to understand transform computations.
Can you think of any problems with this approach? I don't really know how many distinct transforms a P3 grid would have. Is there a sane number of them or infinite variety? =)
I agree the transform should only be computed once per tile “type”, and I like this TransformedPolygonTile idea. (I think you mentioned it before but I didn’t understand until now.)
Also transforms should not be computed or used for the grids that do not use this feature. I think I can revert those changes and only keep a few small changes to the grid interface.
As for removing the translate… Maybe? I have often wondered whether it is a good idea to have three tiles per grid position. It was the easiest way to reuse HexaGrid but it’s pretty messy.
For P3, I think each tile will need its own transform. There are only two shapes, so the skew and scale will be the same for many tiles, but I doubt it’s worth it to count all the possible rotations of those two shapes. (I’ll check though.)
Each tile’s transform and inverse could be computed once. These are 4x4 matrices so it’s not a lot of memory.
Based on my coloring experiment there are 5 ~~kite~~ thick types and 5 ~~dart~~ thin types in P3, so 10 distinct transforms in total.
Rhomb offsets should be easy to do, I'd precompute OFFSETS = [{dx, dy}, ...] for three rhomb types - deltas from hexagon center to rhomb center. And then in which_tile_at and getVisibleTiles add an offset to hexagon center based on rhomb index. I think it makes sense to keep the grid responsible for tile position and the polygon responsible for tile shape.
Next step for me is to implement the P3 tiling itself. I think I’ll use the substitution / drill-down method detailed here:
https://www.chiark.greenend.org.uk/~sgtatham/quasiblog/aperiodic-tilings/
I’m more familiar with D3 for SVG, so I’ll probably implement the geometric algorithm standalone, and come back to the tiles in a couple weeks when I have a generator for coordinate and rotation data.
I have a demo of producing an approximate number of P3 tiles which intersect a polygon.
That Tatham paper says how to keep track of adjacency, and I've implemented coordinates for the Robinson triangles. (You can see them by adding ?coord - not sure if these are correct yet.) Tatham describes a simple recursive algorithm to find neighbors using the coordinates, and that will give us coalescing of the triangles into rhombuses and tile adjacency.
At that point the only challenge to Penrose pipes is the neighbours and opposites problem we talked about before. Your solution of the grid returning the opposite when returning a neighbour sounded good and I may give that a try in a couple of weeks.
I shouldn't jinx myself by talking as if I know what all the problems are. "Patching" the border will also be tricky.
Take this example:
We will prune any half-tiles when we coalesce triangles into rhombuses, but here that will cause such a jagged upper-left corner once the half-blue is removed that we should either drop the red or add in the other half-blue. Same in the upper-right corner.
Implemented Tatham’s neighboring triangles in the demo above. Only a few more steps before I can integrate p3 tiles into hexapipes.
It now finds the rhombuses and their neighbors, and it repeatedly culls any tiles which only have one neighbor. The ending shape can be quite different from the original polygon.
It might be nicer to fill gaps around the border, but I haven't gotten that working, so it's hidden. I think the cull strategy works well enough to try this in hexapipes, maybe next week.
The pattern of which tiles are neighbors is quite interesting, can't wait to try this out!