Google Maps voor een fantasiewereld

Sinds 2005 kan iedereen de wereld verkennen met Google Maps. Op deze digitale kaart staan alle steden en wegen. Je kunt inzoomen, uitzoomen en naar een gebied schuiven. Zelf wilde ik ook zo’n kaart maken voor de Minecraftwereld Wereldbouw, een fantasiewereld bezocht door ruim 7500 verschillende spelers. Spelers kunnen de wereld zelf aanpassen, dus de kaart moest automatisch bijgewerkt worden. Hier volgt een wat technisch verhaal over hoe ik die kaart gemaakt heb, zodat hopelijk anderen die een dergelijk programma willen schrijven er wat aan hebben.

Binnen Minecraft bestaat er al het softwarepakket Dynmap om zoiets te doen. Probleem met Dynmap is alleen dat het berucht is om hoeveel rekenkracht het vereist. Zelfs op (wat ik denk) de lichtste instellingen vertraagde de plugin onze Minecraftserver veels te veel.

Ik begreep niet waarom een simpele 2d kaart zoveel rekenkracht vereiste. Eind januari 2018 besloot ik mijn eigen variant te schrijven. Ik had toen een week vrij; en al snel had ik een programmaatje (een plugin) dat een plaatje kon maken van een gebied van 512 bij 512 blokken, een zogeheten regio.

Ik was online de codebibliotheek Leaflet tegengekomen. Als ik voor elke regio op de server zo’n plaatje kon maken, en die zou opslaan onder de juiste naam, dan zou Leaflet er vanzelf een Google Maps-achtige kaart van maken. Ik wilde de kaart zo simpel mogelijk houden, dus ik besloot een simpele kaart te maken, zonder in- of uitzoomfunctie. Dat kon met deze Leaflet-code:

vvar map = L.map('map__area', {
    crs: L.CRS.Simple,
    zoomControl: false /* Zoomen staat uit, hoeven we geen uitgezoomde plaatjes te tekenen. */
}).setView([0, 0], 1); 
L.tileLayer('/images/world/r.{x}.{y}.jpg', { 
    minZoom: 1, 
    maxZoom: 1, /* Samen met minZoom zorgt dat dat zoomen uit staat. */
    attribution: 'Topographica', 
    tms: false, /* Geen tile map service */
    noWrap: true, 
    continuousWorld: true /* Onze wereld is plat! Deze optie schakelt het Aardse coordinatensysteem uit. */
}).addTo(map); 
Figuur 1: voorbeeld van één tegel van de kaart

Elk stukje van 2×2 blokken wordt weegegeven als 1 pixel. Elke regio kreeg zijn eigen afbeelding, van dus 256 bij 256 pixels. Om opslagruimte te besparen sloeg ik de afbeeldingen op als JPG bestanden. Ik had de JPG-compressie heel hoog gezet, dit bespaarde niet alleen een hoop opslagruimte, maar het voegde wat ruis toe aan de kaart wat er juist wel mooi uit zag.

Met Netty kun je snel een webserver schrijven. Ik bouwde een simpele webserver in bij de plugin. Vervolgens schreef ik code die de een wachtrij maakt van regio’s die moeten worden getekend. Zodra iemand één blok plaatst of sloopt, komt de hele regio in de wachtrij. Zo krijg je een live-kaart. Er is ook een commando om álle regio’s in de wereld in de wachtrij te plaatsen. Op die manier wordt de hele wereld opnieuw getekend.

Omdat Minecraftwerelden groter kunnen zijn dan het aardoppervlak, past de hele wereld onmogelijk in het werkgeheugen. De wereld is daarom opgedeeld in chunks, kolommen van 16 bij 16 blokken. Alleen de chunks waar op dat moment spelers in de buurt zijn worden geladen. Als je de kaart voor het eerst tekent, moeten ook delen van de wereld geladen worden waar nu geen spelers zijn. Om de server niet al te veel te belasten werden hooguit 2 chunks per seconde geladen, en hooguit eentje tegelijkertijd. Omdat er 32 x 32 chunks in een regio zitten (een regio was immers 512 bij 512 blokken), duurde het een aantal minuten voordat de regio getekend was.

Ik was nog niet helemaal tevreden over de kaart. Als één blokje veranderd werd, moest een gebied va 512 bij 512 blokken opnieuw getekend worden, terwijl de rest van de kaart nog gewoon zo kon blijven. Ik bedacht dat het slimmer was om het oude plaatje van de regio opnieuw in te laden en daar alleen de noodzakelijke pixels bij te werken. De rest van het plaatje kon dan zo blijven.

Alleen: iedere keer dat je een JPG laadt en weer opslaat, gaat de kwaliteit achteruit door weer een nieuwe ronde van compressie. Ik zou dus de kaart voortaan als PNG-afbeeldingen moeten opslaan, wat meer opslagruimte zou kosten. Omdat de server toch niet zo druk was, was het geen probleem als de live-kaart zichzelf wat trager bijwerkte. Die twee chunks per seconde die vaak onnodig geladen werden konden de server toch niet deren; voor spelers moeten toch al honderden chunks geladen worden. Ik liet het dus maar bij het oude.

Toen kwam er een update van Minecraft uit, Minecraft 1.14. Opeens werd er rondom elke chunk een bufferzone van negen chunks geladen. Als je één chunk wil laden, worden er dus nog eens 360 chunks geladen… Dit was te zwaar voor de server. Voortaan wilde ik dat alleen nog de chunk waar de speler net iets in heeft gebouwd opnieuw getekend wordt. Deze chunk is dan toch al geladen dankzij die speler, dus dit kost weinig rekenkracht. Ik moest dus nu toch echt over naar PNG afbeeldingen. Als ik toch het opslagsysteem van de kaart aan het aanpassen was, zo bedacht ik, kan ik het ook meteen mogelijk maken om uit te zoomen.

Om uitzoomen toe te staan moet je Leaflet simpelweg afbeeldingen geven op halve resolutie, op kwartresolutie, 1/8-resolutie, enzovoort. De eerste uitgezoomde afbeelding bevat dus 2 bij 2 regio’s. Het programma zo’n afbeelding maken door simpelweg de al getekende afbeeldingen van die regio’s in te laden en te verkleinen.

Wat ik wilde, was dat iedere keer als er op detailniveau de kaart wordt bijgewerkt, dat de uitgezoomde kaarten dan ook worden bijgewerkt. Wat ik echter niet wilde is dat de uitgezoomde plaatjes onnodig vaak worden bijgewerkt. Eigenlijk wil je alle nodige wijzigingen in die vier ingezoomde plaatjes eerst doorvoeren voordat er pas een uitgezoomd plaatje wordt bijgewerkt.

Had ik vroeger een simpele wachtrij met regio’s die opnieuw getekend moesten worden, nu is er een hele boomstructuur opgetuigd. De boomstructuur begint met een “wortel”, waarna alle meest uitgezoomde plaatjes erin staan. Als voorbeeld nemen we het raster in figuur 2.

Het raster bestaat uit vier uitgezoomde regio’s. Elke uitgezoomde regio houdt vervolgens bij welke vier regio’s erin vallen. Die houden op hun beurt weer een lijst bij van alle chunks die nog opnieuw getekend moeten worden. Het programma werkt eerst regio 1, 2, 3 en 4 (zie figuur 2) bij voordat het iets uitgezoomde plaatje maakt van de vier regio’s. Hetzelfde geldt voor de andere drie uitgezoomde plaatjes. Zodra de vier uitgezoomde plaatjes gemaakt zijn, wordt het nog verder uitgezoomde plaatje gemaakt van de 16 regio’s, op basis van de zojuist gemaakte uitgezoomde plaatjes. Zo kun je doorgaan, om zo nog meer zoomniveau’s toe te voegen.

Als een regio net getekend is, en er komt daarna nog een opdracht binnen om een chunk in die regio opnieuw te tekenen, dan is die chunk te laat, en wordt meegenomen bij de volgende keer dat de kaart bijgewerkt wordt. De kaart wordt in principe continue bijgewerkt; zodra alles getekend is begint het programma direct aan een volgende ronde. Om de processor te sparen wordt er wel een vertraging ingevoegd hier.

Al met al kun je met deze boomstructuur efficiënt uitgezoomde kaarten maken. Nadat de wereld voor het eerst getekend is, hoeven er in principe nooit meer chunks geladen te worden om de kaart bij te werken. Alleen waar écht wat veranderd is in Minecraft, wordt de kaart nu opnieuw getekend. In alle andere gevallen worden de oude pixels gewoon gerecycled. 🙂

De code is te vinden op Github.

Geef een reactie