7 ms·

Very cool! Looking forward to playing it. I suggest to minimize visual clutter, because any new player's brain will be overloaded trying to figure out a board,

by paipa 2y ago

Very cool! Looking forward to playing it. I suggest to minimize visual clutter, because any new player's brain will be overloaded trying to figure out a board, and less is sometimes more. I'd remove the forward direction triangles where they can be unambiguously inferred from the baseline. A lower grain contrast wood texture might be a good idea too. You mentioned you sometimes use five tile colours but you can probably improve it: yes, the four colour theorem guarantees that :)

frading 2y ago
Yes, minimizing clutter was a priority, and still is. I've tried to avoid those arrows for a long time, but the pawn movements wasn't clear enough without them. And I agree it's not the optimal display. Displaying them on some tiles only is something I have not thought of. My first reaction is that it may feel harder to read, as tiles with an arrow may look like they would act differently than those without? We may induce the idea that it has a different purpose. So for now, I'd prefer a solution that would look the same on all tiles, I think that's much easier to parse. But then I should probably give this a try before rejecting it. You do have a good point regarding the wood texture, I've tried other textures, but couldn't find a better one yet. But I'm sure that's possible. Nevertheless for now, you can also display different skins: https://imgur.com/a/zitKlpz https://imgur.com/a/zitKlpz And thanks a lot for mentioning the four colour theorem. I'm looking at its wikipedia page now. I'm sure I came across it many times before, but I did not think about it when tackling this part of the problem. My implementation is here is anyone can spot my mistake: https://github.com/polygonjs/polygonjs/blob/master/src/engine/nodes/sop/QuadUniqueNeighbourId.ts https://github.com/polygonjs/polygonjs/blob/master/src/engin...
- wizzwizz4 2y ago
  The five-colour theorem was first proven in the late 19th century. The known proof of the four-colour theorem is non-surveyable. There's probably no small mistake in your implementation, and the solution you should go with is unlikely to be a fully-general algorithm. (I'd suggest starting from the border on the outside, greedily filling in as many choices as are forced (up to isomorphism), then randomly choosing a candidate breadth-first or depth-first until you've found a four-colour solution.)
  - frading 2y ago
    actually, I realise now that the implementation I shared in my previous comment is a generic one. At some point, I decided to make a variation of it, specialised for this board. The reason wasn't the number of colors, though, it was to have better control of the colors of the bottom and top rows. And I also realise that, contrary to what I said above, I do not set the colors on the left and right sides. So that will be an easy modification. After that, I do go breadth first. But I do so by looking at all neighbours of the current tile, simply by taking them in the order given by my internal graph. Instead I should just take those that are connected to another tile that has been already visited. So thank you for those advice, that's super helpful, I really appreciate. I had to look up "non-surveyable" as well, I'm learning a lot here. That said, I'm having a hard time understanding "as are forced (up to isomorphism)", is that something you could clarify?
    - wizzwizz4 2y ago
      Let's say your colours are black, white, green and purple. So far, you've managed to use only black and white, but you've reached a node with both black and white neighbours. You need (are forced) to choose a different colour! You could choose green, or purple – and whatever solutions you reach from that point, you could swap all the greens and all the purples to yield another solution. However, the next "free" choice you make could be the same colour as you chose last time, or a different one, so it is actually free (so isn't forced). Since the "swap green and purple" operation is bijective (a one-to-one, reversible mapping), and preserves all the properties we care about, we can call it an isomorphism. If there's an isomorphism between two solutions, we say that those solutions are isomorphic. Swapping all the greens and purples of any isolated region of the graph (i.e., one surrounded by a strip of black and white) is an isomorphism, if the only property we care about is "is this a colouring of the original graph?". I was saying it's pointless to search isomorphic solutions if you can help it. If you have isolated regions of the graph yet to be filled, you can halve the time it takes to explore each region's possible colourings. However, if you consider isolated regions completely separately, you can solve them one after the other (and backtrack once you know any region's been made impossible by the choices of colours in its border), for a much larger speedup. The whole thing about isomorphisms was a red herring, an artefact of my thought process rather than an actual insight. I doubt trying to exploit this will net you anything more than a 2× improvement, and that's only if you do it cleverly.

by paipa 2y ago

frading 2y ago

Yes, minimizing clutter was a priority, and still is. I've tried to avoid those arrows for a long time, but the pawn movements wasn't clear enough without them. And I agree it's not the optimal display. Displaying them on some tiles only is something I have not thought of. My first reaction is that it may feel harder to read, as tiles with an arrow may look like they would act differently than those without? We may induce the idea that it has a different purpose. So for now, I'd prefer a solution that would look the same on all tiles, I think that's much easier to parse. But then I should probably give this a try before rejecting it. You do have a good point regarding the wood texture, I've tried other textures, but couldn't find a better one yet. But I'm sure that's possible. Nevertheless for now, you can also display different skins: https://imgur.com/a/zitKlpz https://imgur.com/a/zitKlpz And thanks a lot for mentioning the four colour theorem. I'm looking at its wikipedia page now. I'm sure I came across it many times before, but I did not think about it when tackling this part of the problem. My implementation is here is anyone can spot my mistake: https://github.com/polygonjs/polygonjs/blob/master/src/engine/nodes/sop/QuadUniqueNeighbourId.ts https://github.com/polygonjs/polygonjs/blob/master/src/engin...

wizzwizz4 2y ago
The five-colour theorem was first proven in the late 19th century. The known proof of the four-colour theorem is non-surveyable. There's probably no small mistake in your implementation, and the solution you should go with is unlikely to be a fully-general algorithm. (I'd suggest starting from the border on the outside, greedily filling in as many choices as are forced (up to isomorphism), then randomly choosing a candidate breadth-first or depth-first until you've found a four-colour solution.)
- frading 2y ago
  actually, I realise now that the implementation I shared in my previous comment is a generic one. At some point, I decided to make a variation of it, specialised for this board. The reason wasn't the number of colors, though, it was to have better control of the colors of the bottom and top rows. And I also realise that, contrary to what I said above, I do not set the colors on the left and right sides. So that will be an easy modification. After that, I do go breadth first. But I do so by looking at all neighbours of the current tile, simply by taking them in the order given by my internal graph. Instead I should just take those that are connected to another tile that has been already visited. So thank you for those advice, that's super helpful, I really appreciate. I had to look up "non-surveyable" as well, I'm learning a lot here. That said, I'm having a hard time understanding "as are forced (up to isomorphism)", is that something you could clarify?
  - wizzwizz4 2y ago
    Let's say your colours are black, white, green and purple. So far, you've managed to use only black and white, but you've reached a node with both black and white neighbours. You need (are forced) to choose a different colour! You could choose green, or purple – and whatever solutions you reach from that point, you could swap all the greens and all the purples to yield another solution. However, the next "free" choice you make could be the same colour as you chose last time, or a different one, so it is actually free (so isn't forced). Since the "swap green and purple" operation is bijective (a one-to-one, reversible mapping), and preserves all the properties we care about, we can call it an isomorphism. If there's an isomorphism between two solutions, we say that those solutions are isomorphic. Swapping all the greens and purples of any isolated region of the graph (i.e., one surrounded by a strip of black and white) is an isomorphism, if the only property we care about is "is this a colouring of the original graph?". I was saying it's pointless to search isomorphic solutions if you can help it. If you have isolated regions of the graph yet to be filled, you can halve the time it takes to explore each region's possible colourings. However, if you consider isolated regions completely separately, you can solve them one after the other (and backtrack once you know any region's been made impossible by the choices of colours in its border), for a much larger speedup. The whole thing about isomorphisms was a red herring, an artefact of my thought process rather than an actual insight. I doubt trying to exploit this will net you anything more than a 2× improvement, and that's only if you do it cleverly.