Kruskal's algoritme-doolhofgenerator

Kruskal's algoritme is een minimum spanning tree algoritme dat kan worden aangepast voor het genereren van doolhoven. Het is met name effectief voor het creëren van perfecte doolhoven. Een alternatief voor Kruskal's algoritme is Prim's algoritme, wat ook een minimum spanning tree algoritme is, maar aangezien ze identieke doolhoven genereren en Kruskal's sneller loopt, heb ik de moeite niet genomen om Prim's te implementeren.

Een perfect doolhof is een doolhof waarin er precies één pad is van elk punt in het doolhof naar elk ander punt. Dat betekent dat je geen rondjes kunt lopen, maar dat je vaak op doodlopende paden stuit, waardoor je gedwongen wordt om te keren en terug te gaan.

De doolhofkaarten die hier worden gegenereerd bevatten een standaardversie zonder start- en eindposities, zodat je die zelf kunt bepalen: er is een oplossing van elk punt in het doolhof naar elk ander punt. Als je inspiratie wilt, kun je een voorgestelde start- en eindpositie inschakelen - en zelfs de oplossing tussen die twee bekijken.

Over het algoritme van Kruskal

Kruskal's algoritme werd gecreëerd door Joseph Bernard Kruskal, Jr., een Amerikaanse wiskundige, statisticus en computerwetenschapper. Hij beschreef het algoritme voor het eerst in 1956 in zijn paper "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem."

Het algoritme is ontworpen om de minimale spanningsboom (MST) van een grafiek te vinden, waarbij ervoor wordt gezorgd dat alle hoekpunten met het minimaal mogelijke totale randgewicht zijn verbonden en cycli worden vermeden.

Hoe het algoritme van Kruskal werkt voor het genereren van doolhoven

Stap 1: Initialiseren

• Behandel elke cel in het doolhof als een aparte set (een uniek onderdeel).
• Vermeld alle wanden tussen aangrenzende cellen als potentiële randen.

Stap 2: Muren sorteren

• Schud of orden de muren willekeurig. Als u het implementeert als een echt Kruskal-algoritme, sorteer dan muren in willekeurige volgorde (aangezien doolhofgeneratie geen gewichten vereist).

Stap 3: Muren verwerken

• Herhaal de verplaatste muren.
• Als de twee cellen die door de muur gescheiden worden tot verschillende verzamelingen behoren (dat wil zeggen, ze zijn nog niet met elkaar verbonden in het doolhof), verwijder dan de muur en voeg de verzamelingen samen.
• Als ze al in dezelfde set zitten, sla dan de muur over (om cycli te voorkomen).

Stap 4: Ga door tot voltooiing

• Herhaal dit proces totdat alle cellen met elkaar verbonden zijn en er een enkele overspannende boom ontstaat.
• Uiteindelijk is elke cel met de andere verbonden, zonder lussen of geïsoleerde secties.

Omdat Kruskal's algoritme afhankelijk is van het samenvoegen van sets, kan het worden geoptimaliseerd door het Union-Find-algoritme te gebruiken, dat een efficiënte manier biedt om verbonden cellen te volgen tijdens het genereren van doolhoven. U kunt mijn PHP-implementatie van het Union-Find-algoritme hier bekijken: Disjuncte set (Union-Find-algoritme) in PHP