![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
2 week project
kind of been unsteady on these for a while. the last one (may 15 to may 31) was kind of a haphazard mess. i implemented some more operations for my polyhedra data model format, which notably included "loft", which turns out to be very close to a general-purpose extrude. i used that to make some simple "tree" shapes:
* trees 1
* trees 2
* trees 3
but ultimately i got kind of frustrated with the super simplistic shapes and kinda stopped working on that. (ideally i'd get some more structured face splitting code working so that i could e.g., split trunks and branches at arbitrary angles, so that i could hook it up to some kinda l-system and generate continuous models)
so that was late may. early june i decided to focus on something else and i worked on wang tiles. the end result of that is this page (which apparently doesn't work in chrome but look i've tested it in firefox and midori so like, w/e sorry you use a bad browser) which consists of two parts: one is a totally unconstrained tiling that just does some grid math to make a perfect tiling, and the other is a 'nested' tileset that uses a backtracking solver that i wrote and is moderately decent at figuring out how to lay out some tiles. i was intending to get to manual specification of tiles, since that could use the same solver; it's just UI to handle it, but uhhh html/javascript ui is kind of a mess to write and i'm not good at it, so, oh well i'm not gonna get around to that right now.
the main thing that i learned from this is that a naive backtracking solver is just, total garbage. my first attempt at a solver was really simple: for each tile, pick a random tile from the tileset, but constrained so that its edge match with any adjacent tiles that have already been placed. if there aren't any tiles that match, reject the last tile placed and pick a new one. that algorithm worked sometimes, but it got stuck very easily and frequently got into situations where it would have to exhaust its way through dozens of tiles (which would take thousands of backtracking steps) to get to the problem tile. i considered a few options, and inspired by the WFC constraint algorithm i decided to try precaching options: when a tile was chosen, it would check it against all its adjacent unfixed tiles; if that tile lead to a situation where no tile was possible, it would get rejected, and all those partially-constrained tilesets were cached for later when those tiles would get resolved. this made it much more likely to find a solution, though there were still a bunch of cases where it'd get stuck and fail. if i was gonna keep messing with it, i think the next thing i'd try would be having it unplace the adjacent tile with the most options available, or something like that, instead of it unplace the last tile (since frequently that's not a tile that's actually adjacent to the problem). i don't really know if that would meaningfully change anything, but, doing that is how we find out.
(wang tiles can be used for map generation, as in this video, but i'm more familiar with using them as a tileset placing thing. if e.g., you have a bunch of 16x16 pixel squares that are, like, cave walls, and some have vines running down and some have waterfalls running down and there are various different kinds of rock shapes, it's possible to assign them wang colorings (e.g., green edge if a vine runs off, blue edge if water runs off, grey edge otherwise) and then use a tile placement solver to generate a random placement of the tiles in a way that maintains coherency. you see this a lot in like, children's matching games where you have a puzzle and you want to match up all the edges correctly.)
kind of been unsteady on these for a while. the last one (may 15 to may 31) was kind of a haphazard mess. i implemented some more operations for my polyhedra data model format, which notably included "loft", which turns out to be very close to a general-purpose extrude. i used that to make some simple "tree" shapes:
* trees 1
* trees 2
* trees 3
but ultimately i got kind of frustrated with the super simplistic shapes and kinda stopped working on that. (ideally i'd get some more structured face splitting code working so that i could e.g., split trunks and branches at arbitrary angles, so that i could hook it up to some kinda l-system and generate continuous models)
so that was late may. early june i decided to focus on something else and i worked on wang tiles. the end result of that is this page (which apparently doesn't work in chrome but look i've tested it in firefox and midori so like, w/e sorry you use a bad browser) which consists of two parts: one is a totally unconstrained tiling that just does some grid math to make a perfect tiling, and the other is a 'nested' tileset that uses a backtracking solver that i wrote and is moderately decent at figuring out how to lay out some tiles. i was intending to get to manual specification of tiles, since that could use the same solver; it's just UI to handle it, but uhhh html/javascript ui is kind of a mess to write and i'm not good at it, so, oh well i'm not gonna get around to that right now.
the main thing that i learned from this is that a naive backtracking solver is just, total garbage. my first attempt at a solver was really simple: for each tile, pick a random tile from the tileset, but constrained so that its edge match with any adjacent tiles that have already been placed. if there aren't any tiles that match, reject the last tile placed and pick a new one. that algorithm worked sometimes, but it got stuck very easily and frequently got into situations where it would have to exhaust its way through dozens of tiles (which would take thousands of backtracking steps) to get to the problem tile. i considered a few options, and inspired by the WFC constraint algorithm i decided to try precaching options: when a tile was chosen, it would check it against all its adjacent unfixed tiles; if that tile lead to a situation where no tile was possible, it would get rejected, and all those partially-constrained tilesets were cached for later when those tiles would get resolved. this made it much more likely to find a solution, though there were still a bunch of cases where it'd get stuck and fail. if i was gonna keep messing with it, i think the next thing i'd try would be having it unplace the adjacent tile with the most options available, or something like that, instead of it unplace the last tile (since frequently that's not a tile that's actually adjacent to the problem). i don't really know if that would meaningfully change anything, but, doing that is how we find out.
(wang tiles can be used for map generation, as in this video, but i'm more familiar with using them as a tileset placing thing. if e.g., you have a bunch of 16x16 pixel squares that are, like, cave walls, and some have vines running down and some have waterfalls running down and there are various different kinds of rock shapes, it's possible to assign them wang colorings (e.g., green edge if a vine runs off, blue edge if water runs off, grey edge otherwise) and then use a tile placement solver to generate a random placement of the tiles in a way that maintains coherency. you see this a lot in like, children's matching games where you have a puzzle and you want to match up all the edges correctly.)
