Wang tile | Hacker News Reader

Wang tile

en.wikipedia.org

145 pointsmeuk24 comments

We used to use this technique for ground textures a long time ago.

We even wrote an article about authoring textures using the technique here: https://www.pathofexile.com/forum/view-thread/55091

In the end though, we found that the time spent authoring textures like this didn't really pay off so we stopped using the feature.

Instead of that, we blend randomly between a few different material versions that make up the ground which leads to a similar but easier to achieve effect. An obvious example is here http://web.poecdn.com/image/xboxbeta/ss/Panel1/screenshot3.j... where we have a snowy and non-snowy version of the same ground texture and we scatter blends to the snowy version randomly.

Aside: I played through PoE co-op with my fiancee after it was first released, and I really loved it. I'm really happy you guys were able to build such a big ambitious game and make it work financially.

Off topic:

I played PoE back in summer and autumn 2012, in closed beta, and I absolutely loved the game. I even spent some money on it :-) Then my gaming PC died. Nowadays I only play games on PS4. I just noticed that an Xbox1 version was released a few months back: are there any plans of ever bringing PoE to PS4? I would love to play it again, but can’t rationalise getting either a gaming PC or an Xbox to do so.

I noticed it on PSN last night.

Are you sure? I’ve tried to find it since seeing your reply and no luck. Couldn’t find anything about it online either. There’s also this: https://gamingbolt.com/path-of-exile-dev-explains-why-the-ga...

:( Looks like my closed-beta purchases are going to continue to go to waste. I’ll miss you, little kiwi bird...

You can use this technique to build interesting levels for games. By constructing a set of tiles with known edges, and laying them out using this technique, you can see some fascinating, aperiodic dungeons.

http://nothings.org/gamedev/herringbone/

How easy is it to generate the level from the set of tiles?

Not that difficult, but the benefits may not be better than just using tiles and some clever removal/additions a la Spelunky: http://tinysubversions.com/spelunkyGen/

The "can you tile the plane aperiodically" that started the investigation into these tile sets, the disproof was that proving it was equivalent to solving the halting problem... and thus the tile set is equivalent to a Turing machine.

I keep wondering if https://grahamshawcross.com/2012/10/12/wang-tiles-and-turing... is practical as a bathroom wall.

Another Wang tiles problem I've always been fond of because of its deceptive simplicity is the following:

If a finite set of tiles can tile a quadrant of the plane, it can also tile the full plane.

One would guess that there is a constructive proof, but in fact the proof relies on a weak version of the axiom of choice (see for example this proof https://caicedoteaching.wordpress.com/2009/08/24/502-konigs-... ).

Weird. It's not my field at all but intuitively, I would have approached a proof by trying to formalise the following:

1/ Complete part of the tiling in the upper right quadrant (this tiling exists by assumption)

2/ Shove all the tiles down and to the left

3/ Repeat.

It's very surprising that step 2 needs the axiom of choice. (Usually when I'm this surprised it means I've misunderstood something!)

Edit: your link proves something stronger - that the ability to tile an nxn square for all n is equivalent to tiling a quadrant and tiling a plane. I guess that's where choice comes in, is it?

That's what I meant by attempting to find a constructive proof. 2 doesn't work because no matter how much you shift down and to the left you'll always have a boundary.

> our link proves something stronger

No, it proves that the 3 statements are equivalent, so it is not stronger.

But isn't it enough to show that any point in the plane will eventually get tiled after 1 - 3 run for long enough?

Because surely all points do get tiled eventually by the method above.

This falls short of the original goal: While your method shows that for every point, you can find a tiling large enough that covers it, the original question was to find a single tiling covering everything.

Finding progressively larger, finite tilings is not the same as having a single infinite tiling, just like finding larger and larger natural numbers is not the same as having a single number larger than all natural numbers (which wouldn't be a natural number).

König's lemma implies that for tilings both statements are in fact equivalent.

> like finding larger and larger natural numbers is not the same as having a single number larger than all natural numbers

Very nice analogy!

> König's lemma implies that for tilings both statements are in fact equivalent.

Exactly, and instead of working by shifting the tiling (which would produce a sequence of incompatible tilings) it works by finding a sequence of finite tilings where each is a subset of the next, so it makes sense to take the union of the sequence.

With the caveat that if your tiling is inductive in the sense that the tiling of n+1 is an extension of n, a series of finite tilings will tile the plane.

Well, a naïve way to "prove" it would be to flip the quadrant over the axes to tile the other quadrants. Is this legal? Or, more specifically, are there tiles that can tile something one way, but not if flipped?

If you flip the quadrant you're also flipping the tiles. The flipped tiles may not be in your set.

I always wanted to see people use wang tiles or Penrose tiles for texturing large arrays of polygons, so that you don’t get the annoyingly obvious repeats that most texturing gives you.

The theory for this was put forth by Cohen et al. in 2003 [1]. Whether or not it's been implemented, I'm not sure. Interesting idea, for sure.

[1] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.84....

Many games and engines do this. Including Roblox!

Also worth checking out, not sure if its a recent algorithm or just now in vogue, but wave function collapse. See https://twitter.com/ExUtumno?lang=en for some good examples.

wang tiles as noted are used for dna based computing machinery, https://www.dailymotion.com/NicolasSchabanel/videos has videos about molecular computing

people in this field made DNA tile game of life capable implementations, with a full logic substrate.

the chemistry involved is very sensitive but in theory they could compile programs into this (in early 2017 they were limited to afew hundred dna pairs in program size before error rates became unmanageable)

ps: also look up damien woodz

I wrote a gruesome wang tile implementation for dungeon crawl: https://github.com/crawl/crawl/blob/d0efa662383971e981fb52f8...

In addition to color it supports 'oriented colors': blue+ matches blue- for example. This allows graphical manipulations of the art assets to be reflected in the tile structure.

Reply on news.ycombinator.com