Galaxis legenerálás, hogyan?

1. Eltárolod minden létrehozott gömb középpontját és sugarát

2. Amikor generálsz egy következő gömböt, akkor végignézed az eddigi gömböket, és ha az új gömb középpontja valamelyik régi gömb középpontjától vett távolsága < (régi_gömb_sugara + új_gömb_sugara + elvárt_távolság), akkor újragenerálod.

Hasznalhatsz peldaul graph layout algoritmusokat. Ott szokas reszecske taszitas/vonzas szimulaciot hasznalni annak megoldasara, hogy a csucsok ne legyenek egymashoz tul kozel, de tul tavol sem. Ez azt is megoldja, hogy a galaxis kozepen surubben legyenek a gombok.

Itt van egy jo cikk a Wikipedian, ami elmondja, hogy mirol is beszelek. Van egy kep is, ami szerintem pont olyan, mint amilyet te szeretnel generalni.

[link]

Itt van peldaul egy nyilt forrasu JavaScript implementacio

[link]

Ha az elsőnél sokat kell számolni, akkor szerinted a másodiknál keveset???

Az első megoldást úgy tudod optimalizálni, hogy a teret felosztott akkora szegmensekre, amiknek minden oldala a maximális gömbátmérő + a biztonsági távolság. Amikor létrehozol egy új gömböt, azt is eltárolod, hogy melyik szegmensben van. Ellenőrzésnél csak a szomszédos szegmensben lévő gömböket kell ellenőrizned. A végigjárást nem spórolod meg, de a távolságszámítást e legtöbb esetben igen.

A galaxis közepe felé sűrűsödést pedig úgy éred el, hogy nem egyenletes eloszlású véletlen számokat generálsz a helyzetüknek, hanem pl. normál eloszlásút.

#1 vagyok

Igen, lényegében a te gondolatodat tisztáztam le. És scribával egyet értve, nem gondolom, hogy a részecske- és gravitáció szimuláció hatékonyabb lenne, mint egy szimpla O(n)-es számítás. Pláne scriba optimalizálásával. Persze a sűrűsödést lehet, hogy szebben oldja meg a szimuláció. :)

Egyébként az objektumok ADATAINAK legenerálása

(1) pillanatok alatt megvan, tök felesleges a milliszekundumokon aggódni és emiatt elvetni egy egyszerű és triviális megoldást, és

(2) csak 1x kell megcsinálni a játékmenet előtt.

Szerintem az en megoldasom szebb eredmenyt ad, abban viszont valoban igazuk van, hogy sokkal tobb szamitast igenyel. Szerintem ugy kb. 1000-3000 bolygo eseten lehet 2 masodperc alatti generalasi idovel szamolni. Ha ennel tobb kell, akkor lassu lesz.

Viszont, a ket emlitett megoldast kombinalni is lehet, ugyanis az en altalam linkelt megoldas lenyegesen gyorsabb, ha nem kell sokat alakitani az elrendezesen. Vagyis, ha egy masik algoritmussal keszul egy megkozelitoleg jo elrendezes, akkor nagyon-nagyon gyorsan tudja tokeletesiteni.

Az #1. a fapados 'gány' megoldás. A #2. szép. Sokkal szebb és eltszerűbb eredményt fogsz kapni, mint egy teljesen randomizált algoritmussal.

A futási idő szerintem ebben az esetben mellékes. Komoly, nagy méretű modelleket nem szokás on-the-fly generálni:

legnerálod -> eltárolod -> dolgozol vele. Ha újra kell kezdeni visszatöltöd, de nem generálsz minden egyes futtatásnál.