Enterprise Forever

:HUN => Programozás => Topic started by: Povi on 2015.February.18. 04:17:07

Title: Életjáték
Post by: Povi on 2015.February.18. 04:17:07

életjáték

(nem tudtam, melyik topikba tegyem, de István random függvénye van benne :-))

space-re új kezdőállást generál

Title: Re:Életjáték
Post by: Povi on 2015.February.19. 02:43:51

itt az újabb verzió

F1 - új kezdőállapot generálása

F2 - Gosper Glider Gun (http://www.conwaylife.com/wiki/Gosper_glider_gun) kezdőállapot

Title: Re:Életjáték
Post by: Povi on 2015.February.20. 02:34:46

kicsit gyorsítottam rajta, és van egy meglepetés az elején :-)

Title: Re:Életjáték
Post by: Povi on 2015.February.20. 02:38:32

beleraktam még az OUT 191,12-t is

nem gondoltam volna, hogy az ennyit gyorsít rajta :-)

Title: Re:Életjáték
Post by: Povi on 2015.February.20. 22:17:20

Gyorsítottam még egy picit rajta :-)

Title: Re:Életjáték
Post by: geco on 2015.February.20. 22:24:47

Quote from: Povi on 2015.February.20. 22:17:20

Gyorsítottam még egy picit rajta :-)

Ha így folytatod, el fog fogyni a kód :D

Title: Re:Életjáték
Post by: Zozosoft on 2015.February.20. 22:32:26

Lehet, hogy hülye ötlet: 256 szín módba kéne átrakni, és lenne piros, zöld, kék faj, ami egymástól függetlenül élne. És ahol egymásra másznak ott új színek látszanának. Még érdekesebb lenne, ha ezek a hibridek is életre kelnének :) Arra gondolok, hogy egy R és G az egymás számára láthatatlan. De ha egy közös kockában keletkezne egy RG, annak innentől mind az R mind a G, és persze az RG is számítani. Amikor szül, akkor RG-t szül.

Title: Re:Életjáték
Post by: Zozosoft on 2015.February.20. 22:36:24

Rakd be majd ide is. (http://enterpriseforever.com/other-topics/conways-game-of-life/)

Title: Re:Életjáték
Post by: Povi on 2015.February.20. 22:37:33

Quote from: Zozosoft on 2015.February.20. 22:36:24

Rakd be majd ide is. (http://enterpriseforever.com/other-topics/conways-game-of-life/)

Nem is tudtam, hogy van már neki topikja... :oops:

Title: Re:Életjáték
Post by: lgb on 2015.February.20. 23:44:44

Quote from: Zozosoft on 2015.February.20. 22:32:26

Lehet, hogy hülye ötlet: 256 szín módba kéne átrakni, és lenne piros, zöld, kék faj, ami egymástól függetlenül élne. És ahol egymásra másznak ott új színek látszanának. Még érdekesebb lenne, ha ezek a hibridek is életre kelnének :) Arra gondolok, hogy egy R és G az egymás számára láthatatlan. De ha egy közös kockában keletkezne egy RG, annak innentől mind az R mind a G, és persze az RG is számítani. Amikor szül, akkor RG-t szül.

Az eredeti Conway-es szabalynal ugye a Moore-szomszedsag alapjan (8 szomszed szamit) a B3/S23 szabaly adja a mukodeset (azaz egy uj sejt szuletesehez - B - 3 szomszed kell, fennmaradasahoz - S - meg 2 vagy 3). Azaz a szuletesnel harmat kene figyelembe venni, mondjuk a szokasos algoritmusok kozott olyanok is vannak, hogy az uj sejt szinte a tobbseg szinevel fog egyezni, stb. Igaz vannak mas erdekes hasonlo algoritmusok, melyek nem az eredeti Conway B3/S23 alapjan mennek, vagy nem a Moore szomszedsag alapjan, esetleg a sejtnek nem csak ket allapota van stb. Szoval a vegtelensegig lehet ezt fokozni, es egesz tudomanya van, pl a "fenysebesseg" jelentese egy ilyen "univerzumban" es hogy az sem lepheto at, ennek bizonyitasa, kulonbozo alakzatok minimum konfiguracioja bizonyos tulajdonsagokkal, miegymas. Nagyon fura, kb kulon tudomany majdnem ...

Pl itt a "seeds" nevu (B2/S szabaly), eleg burjanzo dolgokat hoz letre, mas szempontbol erdekes mint az eredeti B3/S23:

https://www.youtube.com/watch?v=C9LbzI1BnCI (https://www.youtube.com/watch?v=C9LbzI1BnCI)

Most jobb videot errol nem talaltam :-/ Es akkor meg nem is leptunk tobb dimenzioba, vagy pl hasznaltunk hatszogeket inkabb :) Idonkent pl egyes esetekben fraktalokkal valo kapcsolat is kimutathato vagy eppen lathato. Nekem nagyon bejott ez a tema amikor par eve (? lehet regebben, fene tudja mar) beleakadtam ebbe, de erosen absztrakt a dolog a jellegebol adodoan :)

Legjobb lenne olyan, ahol a szabaly beallithato, es a pattern is amibol induljon meg leptetes/folyamatos, ill par fix pelda persze. Az mar tenyleg nagyon cool lenne :)

Title: Re:Életjáték
Post by: endi on 2015.February.20. 23:55:16

az előbbi videóhoz listázta a yutub, durva :D

https://www.youtube.com/watch?v=Tv-z8JEp5NY

emlékszem mikor először lett pc-m, 40Mhz, azonnal ilyesmiket kezdtem programozni, főleg ilyen szín alapú életjátékokat, tökre hasonlók voltak mint ezen a videón

Title: Re:Életjáték
Post by: lgb on 2015.February.21. 00:04:07

Ha mar a tube, a "classic" conway (B3/S23): https://www.youtube.com/watch?v=C2vgICfQawE (https://www.youtube.com/watch?v=C2vgICfQawE)

Title: Re:Életjáték
Post by: Povi on 2015.February.21. 00:54:10

A legdurvább dolog amit láttam, az a turing-gép megépítve életjátékból (persze ez a te általad linkelt videón is ott van).

Közben még találtam optimalizálható dolgokat, úgy hogy biztos fogok feltölteni újabb verziókat (ha unjátok már, akkor is :-)), meg majd tervezek belerakni editor-t és lépésenkénti végrehajtást is.

Title: Re:Életjáték
Post by: IstvanV on 2015.February.21. 16:48:28

80x50 méretű Game of Life 256 színű módban:

[attachurl=1]
[attachurl=2]

Az Esc billentyűre kilép, Space-re pedig új mintát generál. A sebesség 8.3333 (50/6) fps-re korlátozott, ezt az 54. sorban (015Bh címen található érték) lehet módosítani, de csak turbós gépen lenne sokkal gyorsabb.

Ez a változat arra az esetre optimalizált, amikor a cellák nagy része (>= 80%) nem változik, de valószínűleg még lehetne javítani rajta.

Title: Re:Életjáték
Post by: Povi on 2015.February.21. 22:21:00

Quote from: IstvanV on 2015.February.21. 16:48:28

80x50 méretű Game of Life 256 színű módban:

(Attachment Link)
(Attachment Link)

Az Esc billentyűre kilép, Space-re pedig új mintát generál. A sebesség 8.3333 (50/6) fps-re korlátozott, ezt az 54. sorban (015Bh címen található érték) lehet módosítani, de csak turbós gépen lenne sokkal gyorsabb.

Ez a változat arra az esetre optimalizált, amikor a cellák nagy része (>= 80%) nem változik, de valószínűleg még lehetne javítani rajta.

Marha jó lett!
A ruletable dolgot nem értem egyelőre, még bogarászás vár rá... :-)

Tetszik ahogyan megoldottad, hogy kezdéskor csak a cellák negyede lesz élő.

Code: [Select]

        and     3
        cp      3
        sbc     a, a
        inc     a

Én kicsit nyakatekertebben csináltam ugyanezt: :oops:

Code: [Select]

        and     3
        jp      z,elo
        ld      a,255
elo:    inc     a

Title: Re:Életjáték
Post by: IstvanV on 2015.February.21. 23:23:49

Quote from: Povi on 2015.February.21. 22:21:00

Tetszik ahogyan megoldottad, hogy kezdéskor csak a cellák negyede lesz élő.

Ez valójában egyszerűbb is lehetett volna. :oops: Az alábbi rész helyett:

Code: ZiLOG Z80 Assembler

        and     3
        cp      3
        sbc     a, a
        inc     a
        ld      (ix), a
        jr      z, .l3

ez is elég lenne:

Code: ZiLOG Z80 Assembler

        cp      40h                     ; 64 / 256 chance of live cell
        sbc     a, a
        jr      z, .l3

Az IX által mutatott terület írása, és így a regiszter növelése is törölhető, mert ez a puffer a kezdőállapot generálása után azonnal felülíródik a copyPatternBuf rutin hívásával. Így összesen 40 ciklus időt lehetne megtakarítani.

Quote

A ruletable dolgot nem értem egyelőre, még bogarászás vár rá... :-)

A cellák nem csak az aktuális állapotot tárolják (4. bit), hanem azt is, hogy mennyi "élő" szomszédjuk van (0-3. bit). A 32 elemű és 256 byte-ra igazított ruleTable az összes lehetséges értékhez hozzárendelt új állapotot tartalmazza, és ha ez változik, akkor a szomszédos cellákon ennek megfelelően INC/DEC műveletet kell végezni.

Title: Re:Életjáték
Post by: Povi on 2015.February.21. 23:44:30

Quote from: IstvanV on 2015.February.21. 23:23:49

A cellák nem csak az aktuális állapotot tárolják (4. bit), hanem azt is, hogy mennyi "élő" szomszédjuk van (0-3. bit). A 32 elemű és 256 byte-ra igazított ruleTable az összes lehetséges értékhez hozzárendelt új állapotot tartalmazza, és ha ez változik, akkor a szomszédos cellákon ennek megfelelően INC/DEC műveletet kell végezni.

Nem semmi ötlet!

Én a "hagyományos" módszert használom, annyi trükk van benne, hogy a cellák nem folyamatosan vannak eltárolva a memóriában, hanem soronként 256 byte-os határra igazítva. Így a H regiszter a sorra mutat (1..25), az L pedig az oszlopra (1..40). A 0. és 26. sorom cellái mindig halottak, ugyanígy a 0. és 41. oszlopom cellái.
Így legalább nagyon egyszerű a szomszédok megszámolása:

Code: [Select]

; input: pointer to cell in HL
; output: number of neighbours in A
        xor     a
        dec     h
        dec     l
        add     a,(hl)
        inc     l
        add     a,(hl)
        inc     l
        add     a,(hl)
        inc     h
        add     a,(hl)
        inc     h
        add     a,(hl)
        dec     l
        add     a,(hl)
        dec     l
        add     a,(hl)
        dec     h
        add     a,(hl)
        inc     l

Title: Re:Életjáték
Post by: IstvanV on 2015.February.21. 23:56:40

Én egyelőre az egyszerűbb, de lassabb indexelt címzést használtam. :oops: Ennek az elkerülésével még lehetne gyorsítani, de először elsősorban az ötlet kipróbálása volt a cél.

Title: Re:Életjáték
Post by: IstvanV on 2015.February.22. 16:56:08

Továbbfejlesztett és valamivel gyorsabb verzió:

[attachurl=1]
[attachurl=2] (10 fps-re korlátozott sebesség)
[attachurl=3] (25 fps, de ezt 4 MHz-es gépen nem tudja elérni)

Title: Re:Életjáték
Post by: Zozosoft on 2015.February.22. 17:03:49

Quote from: IstvanV on 2015.February.22. 16:56:08

Továbbfejlesztett és valamivel gyorsabb verzió:

Nagyon jók!

Title: Re:Életjáték
Post by: endi on 2015.February.22. 18:02:48

ha már színes, lehetnének szebb színei :)
meg lehetne egy kis hangot adni neki, a cellák értékét kirakni a DA-ra :)

Title: Re:Életjáték
Post by: Povi on 2015.February.22. 23:37:24

Quote from: IstvanV on 2015.February.22. 16:56:08

Továbbfejlesztett és valamivel gyorsabb verzió:

(Attachment Link)
(Attachment Link) (10 fps-re korlátozott sebesség)
(Attachment Link) (25 fps, de ezt 4 MHz-es gépen nem tudja elérni)

Hú, nem semmi!

Jó gyors lett! Hogy méred ki, hogy hány FPS?

Title: Re:Életjáték
Post by: IstvanV on 2015.February.23. 00:29:31

A 10/25 fps csak a video megszakítással időzített maximális sebesség. Az updatePattern rutin tényleges futásideje Lua scripttel mérve kb. 64-140 ms 4 MHz-es gépen, attól függően, hogy mennyi változás van az előző állapothoz képest. Új véletlenszerű minta generálása után az első ~10-12 lépés még lassabb, mint 100 ms, ami 10 fps-hez már elég lenne. 7.12 MHz-es gépen kb. 36 ms a futásidő amikor már csak kevés mozgás van a képen, az első lépés ideje pedig jellemzően 75-80 ms közötti érték.

[attachurl=1]

Title: Re:Életjáték
Post by: IstvanV on 2015.February.23. 15:20:43

Quote from: endi on 2015.February.22. 18:02:48

ha már színes, lehetnének szebb színei :)

A színek véletlenszerűek F8h és FFh között, ezt egyszerű volt megoldani. :oops: Nem tudom, hogyan lehetne lényegesen jobb, de nem lassabb. Néhány lehetséges ötlet:
- más véletlenszerű színek táblázatból választva
- pozíció alapján választott színek (gyakorlatilag egy kis felbontású fix kép, amelynek a pixelei csak az élő celláknál láthatóak)
- a szomszédok száma alapján választott színek, ezt 16 színű karakteres módban lehetne hatékonyan megvalósítani, de akkor felére csökkenne a felbontás

Title: Re:Életjáték
Post by: Povi on 2015.February.23. 20:44:29

Quote from: IstvanV on 2015.February.21. 23:23:49

A 32 elemű és 256 byte-ra igazított ruleTable az összes lehetséges értékhez hozzárendelt új állapotot tartalmazza, és ha ez változik, akkor a szomszédos cellákon ennek megfelelően INC/DEC műveletet kell végezni.

Ezzel a táblázatos módszerrel most fölizgattál... :-D

Este kipróbálom ezt a módszert:

Code: [Select]

; sets next state of cell
; input:    number of neighbours in A
;           pointer to cell in HL
; output:   next state of cell in A
; destroys: DE
        ld      e,a
        ld      d,(hl)
        ld      a,(de)

és a 0x0000 és 0x0100 címeken meg ez lenne:

Code: [Select]

l0000:  db  0,0,0,1,0,0,0,0,0
l0100:  db  0,0,1,1,0,0,0,0,0

kicsit gyorsabb lenne a mostani kódnál: :-)

Code: [Select]

        ld      b,a
        ld      a,1
        dec     b
        dec     b
        dec     b
        jp      z, vege       ; if (b == 3) return alive
        ld      a,(hl)
        inc     b
        jp      z, vege       ; if (b == 2) return A
        xor     a             ; A = dead
vege:

Title: Re:Életjáték
Post by: Povi on 2015.February.23. 22:31:05

megcsináltam, jeletem: működik :-)

még bele hardkódolok egy-két fix mintát, aztán publikálom :-)

pont emiatt szerettem meg az assembly-t hogy ilyen trükkökkel lehet gyorsítani dolgokat... :-)

Title: Re:Életjáték
Post by: IstvanV on 2015.February.24. 00:18:29

A gyorsulás nagy részét valójában azzal értem el, hogy a szomszédos cellákat csak akkor kell újraszámolni, ha változás történik, aminek a valószínűsége általában csak 20% vagy kevesebb (20% körüli az első néhány generációnál, de később ez 10% alá esik). Így egy sor feldolgozása csak ennyi, és még a puffer másolása LDI utasításokkal:

Code: ZiLOG Z80 Assembler

.l1:    ld      c, (hl)
        ld      a, (bc)
        cp      c
        call    nz, toggleCell
        inc     e
        inc     l
        ld      c, (hl)
        ld      a, (bc)
        cp      c
        call    nz, toggleCell
        inc     de
        inc     l
        jp      p, .l1
        ld      l, low patternBuf1
        inc     h

A toggleCell hívásakor már növelni vagy csökkenteni kell a 8 szomszédos cellát, de mivel erre többnyire nincs szükség, ez a megoldás átlagosan gyorsabb már az első generációknál is, amikor még viszonylag sok a mozgás.

Title: Re:Életjáték
Post by: Povi on 2015.February.24. 16:20:51

Találtam egy jó kis cikket az életjáték-algoritmusok optimalizációjáról:
http://www.nondot.org/sabre/Mirrored/GraphicsProgrammingBlackBook/gpbb17.pdf

át kéne mozgatni egy új topikba az életjátékos hozzászólásokat :oops: (ezt én is meg tudom tenni, vagy adminnak kell lenni hozzá?)

Title: Re:Életjáték
Post by: Povi on 2015.February.24. 17:01:50

Quote from: Povi on 2015.February.24. 16:20:51

Találtam egy jó kis cikket az életjáték-algoritmusok optimalizációjáról:
http://www.nondot.org/sabre/Mirrored/GraphicsProgrammingBlackBook/gpbb17.pdf

Ez pont úgy optimalizálja a kódot, mint Istvan ötlete :-)

Title: Re: Életjáték
Post by: lgb on 2015.February.24. 17:06:19

Na megvan, ez volt amit mondtam: http://en.wikipedia.org/wiki/Hashlife (http://en.wikipedia.org/wiki/Hashlife)

Bar sok ertelme nincs (rosszul emlekeztem, hogy hasznos-e "nekunk"), mivel inkabb arra jo, hogy a "tavoli jovobe" pillantson az ember, ami tenyleg brutal lassu lenne elerni meg modern, gyors gepeken is ...

Title: Re: Életjáték
Post by: Povi on 2015.February.25. 01:44:36

Na, itt a végleges programom (ha valakit érdekel :-)) és a forrása is, ami nem olyan szép, főleg, hogy végül nem írtam át a szuper-gyors algoritmusra (azért majd egyszer lehet, hogy megcsinálom), tehát itt minden lépésben összeszámolja az összes cella szomszédját, és a következő állapotot egy táblázatból szedi.

A bejelentkező képről space-szel lehet tovább lépni.
F1-F7-ig vannak minták programozva, F8-ra kilép
F1 - random pattern
F2 - Gosper Glider Gun
F3 - Bottle
F4 - Star
F5 - P54 shuttle (http://www.conwaylife.com/wiki/P54_shuttle)
F6 - Pentadecathlon (http://www.conwaylife.com/wiki/Pentadecathlon)
F7 - Achim's p144 (http://www.conwaylife.com/wiki/Achim%27s_p144)

Title: Re: Életjáték
Post by: Lacika on 2015.February.25. 20:17:01

Szerintem célszerű lenne belerakni a sebességállítás lehetőségét, pl. a + - billentyűkre.
Így egy kicsit gyors (64K-s gépen nagyjából már jó :) ).

Title: Re: Életjáték
Post by: Povi on 2015.February.25. 21:06:40

belerakhatom, ha gondolod... :-) de egyébként pont az volt a célom, hogy minél gyorsabb legyen :mrgreen:

ami még eszembe jutott, hogy léptetni is lehetne, ENTER-rel.

Title: Re: Életjáték
Post by: Lacika on 2015.February.25. 21:30:48

Quote from: Povi on 2015.February.25. 21:06:40

ami még eszembe jutott, hogy léptetni is lehetne, ENTER-rel.

Az is nagyon jó ötlet! Pl. Sebesség állítás 0-tól 9-ig, 0 a léptetős mód

Title: Re: Életjáték
Post by: Povi on 2015.October.13. 15:49:36

nem életjáték, de hasonló: Langton hangyája (https://en.wikipedia.org/wiki/Langton's_ant)

Pascal-ban írva

Title: Re: Életjáték
Post by: Povi on 2017.February.28. 13:32:41

brutál:
életjáték "leprogramozva" életjátékban!
https://www.youtube.com/watch?v=xP5-iIeKXE8&t=1s

szerkesztve: rossz link volt bent

Title: Re: Életjáték
Post by: endi on 2017.February.28. 16:12:59

Quote from: Povi on 2017.February.28. 13:32:41

brutál:
életjáték "leprogramozva" életjátékban!
https://www.youtube.com/watch?v=xP5-iIeKXE8&t=1s

szerkesztve: rossz link volt bent

kb általános iskola eleje óta gondolkodom egy tudományos elméleten, ami pár éve egyre jobban konkréttá is válik a fejemben.
az ilyen videókat nézve mindig elcsodálkozom, hogy ez az elméletem miért nem jutott még másnak eszébe...
persze elárulni nem fogom :)

Title: Re: Életjáték
Post by: szipucsu on 2017.February.28. 21:52:33

Quote from: endi on 2017.February.28. 16:12:59

persze elárulni nem fogom :)

Én sem árulom el, hogy az univerzumot hasonló módon látnánk, mint a videón, ha a Naprendszertől egyre távolodnánk és a galaxishalmazok is összeállnának, meg ami utánuk jön, az is. Készültek ugyan videók erről, de az csak elmélet, és a galaxishalmazok feletti szinten már nem állja meg a helyét. Itt is a videó. (https://www.youtube.com/watch?v=GoW8Tf7hTGA) Kicsit off, de végülis kapcsolódik valamennyire.