Share
In deze Quick Tip laat ik je zien hoe je het Fisher-Yates shuffle-algoritme implementeert. Als we eenmaal hebben geleerd hoe het werkt, zullen we het gebruiken om een virtueel kaartspel te schudden.
Notitie: Hoewel deze tutorial met JavaScript is geschreven, zou je in bijna elke game-ontwikkelomgeving dezelfde technieken en concepten moeten kunnen gebruiken.
Er zijn verschillende manieren om een reeks elementen in willekeurige volgorde af te spelen, zoals in dit bericht wordt gedemonstreerd. Hoewel dit allemaal geldige opties zijn, is de enige methode die ik altijd heb gebruikt degene die is geïmplementeerd door het Fisher-Yates Shuffle-algoritme.
Ik vind deze methode leuk omdat het een "in-place" shuffle maakt zonder de noodzaak om een nieuwe array te maken (of welke datastructuur dan ook die je toevallig gebruikt).
Als je de Wikipedia-pagina snel hebt doorgelezen, heb je gezien dat er een aantal verschillende methoden voor de implementatie van het algoritme worden genoemd. Degene die we gaan gebruiken, wordt de "Moderne Methode" genoemd:
Een array van een van de n elementen in willekeurige volgorde schudden (indices 0 ... n-1): voor i van (n - 1) tot 1 stel j in op een willekeurig geheel getal met 0 ≤ j ≤ i wissel een [j] en een [i ]
Ik heb een visuele demo samengesteld die de stappen toont die het algoritme neemt. Hopelijk maakt het de bovenstaande uitleg duidelijker:
Dit vertalen naar een voor loop zou er als volgt uitzien:
var someArray = [1,2,3,4,5,6,7,8,9]; var theLength = someArray.length - 1; var toSwap; // De index die we zullen ruilen (dat wil zeggen het willekeurige getal) var temp; // Een tijdelijke variabele die verwijst naar indexvariabele i-punten voor (i = de lengte; i> 0; i--) toSwap = Math.floor (Math.random () * i); temp = someArray [i]; someArray [i] = someArray [toSwap]; someArray [toSwap] = temp;
De reden dat we het nodig hebben temp variabele is omdat we een verwijzing naar het eerste element nodig hebben. Als we geen verwijzing naar het eerste element hadden, zouden we het eerste element verliezen wanneer we het tweede element met het eerste verwisselden. Aangezien het eerste element nu gelijk is aan het tweede, toen we het eerste element verwisselden met het tweede, zou het "het tweede element" zijn, omdat het tweede element nu in de plaats van de eerste staat. Door een verwijzing naar het eerste item te hebben, kunnen we in plaats daarvan het tweede element gelijk aan het stellen.
De bovenstaande demonstratie is leuk voor een visuele weergave van hoe het algoritme werkt, maar om het echt te gebruiken, zullen we het nu gebruiken om een aantal virtuele kaarten in willekeurige volgorde te schudden. Hieronder staat de code.
Accentsconagua
$ (function () var serverString = "http://source.tutsplus.com/gamedev/authors/JamesTyner/FisherYates/src/images/"; var cards = []; var i; for (i = 1; i <= 13; i++) cards.push("c" + i); //console.log(cards); function drawCards() $("#holder").empty(); for (i = 0; i < cards.length; i++) $("#holder").append("
"); drawCards (); $ (" # shuffle "). on ('klik', shuffle); var theLength = cards.length - 1; var toSwap; var tempCard; function shuffle () console.log ( "Kaarten voor shuffle:" + kaarten); voor (i = de lengte; i> 0; i--) toSwap = Math.floor (Math.random () * i); tempCard = kaarten [i]; kaarten [i ] = kaarten [toSwap]; kaarten [toSwap] = tempCard; console.log ("Cards after shuffle:" + cards); drawCards ();); Hier maken we een kaartspel van dertien kaarten en schuifelen ze vervolgens door op de schuifknop te drukken. Het Fisher-Yates Shuffle-algoritme is geïmplementeerd in de shuffle () functie.
Ik heb een nieuwe demo gemaakt om dit in actie te tonen, maar je kunt het ook zelf proberen met de bestanden in de downloadbare items van deze tutorial.
Het Fisher-Yates Shuffle-algoritme is een van de vele manieren om schuifelen binnen uw toepassingen te implementeren. Het is niet nodig om nieuwe arrays te maken, omdat de shuffle op zijn plaats is. Ik ben een groot fan van dit shuffle-algoritme en misschien ben je het nu ook.
Bedankt voor het lezen en ik hoop dat je deze tutorial nuttig hebt gevonden.
"); drawCards (); $ (" # shuffle "). on ('klik', shuffle); var theLength = cards.length - 1; var toSwap; var tempCard; function shuffle () console.log ( "Kaarten voor shuffle:" + kaarten); voor (i = de lengte; i> 0; i--) toSwap = Math.floor (Math.random () * i); tempCard = kaarten [i]; kaarten [i ] = kaarten [toSwap]; kaarten [toSwap] = tempCard; console.log ("Cards after shuffle:" + cards); drawCards (););