Fog of war

[maniak]

Ik ben wat aan het spelen in C# en ben een soort RTS aan het maken. Op dit moment loop ik tegen een ding aan.

Het idee is dat elke unit van een speler een bepaalde afstand kan kijken. En wat ik nu doe is bij elke tick alle units itereren om te testen welke andere units ze zien. Voor een paar units wil dit nog wel. Maar bij veel units slokt dit alle CPU op.

Nu heb ik het eea gevonden zoals een Quadtree, kd tree, etc.. maar omdat alle units continue in beweging zijn is het telkens opbouwen en/of aanpassen van bv een Quadtree ook redelijk zwaar. Doordat er een verschil zit tussen de afmetingen van een unit en het zicht van de unit moet je voor elke unit een eigen Quadtree opbouwen.

Heeft iemand nog een briljant idee of ervaring hiermee?

Bvd

[Gonadan]

Sowieso events gebruiken?

[maniak]

Gonadan schreef op woensdag 28 december 2016 @ 11:11:
Sowieso events gebruiken?

Events? Ik begrijp je niet. In mijn geval wordt het spel elke 33ms geupdate waarbij alle gamelogic gedaan wordt.

[Mint]

Wat Gonadan bedoelt is dat je eventbased wilt gaan kijken dat er een instance van iets bijgewerkt moet gaan worden in plaats van proactief alle instances aflopen en checken of er misschien iets voor gedaan moet worden. Dat kan enorm schelen in de benodigde resources.

[armageddon_2k1]

maniak schreef op woensdag 28 december 2016 @ 11:10:
Heeft iemand nog een briljant idee of ervaring hiermee?

Bvd

Leuk projectje, waar je zelf veel van kan leren.

Volgens mij zit je op de goede weg en vergis je je in het feit hoe veel rekenwerk een computer aankan. Ik heb een tijdje terug een N-Body physics simulatie gemaakt met behulp van een Barnes-Hut tree die ik elke tick opnieuw opbouwde. Dit deed ik voor 20.000 entities nog makkelijk op 60fps.

Dus begin het eerst te bouwen met een mooie Quad-Tree (of soortgelijks) en kijk dan of je optimalisaties kan maken daarin. De boomstructuur ga je ook nog wel voor andere dingen gebruiken zoals collision detection en weet ik wat nog meer.

Waar je aan kan denken als optimalisaties:
- Is het echt nodig elke tick alle units te updaten? Wat als ze niet bewogen zijn?
- Kan je de tree niet updaten door alleen de relevante wijzigingen door te voeren? (Gerelateerd aan punt 1).

[maniak]

armageddon_2k1 schreef op woensdag 28 december 2016 @ 11:24:
[...]


Leuk projectje, waar je zelf veel van kan leren.

Volgens mij zit je op de goede weg en vergis je je in het feit hoe veel rekenwerk een computer aankan. Ik heb een tijdje terug een N-Body physics simulatie gemaakt met behulp van een Barnes-Hut tree die ik elke tick opnieuw opbouwde. Dit deed ik voor 20.000 entities nog makkelijk op 60fps.

Dus begin het eerst te bouwen met een mooie Quad-Tree (of soortgelijks) en kijk dan of je optimalisaties kan maken daarin. De boomstructuur ga je ook nog wel voor andere dingen gebruiken zoals collision detection en weet ik wat nog meer.

Waar je aan kan denken als optimalisaties:
- Is het echt nodig elke tick alle units te updaten? Wat als ze niet bewogen zijn?
- Kan je de tree niet updaten door alleen de relevante wijzigingen door te voeren? (Gerelateerd aan punt 1).

Dat is ook het idee, leren.. als je al jaren hetzelfde truukje op je werk doet mis je enorm veel.

Die Barnes-Hut, ik lees dat er gebruik gemaakt wordt van een octree? Ik las ergens dat octrees meer voor 3D worden gebruikt en quad-trees voor 2D?

Op dit moment laat ik elke unit continue random bewegen om zo een maximale belasting te krijgen. Ik wil dit eerst gefixed hebben voordat ik verder ga naar de volgende uitdaging. Uiteindelijk moet er ook nog neural nets aan te pas komen

[Gonadan]

maniak schreef op woensdag 28 december 2016 @ 11:20:
Events? Ik begrijp je niet. In mijn geval wordt het spel elke 33ms geupdate waarbij alle gamelogic gedaan wordt.

Een beetje wat mint zegt, waarom alle logica af gaan als dat niet nodig is? FoW behoeft pas een update als een unit verplaatst, daar kan je dus een event aan hangen. Ze verplaatsen echt niet elke paar ms.

[maniak]

Gonadan schreef op woensdag 28 december 2016 @ 11:30:
[...]

Een beetje wat mint zegt, waarom alle logica af gaan als dat niet nodig is? FoW behoeft pas een update als een unit verplaatst, daar kan je dus een event aan hangen. Ze verplaatsen echt niet elke paar ms.

Ook al staat een unit stil (in mijn geval is dit niet het geval) dan kan een andere unit in zijn FoV terecht komen. Daarbij moet je een event ook programmeren en logica meegeven en dit kost dus minstens net zo veel CPU power.

[armageddon_2k1]

maniak schreef op woensdag 28 december 2016 @ 11:29:
[...]


Dat is ook het idee, leren.. als je al jaren hetzelfde truukje op je werk doet mis je enorm veel.

Die Barnes-Hut, ik lees dat er gebruik gemaakt wordt van een octree? Ik las ergens dat octrees meer voor 3D worden gebruikt en quad-trees voor 2D?

Op dit moment laat ik elke unit continue random bewegen om zo een maximale belasting te krijgen. Ik wil dit eerst gefixed hebben voordat ik verder ga naar de volgende uitdaging. Uiteindelijk moet er ook nog neural nets aan te pas komen

Barnes-Hut is 2D maar kan ook 3D zijn. Is een tree dit elke keer de quads opsplits als er een maximale hoeveelheid entities in een quad zit. In mijn geval had ik 1 unit per keer erin. Wikipedia: Barnes–Hut simulation

[PrisonerOfPain]

Meestal, voor entity updates, sla je alleen de center van je object op in de quadtree / grid. Vervolgens zou ik een center + radius check doen voor visibility (misschien gevolgd door een duurdere & accuratere test).

Gonadan schreef op woensdag 28 december 2016 @ 11:11:
Sowieso events gebruiken?

Sowieso niet. Event based gaan heeft best wat overhead die je absoluut niet wilt in een game. Nog los van het feit dat events eigenlijk best een slechte oplossing zijn op architecture niveau omdat je oorzaak & gevolg compleet los koppelt en het daardoor best lastig te volgen is wat er allemaal in je applicatie gebeurt. Zeker als je meerdere honderden entities hebt rondlopen zie je al snel door de bomen het bos niet meer.

[Gonadan]

PrisonerOfPain schreef op woensdag 28 december 2016 @ 11:44:
Sowieso niet. Event based gaan heeft best wat overhead die je absoluut niet wilt in een game.

Dat heeft ook gewoon een breekpunt, maar het was maar een suggestie hoor.

Nog los van het feit dat events eigenlijk best een slechte oplossing zijn op architecture niveau omdat je oorzaak & gevolg compleet los koppelt en het daardoor best lastig te volgen is wat er allemaal in je applicatie gebeurt. Zeker als je meerdere honderden entities hebt rondlopen zie je al snel door de bomen het bos niet meer.

Events zijn inderdaad niet geschikt als je alles continu wilt bijhouden, het is meer bedoeld voor fire and forget. Maar alle logica altijd lineair langs willen lijkt mij dan weer geen fijne architectuur keuze. 't Optimum zal er wel ergens tussen liggen.

[DroogKloot]

Vergeet quadtrees (of uberhaupt trees) en events, *veel* te traag voor een RTS engine die meer te doen heeft dan alleen LOS bijhouden. Construeer in plaats daarvan per speler een 2D grid van uniforme cellen en schrijf de visie-zones (doorgaans cirkels) van de units daarin weg. Iets is zichtbaar voor speler (i) op positie (x,y) als de waarde van de cel waar (x,y) in valt in grid (i) groter is dan 0. De grid resolutie bepaalt zowel performance als nauwkeurigheid.

Optimalisaties kun je aanbrengen door overlappende instanties te combineren, gebruik te maken van batches wiens grootte een functie is van je object-count (bijvoorbeeld bij 100 units alle met id 0 t/m 9 op frame 0 + 10*k behandelen, die met id 1 t/m 19 op frame 1 + 10*k, enz), en over tijd te discretiseren: units hoeven niet elke frame opnieuw bekeken te worden, maar alleen als hun positie "genoeg" veranderd is.

NB: het wordt pas echt interessant wanneer je LOS terrein-afhankelijk wil laten zijn, dan komt raycasting namelijk om de hoek kijken en dat is weer zeer goed paralleliseerbaar.

[maniak]

Kijk.. dit is wat ik nu doe per unit:

code:

foreach (GameObject o in Engine.Storage.GameObjects.Where(pair => pair.Value.Location.IntersectsWith(scanArea)).Select(pair => pair.Value))
                {
                    logicalObject.Owner.KnownMap.UpdateLocation(o);
                }

De IntersectsWith functie is:

code:

public bool IntersectsWith(Rectangle rectangle)
        {
            return rectangle.X2 >= X && rectangle.X <= X2 && rectangle.Y2 >= Y && rectangle.Y <= Y2;
        }

[diondokter]

Misschien is het een idee om de units gewoon zichtbaar te laten en ze te maskeren met een stencil shader.
YouTube: Field of view visualisation (E03: stencil shader)

Dan hoef je niet meer elke tick te kijken of hij zichtbaar is of niet.

(Ik merk nu net op dat je niet hebt gezegd dat je Unity gebruikt... Maar ik ga er toch even van uit )

Daarbij, doe iedereen en jezelf een plezier en limiteer je fps niet tot 30. Als je hem al vast zet, doe het dan op 60.

[maniak]

diondokter schreef op woensdag 28 december 2016 @ 12:49:
Misschien is het een idee om de units gewoon zichtbaar te laten en ze te maskeren met een stencil shader.
YouTube: Field of view visualisation (E03: stencil shader)

Dan hoef je niet meer elke tick te kijken of hij zichtbaar is of niet.

(Ik merk nu net op dat je niet hebt gezegd dat je Unity gebruikt... Maar ik ga er toch even van uit )

Daarbij, doe iedereen en jezelf een plezier en limiteer je fps niet tot 30. Als je hem al vast zet, doe het dan op 60.

Ik gebruik geen Unity, heb zelf een engine gemaakt van de grond op. Oh enne.. Het is een server <> client oplossing. De server update elke 33ms, wat de client doet moet die zelf weten. Op dit moment heb ik een webclient gemaakt die verbinding maakt met de server.

[ Voor 12% gewijzigd door maniak op 28-12-2016 12:56 ]

[diondokter]

maniak schreef op woensdag 28 december 2016 @ 12:55:
[...]

Ik gebruik geen Unity, heb zelf een engine gemaakt van de grond op. Oh enne.. Het is een server <> client oplossing. De server update elke 33ms, wat de client doet moet die zelf weten. Op dit moment heb ik een webclient gemaakt die verbinding maakt met de server.

Ah ok, maar welke api/framework heb je dan gebruikt voor de visuals? Het kan namelijk zijn dat nog steeds wel een stencil shader kan gebruiken. Dit zou dan wel client-side moeten gebeuren wat cheaten weer makkelijker maakt...

Wat misschien wel genoeg optimalisatie is van wat je nu gebruikt is het omzetten van LINQ code naar gewone code. Linq is best wel zwaar.
Probeer dus geen where en select te gebruiken maar gewoon een simpele for-loop.
Dit kan het verschil zijn tussen iets dat 10ms kost en 2ms.

[maniak]

Ik wil geen cheating. Maar ik denk dat ik een oplossing heb, ben het nu aan het implementeren.

Wat ik doe is alle objecten in een sortedlist te zetten waarbij elke element ook een sortedlist in. In de "hoofd" list bevatten alle bestaande horizontale locaties waarbij de child list alle bestaande verticale locaties die bij de horizontale locaties behoren.

Als ik dan wil weten welke units een bepaalde unit ziet begin ik bij de X van de unit en itereer ik vooruit en achteruit net zolang totdat een unit niet meer te zien is. Dan stop ik verder met itereren, immers de opvolgende units zijn ook niet te zien.

In het beste geval hoef ik dan maar 2 units te controleren.

[diondokter]

Maar heeft je fow dan altijd een convexe vorm? Ik kan me voorstellen dat er een gat in het midden valt waar je weer niks kan zien als er geen unit/gebouwen in de buurt zijn. In dat geval werkt jouw oplossing niet.

[Voutloos]

Dion, het topic gaat stiekem niet over de gehele fog of war en wat de menschelijke speler ziet, maar de zichtradius van elke unit op zich.

[Caelorum]

Maar zelfs dan kan de zichtbare omgeving concaaf zijn