Diskussionsforum

Vilka tekniska utmaningar st�lls ni inf�r, hur reagerar ni p� dem osv.? I b�sta fall kan vi byta en del tips.

Sj�lv b�rjar jag med att tala varmt om quad tree!

Quad tree �r anv�ndbart n�r man g�r spatial detektering av saker som �r spridda l�ngs ett plan (t.ex. terr�ng), eftersom man via tr�ddatastrukturen snabbt kommer �t endast de f�rem�l som �r n�rmast. Det funkar genom att dela in terr�ngen i fyra partitioner/rektanglar som vardera refererar t.ex. de polygoner som finns inom varje rektangel. De rektanglar som inneh�ller m�nga polygoner delas p� samma s�tt i �nnu mindre rektanglar tills man n�r en viss uppl�sning.

Jag implementerade quad tree och h�r kommer lite siffror som visar hur v�rt det var i mitt fall. I antal detekteringsanrop kunde det se ut s� h�r, f�r detektion av 3D-figur i en j�mnt f�rdelad terr�ng:

Spelfigur inom partition:
660 calls to "DetectConv( Vector..."
0 calls to "DetectConv( Line..."
36 calls to "DetectArb( Vector..."

Spelfigur mellan tv� partitioner:
1380 calls to "DetectConv( Vector..."
660 calls to "DetectConv( Line..."
72 calls to "DetectArb( Vector..."

Antalet anrop minskade enormt efter att ha delat alla partitioner 3 g�nger, och det h�r var �nd� "brute force" utan vidare optimering:

Spelfigur inom partition:
72 calls to "DetectConv( Vector..."
0 calls to "DetectConv( Line..."
36 calls to "DetectArb( Vector..."

Spelfigur mellan tv� partitioner:
150 calls to "DetectConv( Vector..."
72 calls to "DetectConv( Line..."
72 calls to "DetectArb( Vector..."

Summa kardemumma �r allts� - implementera quad tree! I alla fall om ni har terr�ng med h�g/varierande detaljniv�. Kan ocks� vara intressant att j�mf�ra quad tree med en vanlig grid, som kan vara sv�rare att anpassa till polygoner av olika storlekar som �verlappar partitioner.

Intressant, men jag fattar �nd� inte ett dugg

Finns det h�r p� svenska?

Jajamen, h�r kommer i alla fall lite termer.

Quad tree: "tr�d" som best�r av fyra delar (d�r "tr�d" �r namnet p� en datastruktur, vars delar "f�rgrenar" sig).
Datastruktur: En liten karta som beskriver hur man kommer �t v�rden fr�n dataminnet.
Partition: N�r man delar n�t i mindre delar.
Calls: Anrop (n�r datorn h�mtar/g�r en enskild funktion, t ex. en ber�kning, eller som ovan en s�kning efter 3D-ytor).
Conv = Convex: Konvex (i princip ett ut�tbuktande objekt).
Arb = Arbitrary: Godtycklig (i mitt fall en r�ra av polygoner som kan vara formad som man tycker att den ska vara *).

* Det �r endast i vissa fall inom detektering som objekt kan vara precis som man tycker, ofta �r man begr�nsad till t.ex. ut�tbuktande objekt (i mitt fall gjorde det att antalet anrop till "DetectConv" (konvexa objekt) �r h�gre �n resten).

Hj�lp, s�ger storykillen. Men vi har ju f�tt ombord ett par ordentliga programmerare nu, s� jag kan ju, eh, h�lsa dem att det h�r �r en bra grej. Kanske f� dem att h�nga i den h�r tr�den �verhuvudtaget kanske - vi kan nog t�nkas ha ett par gemensamma problem.
/Hugo

Spinjump project: quad tree
Har Oct trees n�got att s�tta emot?

Ja, octrees �r �ven b�ttre i vissa fall! N�r man har en h�g 3D-milj� med flera v�ningar/avsatser, eftersom octrees l�ter en partitionera p� h�jden ocks�. B�da strukturerna blir g�rna ganska fina ur en kodsynvinkel, om man g�r koden rekursiv, men jag skulle lyssna med sp�nning p� n�n som gjort p� annat s�tt =)

B�da strukturerna verkar dock funka b�st f�r fasta objekt som terr�ng, och kan vara ol�mpliga n�r det g�ller r�rliga objekt.

mhmmm... porr... eller jag menar datastrukturer
Kan t�nka mig att det beh�vs en del f�r erat/ditt projekt.

I och med att vi har valt att k�ra 2d s� fungerar det mesta r�tt s� bra att k�ra brute-force hitills f�r oss. Men n�r vi n�r gr�nsen f�r att det blir f�r mycket skr�p p� sk�rmen, och det �r dags f�r mig att b�rja optimera. D� ska jag nog dumpa in lite roliga l�sningar h�r.

Det enda jag kan n�mna som har rolig l�sning i v�rat spel �r en scene graf, i och med vi har en hel del hierarkiska relationer, s� k�nde jag att det kan vara r�tt s� trevligt att slippa bry sig om alla relativa f�rflyttningar i varje objekt, s� kan det vara trevligt att anv�nda sig av en scene graf f�r att slippa manuellt f�rflytta alla objekt som �r fastpinnade p� skeppet. K�nns ibland dock lite overkill f�r ett 2d-spel.

Har �verv�gt quad-trees f�r att optimera kollissionsdetekteringen, men som du s�ger, quad-trees �r b�st f�r statiska objekt, och jag tror inte vi kommer ha ett enda statiskt objekt i v�ran v�rld ;) S� f�r se ifall man kan hitta n�gra s�ta l�sningar.

// Markus aka Mackyman

Kan t�nka mig att det kan vara v�rt att bygga om sitt quad tree f�r objekt i realtid om m�ngden detektioner v�ger tyngre �n den minneshantering som "byggandet" kr�vde, fast det �r sv�rt att veta innan man har frame rates att j�mf�ra.

NotLogical: Det enda jag kan n�mna som har rolig l�sning i v�rat spel �r en scene graf, i och med vi har en hel del hierarkiska relationer, s� k�nde jag att det kan vara r�tt s� trevligt att slippa bry sig om alla relativa f�rflyttningar i varje objekt, s� kan det vara trevligt att anv�nda sig av en scene graf f�r att slippa manuellt f�rflytta alla objekt som �r fastpinnade p� skeppet.
Scengraf �r briljant �ven i 2D, vill jag s�ga =)
H�rligt att ha s�na hierarkiska positioner, j�mf�rt med att mixtra med relativa hastigheter (eller v�rre, krafter!)

Sitter och funderar p� p� att faktiskt implementera en quad-tree, har b�rjat f� prestanda problem nu ;) Inte s� kul att k�ra kollision mellan n�rmare 1000 metallflisor som flyger ut med j�mna mellanrum d� man skjuter skepp.

Har ett par id�er om hur man kan implementera n�got quad-tree liknande som jag har funderat p�. K�nns som att man borde kunna anv�nda samma quad-tree f�r klippning ;) S� b�rjar hitta flera anledningar att anv�nda det =)

Men gameplay f�re optimering, s� ska nog satsa p� att f� in mer gameplay innan jag sl�r ig�ng med att g�ra riktigt roliga saker =P

NotLogical: Inte s� kul att k�ra kollision mellan n�rmare 1000 metallflisor som flyger ut med j�mna mellanrum d� man skjuter skepp.
Oj, s� m�nga. Ett tips �r att testa med en enklare grid/matris f�rst d�r man snabbt kan indexera in objekt i "element/kvarter", sen testar man bara kollision f�r varje objekt med dess grannar i "kvarteret".

T�nkte p� att f�rdelen med quad tree �r att den inte tar upp minne d�r det inte finns n�gra objekt, s� om objekten r�r p� sig kan man bli tvungen att �terallokera mycket minne - s� om man f�rallokerar minnet f�r man i praktiken en 2D-matris (vilket kan vara en l�mpligare l�sning i det fallet).

Jag blir m�rkr�dd bara jag h�r allokera minne. Tyv�rr. Men s� �r det.

Hmmm, �r nog inte ett quad-tree jag t�nkt implementera, utan min tanke var att bygga ett tr�d best�ende av partitioneringsnoder.

Man b�rjar sedan med att dela in v�rlden i 4 delar, och l�gger till max 4 barn till varje nod, innan man g�r p� och l�gger p� mer en ny partitioneringsnod som man kan l�gga till fler kollisionsentiteter till... Och sedan testar man kollisionen hierarkiskt mot cirklar som man bygger upp till partioneringsnoderna. Dessa cirklar innesluter alla barn till paritioneringsnoden.

Detta kr�ver inte direkt n�gon omallokering av minnet, men en del skyfflande och jag s�g inget obvius s�tt att bygga om det, som �r effektivt.

Nu n�r jag skriver det och l�ser id�n med att g�ra en matris, s� undrar jag varf�r jag inte t�nkt p� det innan. Det blir skitenkelt att v�lja vilken cell man ska l�gga till en kollisionsentitet i, blir inte m�nga instruktioner f�r att flytta om en entitet till en annan cell =) Och det blir inget direkt minne som beh�ver omallokeras.

Vad irriterad man blir n�r man inte ser en s� sj�lvklar l�sning direkt. ;) S� l�tt att g�ra det on�digt sv�rt f�r sig =P Tackar f�r f�rslaget =)

Cloudius: Jag blir m�rkr�dd bara jag h�r allokera minne. Tyv�rr. Men s� �r det.
Haha, smart minnesallokering �r vackert f�r ens estetiska k�nsla ;)

Jag �r lite nyfiken p� vad andra anv�nder f�r program f�r att formge spelomgivningar?

Ins�g hur omst�ndigt det skulle kunna bli om alla polygoner i omgivningarna ska placeras f�r hand, s� jag spenderade lite energi p� en skr�ddarsydd niv�editor. Ist�llet f�r punkter och polygoner, s� placerar man ut tv�rsnitt som tillsammans formar plattformar, med en kod som genererar polygoner mellan dem. Varje tv�rsnitt (som "st�mplas" ut) ers�tter omkring tio punkter och dubbelt s� m�nga polygoner, vilket f�rst�s underl�ttar.

NotLogical: Haha, smart minnesallokering �r vackert f�r ens estetiska k�nsla ;)
Ja, man kan kanske s�ga att det handlar en del om "konst", n�r spr�ket till�ter s� pass olika stilar av minneshantering.