OTCA Metapixel - Conways spelet i livet

Conway's Game of Life är en typ av 2D cellulär automat som använder en enkel uppsättning regler för att beskriva funktionen hos celler över diskret tid steg. Överraskande, kan du skapa mycket komplexa beteende från cellulära automater även om reglerna kan brukar sammanfattas i en mening. I 2D cellulära automater styrs cellens beteende i nästa tidssteg av dess nuvarande tillstånd och det aktuella läget för sina åtta grannar. Regler för Conways spelet i livet återges nedan:

1. En levande cell med färre än två levande grannar dör, som om orsakas av bristande befolkningen.
2. En levande cell med två eller tre levande grannar lever vidare till nästa generation.
3. En levande cell med mer än tre levande grannar dör, som genom överbefolkning.
4. En död cell med exakt tre levande grannar blir en levande cell, som genom reproduktion.

Många intressanta mönster har studerats i livet, några enkla mönster visas här. Några mönster, kallas "fortfarande liv" är stationärt och förändras inte över tid (block, limpa, båt). "Oscillatorer" är mönster som upprepar sig efter ett visst antal tid steg (

,

,

). "Rymdskepp" är en typ av oscillator som flyttar över utrymme som de pendlar. Den enklaste och vanligaste formen av rymdskepp kallas ett

. En annan gemensam rymdskepp är

. "Vapen" är strukturer som producerar en ström av rymdskepp, här är ett exempel på

. Några mycket enkla initialt villkorar skapa komplexa beteende, vilket är fallet med den r pentomino, ett fem cell mönster.

Använda en kombination av rymdskepp, stilla stilleben, oscillatorer, vapen och andra grundläggande objekt, är det möjligt att konstruera otroligt komplexa strukturer i livet. Här är ett exempel på en period 416 pistol som konstruerar 60P5H2V0 rymdskepp med hjälp av en serie tajmade glider kollisioner:

2006 publicerade Brice på grund av en struktur som kallas OTCA Metapixel, dess syfte är att efterlikna beteendet för en enskild cell liv. Jag kom över den här videon förra veckan och beslutade jag var tvungen att räkna ut hur det fungerar:

OTCA Metapixel är inte först eller den snabbaste metapixel upptäckte i livet (också kolla P5760 enhet liv cell och den djupa cell), men det har den intressanta egenskapen att ser ut som en liv cell utzoomat. Det har också ett register som gör att du kan programmera den att uppföra sig enligt någon godtycklig verklighetstrogen cellulär automat regeluppsättning.

Jag fick all min information från Liv Wiki, OTCA webbplatsoch Liv Lexicon och (oftast) genom att ladda ner Golly och tittar OTCA Metapixel kör.

Här är hur det fungerar:

Klocka - en traktor balk är en ström av rymdskepp som långsamt dra ett objekt mot riktningen av dess källa. Ett enkelt exempel är limpa traktor balk. Denna video visar en något annorlunda typ av traktor balk i en sawtooth.

OTCA Metapixel använder en traktor balk som en klocka för att reglera tidpunkten för händelserna:

I videon ovan drar en traktor balk ett kvarter ner av 8 celler i varje kollision, släppa ett segelflygplan till rätt varje gång. Ett staket vid sidan av traktorn strålen av ätare 1förstör glidflygplan omedelbart, men det finns några hål i stängslet som tillåter segelflygplan att passera och interagera med andra strukturer i metapixel vid regelbundet olika tidsintervaller.

Det första skottet i videon visar källan blocket och tre skrov skjuter in i en lätt rymdskepp (LWSS) paket pistol, som sedan skjuter ut tre uppsättningar av tre LWSSes, en uppsättning för varje inkommande segelflygplan. Nästa skott visar källan traktor balkens och fyra mer segel sköt från traktor balk i metapixel. Denna första segelflygplan initierar en granne greve avkoda sekvens, de nästa två segelflygplan läsa resultaten från dekodern och sista segelflygplan initierar en logik kaskad som till slut avgör om du vill aktivera metapixel på eller av i nästa klockcykel (alla beskrivs mer i detalj senare). Rollen som de 7 segelflygplan sammanfattas i

.

Under varje cykel av OTCA Metapixel klockan, är blocket förstört vid källan traktor balkens och återställd i sin startposition, fortgång.

Regler och logik - reglerna för metapixel kodas i två kolumner (register) som visas i bilderna nedan. Liv-liknande automater regler skrivs i den form B # / s #, beskrivs här. Conways regler definieras som B3/S23, så de motsvarande bitarna i registren för OTCA metapixel fylls med en Eater-1 varje.

regel register

På varje klockcykel är tre uppsättningar av tre LWSSes (9 totalt i en enda rad) sköt från en packet pistol (utlöst av klockan, ovan) och skickas ut på en komplett slinga runt metapixel. Som tåget av rymdskepp passera var och en av dess Moore grannar det första fartyget i tåget kommer att kollidera med en damm i sin väg om grannen är för närvarande vid liv, förstöra fartyget och minskar det totala antalet fartyg i tåget av en. Så om en metapixel har 4 levande grannar, kommer endast fem LWSSes tillbaka efter att ha avslutat ett pass i ytterkanten. En kollision mellan ett tåg av LWSSes med en damm visas nedan på om 0:32 (jag ska förklara hur dammarna dit senare):

Denna video visar också shepherding av tåget av LWSSes runt metapixel av twin bin Transfer och andra reflexer, och ett exempel på "justering" av fartyg (ändra deras fas något) genom ett par glider kanoner. Sökvägen till LWSSes tillsammans med placeringen av färg justeringsanordningar och möjliga dammar visas i

.

Den fullständiga sökvägen LWSS tågets visas nedan. Lägg märke till hur ett fartyg tas bort från framsidan av tåget när den passerar varje levande granne.

När tåget av LWSSes är klar en loop, de är kanaliseras i en sync buffert och p46 till p40 converter där de ges samma fas. Sedan skickas de till regler registret där de är kolliderade med en annan LWSS kommer från motsatt riktning (med ursprung från en av segelflygplan skott av klockan) att avkoda tåget av LWSS till antalet levande grannar (visas i

).

Placeringen av kollisionen mellan LWSS tåget och LWSS med ursprung form klockan beror på hur många LWSS förstördes från framsidan av tåget under en slinga runt metapixel. Mekanismen är inställd så att kollisionen skjuter ut två glidflygplan i motsatta riktningar, riktning mot registret som motsvarar antalet levande grannar metapixel har (igen, se

som referens).

Normalt, glidflygplan kommer att kollidera med en bikupa att producera ett block och en damm, detta kallas en honeybit reaktion. Om du tittar från ca 6 min in i videon ovan, ser du sammanstötningen av antiparallel LWSSes, skicka två segelflygplan mot 4: e plats (räkna upp från botten, börjar på 0) i både födelse- och överlevnad register, och omkring 6:30 två dammar bildas i registren. De återstående rymdskepp i LWSS tåg kolliderar med en Eater-1 och förstörs. Videon nedan visar en närmare titt över många generationer:

Om facket i registret upptas av en Eater-1 (som är den 3: e platsen i födelseregister och de 2: a och 3: e platser i överlevnad registren, återigen räkna upp från botten börjar på 0), sedan förstörs inkommande segelflygplan innan den har en chans att förtrolig en honeybit reaktion med en bikupa. Detta ger inget damm i registret. I denna mekanism har ett register en damm om antalet levande grannar inte uppfyller villkoren för livet i nästa generation, och inget damm om den gör. Kom ihåg denna information delas mellan två register (födelse och överlevnad) och i ett senare steg några logik kommer att titta på det aktuella läget för metapixel att avgöra som registrerar för att läsa från (beskrivs senare). Denna mekanism är det som gör OTCA Metapixel programmerbara för alla liv-liknande regeluppsättning, ganska cool.

Nästa, klockan skjuter ut ett par LWSSes att läsa dessa register (en LWSS för varje kassa), efter trajectoriesen visas i

. Om en damm finns i ett register, LWSS kolliderar med dammen och förstörs. Detta avslutar honeybit reaktionen och återställer bikupa i samma position det ursprungligen. Om LWSS har ingen damm i sin väg, är det tillåtet att fortsätta till nästa logik mekanism. I videon ovan, se om du kan förutse nästa tillstånd för metapixel genom att läsa ur registren.

Innan jag går till den slutliga logiken i systemet, ska jag titta på hur grannarna staterna är stämde upp.

visar de 8 ingång/utgång kanalerna för varje metapixel. Genom att ta en närmare titt på en av dem, ser du en annan honeybit reaktion händer:

Honeybit reaktionen till vänster motsvarar tillståndet för metapixel till höger, och reaktionen till höger motsvarar tillståndet för metapixel till vänster. LWSS tåget rör sig medsols runt metapixel, så tåget flyttar ner skärmen tillhör pixeln till vänster och tåget går upp skärmen tillhör pixeln till höger.

Dessa honeybit reaktioner ställs in av en mitten vikt rymdskepp (MWSS) som rör sig i en moturs väg runt pixel varje klockcykel.

är en beskrivning av dess sökväg och sökvägen för alla segel det genererar för 8 honeybit reaktioner runt metapixel. MWSS skapas endast om det aktuella läget för metapixel är levande och i slutet av sin slinga runt pixeln den förstörs.

Den slutliga logiken i metacell summeras i

.

Första några definitioner:

C är det aktuella läget i cellen, 1 eller 0

B är statligt av födelseregister, 1 för nöjd födelse villkor, 0 för inte-nöjd

S om tillståndet för överlevnad registret, 1 för nöjd, 0 för inte-nöjd

Påstår av C, B och S lagras i metapixel av förekomst ("1") eller ("0") av tre båtar. Båtar har en intressant egenskap som när de är hit med ett segelflygplan de återspeglar ett nytt segelflygplan med en bana som är vinkelrät till sökvägen för inkommande segelflygplan. Denna kollision förstör båten, så båtar är kända som en tid reflektorer. Placera av båtarna i metacell visas i

. B och S båtarna ställs in med hjälp av den LWSSes som kan passera genom födelse och överlevnad registren under avkodning steg beskrivs ovan. I den här videon kommer titta på hur staterna i B och S är satt till "1" av ett par LWSSes börjar på 3:47, de ligger för närvarande på 4:54:

Ett segelflygplan används för att läsa påstår av C, B och S och sätta en damm på G eller H (visas i

). Logiken för G och H damm bildandet ("1" innebär en damm bildas, "0" betyder inget damm) ges av följande logik:

Om C är närvarande, då:

G = ! S (G motsvarar motsatsen till S)

H = 0

om C inte finns:

G = 0

H = B

Slutliga segelflygplan släpptes av klockan (beskrivs i början) uppsättningar en logik kaskad som beräknar dessa relationer. Segelflygplan frigörs genom det lilla hålet i staketet bredvid klockan, lite mindre än halvvägs upp till vänster i videon ovan, utlöser bildandet av en LWSS som färdas mot den högra sidan av videon, släppa två segelflygplan på väg (exempel börjar vid ca 16:12). Den första segelflygplan studsar runt och så småningom förvandlas till en LWSS som läser resultaten på G och H, mer om detta i nästa stycke. Andra segelflygplan huvuden mot C, om C finns det återspeglar och börjar på väg mot S. Om S finns det reflekterar in en eater och dör, om S inte finns det fortfarande en bikupa på G och gör en honeybit reaktion, bildar en damm. Om C inte är närvarande, huvuden andra segelflygplan mot B istället. Om B är närvarande, segelflygplan speglar av B och gör en honeybit reaktion på H, annars det kör in i en eater och dör. 16:20 i videon ovan visar segelflygplan reflekteras från C, går genom ett frånvarande S och bildar en damm på G.

Vid 16:38 kan du se en damm på G och en LWSS kommer in från vänster för att läsa G och H. Om antingen G eller H har en damm ställa, förstörs LWSS, som visas vid 16:39. Om varken är inställda (se 10:47) LWSS fortsätter på och bildar en båt på notT (visas som T med en linje på toppen på

). Detta kan sammanfattas med logik:

notT =! (G || H) (notT är lika med 1 när G och H är båda 0, annars är det 0)

En tredje glida ut på 10:57 av de ursprungliga LWSS logik cascade trigger huvuden mot notT. Om båten är fortfarande närvarande det speglar av båten och träffar en eater, om båten är inte presentera det T (igen,

). Segelflygplan förstörs av en eater i 11:16, men du kan se det huvud till T börjar på 5:33.

Ett fjärde segelflygplan är utsläppt vid den ursprungliga LWSS som förvandlas till en LWSS som rensar upp alla överblivna båtar kvar på B eller S efter de logiska operationerna har slutförts. Ett exempel börjar på 5:24. Denna LWSS har ingen annan funktion, den förstörs av en båt som det rensar upp, eller en eater. Dess bana visas

.

Efter allt detta är vi kvar med följande tillstånd:

T = närvaron av en LWSS vid T, den formella logiken för detta tillstånd ges av:

T =! notT = G || H = (C & &! S) || (! C & & B)

som du kan läsa som "om pixeln arbetar för närvarande och det inte uppfyller kraven för överlevnad, eller om pixeln är nu död och uppfyller kraven för födelse", i princip om nästa metapixel tillstånd skiljer sig från det aktuella läget blir det en LWSS på T.

LWSS vid T följer sökvägen som visas

. Vid 6:28 kan du se ett exempel på den LWSS förvandlas till en serie av vändningar. Vid 6:39 skjuter ett segelflygplan off som förvandlas till en LWSS att huvuden till sync bufferten och så småningom den cell stat båten lite (annan än C, mer om detta i nästa stycke). Den ursprungliga LWSS fortsätter till vänster, skjuter en annan segelflygplan på 6:44, att skapa en tredje LWSS som huvuden till det nedre högra hörnet av metapixel att växla tillståndet för utdata bildskärm. den ursprungliga LWSS huvuden till det övre vänstra hörnet för metapixel göra samma (mer om detta i nästa avsnitt).

Den cell stat båten lite är vad faktiskt lagrar det aktuella läget i cellen, (C uppdateras med jämna mellanrum baserat på tillståndet i den båt lite). Om båten bit är närvarande, som anger att det aktuella läget för metapixel är "off", inkommande LWSS bildar ett segelflygplan som kolliderar med det och tar bort det (börjar vid 7:03). Om cellen staten båt bit är inte närvarande, som anger att det aktuella läget för metapixel är "på", bildar den inkommande LWSS ett segelflygplan som skapar lite ny båt (börjar vid 18:58).

Slutligen, låt oss följa väg av den ursprungliga LWSS som utlöste hela denna serie av händelser. Det följer yttre sökvägen som visas

, får omvandlas till en MWSS och huvuden mot cell staten båten lite. Om båten lite finns det kolliderar med det och dör, även om det bevarar den båt lite under denna död (3:18). Om båten lite inte finns går oskadd och håller på väg till höger (7:14). Detta är den samma MWSS som gör en moturs slinga runt cellen, utlöser honeybit reaktioner på alla grannar insatsvaror. Denna MWSS är endast tillåten att göra slingan när cellen staten båten lite inte är närvarande, när metapixel är "on". Precis innan det lämnar göra loopen det skjuter ut ett segelflygplan som studsar runt och så småningom sätter en båt vid C (7:20). Vid 7:54 kan du se den sätta igång först av 8 honeybit reaktioner runt metapixel, en för varje Moore granne.

Utdata visas - den sista biten av metapixel är utdata display som använder massor av rymdskepp för att fylla i en stor kvadrat område så det ser mer eller mindre vitt. Två synkroniserade LWSSes växla utdata bildskärm. de kom från den senaste logik mekanism som beskrivs i de föregående punkterna, visas

. Tidpunkten är synkroniserad upp genom en serie av

, då de används för att växla aktiverar en HWSS pistol som utlöser en serie av LWSS "out of the blue" reaktioner. Strömmar av LWSSes fylla kvadratmeter utrymme och ömsesidigt förinta varandra i mitten av metapixel, visas

. Mekanismerna för båda spärrarna är lik:

Jag har bifogat alla video-filer för detta instructable nedan i fall kompressionen från youtube gör dem svåra att se.