3 ms·

I just played Carcassonne last night and immediately thought of it when I started reading the piece. I am not sure how the game designers built the game to almo

by ryanar 9y ago

I just played Carcassonne last night and immediately thought of it when I started reading the piece. I am not sure how the game designers built the game to almost always ensure there was a valid configuration, in my play-throughs I think I have only hit that situation once.

stutonk 9y ago
After looking up a couple images -- that game appears to use Wang tiles. They're also sometimes used for terrain textures in video games to make seamless mosaics with less obvious repetition. https://en.wikipedia.org/wiki/Wang_tile https://en.wikipedia.org/wiki/Wang_tile
- tgb 9y ago
  While they could be drawn similarly to how Wang tiles are drawn, they definitely lack the aperiodicity property of Wang tiles. (Eg there are tiles with all four edges the same, hence you could tile the plain with nothing but that tile.) Of course the other distinction is that you only use each tile once in Carcassonne, unlike a set of Wang tiles.
  - fwip 9y ago
    It doesn't look like aperiodicity is a required property of Wang tiles. Just the cool ones. :)
    - tgb 9y ago
      I suppose you're right.
jon_richards 9y ago
With Carcassonne it's easy. You never have to go back in and solve the unsolvable areas of the puzzle. I've had players get really pissed when they realized my river placement meant they'd never be able to finish their city. There also aren't that many edge types, you can rotate your tiles, and there isn't a space limitation (you can just keep building outwards). I'm impressed by the procedural world in the link, but I am curious about the situations that lead to unsolvable maps in his second algorithm. As long as your tile spheres are large enough that all probabilities along the edge are non-zero (this may mean infinitely large), the only situation that creates an unsolvable map is when a tile's probability in a space goes to zero. In his algorithm, this can send the real probability of tiles in other spaces to 0 (without the calculated probability being set to 0). Given that there are polynomial number of probabilities across all spaces and all tiles, I wonder if there's some calculation you could do every time a probability goes to 0 that would update the other probabilities and prevent unsolvable situations. Edit: I should point out that I am not very convinced about the futility of this, given that he has demonstrated that tiling is a subset of CSP, not that CSP is a subset of tiling.
- HelloNurse 9y ago
  Constraints can be "easy" enough to prove that a solution can be found trivially without backtracking (e.g. large sets of Wang tiles with one or more tile choices for any possible combination of edge types), "hard" enough to emulate a Turing machine (possible with Wang tiles alone), or anything in between. Going beyond Wang tiles and corner tiles, constraints can be nonlocal, for example "the map contains 2 to 3 treasure room tiles" (which can be proved to form exactly 1 treasure room) or "river tiles belong to the same connected river component, accounting for flow direction, as a river tile on the edge of the map, or a river beginning tile, or a river end tile". So efficient CSP solution is an engineering problem: there is the very easy case (no backtracking), the hard case (let's search for a couple of hours with a state of the art constraint solving package) and the interesting generic case (general constraints, used with significant restraint for efficiency reasons; complex but hopefully quick computation; interactive assistance to signal unsolvable and close to unsolvable sets of constraints and their problem sites.

by ryanar 9y ago

stutonk 9y ago

After looking up a couple images -- that game appears to use Wang tiles. They're also sometimes used for terrain textures in video games to make seamless mosaics with less obvious repetition. https://en.wikipedia.org/wiki/Wang_tile https://en.wikipedia.org/wiki/Wang_tile

tgb 9y ago
While they could be drawn similarly to how Wang tiles are drawn, they definitely lack the aperiodicity property of Wang tiles. (Eg there are tiles with all four edges the same, hence you could tile the plain with nothing but that tile.) Of course the other distinction is that you only use each tile once in Carcassonne, unlike a set of Wang tiles.
- fwip 9y ago
  It doesn't look like aperiodicity is a required property of Wang tiles. Just the cool ones. :)
  - tgb 9y ago
    I suppose you're right.

jon_richards 9y ago

With Carcassonne it's easy. You never have to go back in and solve the unsolvable areas of the puzzle. I've had players get really pissed when they realized my river placement meant they'd never be able to finish their city. There also aren't that many edge types, you can rotate your tiles, and there isn't a space limitation (you can just keep building outwards). I'm impressed by the procedural world in the link, but I am curious about the situations that lead to unsolvable maps in his second algorithm. As long as your tile spheres are large enough that all probabilities along the edge are non-zero (this may mean infinitely large), the only situation that creates an unsolvable map is when a tile's probability in a space goes to zero. In his algorithm, this can send the real probability of tiles in other spaces to 0 (without the calculated probability being set to 0). Given that there are polynomial number of probabilities across all spaces and all tiles, I wonder if there's some calculation you could do every time a probability goes to 0 that would update the other probabilities and prevent unsolvable situations. Edit: I should point out that I am not very convinced about the futility of this, given that he has demonstrated that tiling is a subset of CSP, not that CSP is a subset of tiling.

HelloNurse 9y ago
Constraints can be "easy" enough to prove that a solution can be found trivially without backtracking (e.g. large sets of Wang tiles with one or more tile choices for any possible combination of edge types), "hard" enough to emulate a Turing machine (possible with Wang tiles alone), or anything in between. Going beyond Wang tiles and corner tiles, constraints can be nonlocal, for example "the map contains 2 to 3 treasure room tiles" (which can be proved to form exactly 1 treasure room) or "river tiles belong to the same connected river component, accounting for flow direction, as a river tile on the edge of the map, or a river beginning tile, or a river end tile". So efficient CSP solution is an engineering problem: there is the very easy case (no backtracking), the hard case (let's search for a couple of hours with a state of the art constraint solving package) and the interesting generic case (general constraints, used with significant restraint for efficiency reasons; complex but hopefully quick computation; interactive assistance to signal unsolvable and close to unsolvable sets of constraints and their problem sites.