Kispad

Kispad: közös blog
4230 cikk, 53894 hozzászólás
Szerzők | Tudnivalók | Feedek


Mandelevo 1

Mikolaj cikke a Torokgeek rovatból, 2006. január 17. kedd, 19:43 | 13 hozzászólás

Szeretném egy régóta dédelgetett tervem megvalósulásának legalábbis kezdeti lépéseit, élve az adódott lehetőséggel, közzétenni itt — a kezdetektől mondjuk a kifulladásig. A tervem a következő: képzeljük el Mandelbrot halmazok mint speciális élőlények populációját egy weblapon, melyek kattintásokkal táplálkoznak. Ha valaki megnyitja az oldalt, egy egész csomó Mandelbrot halmazt láthat négyszázszor négyszáz pixeles képek formájában. A látogató a neki leginkább tetszőket megetetheti oly módon, hogy kattintgat rájuk. Ha egy halmaz elér egy bizonyos számú kattintást, utódot hoz létre, de az utód matematikai formulájában születésekor apró mutáció megy végbe, így az újszülött valamelyest különbözni fog szülőjétől. Ha egy halmaz egy meghatározott ideig nem jut táplálékhoz, kimúlik, eltűnik az oldalról. A címben szereplő összetétel a Mandelbrot Evolution rövidítése.

Érzem, hogy ez a téma valószínűleg az öncélú játékokban örömüket lelő, a matematika iránt nyitott programozók érdeklődésére tarthat számot elsősorban. Tudom, hogy sok itt a játékos kedvű programozó, így kicsit azért bízom benne, hogy nem fullad az egész érdektelenségbe rögtön. Fontos még leszögeznem, elébe menve az ilyen jellegű kérdéseknek, hogy az egésznek nincs semmilyen önmagán túlmutató célja, ez egy öncélú játék, semmire sem jó.

Mi a Mandelbrot halmaz? Rövid leszek és pongyola, ezen a ponton nem akarok matematikai részletekbe bocsátkozni — nagyon nem is tudnék, majdnem teljesen laikus vagyok. A Mandelbrot halmaz komplex számok speciális halmaza. A komplex számokat a vektorokhoz hasonlóan képzelhetjük el: van egy valós és egy imaginárius részük, mindkét rész egy valós szám. A komplex számok teljes halmazát számsíknak nevezzük, amely síkon az x koordináta a komplex szám valós, az y az imaginárius része. A komplex számokkal majdnem minden valós számok halmazára is értelmezett művelet elvégezhető, így az összeadás, a szorzás, a hatványozás stb.

Jelöljünk ki a komplex számsíkon egy négyzet alakú területet mondjuk olymódon, hogy a bal felső sarka legyen (-2,2) — ez a koordináta lesz a START mennyiség —, és haladjunk 0.01-enként, ami pedig a STEP. Mivel most négyszázszor négyszáz ponttal dolgozunk, ezért a négyzet jobb alsó sarka a (2,-2) pont (de ennek nem adunk nevet). A négyzet minden egyes pontjára „futtassuk le” a következő algoritmust: vegyünk egy komplex számot (jelöljük Z-vel), emeljük négyzetre, és adjuk hozzá a mi pontunknak megfelelő komplex számot (PIXEL). A kapott eredményt helyettesítsük be az eredeti formulába (Z = Z * Z + PIXEL), újra emeljük négyzetre, és adjuk hozzá PIXEL-t megint. Z első lépésben legyen mondjuk 0 — de lehet persze bármi más is, a lényeg, hogy az induló érték neve INIT. Ismételjük (iteráljuk) ezt a műveletet sokszor, mondjuk maximum MAXITER-szer. A számsíkunkra képzeletben rajzoljunk origó középponttal egy kört, melynek sugara legyen BAILOUT. Ha az iterálás során Z bármikor elhagyja a kör területét (az origótól való távolsága nagyobb lesz mint BAILOUT), befejezhetjük azt, mielőtt eljutnánk MAXITER számú iterációig. Jegyezzük meg, hogy hányadik ismétlésnél léptünk ki a körből (ezt a számot hívjuk NUMITER-nek). Amennyiben eljutunk MAXITER számú ismétlésig, és Z még mindig a körön belül van, úgy az adott pont a Mandelbrot halmazhoz tartozik, ha NUMITER-rel kiléptünk, akkor nem. (A halmazunkat ki is fogjuk színezni, de nem most — erre majd egy későbbi részben térek rá. Itt láthattok példákat Mandelbrot halmaz részletekre és egyéb fraktálokra. )

Tekintsük át a tervet kicsit részletesebben, főleg abból a szempontból, hogy milyen részfeladatokra lehet azt bontani. Ezt a bontást persze leginkább az határozza meg, hogy milyen új ismeretekre és eszközökre van szükségem a megvalósításhoz.

Először kicsit pontosítsuk az algoritmust. Minden halmaz 50 ponttal születik, és óránként veszít egy pontot, a nullát elérve törlődik. Ha viszont összegyűlik száz pontja, létrehozza utódját, amelynek a születés pillanatában átad 50 pontot. Az összes halmaz őse, a játék indulásakor egyedül élő klasszikus Mandelbrot halmaz lesz.

Az alkalmazás legsarkalatosabb pontja talán a halmazok mögötti matematikai formulák kezelése. Dinamikus formula-evaluációt (elnézést ezért) kell megvalósítanunk, illetve formuláink mutálhatóságát is biztosítanunk kell, ezért egy alkalmas formula-reprezentációra van szükségünk. Mindenképpen az xml tűnik a legkézenfekvőbbnek, hiszen egy matematikai formula hierarchikus képződmény, amely képződmények legtermészetesebb módon xml segítségével foghatók meg. Gondolkoztam MathML megoldáson, de úgy vélem, hogy a specifikáció feldolgozása több időt venne igénybe, mint egy saját séma kialakítása. Tehát első lépésben meg kell határoznunk a matematikai formulákban szereplő elemeket, a lehetséges műveletek körét, majd vázolnunk kell a formulákat leíró xml sémát.

Mivel a fraktálok esetében (és a Mandelbrot halmaz egy fraktál) a lebegőpontos műveletek kulcsszerepet játszanak, továbbá legfőképp komplex számokkal fogunk dolgozni, ezért a korábban meghatározott matematikai műveleteket magunknak kell implementálnunk. (Biztos vagyok benne, hogy kevés nyelv nyújt alapból olyan szolgáltatást, mint például komplex számok szinuszának számítása.)

Ezt követően ki kell dolgoznunk a mutációs algoritmus részleteit. Háromféle mutációs lépést tudok elképzelni esetünkben: egy olyat, amely bővíti a formulát (függvénnyel, konstanssal, változóval), egyet, amely szűkíti, és egyet, amely módosítja. Ezek sorban: ADD, SUBS, MOD. Minden mutációkor a három közül az egyik hajtódik végre véletlenszerűen. A teljes formula mutálódhat, illetve ezeken felül a halmaz olyan tulajdonságai is, mint a fent említett START, STEP és INIT. MOD esetén, ha egy konstans értéke változik, akkor az itt alkalmazott képlet: KONSTANS + (KONSTANS * MUTSPEED). A MUTSPEED bizonyos értelemben a változás sebességét szabályozó faktor — maga is a halmaz tulajdonsága, ennek megfelelően szintén mutáció tárgyát képezheti.

Végül ejtenem kell egy-két szót a user interfészről, mely esetünkben, mint írtam, egy webes felület. Ez a lehető legegyszerűbb: a képernyő nagyobb részét az egymás mellett és alatt sorakozó képek foglalják el, mindegyiknél található egy azonosító (vagy esetleg egy „anyakönyvezett” név?), és az aktuális pontszám. Az egeret egy kép fölé húzva a képernyő jobb oldalán, egy keskenyebb hasábban megjelennek az adott halmazra vonatkozó adatok, mint a születés időpontja, az aktuális pontszám, az összes, arra a képre érkezett kattintás száma, a halmaz formulája, és egy link, amely egy új oldalra visz (vagy feldob egy popup ablakot), ahol tanulmányozhatjuk a halmaz leszármazási vonalát.

Kezdésnek ennyi — a következő részben előbb platformot választok, majd belevetem magam a használni kívánt matematikai formulák reprezentálására hivatott xml séma kialakításába.

» Ugorj a hozzászóló ablakhoz

Megosztások Facebookon

Eddigi hozzászólások (13)

1

an, 2006. január 17. kedd, 23:47 (#)

Tamogatom az otletet, szerintem nagyon jo jatek lesz belole! Es egy ido mulva majd mindenkinek lehet szemelyre szabott fraktal-farmja, amit naponta jar "etetni"! Mint a csillagharcost anno ;-)

Komolyra forditva a szot, boldog lennek, ha en is ilyeneket keszithetnek. Az algoritmusrol annyit, hogy szerintem nem erdemes tulzottan bonyolult muveletekbe bocsatkozni (komplex szam szinusza - minek?!) inkabb minel nagyobb foku optimalizalasra torekednek. Bar en programozni csak autodidakta modon tanultam, es azt is sok evvel ezelott, emlekszem hogy asm-ben is le tudtam kodolni a mandel szamito rutinjat - ott pedig frankon csak egesz szamok vannak (voltak, ~286) es megis jo lett.

Hogy vegtelenul hosszura nyujtsam a kommentemet, meg egy par dolog ami eszembe jutott errol. Nem biztos, hogy a mandelbrot halmaz a legmegfelelobb erre a celra, mert valoszinuleg nem eleg latvanyos. Ha szabad javasolnom valamit, akkor a Visions of Chaos nevu kis porgit erdemes lerantani (ha meg van ilyen, ha nem elokeresem) mert azzal nagyon szepen lehet ilyen mutalos dolgokat csinalni, es az megadja a kepleteket is, mindent. Kiindulasi alapnak jo lehet.

Masreszt a 400x400-as halmazok (legalabbis a kepernyon) tul nagyok - 1600x1200-ban max 12 fer ki (bar mar az sem) ami nem tul sok. Ha viszont mondjuk 50%-ra van kicsinyitve, akkor mar egesz sok kiferhet, amitol tenyleg "farm" jellege lesz.

A kattintasos etetes nem rossz otlet, de ha belegondolsz, akkor egy hosszu hetvege alatt siman kihal(hat) az egesz. Inkabb kitalalnek moge egy "bioszferat" akar csak annyival, hogy pl. szumma fix mennyisegu kajat kapnak, de vagy random modon, vagy "megkuzdenek" erte. Persze ezzel mar egesz kozel kerulnel az elet-szimulatorokhoz, ami persze nem feltetlenul rossz. Es a rendszer folyamatosan bovitheto (lasd Darwinia c. jatek hattersztorija-alapotlete).

Remelem ertheto voltam, es koszonom ha valaki vegigolvasta ;-)

2

ant, 2006. január 18. szerda, 00:31 (#)

Ja, es a nevem "ant" ;-)

3

mikolaj, 2006. január 18. szerda, 00:35 (#)

an, köszi az ötleteket és a megjegyzéseket!

a komplex szám szinusza csak azért kell, mert végső soron valahol, egy elvi síkon komplex számokkal dolgozunk, és én úgyterveztem, hogy a képletek alapműveletei az összeadás, szorzás, hatványozás, logaritmus, szinusz, abszolút értek lennének. azért gondoltam így, mert iszonyú sokat játszottam az ultra fractallal anno, és úgy tűnt, hogy a legizgalmasabb formulákat e függvények vég nélküli kombinálásával lehet kihozni. tehát valamelyik szintjén a programnak szerintem implementálni kell egy komplexszám szinusz (meg logaritmus stb.) függvényt, ettőlmég persze igazad van, maga a függvény implementációja használhat akár csak egészeket is.
igen, a mandelbrot halmaz egy idő után annyira nem izgalmas, de csak kiindulási pont, az Ős. mivel pont a formula mutálódna, ezért idővel jól eltávolodnánk ettől.

igazad van teljesen, hogy a 400x400 túl nagy. igazából majd kiderül, hogy mi néz ki a legjobban az oldalon.

a kattintásos dolgon én is sokat törtem a fejem. mondjuk ha valami érdekeset bele akarok látni az egész elképzelésbe, akkor az az, hogy az emberek esztétikai megfontolásai milyen mögöttes matematikai formulákat szelektálnak ki. lehet-e találni valami mintázatot aközött, hogy kinek milyen színek és formák tetszenek, éshogy ezek jellemzően mondjuk a szinusz vagy a logaritmus hatásának eredményei. szóval ezért gondoltam valódi külső mechanizmusra, azaz klikkekre. ha önjáró, önszerveződő ökoszisztémát építenék, azt hiszem nem mandelbrot halmazokkal csinálnám, hanem mondjuk sejtautomatákkal, vagy formális rendszerekben keresnék gödel állításokat valamilyen evolúciós algoritmussal, vagy neurális hálókat eresztenék össze stb.

teljesen érthető voltál, és én köszönöm a támogatást :)

4

mikolaj, 2006. január 18. szerda, 00:37 (#)

ehh, túl későn szóltál a nevedről...

5

NagyGa1, 2006. január 18. szerda, 03:08 (#)

Definiáld légyszi a Mandelbrot halmazt!

Ja, és a komlex számot is.

(;))

6

Toroid, 2006. január 18. szerda, 07:49 (#)

Írod: "egy egész csomó Mandelbrot halmazt láthat négyszázszor négyszáz pixeles képek formájában."

Hát, ekkora képből egy egész csomó nem nagyon fér el egy normál méretű monitoron.

7

eszpee, 2006. január 18. szerda, 09:01 (#)

Két módosító javaslat, egyébként nekem is tetszik az ötlet :)

1. Ez pusztán praktikus: szerintem jobb, ha naponta változik a cucc, nem óránként. Így követhetőbb is, nem kell az addiktoknak 55 percenként felkelni, plusz a szervered se terheli szanaszét a napi egy számolási processz a napi 24-gyel szemben.

2. Egy ötlet, korán van, nem gondoltam végig még, csak zavart az elejétől fogva, hogy nem két egyed szaporodik, és hoz létre utódokat, hanem csak egy. Ezt első pillanatra talán úgy lehetne áthidalni, hogy a látogatók kattintásai növelnék az adott egyed "vonzóságát", majd ha leszáll az éj, a hasonlóan vonzóak választanának partnert, és valamilyen matematikai módszerrel megkeverve örökítenék a paramétereiket. A kevésbé vonzóaknak mondjuk kevésbé lenne esélyük szaporodni, a szebbeknek többször is. A nemeket nem vinném bele, már így is elég bonyolult lenne a kezdeti ötlethez képest... viszont lehetne jó kis családfákat rajzolni. Persze így nem lehet egy egyedből elindulni, muszáj Ádámnál és Évánál kezdeni. :)

Hát így, nagyon bízom benne, hogy meg is valósítod, az én ilyen ötleteim általában lustaságból (az időhiány realisztikusabb megfogalmazása) kifolyólag a kukában végzik.

8

Deansdale, 2006. január 18. szerda, 10:49 (#)

Jövök én is okoskodni :)
Fix növekedés/csökkenés szerintem nem kóser, mert a honlap látogatottságának kis csökkenése végzetes hatású lehet.
Ha pörgősre akarod csinálni az egészet, akkor ki kell jelölni egy határszámot, amit ha klikkelésekben elér egy adott egyed, akkor szaporodik. Az új egyed pedig az addig legkevesebb klikket kapott (sikertelen) egyed helyét foglalja el.
Ha nyugisabbra akarod csinálni, hogy kiforrhassa magát a dolog, akkor érdemesebb lenne 1-3 napos ciklusidőt beállítani, aminek lejártával a legtöbb szavazatot kapott ábra szaporodna a legsikertelenebb kárára.
(Adott IP-ről napi kattintások számát korlátozni kell.)
Ha elkészül és megmondjátok merre van a honlap, akkor felveszem én is a napi rutinba :)
Egyébként nekem első olvasásra egyből az emberek esztétikai érzéke és a képletek közötti összefüggés keresése jött le, a javaslataim erre irányulnak.

ui. Mikolaj, ha minden cikkedből kihagynád a *legelvadultabb* tech/filo 10%-át akkor ezerszer élvezhetőbb lenne... A szőrszálhasogató részletek legfeljebb a nagyon hozzáértőket érdeklik, de azokat sem mindig :P

9

mikolaj, 2006. január 18. szerda, 12:01 (#)

eszpee, az ivaros szaporodásra énis gondoltam, de az inkább egy következő lépcső lehetne, az osztodás sem olyan egyszerű már.

mivel egy mutáció nem feltétlenül eredményez látványos változást, ezért ha napi vagy több napos ciklussal dolgozom órás helyett, akkor unalmas lenne az oldal. szerintem éppen ezért nem kell korlátozni az egy ipről jött kattintások számát sem - ha valaki akarja, akkor futtassa kedvenceit bátran. viszont Deansdale a leggyengébb helyébe lépő újszülött ötlete elgondolkodtatott erősen.

Deansdale, megfontolom a tanácsod. de ebben a postban szándékosan mentem bele a részletekbe - azoknak szántam akiket annyira érdekelhet a dolog, hogy akár együttgondolkodás erejéig is szivesen involválódnak egy ilyen "projektbe". a többinél valszeg igazad van, valószínűleg ez ilyen énblogger szindróma, hogy az ember igyekszik minden gondolatát leírni, figyelmen kívül hagyva az olvasói igényeket vagy nemtudom...

10

Boca, 2006. január 18. szerda, 15:52 (#)

Régen a Fractint-tel szórakoztam órákig, ott is játszottam a paraméterekkel. Az rémlik, h már a 3 alap paraméter apró változtatásával igen sokféle ábra jön ki, így nekem soknak tűnik a képletek ilyen szintű módosítása.
A 400x400 bizonyos értelemben meg kevés. Szép részek veszhetnek el. De hát valahol határt kell húzni, különben nem lesz elég nagy a választék.

11

nyelv-ész, 2006. január 18. szerda, 17:57 (#)

Mikolaj,

Neked a TTC (Tétova Teve Club) nem elég? Mér' akarsz fraktálokat etetni, amikor tevét is etethetsz?

12

Alfi, 2006. január 19. csütörtök, 12:17 (#)

A Mandelbrot-halmaz matematikai és grafikai érzékeltetése után ezt már élőben is lehet látni.
A Hubble Űrtávcső folyamatos fejlesztésével egyre nagyobb és nagyobb felbontású képeket kapunk és simán belelehet menni egy galaxisba és többszintű élményt kapunk.
Innentől kezdve lehet választani a matematikai,grafikai, valós tér-időben látható észlelés és tudatosság között.

13

mikolaj, 2006. február 13. hétfő, 02:52 (#)

frissítettem az http://evolution.labs.hu oldalt. elnézést a szemérmetlen önreklámért, többet nem fogom ideírni, csak gondoltam, hogy mivel igazából most került rá először rendes tartalom, ezért most az egyszer szólok, hátha maradt még itt érdeklődő.


Hozzászólsz?

Igen

Hozzászólást csak névvel együtt fogadunk el. Ha linket írsz be, akkor előtte és utána hagyj egy szóközt, főleg akkor, ha zárójelbe teszed.


Az oldal tetejére | Szerzők, tudnivalók, feedek | sesblog és Kispad © 2003-2010 ervin, eszpee, stsmork