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.