Meta tags:
description=Bitmap & tilemap generation from a single example with the help of ideas from quantum mechanics - GitHub - mxgmn/WaveFunctionCollapse: Bitmap & tilemap generation from a single example with the help of ideas from quantum mechanics;

Headings (most frequently used words):

launching, wavefunctioncollapse, in, forks, footer, license, github, desktop, mxgmn, name, already, use, latest, commit, git, stats, files, readme, md, algorithm, tilemap, generation, higher, dimensions, constrained, synthesis, comments, used, work, how, to, build, notable, ports, and, spinoffs, credits, about, releases, sponsor, this, project, contributors, 16, languages, topics, resources, stars, watchers, navigation, sign, required, xcode, visual, studio, code,

Text of the page (most frequently used words):
the (206), and (90), with (65), wfc (53), that (45), model (45), for (33), #algorithm (27), this (26), from (26), made (26), tiled (25), code (21), github (19), can (18), tiles (18), overlapping (17), 2022 (16), #generation (15), are (15), implemented (15), input (15), all (15), nxn (14), jul (13), tilesets (13), synthesis (13), output (13), about (12), system (12), state (12), patterns (12), into (11), generate (11), run (11), better (11), not (11), project (10), game (10), faster (10), image (10), propagation (10), coefficients (10), you (9), bitmap (9), tileset (9), samples (9), where (9), file (9), work (9), texture (9), wavefunctioncollapse (9), example (8), oskar (8), uses (8), published (8), wrote (8), use (8), wave (8), then (8), simplification (8), more (7), sample (7), was (7), examples (7), their (7), voxel (7), tile (7), stålberg (7), based (7), level (7), constraints (7), many (7), each (7), step (7), symmetry (7), adjacency (7), entropy (7), download (7), forks (6), tilemap (6), single (6), taken (6), has (6), observation (6), heuristic (6), local (6), open (6), interactive (6), library (6), levels (6), how (6), only (6), they (6), problem (6), observed (6), data (6), dimensions (6), version (6), distribution (6), repository (6), being (6), easy (6), branch (6), time (5), view (5), license (5), his (5), paul (5), applied (5), produce (5), generates (5), using (5), supports (5), one (5), which (5), port (5), similar (5), programmed (5), other (5), new (5), constraint (5), states (5), makes (5), simple (5), colors (5), first (5), but (5), higher (5), completely (5), zero (5), may (5), replace (5), drawing (5), imagesharp (5), commit (5), mxgmn (5), nothing (5), desktop (5), sign (5), jump (5), your (4), security (4), latest (4), readme (4), quantum (4), mechanics (4), were (4), qud (4), wall (4), models (4), method (4), generator (4), merrell (4), used (4), like (4), houdini (4), generated (4), gave (4), games (4), 2019 (4), rust (4), grids (4), created (4), get (4), global (4), 2018 (4), backtracking (4), order (4), significantly (4), information (4), such (4), there (4), color (4), kotlin (4), build (4), program (4), results (4), harrison (4), web (4), make (4), constrained (4), pixel (4), note (4), knot (4), have (4), without (4), same (4), actions (4), should (4), case (4), unobserved (4), boolean (4), create (4), source (4), region (4), means (4), pattern (4), try (4), again (4), launching (4), tags (4), branches (4), stars (3), learning (3), help (3), ideas (3), summer (3), brian (3), bucklew (3), link (3), krystian (3), integrated (3), boris (3), brave (3), doesn (3), adjacencies (3), edge (3), tool (3), unreal (3), engine (3), between (3), tutorial (3), implementation (3), ported (3), unity (3), talks (3), problems (3), caves (3), roguelike (3), irregular (3), number (3), townscaper (3), phase (3), python (3), well (3), explanation (3), propagate (3), function (3), runs (3), connected (3), isaac (3), karth (3), algorithms (3), bad (3), north (3), adapted (3), improvements (3), textures (3), allows (3), 2017 (3), joseph (3), provided (3), visualize (3), partially (3), possible (3), heuristics (3), bitmaps (3), nick (3), dimensional (3), line (3), ports (3), spinoffs (3), pull (3), release (3), also (3), large (3), non (3), any (3), because (3), minimal (3), convchain (3), find (3), cannot (3), adjacent (3), type (3), corresponding (3), pairs (3), symmetrical (3), its (3), small (3), elements (3), collapse (3), element (3), superposition (3), https (3), name (3), load (3), git (3), happens (3), codespaces (3), tag (3), issues (3), signed (2), another (2), tab (2), window (2), refresh (2), session (2), reload (2), blog (2), pricing (2), footer (2), navigation (2), 2023 (2), contributors (2), learn (2), sponsors (2), sponsor (2), resources (2), procedural (2), machine (2), topics (2), cat (2), video (2), rid5x (2), arvi (2), teikari (2), samp (2), generating (2), suggested (2), style (2), mario (2), credits (2), modifying (2), blocks (2), technique (2), marian (2), kleineberg (2), infinite (2), city (2), induced (2), labels (2), plugin (2), ján (2), commercial (2), escheresque (2), scenes (2), talk (2), casey (2), clojure (2), java (2), discuss (2), developers (2), conference (2), chapter (2), combined (2), town (2), building (2), 2021 (2), contradiction (2), rate (2), works (2), arbitrary (2), structure (2), detailed (2), various (2), edwin (2), jakobs (2), julia (2), option (2), locally (2), queue (2), instead (2), propagates (2), procjam (2), setting (2), article (2), additional (2), haxe (2), both (2), general (2), adam (2), smith (2), process (2), text (2), tilings (2), them (2), sylvain (2), lefebvre (2), clingo (2), asp (2), parker (2), making (2), gui (2), resulting (2), options (2), per (2), voting (2), group (2), different (2), earlier (2), paper (2), visual (2), nenov (2), browser (2), itch (2), page (2), 2016 (2), javascript (2), notable (2), community (2), convenient (2), issue (2), change (2), xml (2), configuration (2), csproj (2), windows (2), author (2), demonstration (2), thomas (2), less (2), suited (2), reduce (2), either (2), don (2), here (2), lowest (2), contains (2), those (2), present (2), perfect (2), particular (2), captures (2), very (2), belief (2), way (2), markov (2), chains (2), why (2), when (2), often (2), themselves (2), watch (2), comments (2), than (2), long (2), correlations (2), brick (2), exactly (2), sense (2), blueprint (2), condition (2), outputs (2), however (2), defects (2), point (2), close (2), gifv (2), gif (2), these (2), density (2), circuit (2), yet (2), interesting (2), call (2), knots (2), assigned (2), letters (2), words (2), lists (2), even (2), several (2), nontrivial (2), probabilities (2), initialize (2), gained (2), previous (2), definite (2), according (2), cycle (2), true (2), array (2), real (2), coefficient (2), forbidden (2), official (2), certain (2), fast (2), solution (2), value (2), numbers (2), aug (2), ground (2), attribute (2), message (2), a6f79f0 (2), codespace (2), please (2), xcode (2), cli (2), already (2), default (2), refname (2), show (2), could (2), belong (2), fork (2), outside (2), insights (2), projects (2), requests (2), notifications (2), star (2), manage (2), packages (2), out, perform, action, training, api, contact, docs, status, privacy, terms, inc, 100, languages, releases, watching, 509, watchers, csharp, gamedev, circles, floorplan, drawn, hermann, hillmann, nyan, water, forest, mountains, ultima, 3bricks, dungeon, crawl, stone, soup, magicoffice, spirals, coloredcity, mazelike, reddot, smilecity, arcaniax, notknot, sand, wrinkles, circle, noah, buddy, rest, idea, circuits, zachtronics, rendered, magicavoxel, ruckingenur, moonasaur, lingdong, huang, klingemann, lazy, unbounded, configurations, island, combines, triangle, quad, custom, minimums, deepmind, ended, team, arenas, reinforcement, agents, explores, gerald, extends, grasshopper, tóth, pernecký, ivan, donchevskii, łukasz, jakubowski, maciej, kaszlewicz, paweł, kroll, stefan, radziuk, zelda, observable, notebook, lionel, radisson, posted, explains, relationship, twitter, thread, élie, michel, simon, verstraete, keijiro, takahashi, hive, 2020, ambrosiussen, nuño, serna, symmetries, openframeworks, addon, steven, asset, freehold, overfitting, homogeny, connectedness, combining, constructive, procgen, methods, celebration, implementing, scratch, herbert, wolverson, marching, cubes, toy, interviews, mixed, initiative, konsoll, sgc21, epc2021, bob, burrough, percolation, transition, manifests, spiking, discovered, florian, drux, graphs, generalization, stephen, sherratt, 7drl, challenge, soon, jam, player, interact, resetting, portions, weapons, andy, wallace, shawn, ridgeway, breanna, baltaxe, admony, music, dithering, transfer, robert, hoenig, wouter, van, oortmerssen, priority, sol, bekic, gpu, pyopencl, keeping, nodes, every, node, grid, parallel, describing, approaches, online, variation, structures, hex, chiseling, tim, kong, brendan, anthony, decorations, rodina, describe, learns, positive, negative, context, dialogs, driven, generators, preprint, approximately, unbiased, paths, points, everything, experimented, hwanhee, kim, vasu, mahesh, typescript, webgl, visualised, running, magnitude, improved, nathanael, courant, mathieu, fehr, possibility, hiding, inside, encode, messages, decode, back, codes, investigating, connelly, barnes, wei, matvey, khokhlov, formulated, connectivity, aman, tiwari, william, manning, primary, goal, readable, wpf, upcoming, tries, select, zone, navigable, remy, devaux, pico, coherent, ways, values, averaged, semi, transparent, boxes, box, bigger, shows, generalized, cube, described, thought, designing, ensure, walkable, examine, role, experiment, combine, vae, authors, formulate, solver, trace, history, give, workshop, access, guide, matt, rix, lua, headchant, löve, danny, wynne, built, pipeline, applies, multiple, passes, executable, ocaml, sean, leffler, castle, reconstruct, cinema, poetry, martin, leary, skateparks, bug, gun, platform, swapland, fantastic, plateaus, proc, skater, sphere, beautiful, kevin, chapelier, jvm, roskopf, optimized, kollapse, max, aller, emil, ernerfeldt, alternatively, instructions, platforms, marshall, command, includes, snap, packaging, request, relevant, put, folder, edit, parameters, dotnet, console, application, depends, standard, linux, macos, net, core, 2005, influenced, declarative, dissertation, defines, labeling, borders, search, fill, available, tools, alan, mackworth, 1977, translates, satisfaction, currently, roger, mohr, henderson, 1986, consistency, networks, relations, 2009, derives, larger, generalize, approach, individual, varying, look, introduce, removes, defined, implement, sizes, inputs, introduced, incrementally, parts, failure, recently, averaging, pre, directional, bias, alexei, efros, leung, 1999, compared, guarantees, art, full, parametric, sampling, behaviour, cellular, automata, trick, loopy, fact, switched, saved, stationary, slower, massive, parallelization, cpu, didn, relates, relate, noticed, humans, draw, something, follow, enjoyable, trouble, difficult, synthesize, correctly, aligned, bricks, shines, satisfies, strong, limit, producing, distributions, satisfy, produces, noticeable, sampled, correct, common, strategy, optimization, monte, carlo, optimum, gradient, descent, greater, accuracy, autocompleting, started, human, therefore, easily, generative, manual, creation, markovjunior, resolution, screenshots, dimension, though, performance, becomes, 5x5x5, 5x5x2, height, curvature, rooms, wang, two, corners, connection, diagonal, tracks, direction, unrestrained, allowed, situation, place, property, special, arrangements, quickly, fall, off, distance, found, consider, dual, junctions, while, answer, narrow, class, guy, walker, website, dihedral, isomorphic, enough, enumerate, despite, drawings, considers, times, shorter, practical, quite, shorten, enumeration, simplest, 1x2, nxm, simplify, further, storing, what, just, list, viewed, set, rather, now, except, contradictory, return, second, finish, returning, anything, repeat, following, steps, nonzero, undefined, break, called, represents, false, read, count, optional, augment, rotations, reflections, youtube, youtu, doqtr2xmlz0, been, graphical, prototypes, led, see, section, tutorials, guides, demos, explanations, related, research, smaller, matrix, awakens, dead, static, drive, happen, during, become, continue, determining, whether, satisfying, hard, impossible, always, finishes, practice, contradictions, surprisingly, rarely, decreases, end, collapsed, through, chosen, among, shannon, collapses, initializes, black, white, shown, shades, grey, superpositions, complex, actual, inspired, goes, typical, weak, over, sufficiently, probability, meet, contain, pixels, similarity, simpletiledmodel, overlappingmodel, helper, rng, mode, citation, cff, images, failed, permalink, files, commits, 140, stats, preparing, will, once, ready, studio, required, zip, our, checkout, svn, url, clone, cancel, exists, commands, accept, names, creating, cause, unexpected, behavior, sure, want, switch, master, does, public, user, collections, trending, repositories, articles, fund, customer, stories, studies, devsecops, devops, automation, education, startups, teams, enterprise, solutions, skills, documentation, features, explore, collaborate, discussions, plan, track, changes, review, write, copilot, instant, dev, environments, fix, vulnerabilities, host, automate, workflow, product, toggle, skip, content, wayback, http, archive, org, 20230129220642, com, timestamps, capture, fail, success, 2024, feb, jan, dec, sep, 2026, 638,

Text of the page (random words):
ity means that c1 the output should contain only those nxn patterns of pixels that are present in the input weak c2 distribution of nxn patterns in the input should be similar to the distribution of nxn patterns over a sufficiently large number of outputs in other words probability to meet a particular pattern in the output should be close to the density of such patterns in the input in the examples a typical value of n is 3 wfc initializes output bitmap in a completely unobserved state where each pixel value is in superposition of colors of the input bitmap so if the input was black white then the unobserved states are shown in different shades of grey the coefficients in these superpositions are real numbers not complex numbers so it doesn t do the actual quantum mechanics but it was inspired by qm then the program goes into the observation propagation cycle on each observation step an nxn region is chosen among the unobserved which has the lowest shannon entropy this region s state then collapses into a definite state according to its coefficients and the distribution of nxn patterns in the input on each propagation step new information gained from the collapse on the previous step propagates through the output on each step the number of non zero coefficients decreases and in the end we have a completely observed state the wave function has collapsed it may happen that during propagation all the coefficients for a certain pixel become zero that means that the algorithm has run into a contradiction and can not continue the problem of determining whether a certain bitmap allows other nontrivial bitmaps satisfying condition c1 is np hard so it s impossible to create a fast solution that always finishes in practice however the algorithm runs into contradictions surprisingly rarely wave function collapse algorithm has been implemented in c python kotlin rust julia go haxe java clojure javascript and adapted to unity unreal engine 5 and houdini you can build wfc from source download an official release for windows download an interactive graphical version from itch io or run it in the browser wfc generates levels in bad north caves of qud dead static drive townscaper matrix awakens several smaller games and many prototypes it led to new research for more related work explanations interactive demos guides tutorials and examples see the ports forks and spinoffs section watch a video demonstration of wfc algorithm on youtube https youtu be doqtr2xmlz0 algorithm read the input bitmap and count nxn patterns optional augment pattern data with rotations and reflections create an array with the dimensions of the output called wave in the source each element of this array represents a state of an nxn region in the output a state of an nxn region is a superposition of nxn patterns of the input with boolean coefficients so a state of a pixel in the output is a superposition of input colors with real coefficients false coefficient means that the corresponding pattern is forbidden true coefficient means that the corresponding pattern is not yet forbidden initialize the wave in the completely unobserved state i e with all the boolean coefficients being true repeat the following steps observation find a wave element with the minimal nonzero entropy if there is no such elements if all elements have zero or undefined entropy then break the cycle 4 and go to step 5 collapse this element into a definite state according to its coefficients and the distribution of nxn patterns in the input propagation propagate information gained on the previous observation step by now all the wave elements are either in a completely observed state all the coefficients except one being zero or in the contradictory state all the coefficients being zero in the first case return the output in the second case finish the work without returning anything tilemap generation the simplest nontrivial case of the algorithm is when nxn 1x2 well nxm if we simplify it even further by storing not the probabilities of pairs of colors but the probabilities of colors themselves we get what we call a simple tiled model the propagation phase in this model is just adjacency constraint propagation it s convenient to initialize the simple tiled model with a list of tiles and their adjacency data adjacency data can be viewed as a large set of very small samples rather than a sample bitmap gif gifv lists of all the possible pairs of adjacent tiles in practical tilesets can be quite long so i implemented a symmetry system for tiles to shorten the enumeration in this system each tile should be assigned with its symmetry type note that the tiles have the same symmetry type as their assigned letters or in other words actions of the dihedral group d4 are isomorphic for tiles and their corresponding letters with this system it s enough to enumerate pairs of adjacent tiles only up to symmetry which makes lists of adjacencies for tilesets with many symmetrical tiles even the summer tileset despite drawings not being symmetrical the system considers such tiles to be symmetrical several times shorter note that the unrestrained knot tileset with all 5 tiles being allowed is not interesting for wfc because you can t run into a situation where you can t place a tile we call tilesets with this property easy without special heuristics easy tilesets don t produce interesting global arrangements because correlations of tiles in easy tilesets quickly fall off with a distance many easy tilesets can be found on guy walker s website consider the dual 2 edge tileset there how can it generate knots without t junctions not easy while being easy the answer is it can only generate a narrow class of knots it can t produce an arbitrary knot note also that circuit summer and rooms tilesets are non wang that is their adjacency data cannot be induced from edge labels for example in circuit two corners cannot be adjacent yet they can be connected with a connection tile and diagonal tracks cannot change direction higher dimensions wfc algorithm in higher dimensions works completely the same way as in dimension 2 though performance becomes an issue these voxel models were generated with n 2 overlapping tiled model using 5x5x5 and 5x5x2 blocks and additional heuristics height density curvature higher resolution screenshots 1 2 3 markovjunior repository contains an implementation of the 3d simple tiled model with many tilesets and examples constrained synthesis wfc algorithm supports constraints therefore it can be easily combined with other generative algorithms or with manual creation here is wfc autocompleting a level started by a human gif gifv convchain algorithm satisfies the strong version of the condition c2 the limit distribution of nxn patterns in the outputs it is producing is exactly the same as the distributions of patterns in the input however convchain doesn t satisfy c1 it often produces noticeable defects it makes sense to run convchain first to get a well sampled configuration and then run wfc to correct local defects this is similar to a common strategy in optimization first run a monte carlo method to find a point close to a global optimum and then run a gradient descent from that point for greater accuracy p f harrison s texture synthesis algorithm is significantly faster than wfc but it has trouble with long correlations for example it s difficult for this algorithm to synthesize brick wall textures with correctly aligned bricks but this is exactly where wfc shines and harrison s algorithm supports constraints it makes sense first to generate a perfect brick wall blueprint with wfc and then run a constrained texture synthesis algorithm on that blueprint comments why the minimal entropy heuristic i noticed that when humans draw something they often follow the minimal entropy heuristic themselves that s why the algorithm is so enjoyable to watch the overlapping model relates to the simple tiled model the same way higher order markov chains relate to order one markov chains wfc s propagation phase is very similar to the loopy belief propagation algorithm in fact i first programmed belief propagation but then switched to constraint propagation with a saved stationary distribution because bp is significantly slower without a massive parallelization on a cpu and didn t produce significantly better results in my problems note that the simple knot and trick knot samples have 3 colors not 2 one of the dimensions can be time in particular d dimensional wfc captures the behaviour of any d 1 dimensional cellular automata used work alexei a efros and thomas k leung texture synthesis by non parametric sampling 1999 wavefunctioncollapse is a texture synthesis algorithm compared to the earlier texture synthesis algorithms wfc guarantees that the output contains only those nxn patterns that are present in the input this makes wfc perfect for level generation in games and pixel art and less suited for large full color textures paul c merrell model synthesis 2009 merrell derives adjacency constraints between tiles from an example model and generates a new larger model with the ac 3 algorithm we generalize his approach to work with nxn overlapping patterns of tiles instead of individual tiles this allows to use a single image as the input to the algorithm by varying n we can make the output look more like the input or less we introduce the lowest entropy heuristic that removes the directional bias in generated results is defined for irregular grids and is better suited for pre constrained problems we implement a tile symmetry system to reduce the sizes of inputs we visualize partially observed states either with color averaging or per voxel voting merrell also introduced a method of incrementally modifying the model in parts to reduce the failure rate which we don t use here recently the author created a page for model synthesis and published code alan k mackworth consistency in networks of relations 1977 wfc translates a texture synthesis problem into a constraint satisfaction problem currently it uses the ac 4 algorithm by roger mohr and thomas c henderson 1986 paul f harrison image texture tools 2005 wfc was also influenced by the declarative texture synthesis chapter of paul harrison s dissertation the author defines adjacency data of tiles by labeling their borders and uses backtracking search to fill the tilemap a demonstration of the algorithm is available on the web how to build wfc is a console application that depends only on the standard library get net core for windows linux or macos and run dotnet run configuration release wavefunctioncollapse csproj generated results are put into the output folder edit samples xml to change model parameters alternatively use build instructions from the community for various platforms from the relevant issue casey marshall made a pull request that makes using the program with the command line more convenient and includes snap packaging notable ports forks and spinoffs emil ernerfeldt made a c port max aller made a kotlin jvm library kollapse joseph roskopf made a line by line kotlin port of the optimized 2018 version edwin jakobs made a kotlin library that supports 3d examples kevin chapelier made a javascript port oskar stålberg programmed a 3d tiled model a 2d tiled model for irregular grids on a sphere and is building beautiful 3d tilesets for them 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 joseph parker adapted wfc to unity and used it generate skateparks in the proc skater 2016 game fantastic plateaus in the 2017 game swapland and platform levels in the 2018 game bug with a gun martin o leary applied a wfc like algorithm to poetry generation 1 2 3 4 nick nenov made a 3d voxel tileset based on my castle tileset nick uses text output option in the tiled model to reconstruct 3d models in cinema 4d sean leffler implemented the overlapping model in rust rid5x is making an ocaml version of wfc i made an interactive version of the overlapping model you can download the gui executable from the wfc itch io page brian bucklew built a level generation pipeline that applies wfc in multiple passes for the caves of qud game 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 danny wynne implemented a 3d tiled model arvi teikari programmed a texture synthesis algorithm with the entropy heuristic in lua headchant ported it to work with löve isaac karth made a python port of the overlapping model oskar stålberg made an interactive version of the tiled model that runs in the browser matt rix implemented a 3d tiled model 1 2 3 4 and made a 3 dimensional tiled model where one of the dimensions is time 1 2 3 4 5 nick nenov made a visual guide to the tile symmetry system isaac karth and adam m smith wrote a paper open access link in which they examine the role of backtracking and different possible heuristics in wfc experiment with global constraints and combine wfc with vq vae earlier in 2017 the authors wrote a workshop paper where they formulate wfc as an asp problem use general constraint solver clingo to generate bitmaps trace wfc s history and give a detailed explanation of the algorithm sylvain lefebvre made a c implementation of 3d model synthesis described the thought process of designing a sample and provided an example where adjacency constraints ensure that the output is connected walkable i generalized 3d wfc to work with cube symmetry group and made a tileset that generates escheresque scenes there are many ways to visualize partially observed wave states in the code color values of possible options are averaged to produce the resulting color oskar stålberg shows partially observed states as semi transparent boxes where the box is bigger for a state with more options in the voxel setting i visualize wave states with per voxel voting remy devaux implemented the tiled model in pico 8 and wrote an article about generation of coherent data with an explanation of wfc for the upcoming game bad north oskar stålberg uses a heuristic that tries to select such tiles that the resulting observed zone is navigable at each step william manning implemented the overlapping model in c with the primary goal of making code readable and provided it with wpf gui joseph parker wrote a wfc tutorial for procjam 2017 aman tiwari formulated the connectivity constraint as an asp problem for clingo matvey khokhlov programmed a 3d overlapping model sylvain lefebvre li yi wei and connelly barnes are investigating the possibility of hiding information inside textures they made a tool that can encode text messages as wfc tilings and decode them back this technique allows to use wfc tilings as qr codes mathieu fehr and nathanael courant significantly improved the running time of wfc by an order of magnitude for the overlapping model i integrated their improvements into the code vasu mahesh ported 3d tiled model to typescript made a new tileset and visualised the generation process in webgl hwanhee kim...