Welcome, Guest. Please login or register.


Author Topic: Életjáték (Read 4055 times)

Offline IstvanV

  • EP addict
  • *
  • Posts: 4806
  • OS:
  • Linux Linux
  • Browser:
  • Firefox 35.0 Firefox 35.0
    • View Profile
Re:Életjáték
« Reply #15 on: 2015.February.21. 23:23:49 »
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
  1.         and     3
  2.         cp      3
  3.         sbc     a, a
  4.         inc     a
  5.         ld      (ix), a
  6.         jr      z, .l3
ez is elég lenne:
Code: ZiLOG Z80 Assembler
  1.         cp      40h                     ; 64 / 256 chance of live cell
  2.         sbc     a, a
  3.         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.

Offline Povi

  • EP addict
  • *
  • Posts: 1873
  • Country: hu
  • OS:
  • Windows 7/Server 2008 R2 Windows 7/Server 2008 R2
  • Browser:
  • Firefox 35.0 Firefox 35.0
    • View Profile
    • http://povi.fw.hu
Re:Életjáték
« Reply #16 on: 2015.February.21. 23:44:30 »
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

*** Speicherplatz zu klein

Offline IstvanV

  • EP addict
  • *
  • Posts: 4806
  • OS:
  • Linux Linux
  • Browser:
  • Firefox 35.0 Firefox 35.0
    • View Profile
Re:Életjáték
« Reply #17 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.

Offline IstvanV

  • EP addict
  • *
  • Posts: 4806
  • OS:
  • Linux Linux
  • Browser:
  • Firefox 35.0 Firefox 35.0
    • View Profile
Re:Életjáték
« Reply #18 on: 2015.February.22. 16:56:08 »
Továbbfejlesztett és valamivel gyorsabb verzió:

* gamelife.s (18.54 kB - downloaded 118 times.)
* gamelife.com (1.05 kB. 36x4 - viewed 111 times.)    (10 fps-re korlátozott sebesség)
* gamelife2.com (1.05 kB. 36x4 - viewed 109 times.)    (25 fps, de ezt 4 MHz-es gépen nem tudja elérni)

Online Zozosoft

  • EP addict
  • *
  • Posts: 13521
  • Country: hu
  • OS:
  • Windows 7/Server 2008 R2 Windows 7/Server 2008 R2
  • Browser:
  • Firefox 35.0 Firefox 35.0
    • View Profile
    • http://enterprise.iko.hu/
Re:Életjáték
« Reply #19 on: 2015.February.22. 17:03:49 »
Továbbfejlesztett és valamivel gyorsabb verzió:
Nagyon jók!

Offline endi

  • EP addict
  • *
  • Posts: 7305
  • Country: hu
  • grafikus, játékfejlesztõ, programozás, scifi, tudományok, vallás
  • OS:
  • Windows 7/Server 2008 R2 Windows 7/Server 2008 R2
  • Browser:
  • Chrome 40.0.2214.111 Chrome 40.0.2214.111
    • View Profile
    • Honlapom
Re:Életjáték
« Reply #20 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 :)
Vigyázat! Szektás vagyok! :)

Offline Povi

  • EP addict
  • *
  • Posts: 1873
  • Country: hu
  • OS:
  • Windows 7/Server 2008 R2 Windows 7/Server 2008 R2
  • Browser:
  • Firefox 35.0 Firefox 35.0
    • View Profile
    • http://povi.fw.hu
Re:Életjáték
« Reply #21 on: 2015.February.22. 23:37:24 »
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?
*** Speicherplatz zu klein

Offline IstvanV

  • EP addict
  • *
  • Posts: 4806
  • OS:
  • Linux Linux
  • Browser:
  • Firefox 35.0 Firefox 35.0
    • View Profile
Re:Életjáték
« Reply #22 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.

* timer.lua (0.72 kB - downloaded 115 times.)
« Last Edit: 2015.February.23. 00:32:38 by IstvanV »

Offline IstvanV

  • EP addict
  • *
  • Posts: 4806
  • OS:
  • Linux Linux
  • Browser:
  • Firefox 35.0 Firefox 35.0
    • View Profile
Re:Életjáték
« Reply #23 on: 2015.February.23. 15:20:43 »
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

Offline Povi

  • EP addict
  • *
  • Posts: 1873
  • Country: hu
  • OS:
  • Windows 7/Server 2008 R2 Windows 7/Server 2008 R2
  • Browser:
  • Firefox 35.0 Firefox 35.0
    • View Profile
    • http://povi.fw.hu
Re:Életjáték
« Reply #24 on: 2015.February.23. 20:44:29 »
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:
*** Speicherplatz zu klein

Offline Povi

  • EP addict
  • *
  • Posts: 1873
  • Country: hu
  • OS:
  • Windows 7/Server 2008 R2 Windows 7/Server 2008 R2
  • Browser:
  • Firefox 35.0 Firefox 35.0
    • View Profile
    • http://povi.fw.hu
Re:Életjáték
« Reply #25 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... :-)
*** Speicherplatz zu klein

Offline IstvanV

  • EP addict
  • *
  • Posts: 4806
  • OS:
  • Linux Linux
  • Browser:
  • Firefox 35.0 Firefox 35.0
    • View Profile
Re:Életjáték
« Reply #26 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
  1. .l1:    ld      c, (hl)
  2.         ld      a, (bc)
  3.         cp      c
  4.         call    nz, toggleCell
  5.         inc     e
  6.         inc     l
  7.         ld      c, (hl)
  8.         ld      a, (bc)
  9.         cp      c
  10.         call    nz, toggleCell
  11.         inc     de
  12.         inc     l
  13.         jp      p, .l1
  14.         ld      l, low patternBuf1
  15.         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.

Offline Povi

  • EP addict
  • *
  • Posts: 1873
  • Country: hu
  • OS:
  • Windows 7/Server 2008 R2 Windows 7/Server 2008 R2
  • Browser:
  • Firefox 35.0 Firefox 35.0
    • View Profile
    • http://povi.fw.hu
Re:Életjáték
« Reply #27 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á?)
*** Speicherplatz zu klein

Offline Povi

  • EP addict
  • *
  • Posts: 1873
  • Country: hu
  • OS:
  • Windows 7/Server 2008 R2 Windows 7/Server 2008 R2
  • Browser:
  • Firefox 35.0 Firefox 35.0
    • View Profile
    • http://povi.fw.hu
Re:Életjáték
« Reply #28 on: 2015.February.24. 17:01:50 »
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 :-)
*** Speicherplatz zu klein

Offline lgb

  • EP addict
  • *
  • Posts: 3496
  • Country: hu
  • æðsta yfirmaður
  • OS:
  • Linux (Ubuntu) Linux (Ubuntu)
  • Browser:
  • Firefox 35.0 Firefox 35.0
    • View Profile
    • http://lgb.hu/
Re: Életjáték
« Reply #29 on: 2015.February.24. 17:06:19 »
Na megvan, ez volt amit mondtam: 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 ...