Bjarno Oeyen

A* + Minecraft = ?

Ik speel al een heel lang tijdje Minecraft (als je nog de oude tijden van alpha kent, ja, uit die generatie kom ik, als je het niet kent, ja, zo oud ben ik). De laatste paar maanden draai ik ook mijn eigen privéserver om met enkele vrienden op te spelen. We bouwen al een hele grote tijd aan een gigantische stad. Maar heel dicht bij mijn stad (of moet ik zeggen: onze stad, aangezien ik deze stad met mijn vriendin deel) bij een andere stad lag was er wel nood aan een openbaar vervoersysteem... Dat was in het begin.

We bouwden een treinspoor op een gigantische brug: twee sporen om tweerichtingsverkeer toe te laten (we willen niet dat er carts botsen), en aan elke kunt maken we een stationshalletje (in een berg) met een grenscontrole, de ene al wat uitgebreider dan de andere.

De stad blijft groeien, en naarmate het vordert bouwen we een winkelstraat, een gigantisch dorp voor alleen villagers (met een muur erond), een arena, een kasteel (dat nog steeds niet af is...)... De stad wordt vrij groot. Ook aan de andere kant gaat het verder: een monument, een industrieterrein, een paleis, een rechtbank... De twee steden versmelten niet echt samen omdat er een muur aan is, maar ze worden wel steeds groter. Daarom dat er nood was aan iets extra, en niet alleen meer een treinspoor: een metronetwerk.

Het begon klein: eerst eens een testje of het echt ondergronds moet, konden we niet op de bestaande wegen bouwen? Maar dat zou al snel een soep worden van sporen en wegen, en helemaal niet zo mooi uitkomen. Dus werd de beslissing gemaakt om de meeste sporen ondergronds te laten gaan. Het begon simpel: lijn 1, tussen Terminus (vlakbij het spoorstation) en een tunnel die maanden geleden was uitgegraven, wat verderop. Maar wel met een cirkeltje erond want anders is het ook maar snel gedaan. Een enkele lijn is nog prima te doen, maar al snel bleek dat er nog wel wat lijnen bij mochten komen.

Zo gaat het verder: er komt een nieuwe lijn die boven op een berg een stukje doet, en vervolgens aansluit op het metronet over de grens (een internationaal metronetwerk eigenlijk). Er komen meer haltes bij en ook haltes waar meerdere metrolijnen stoppen.

We zijn nu op een punt gekomen in deze wereld dat er 7 à 8 lijnen (eventueel gedeeltelijk) geplaatst zijn, of gepland zijn. 5 lijnen in Breeg en 3 in Tembië (waarvan 1 gepland zonder haltes).

Ik studeer Computerwetenschappen.
Ik heb de basis van Artificiële intelligentie gezien.
Ik weet hoe routeplanners (kunnen) werken.
Ik krijg het idee om een routeplanner te schrijven voor het metronetwerk.

Ik zat al een tijdje met het idee, maar een paar dagen geleden heb ik dan toch beslist om er eens werk in te steken, en het resultaat mag er zijn (natuurlijk is er nog ruimte voor verbetering, dat is er altijd). Voor het zoekproces te versnellen heb ik gekozen voor A*.

A* is een supersonisch snel algoritme, in deze toepassing kan ik zelf een debugmodus aanzetten en dan zie je heoveel overbodige informatie hij eigenlijk nooit verder genereert. Een halte die verder weg licht in vogelvlucht gaat minder snel gekozen worden op de route. In de meeste situatie's gaat A* er gewoon pijlsnel naartoe. De hele uitleg van A* zal ik jullie besparen, ik ben er zeker van dat er op het internet een betere uitleg te vinden is dan dat ik hier onmogelijk kan geven. Maar om zelf eens volledig A* te schrijven, en dan dit te gebruiken in een applicatie, was wel een leuke ervaring. Het algoritme is niet zo ontzettend moeilijk om te implementeren (het meeste zit dan ook verborgen achter een priority queue).

De routeplanner doet het goed, nu de laatste foutjes eruit zijn gehaald, en overstappen iets zwaarder belast wordt, berekent hij altijd de meest correcte (en aangenaamste route). Het kan zijn dat de spoorweg sneller is, en minder keren stopt aan een halte, maar je moet dan wel overstappen naar een ander station.

Maar genoeg gepraat! Hier is de applicatie.

De code is vrij te vinden en wordt gedistribueerd onder de MIT License.

Reacties op "A* + Minecraft = ?"

Nog geen reacties, waarom laat je er geen achter?

Laat een reactie achter

Naam: Bericht: Bewijs dat je geen robot bent: