Deleted User - 308552
Dit is een vertaling van de nieuwste devblog; MPI: Hide'n seek, deze keer is het vooral technisch gepraat over algoritmen, maar we hebben iets gekregen waar we mee kunnen spelen! 
Wat vinden jullie? (en als er fouten in zitten, meld het even)
De afgelopen weken is er steeds meer informatie vrijgegeven over de feature genaamd multiplayer instances. Omdat dit nogal een lange en saaie naam is noemen we het intern ook wel "MPIs". Niet erg creatief, maar de functie is belangrijker dan de vorm.
Vandaag zal ik nog wat extra informatie beschikbaar maken. Zoals we al eerder hebben gezegd, zijn MPIs afgeleid van het huidige fortgevechtsysteem en zijn ze, in de huidige versie, PvE (Player vs Environment) content. In tegenstelling tot fortgevechten kun je op elk gewenst moment deel nemen aan een MPI (zolang je character geen andere dingen aan het doen is). Je kan dit zowel met je vrienden als met willekeurige spelers doen. Momenteel werken we aan een werkend prototype dat één character heeft, naast de spelers: De Beer™. Samengevat, jij en je vrienden slapen in een bos en plotseling verschijnt er een beer! Omdat je een slechte scout bent (anders had je gemerkt dat zijn grot vlak naast je kamp was) moet je je beschermen en tegen de beer vechten. Gelukkig is de beer niet de allerslimste beer en valt hij alleen de dichtstbijzijnde speler aan - maar zijn gebrek aan intelligentie maakt hij goed met zeer sterke aanvallen en hij is nog snel ook!
De kunst van het tekenen
Hoewel ik het verhaal helemaal heb bedacht, het scenario is dat niet en omvat een aantal features (AI iemand?), waar ik het vandaag niet over zal hebben. Een feature die niet in het verhaal voorbij is gekomen maar waar ik het wel over wil hebben zijn de ogen van de beer en de speler. Ik weet zeker dat je prachtige ogen hebt, maar de belangrijkste taak van je ogen is om te zien wat er gebeurt. Fortgevechten hebben al een line of sight, maar deze zijn pre-compiled (berekend per plek) voor elke map omdat de objecten die het beeld blokkeren van te voren bekend zijn en omdat de andere spelers je zicht niet blokkeren.
Dit is anders voor de toekomstige MPI. Elk object zal je beeld blokkeren. Staat er een boom? Dan weet je niet wat er achter staat. Staat er een grote dikke beer op zn achterpoten voor je? Je zal maar aan zijn harige buik moeten wennen, want je zal niets anders kunnen zien. Naast een aantal statische objecten (bv muren, bomen) is er een heleboel beweging gaande wat betekent dat je beeld bijna elke ronde verandert - alles moet in realtime berekend worden.
We hebben dus een algoritme nodig dat berekent wat de spelers wel en niet zien, en dat is waar ik de laatste dagen aan gewerkt heb. Het begon met een kunstklas waarin we mooie lijnen en cirkels tekenden om aan het probleem te wennen. Dit is hoe het eruit ziet als een niet-artistieke software developer gaat tekenen:
Prachtig toch? Ik zou eens aan een meer kunstzinnige carriere moeten denken - in ieder geval weet ik dat ik een alternatief heb. Wat hier belangrijker is is de betekenis van al deze lijnen en hokjes. Omdat ik een aardig iemand ben zal ik je het meteen vertellen. Misschien zie je het niet, maar er zijn verschillende ideeën verborgen in dit plaatje. Bij de eerste heb ik mijn meetkunde-vaardigheden opgegraven en een aantal rechte lijnen met verschillende hoeken ten opzichte van elkaar getekend (verschillende hoeken, waaronder 90, 180 en 360 graden). Onze eerste aanpak was om deze lijnen van een specifiek punt (het oogpunt van de speler) in de richting waarin ze kijken te trekken. Dit staat ook wel bekend als ray tracing. Als een lijn (of straal) een blokkerend object raakt is alles wat zich achter dat object bevindt verborgen. Dit is één aanpak, maar we hebben van het begin af aan ook aan een ander systeem gewerkt wat je in de rechterbovenhoek kan zien.
In plaats van het gebruiken van lijnen kun je over het zichtveld van de speler itereren (testen) en wanneer je een blokkerend object vindt de schaduw van dit object berekenen. Uiteindelijk kun je de resulterende blokjes aan de lijst van verborgen blokjes toevoegen. Wanneer je dit raster weergeeft, controleer je of een hokje in de lijst van de verborgen hokjes staat, waarna je de inhoud wel of niet weergeeft, afhankelijk van de uitkomst. Het algoritme om de schaduw van een object te berekenen is het interessante gedeelte. Het begin was vrij eenvoudig, maar er zijn een heleboel grensgevallen en er zijn nog steeds een aantal bugs aanwezig.
Na het implementeren begonnen we met een ray tracing algoritme. Omdat een lijn niet in een hokje van één bij één past moesten we deze informatie converteren met het Bresenham-algoritme om het effect van de straal op de onderliggende hokjes te projecteren. De code is eenvoudiger, korter en efficienter maar geeft andere resultaten. Hoe kunnen we dan controleren of deze resultaten correct zijn? In het begin was ik niet zo enthousiast over het schrijven van tests voor een visuele feature, dus ik besloot om een simpel, eenvoudig programma te schrijven dat dit visualiseert. Nu het leukste; het is online beschikbaar! Voordat je gaat testen, het is nog niet geoptimaliseerd en eigenlijk alleen maar een bewijs dat het concept werkt (de zichtbare code is echt heel slecht). Het is ook erg traag wanneer het niet met een redelijke computer en in een redelijke browser is geopend (Firefox is hier helaas niet "redelijk", Chrome zou moeten werken).
Space Invaders Incoming!
Een korte uitleg van wat er te zien is en wat je kan doen:
Wanneer je over het raster beweegt is er een rood vakje onder de cursor. Dit is de "speler", van waaruit wordt berekend wat je wel en niet kan zien. Verborgen dingen zijn donkergroen of grijs (bekijk de legenda), licht groen staat voor objecten die het zicht blokkeren en die daardoor een schaduw hebben. De overige (witte) vakjes zijn vakjes die de speler kan zien. Je kan objecten toevoegen en verwijderen door op een vakje te klikken.
Rechts van het raster zijn een paar instellingen die je kan veranderen: een andere richting (standaard 360 graden zicht) en een andere beeldhoek, die het zichtbare gebied vergroot of verkleint. Je kan ook instellen hoe ver de speler kan kijken. De volgende instelling is "Show Shadows", deze werkt alleen wanneer de andere, "Use Ray tracing" niet actief is en laat de berekende schaduw zien. Als je "Use Ray tracing" aanklikt wordt het ray tracing algoritme gebruikt. Als het uit is wordt het "standaard" algoritme gebruikt.
Nou, hier komt-ie: http://map.the-west.de/view.html
Ik heb een behoorlijk aantal doolhof-achtige gebieden gemaakt waar ik doorheen ben "gelopen". Wat hebben jullie gemaakt?
Wat vinden jullie? (en als er fouten in zitten, meld het even
)