Gaming, regular expression og et hobbyprosjekt med millionvis av av sidevisninger i måneden. En nettside for å generere regex til spillet Path of Exile.
poe.re
Sjekk ut nettsiden på https://poe.re og finn kildekoden på github.
Hva er prosjektet?
Hobbyprosjektet mitt er en nettside for å generere regular expressions for spillet Path of Exile. Regular expressions, eller regex, er enkelt forklart er en måte å skrive mønster på som lar deg søke i tekst. Vi kan for eksempel bruke regex til å sjekke om en setning inneholder et av flere søkeord eller at en setning er av en viss lengde. Men hva har det med spillet Path of Exile å gjøre?
Path of Exile er et action-RPG. Du spiller en karakter og målet er å bli sterkere. Du blir sterkere av å drepe monster, og for å bli så sterk som mulig, så raskt som mulig er effektivitet det mange streber etter. Og det er her regex kommer inn i bildet. Spillet har søkefelt med støtte for regex og disse søkefeltene inkluderer butikken som selger nye våpen og rustninger, din personlige kiste som har de tingene du har funnet og en haug med andre ting.
I spillet kan man bruke minutter til å se gjennom gjenstandene manuelt eller så kan man bruke søkefeltet og regex for å få gjenstandene uthevet umiddelbart. Valget er enkelt. Hvertfall for en del av spillerne.
Hva inspirerte deg?
Den originale motivasjonen til nettsiden var at jeg ønsket å bli raskere i spillet. Jeg øvde meg på å spille igjennom så raskt som mulig, men hver gang jeg kom til personen som solgte rustninger brukte jeg flere minutter på å lete etter oppgraderinger. Så jeg lagde en nettside for å generere en søkestreng/regex jeg kunne lime inn.
Etter jeg viste MVPen til et lite community jeg er en del av, kom det mange gode tilbakemeldinger og ønsker til mer funksjonalitet.
Etter to år med oppdateringer, feedback og feature requests har nettsiden gått fra en hvit nettside med minimalt med css og html, til et stort beist med både css, features, 130+ lukkede saker på Github og over 7 millioner sidevisninger det siste året.
Teknisk snacks
Frontend er skrevet i React og hostes på Github Pages som en statisk nettside. Frontend har ikke noen backend, men har et sett med genererte filer som brukes til å slå opp regex basert på det brukeren velger. Disse filene er generert av et program skrevet i Kotlin og oppdateres kun når det kommer endringer i spillet (ca hver 4. mnd). Frontend blir generert på nytt hver fjerde time (github action cronjob) med økonomidata fra en annen nettside. Disse filene blir lagret som json-dumps og inkludert i frontend-bygget. Nettsiden har dynamisk innhold, men ingen backend eller integrasjoner. Dette er gjort for å holde kostnadene nede da Github Pages er gratis å bruke for open source prosjekt, og det å sende 20+ millioner API-kall i måneden ikke er et alternativ.
Søkefeltet i spillet har en karakterbegrensning på 50 som skaper en veldig kul teknisk utfordring. Her er det om å gjort å få så mye regex inn på så lite plass som mulig.
For å finne den korteste mulige regexen for en setning, splittes den opp i substrings og det sjekkes om noen andre setninger inneholder denne. Denne substrengen blir sjekket mot rundt 15000 tekster for å være helt sikker på at vi ikke får noen falske positive matches. Resultatet er er den korteste setningen som kun matcher setningen du sjekker for.
Eksempel:
input: “Monsters reflect 18% of Elemental Damage”,
shortest unique substring: “f el”
input: “Monsters reflect 18% of Physical Damage”,
shortest unique substring: “f ph”For å matche begge disse tekstene blir regexen “f el|f ph”. Den observante leseren vil her se at det finnes en kortere match hvis man ønsker å matche begge setningene. “efl” vil matche begge disse og være betydelig kortere. Å finne løsningen på dette programmatisk er ganske tricky og kan minne litt om boolean satisfiability problem.
Å brute-force en løsning på dette er nesten umulig, men med hjelp av en miks av genererte lookup tables i og en del smart caching kan vi få denne sjekken til å gå relativt kjapt i frontend. Uten lookup tables og caching vil en sjekk av 5 kombinasjoner typisk ta 4-5 sekunder, men ved å hashe input og sjekke mot en lookup table kjører dette på under 1ms. På nettsiden er en del av det som tar tid flyttet fra frontend til algoritmen som bygger optimaliseringstabellen og kjører hver gang en ny oppdatering til spillet kommer. Denne kjøringen bruker rundt 5 minutter på å generere optimaliseringstabellen, men siden denne er statisk og ikke endres ofte er det ikke noe problem.
Status og hva jeg har lært
Det kan være litt krevende å ha et open source-prosjekt med masse brukere som har høye forventninger til nye features og bugfixes, men det er sykt gøy å ha et hobbyprosjekt som blir brukt av så mange andre.
Over det siste året har nettsiden hatt over 7 millioner sidelastninger og i morgen kommer Path of Exile 2! Om noen uker kommer også forhåpentligvis poe2.re.
