Hoe RuneScape uit 2004 een multiplayer RPG in 56k dial-up paste

Als kind was ik te druk bezig met het plukken van vlas en het doden van goblins om na te denken over de techniek. Het antwoord is echter een aanhoudende, bijna obsessieve oefening in het niet verspillen van bytes. Laten we klikken op een tegel ten noorden van waar we staan en elke byte volgen die van die klik naar de server en vervolgens naar het scherm van een andere speler reist.

Methodologie

De details in dit artikel zijn gebaseerd op een gedecompileerde RuneScape 2-client uit 2004. Codefragmenten zijn ruwe vertalingen van die decompilatie, op sommige plekken opgeschoond voor de leesbaarheid, maar met behoud van de logica.

De kernprincipes zijn niet identiek over alle versies, maar de meeste ervan lopen door van RuneScape Classic (2001) tot het huidige RuneScape 3 en natuurlijk Old School RuneScape.

Beperkingen

Laten we kijken naar de beperkingen waar Jagex destijds mee te maken had:

  • Bandbreedte: Een 56k-modem synchroniseert op 56 kilobits per seconde downstream, en minder upstream, minus protocol-overhead en ruis op de lijn. Reken op ongeveer 5 KB/s download en aanzienlijk minder upload. Breedband was in Britse huishoudens al beschikbaar vanaf 2000, maar pas eind jaren 2000 had de meerderheid van de Britse huishoudens een breedbandverbinding; veel spelers zaten dus nog op dial-up.
  • Java-applet in een browser (2004): Java-applets draaiden in een security sandbox, wat betekende dat er geen toegang was tot raw native sockets en geen UDP. Elke byte reisde over één enkele TCP-verbinding, in de juiste volgorde en met per-segment overhead.
  • Een servercycle van 600ms: De RuneScape-gameserver schrijdt vooruit in discrete cycli (of 'ticks') van ongeveer 600 milliseconden. Elke cyclus moet de server voor elke speler bepalen wat die speler nu kan zien en dit verzenden voordat de volgende cyclus begint.

De encryptielaag

Nadat de login-handshake is voltooid en voordat er game-pakketten worden verzonden, wordt een kleine encryptielaag opgezet. Dit is niet bedoeld om bytes te besparen, maar om de opcode te beschermen, aangezien elk volgend onderdeel van het protocol hierop vertrouwt.

Elk pakket begint met een "opcode"-byte: een klein getal dat aangeeft wat voor soort pakket dit is. Deze opcode (en alleen deze) is versleuteld met een stream-cipher genaamd ISAAC. Er zijn twee streams: één voor verkeer van client naar server, en één voor de tegenovergestelde richting. Beide partijen hebben beide streams nodig.

Beide streams worden gevoed door een gedeelde sleutel van vier integers. De client genereert er twee zelf; de andere twee komen van de server tijdens de handshake. De stream van server naar client gebruikt dezelfde seed, maar met 50 toegevoegd aan elk woord om te voorkomen dat beide richtingen dezelfde keystream delen:

this.outboundCipher = new ISAAC(seed);
for (int index = 0; index < 4; index++) {
    seed[index] += 50;
}
this.inboundCipher = new ISAAC(seed);

Het versleutelen bij verzending is één regel:

public void putOpcode(int opcode) {
    this.putByte(opcode + this.outboundCipher.value());
}

En bij ontvangst het spiegelbeeld:

this.currentOpcode = (this.currentOpcode - this.inboundCipher.value()) & 0xFF;

De rest van het pakket is dus niet versleuteld, alleen de opcode. Omdat de opcode bepaalt hoe de rest van het pakket gelezen moet worden en waar een pakket eindigt, was het versleutelen van deze ene byte de goedkoopste mogelijke verdediging tegen externe packet-parsers.

Een loopverzoek verzenden

Wat gebeurt er als je klikt op een tegel één vakje naar het noorden?

Voordat er netwerkverkeer plaatsvindt, voert de client een breadth-first search (BFS) uit met de lokale collision map om een pad te bepalen. Daarna schrijft de client het pakket voor de server.

Het eerste deel van het pakket is de opcode, gevolgd door een enkele byte die de lengte van het pakketlichaam (body) bevat. Omdat het aantal bytes afhankelijk is van de lengte van het pad, laat deze "lengte-byte" de server weten hoeveel gegevens er gelezen moeten worden. Niet alle pakketten hebben deze byte, alleen die met een variabele grootte.

De startpositie neemt 4 bytes in beslag (twee shorts), elk opeenvolgend waypoint-delta neemt 2 bytes in beslag, en er is een laatste byte voor de status van de Ctrl-toets. De totale body-lengte is dus 4 + 2 * (padLengte - 1) + 1.

this.outboundStream.putOpcode(ClientToServerOpcodes.WALK_TILE);
this.outboundStream.putByte(4 + 2 * (pathLength - 1) + 1);

Het pakket bevat de absolute positie van het eerste waypoint (x en z als shorts van twee bytes), gevolgd door de delta van elk waypoint ten opzichte van het eerste. Dit zijn ondertekende bytes per as, wat ruimt binnen het bereik van -128 tot 127 past, aangezien een enkele klik niet extreem ver weg kan landen.

De keuze om alleen een delta te sturen (2 bytes per stap) in plaats van absolute coördinaten (4 bytes per stap) is het eerste voorbeeld van de netwerkzuinigheid van Jagex. Bij een enkel loop-pakket bespaart dit weinig, maar bij elk extra waypoint wordt 50% bespaard.

int firstX = pathX[0];
int firstZ = pathZ[0];
this.outboundStream.putShort(this.playerPositionX + firstX);
this.outboundStream.putShort(this.playerPositionZ + firstZ);
for (int i = 1; i < pathLength; i++) {
    this.outboundStream.putByte(this.pathX[i] - firstX);
    this.outboundStream.putByte(this.pathZ[i] - firstZ);
}

Om fraude tegen te gaan, varieerde de volgorde waarin de onderdelen van het pakket werden geschreven tussen verschillende versies. Ook werden er "byte-mangling" transformaties toegepast, zoals verschillende endianness of het toevoegen van constante waarden. In bovenstaande code is dit weggelaten voor de helderheid.

Een andere zuinige beslissing is dat pathX en pathZ niet elke tegel in het pad bevatten, maar alleen de hoeken. Het lopen van tien tegels in een rechte lijn verzendt slechts één waypoint: de bestemming. De server weet waar je begon en berekent de lijn zelf.

Het laatste deel van het pakket is een byte die aangeeft of de Ctrl-toets is ingedrukt. In vroege versies was dit voor "force run", in latere versies omkeerde dit de huidige bewegingsmodus.

Layout van een WALK_TILE pakket (één stap):

  • Byte 0: Opcode (versleuteld)
  • Byte 1: Lengte (waarde 5)
  • Byte 2-3: Bestemming X (2-byte short)
  • Byte 4-5: Bestemming Z (2-byte short)
  • Byte 6: Ctrl / Run-toggle
  • Totaal: 7 bytes

Dit pakket wordt ongeveer elke 20ms vanuit de client-stream naar het netwerk gestuurd.

De server ontvangt het verzoek

De hoofdloop van de server wordt ongeveer elke 600ms wakker. Hij leegt de inbound buffers van alle spelers, voert de handlers uit en stelt de updates samen. Een pakket dat net voor een cyclus arriveert, wordt bijna direct verwerkt; een pakket dat net daarna arriveert, wacht bijna 600ms.

Het lezen van het pakket op de server is in feite het omgekeerde van het schrijfproces:

int opcode = player.inboundStream.takeOpcode();
if (opcode == ClientToServerOpcodes.WALK_TILE) {
    int length = player.inboundStream.takeByte();
    int deltaCount = (length - 4 - 1) / 2;
    int[] firstWaypoint = new int[2];
    firstWaypoint[0] = player.inboundStream.takeShort();
    firstWaypoint[1] = player.inboundStream.takeShort();
    int[][] waypointDeltas = new int[deltaCount][2];
    for (int i = 0; i < deltaCount; i++) {
        waypointDeltas[i][0] = player.inboundStream.takeByte();
        waypointDeltas[i][1] = player.inboundStream.takeByte();
    }
    boolean holdingCtrl = player.inboundStream.takeByte() == 1;
    player.processWalkTile(firstWaypoint, waypointDeltas, holdingCtrl);
}

De meeste pakketten hebben echter een vaste lengte en hebben dus geen lengte-marker nodig. Neem bijvoorbeeld het "item on item" pakket (wanneer een speler een voorwerp op een ander gebruikt), dat altijd exact 12 bytes (6 shorts) groot is.

De servercyclus

Een servercyclus bestaat uit de volgende stappen:

  1. Inkomende pakketten lezen.
  2. Spelers verwerken (geplande acties, triggers, beweging, etc.).
  3. Spelersupdates bouwen.
  4. Uitgaande pakketten verzenden (flush).

Spelersupdates

De client houdt een lokale kopie bij van elke speler die hij kan zien. De update-pakketten van de server dienen om deze kopie synchroon te houden. Omdat de client al data heeft, stuurt de server bijna altijd alleen de wijzigingen (deltas). "Geen wijziging" is de goedkoopste staat.

Elke cyclus ontvangt een speler één samengesteld "player update packet". De client verwerkt dit in vier stappen:

private void readPlayerUpdates(Packet packet) {
    packet.accessMode(PacketAccess.BITS);
    this.readLocalPlayer(packet);
    this.readOtherPlayers(packet);
    this.readNewPlayers(packet);
    packet.accessMode(PacketAccess.BYTES);
    this.readPlayerDetails(packet);
}

De eerste drie stappen zijn bit-packed: de stream wordt bit voor bit gelezen in plaats van byte voor byte. Dit is gedaan omdat beweging en registratie zeer frequent voorkomen en weinig data vereisen. De vierde stap is byte-aligned voor rijkere, minder frequente updates.

Stap 1: Lokale speler

Als de lokale speler niet is bewogen en er geen details zijn gewijzigd, is de aanwezigheid in het update-pakket slechts één enkele bit.

Als de speler wel is bewogen, kost dit 7 bits: 1 bit (update nodig), 2 bits (type beweging), 3 bits (richting) en 1 bit (volgen er details?).

Andere types zijn ook goedkoop:

  • Type 0 (geen beweging, wel details): 0 bits payload.
  • Type 2 (rennen): Twee 3-bit richtingen en een detail-flag (7 bits).
  • Type 3 (teleport): Hoogtevlak (2 bits), X en Z coördinaten (7 bits elk), detail-flag en een "jump"-bit (totaal 18 bits).

Stap 2: Gevolgde spelers

Hetzelfde principe geldt voor andere spelers in het zicht. Eerst volgt een 8-bit count (aantal spelers), daarna één bit per bekende speler om aan te geven of er iets is gebeurd. In een menigte van veertig stilstaande spelers kost dit slechts 48 bits (6 bytes) om te bevestigen dat de hele scène statisch is.

Stap 3: Nieuwe spelers in bereik

Wanneer iemand voor het eerst in beeld komt, moet de server deze introduceren:

  • 11-bit speler-ID (waarbij 2047 dient als stop-signaal).
  • 1 bit voor detail-updates.
  • 1 bit voor teleportatie.
  • 10 bits voor de positie.

Relatieve coördinaten: In plaats van absolute wereldcoördinaten (die 32 bits zouden kosten), gebruikt RuneScape relatieve coördinaten. Omdat een speler in beeld maximaal ongeveer 15 tegels verwijderd is, past dit in een signed 5-bit getal (-16 tot +15). De positie van een nieuwe speler kost dus slechts 10 bits (5 per as) in plaats van 32.

De bit-cursor

De methode takeBits houdt de administratie bij. Bits vullen elke byte van boven naar beneden (positie 7 naar 0). Zonder deze bit-cursor zouden acht inactieve spelers acht bytes kosten in plaats van één byte.

Stap 4: Detailwijzigingen van spelers

Deze stap is voor gedetailleerde updates, zoals het uiterlijk. Alleen spelers die in eerdere stappen zijn gemarkeerd met "meer details volgen", worden hier verwerkt.

De update-flags zijn onder andere:

  • Kijkt naar entiteit / Kijkt naar tegel.
  • Geforceerde publieke chat / Normale publieke chat.
  • Animatie / Grafisch effect.
  • Uiterlijk gewijzigd (uitrusting, etc.).
  • Schade opgelopen.
  • Geforceerde beweging langs een pad.

Om bytes te besparen, worden zeven flags in de eerste byte gepakt met een marker-bit. Alleen als deze marker-bit is gezet, wordt er een tweede byte gelezen voor de zeldzamere events.

Uiterlijk-update: De sectie "uiterlijk" is de duurste, met informatie over naam, combat level, uitrusting, kleur, animaties, gender en iconen. Dit kost tussen de 44 en 80 bytes per speler.

Waarom hier geen bit-packing? Bit-packing ruilt CPU-kracht in voor bytes. Dit is zinvol als er veel "slack" (overtollige ruimte) is die zich herhaalt. Bij uiterlijk-updates is er geen kleine default-staat; een update is ofwel aanwezig of niet. Bovendien zijn deze data-blobs op de server vaak gecached als byte-aligned buffers. Een byte-aligned blob is positie-onafhankelijk, waardoor de server deze simpelweg in het pakket kan kopiëren zonder voor elke observer opnieuw bit-verschuivingen uit te voeren.

De bytes op de lijn

Laten we een scenario berekenen: jij zet één stap naar het noorden. Er zijn 20 andere spelers in beeld.

Het update-pakket voor een omstander:

  • Stap 1 (lokale speler): 1 bit (geen beweging)
  • Stap 2 (spelersaantal): 8 bits
  • Stap 2 (jouw stap): 7 bits
  • Stap 2 (19 inactieve spelers): 19 bits
  • Stap 3 (sentinel voor nieuwe spelers): 11 bits
  • Padding voor byte-alignment: 2 bits
  • Totaal: 48 bits = 6 bytes
  • + 1 byte opcode + 2 bytes lengte = 9 bytes totaal.

Voor een enkele stap in een groep van 21 mensen is het antwoord op "wat deed iedereen om me heen?" dus ongeveer 9 bytes. Jouw loopverzoek was 7 bytes; de update terug is ongeveer 9 bytes. 16 bytes round-trip voor één stap.

De algemene les

De RuneScape-client en de server zijn geen twee systemen die berichten uitwisselen; ze werken samen als één systeem dat toevallig is gesplitst over een TCP-verbinding. De efficiëntie komt voort uit gedeelde kennis die nooit over de lijn wordt verzonden:

  • Beide kanten gebruiken dezelfde pathfinder en collision map.
  • Beide kanten zijn het erover eens dat de default staat "niet gewijzigd" is (1 bit).
  • Beide kanten weten dat "zichtbaar" betekent "binnen ~15 tegels" (5 bits per as).
  • Beide kanten gebruiken een vaste tabel voor mogelijke wijzigingen (bitmask).

Het protocol is klein omdat de twee programma's samen zijn geschreven, waarbij het netwerk werd behandeld als een implementatiedetail van één applicatie in plaats van een grens tussen twee systemen.

Moderne webdiensten zijn vaak het tegenovergestelde: losgekoppeld, zelfbeschrijvend en verbose (zoals JSON over HTTP). Dat is geen verspilling, maar een bewuste keuze om onafhankelijk van elkaar updates te kunnen deployen. Echter, voor systemen waar elke byte telt — zoals competitieve shooters of marktdata-feeds — is de strakke, bit-packed benadering van RuneScape nog steeds de standaard.