Sorozat függvény keresése

Algoritmusok

Adott egy játék (https://portal.gacivs.info), ahol a napokban jutottam el oda, hogy lehet a szárazföldi egységeket vízi járművekkel szállítani, így az élvezhetőbb játékmenet okán az eddigi "egy kontinens" térképgenerálás helyett szigeteket generálok

A szigetek generálása viszonylag egyszerű algoritmus alapján történik, az alábbi ábrán egy négyzet az egy 16x16 csempéből álló térképszelvény, szóval lesznek nagyjából 32x32 csempéből álló nagyobb szigetek, köztük pedig 32 csempéből álló tenger, amelyet néhány kisebb sziget tarkít (a kisebb szigeteket nem ábrázoltam):
https://twitter.com/gacivs/status/686923625140715520

A problémám az, hogy az időben folyamatosan regisztráló játékosokat el kellene helyeznem a szigeteken, némi harc kikényszerítése okán egy szigetre négy játékost kellene tennem, az alábbi két képen ábrázolt algoritmus szerint:
https://twitter.com/gacivs/status/687211310673739776
https://twitter.com/gacivs/status/687208408957620224

Az első lenne jobb, de a második se annyira rossz, csak ott a külsőbb körökön össze tud kerülni több olyan játékos, akik nagyon eltérő fejlettségi szinten vannak... :)

Tegnap óta forgatom az algoritmust, mint medve a sünt, de nem tudtam kitalálni olyan függvényt, amelyik a sorszámból visszaad egy koordinátát... :(

Több szem többet lát: van valami ötletetek? :)

Példa az első ábrára (a szürke négyzet bal alsó koordinátája):

sorszám -> (x,y)
0 -> (1,2)
1 -> (2,2)
2 -> (2,1)
3 -> (1,1)
4 -> (1,-2)
5 -> (2,-2)
...
12 -> (-3,2)
13 -> (-2,2)
...
16 -> (5,6)
17 -> (6,6)
18 -> (6,5)
19 -> (5,5)
20 -> (5,2)
...
24 -> (5,-1)

  • 2224 megtekintés

( fhuse | 2016. 01. 13., sze – 11:27 )

Jól értem, az első ábrát?
0-3 user 1. sziget
4-7 user 2. sziget? stb :)

Mert ha pl sorszámozod szigeteket, akkor nekem ez egy sima egészosztás, az egy szigetre elhelyezendő userkek számával. :)

Nos, a szigeteid - ha jól értem - rácsban vannak.
Ez azt jelenti, hogy 3x3-as esetben így:
012
345
678
Tehát ha tudod a sziget számát (0..8), akkor ha osztod hárommal, megtudod a sorának számát a rácsban. Ha maradékát veszed, akkor tudod, hogy melyik oszlopban van.

Honnan tudod, hogy hányadik sziget: tudod, hogy egy szigeten 4 ország van. Osztod a játékos számát 4-gyel: megvan, hányadik sziget.

Tegyük fel, hogy a szigeteid mérete NxN-es, köztük MxM óceánnal. Akkor egy sziget+óceán mérete (N+M)x(N+M).

Tehát egy sziget bal felső sarkának (N+M)*oszlop, (N+M)*sor

A csigavonal se vészes, nézd az "oldalhosszt". A csigavonal első vonala 2 hosszú balra, aztán 2 le. Utána három hosszú jobbra és 3 fel. Aztán négy balra és le. Aztán öt jobbra és fel.

Mit kell eltárolnod: legutolsó sziget koordinátája, melyik irányban lesz a következő (fel, le, jobbra, balra, hányadik a sorban, hány hosszú a sor. A kód persze gusztustalan lesz :-)

Ez alapján a szigetszámból kijön a koordináta.

( vilmos.nagy | 2016. 01. 13., sze – 15:36 )

első körben a szigetet határoznám meg: leosztanám / 4-gyel, s lefelé kerekítve kapok egy sziget-sorszámot.
nem gondoltam végig, de, nem lenne érdemes megnézni, hogy az adott körben 4^(korszam-1)-től 4^(korszam)-ig lesznek szigetek. Ebből az első negyed a jobb-felső, a második negyed a jobb-alsó, ésígytovább negyedben lesz.

Egy mod 4 megadja, hogy az adott negyedben hanyadik. Ebből számolnék koordinátát, majd a negyed alapján beforgatnám. Ha a mod 4 értéke kissebb, mint a korszám, akkor a felső soron van, a mod 4 értéke oszlopban. Egyébként a korszám oszlopban van, a magasság - mod4 érték sorban.

kicsit kusza, de este lehet leülök egy papír mellé, s kiokoskodom.
--
blogom

Én egy nap után nagyjából az alábbi metódusnál tartok: 


    /**
     * Return the coordinate of the map tile by the sequence.
     *
     * @param sequence the sequence
     * @return the coordinate
     */
    public static Point2D positionBySequence(final Integer sequence) {
        final Integer islandSequence = sequence / 4;
        final Integer side = Double.valueOf(Math.floor(Math.sqrt(islandSequence / 4))).intValue();

        final Integer length = side * 2 + 1;
        final Integer offset = islandSequence - side * side * 4;

        final Integer dx, dy;
        if (offset < length) {
            dx = 0;
            dy = offset;
        } else if (offset < 2 * length) {
            dx = offset - length;
            dy = length;
        } else if (offset < 3 * length) {
            dx = length;
            dy = 3 * length - offset;
        } else {
            dx = 4 * length - offset;
            dy = 0;
        }

        final Integer x = (side - dx) * 4 + sequence % 4 % 2 + 1;
        final Integer y = (side - dy) * 4 + sequence % 4 / 2 + 1;
        return new Point2D(x, y);
    }

Hajlok arra, hogy így marad, de egy szép algoritmus azért érdekelne... :)

( persicsb | 2016. 01. 13., sze – 16:47 )

Legyen a sorszám n.
Jelölje / az egészosztást, % pedig a maradékképzést.

Az, hogy egy szigeten belül hol van, megadja n % 4:
0: (0, 1)
1: (1, 1)
2: (1, 0)
3: (0, 0)
Ez lesz az az offszet, amit a sziget koordinátájához kell hozzáadni, hogy megkapjuk a teljes koordinátát. Jelölje ezt offsetX, offsetY.
Ezt szépen le lehet írni függvénnyel, kis bitbűvészkedéssel:
offsetX = ((((n % 4) / 2) + ((n % 4) % 2)) % 2
offsetY = 1 - (n % 4) / 2

Most már csak az a feladat, hogy megadjuk, hol van a sziget kezdőpontja.
Ez kicsit nehezebb feladat. Mivel egy szigeten 4 emberke van, ezért elég n / 4-nek megadni a sziget koordinátáját, a szigeten belüli koordináta jön az előző lépésből.

Ugyebár a szigetek "gyűrűkbe" vannak helyezve. Számozzuk a gyűrűket is 0-tól.

Az i-edik gyűrűben (2*i+2)^2 - (2*i)^2 = 8*i + 4 elem van, az első elem sorszáma (2*i)^2, az utolsóé (2*i+2)^2 - 1. Az elemek száma mindig osztható néggyel
Azt kell megtalálnunk először, hogy n /4 melyik gyűrűbe esik, azaz melyik az az i, amire (2*i)^2 <= n / 4 <= (2*i+2)^ -1.
Ezt egyrészt megnézheted iteratívan, másrészt megpróbálhatsz rá zárt képletet adni.
4i^2 <= n / 4, ebből következik, hogy i <= sqrt(n) / 4, ez i-re a felső korlát.
0 <= 4*i^2 + 8*i + 3 - n / 4, ebből következik, hogy i értéke a kisebbik gyöktol kisebb, vagy a nagyobbik gyöktol nagyobb kell legyen. A kisebbik gyök negatív, így az korlátot nem ad.
Azaz i > (-8 + sqrt(64-16*(3 - n / 4) ) / 8, ez i-re az egyik alsó korlát.
De nem lehet negatív, i >= 0, ez i-re a másik alsó korlát.

A lehetséges legkisebb i-t keressük, ami megfelelő, azaz az alsó korlátok közül a nagyobbikat kell összehasonlítani a felső korláttal, ebből a kisebbik nyer.
Azaz
i = min(max(0, (-8 + sqrt(64-16*(3 - n / 4) ) / 8), sqrt(n) / 4)

Most jön a kérdés, hogy hol is van a sziget a gyűrűn belül. Ne feledjük, az i-edik gyűrűben 8*i + 4 elem van.
A te leírásod szerint (vagyis a kép szerint) a jobb felső sarokban lévő szigettel kezded a számozást, majd haladsz óramutató járásanak megfelelően.

Az i-edik gyűrű szigeteinek bal alsó sarkai (amihez az offsetet majd adjuk) így néznek ki:
(1, 1), (1, -1), (-1, -1), (-1, 1)
(5, 5), (5, 1), (5, -3), (5, -7), (1, -7), (-3, -7), ....
Hogy jobban lássuk ennek a struktúráját, bontsuk 4 részre ezt:
0-as kvadrans: jobb felső saroktol (beleértve) a jobb alsó sarokig (nem beleértve), x koordinata állando, y 4-gyel csökken
1-es kvadrans: jobb alsó saroktol (beleértve) a bal alsó sarokig (nem beleértve), x koordinata 4-gyel csökken, y állandó
2-es kvadrans: bal alsó saroktol (beleértve) a bal felső sarokig (nem beleértve), x koordinata állando, y 4-gyel növekszik
3-as kvadrans: bal felső saroktol (beleértve) a jobb felső sarokig (nem beleértve), x 4-gyel növekszik, y állandó

Minden egyes kvadránsban a gyűrű elemeinek negyede van, azaz 2 * i + 1 elem. Számozzuk őket j-vel, 0-tól 2*i-ig terjed a koordináta, és mindig 4-gyel csökken.
A kvadránsokban az j-edik elem (sziget bal alsó sarka) koordinátája a következő:
0-as kvadráns: (4 * i + 1, 4 * (i - j) + 1)
1-es kvadráns: (4 * (i - j) + 1, - 4 * i - 3)
2-es kvadráns: (- 4 * i - 3, - 4 * (i - j) - 3)
3-as kvadráns: (- 4 * (i - j) - 3, 4 * i + 1)

Most már csak két dolgot kell tudni. Egyrészt, melyik kvadránsban van n / 4.
Ez pedig nem más, mint
q = (n / 4 - (2 * i)^2) / (2 * i + 1).

Másrészt, hogy az adott kvadránsban hányadik n / 4.
Ne feledjük, a gyűrűben (2*i)^2 es (2*i+2)^2 - 1 közötti elemek vannak. A gyűrűn belül a sziget offsete (n - (2*i)^2) / 4 , ez pedig a (n - (2*i)^2) / 4) % (2 * i + 1) -edik elem a kvadránsban.
j = ((n - (2*i)^2) / 4) % (2 * i + 1)

Példa
n = 20.
i = min(max(0, (-8 + sqrt(64-16*(3 - 5) ) / 8), sqrt(20) / 4) = min(max(0, (-8 + sqrt(96)) / 8), 1) = 1
q = (20 / 4 - (2 * 1)^2) / (2 * 1 + 1). = (5 - 4) / 3 = 1 / 3 = 0
j = ((20 - 4) / 4) % (2 * 1 + 1) = 1 % 3 = 1

Sziget koordináta:
i = 1,
q = 0 (ez adja meg a használandó kvadráns képletet)
j = 1
(4 * 1 + 1, 4 * (1 - 1) + 1) = (5, 1)
Cella offsetek:
offsetX = ((((20 % 4) / 2) + ((20 % 4) % 2)) % 2 = (0 + 0) % 2 = 0
offsetY = 1 - (n % 4) / 2 = 1 - 0 / 2 = 1
Azaz végső koordináta:
(5,1) + (0, 1) = (5, 2)

Kezességet nem vállalok érte, de szerintem működik, ha implementálod a szoftverben, akkor légyszi a nevem említsd meg. Köszi.

Update: gyorsan összedobtam JS-ben.
https://jsfiddle.net/persicsb/8kq3y1d5/3/

Nézzük végig 153-ra:
sequence = 153
islandSequence = 38
side = Double.valueOf(Math.floor(Math.sqrt(9))).intValue(); = 3
length = 3 * 2 + 1 = 7
offset = 38 - 3 * 3 * 4 = 2;
offset < length
dx = 0
dy = 2
x = (side - dx) * 4 + sequence % 4 % 2 + 1 = (3-0)*4 + 1 +1 = 14
y = (side - dy) * 4 + sequence % 4 / 2 + 1 = (3-2)*4 + 0 + 1 = 5;

Az én algoritmusom pedig (14, 10)-et ad.

Vagy számoljuk ki 35-re. A helyes eredmény elvileg (1, -7):
A 20-as alatti szigeten van a 24-27, az alatt a jobb alsósarokban 28-31,
az mellett 32-35, a 35 a bal alsó cella.

A te algoritmusod:
sequence = 35
islandSequence = 35 / 4 = 8
side = Double.valueOf(Math.floor(Math.sqrt(8 / 4 ))).intValue(); = 1
length = side * 2 + 1 = 1 * 2 + 1 = 3
offset = islandSequence - side * side * 4 = 8 - 1*1*4 = 4

offset < length HAMIS
offset < 2 * length IGAZ
dx = offset - length = 4 - 3 = 1
dy = length = 3
x = (side - dx) * 4 + sequence % 4 % 2 + 1 = (1-1)*4 + 1 +1 = 2
y = (side - dy) * 4 + sequence % 4 / 2 + 1 = (1-3)*4 + 1 + 1 = -6;

Ez tuti nem a helyes eredmény.

Az én algoritmusom viszont visszaadja a helyeset.

Szerk: a copy-past miatt elszámoltam, de most már megvan jsfiddle-ben is a te algoritmusod, ellenőrizheted mondjuk 35-re.

https://jsfiddle.net/persicsb/8kq3y1d5/4/

"x = (side - dx) * 4 + sequence % 4 % 2 + 1 = (3-0)*4 + 1 +1 = 14
y = (side - dy) * 4 + sequence % 4 / 2 + 1 = (3-2)*4 + 0 + 1 = 5;

Az én algoritmusom pedig (14, 10)-et ad."

Miből gondolod, hogy jó az algoritmusod? A 38. sziget szerintem az x=13-14 és y=5-6 pozícióban van.

"x = (side - dx) * 4 + sequence % 4 % 2 + 1 = (1-1)*4 + 1 +1 = 2
y = (side - dy) * 4 + sequence % 4 / 2 + 1 = (1-3)*4 + 1 + 1 = -6;"

"Ez tuti nem a helyes eredmény."

De, a 35. játékos ott van valahol azon a szigeten, ami ezen a koordinátán van. Hogy a szigeten belül egészen pontosan milyen pozícióban van, azt had vegyem már figyelmen kívül, teljesen lényegtelen.

A 35-ödik cella bal alsó sarka a z (1, -7). Te egy olyan függvényt kerestél, ami 35-re (1, -7)-et ad vissza, 20-ra (5, 2)-t, stb.

"A 38. sziget szerintem az x=13-14 és y=5-6 pozícióban van."
Most akkor szigeteket, vagy a szigeteken belüli cellákat sorszámozzuk?
Én azt hittem, te az n-edik cellára vagy kíváncsi, hogy az hol van.

Magyarán a 38-as cellád a bal alsó sarka a (13, 5)? Ez az ábrádból kilóg. Míg a csigavonalas szabály szerint ott lesz alul. Méghozzá az alsó sorban a balról második sziget jobb alsó cellájában.
Ennek a (bal alsó sarkának) a koordinátája (te mondtad: "Példa az első ábrára (a szürke négyzet bal alsó koordinátája):"): (-2, -7). Ez nem éppen (13, 5).
A 38-as sziget, meg a 38-as cella megint más.A szigetek számozásáról itt szó nem volt eddig.

Az ábra szerint 1 szigeten (szürke négyzete) van 4 darab cella, és te arra vagy kíváncsi, hogy ha adott egy sorszám, akkor az a cella hol van, melyik koordinátán, ha az ábra szerinti cellaszámozást csináljuk.

"A 35-ödik sziget bal alsó sarka a z (1, -7)."

Valamit keversz... egy sziget, négy játékos. A 35. játékos a 9. szigeten lesz, a 35. sziget pedig valahol a +/+ részen van.

"Most akkor szigeteket, vagy a szigeteken belüli cellákat sorszámozzuk?"

Szigeten belüli cellákat. Csak azért írtam a 38. szigetet, mert azon van a 135. játékos, viszont a 38. sziget nem ott van, ahol a megoldásod sejti. Ezért kérdeztem rá, hogy biztos jó-e az algoritmus...

"Ez az ábrádból kilóg."

Igen, a 38. sziget kilóg. Az ábra ugyanis nem az összes szigetet tartalmazza, csak annyit, amennyi a kérdés megfogalmazásához lényeges volt.

"A szigetek számozásáról itt szó nem volt eddig."

Ó, pedig az 'islandSequence' nevet adtad neki... :)

"Az ábra szerint 1 szigeten (szürke négyzete) van 4 darab cella, és te arra vagy kíváncsi, hogy ha adott egy sorszám, akkor az a cella hol van, melyik koordinátán, ha az ábra szerinti cellaszámozást csináljuk."

Igen. Annyi varianciával, hogy a szigeten belül már nem érdekel, hogy pontosan miképp következnek egymás után a játékosok (tehát a 0-1-2-3 vagy 0-2-1-3 teljesen mindegy).

"Ó, pedig az 'islandSequence' nevet adtad neki... :)"
Ezt a nevet te adtad neki.

"Valamit keversz... egy sziget, négy játékos. A 35. játékos a 9. szigeten lesz, a 35. sziget pedig valahol a +/+ részen van."
A 35-ik sziget valóban ott lesz. És a 35-ik játékos is.
Azonban:
"Csak azért írtam a 38. szigetet, mert azon van a 135. játékos,"
135 / 4 = 33.
A 135-ös játékos a 33-as szigeten van. A 33-as sziget pedig a -/+ részen van.

"Igen. Annyi varianciával, hogy a szigeten belül már nem érdekel, hogy pontosan miképp következnek egymás után a játékosok (tehát a 0-1-2-3 vagy 0-2-1-3 teljesen mindegy)."
Akkor miért is fontos, hogy f(20) = (5,2), f(19) = (5,1), ahogy a grafikád is mutatja?

"Ezt a nevet te adtad neki."

Szóval fogtad a Java nyelvű metódust és újraimplementáltad?! Ott szerepelt időben először ez a kifejezés... :D

"Akkor miért is fontos, hogy f(20) = (5,2), f(19) = (5,1), ahogy a grafikád is mutatja?"

Nem fontos, sehol nem írtam, hogy fontos lenne. Az a fontos, hogy négy (egymás után regisztráló) játékos ugyanazon a szigeten legyen, ne legyen olyan, hogy egy kicsit később regisztráló játékos éppen a kőbaltával ismerkedik, a másik pedig már űrhajót épít, lásd a mellékelt leírást, illetve a második variációt is, ami teljesen más módon teszi le a játékosokat. :)

...no, ki is ment élesbe az új térképgenerálás és az új placement algoritmus, működik.

"Nem fontos, sehol nem írtam, hogy fontos lenne."
Dehogynem, a nyitóposztban a példáknál. Plusz így sorszámoztad be a képet is.

Ezt hogyan máshogyan lehet másképp értelmezni?
"Példa az első ábrára (a szürke négyzet bal alsó koordinátája):

sorszám -> (x,y)
0 -> (1,2)
1 -> (2,2)
2 -> (2,1)
3 -> (1,1)
4 -> (1,-2)
5 -> (2,-2)
...
12 -> (-3,2)
13 -> (-2,2)
...
16 -> (5,6)
17 -> (6,6)
18 -> (6,5)
19 -> (5,5)
20 -> (5,2)
...
24 -> (5,-1)

"

Itt te az egyes, szigeteken belüli cellák sorszám -> koordináta hozzárendelését nem tudtad megoldani. És amit írtál algoritmus, az ennek az adatsornak nem is felel meg.

"Dehogynem, a nyitóposztban a példáknál. Plusz így sorszámoztad be a képet is."

Igen. És leírtam, hogy _mire_ kell... hátha valakinek van jobb ötlete a _problémára_.

"Ezt hogyan máshogyan lehet másképp értelmezni?"

Ettől még jelentős eltérések vannak a két megoldás között, lásd: 153 -> (14,10) és (14,5) megoldás, ami biztos nem azonos sziget... és a rajz alapján a (13-14,5-6) szigeten kell lennie a 153. játékosnak, a (14,10) szerintem nem jó megoldás.