Share
I denne Quick Tip, vil jeg vise deg hvordan du implementerer Fisher-Yates shuffle-algoritmen. Når vi har lært hvordan det fungerer, vil vi bruke det til å blande en virtuell kortstokk.
Merk: Selv om denne opplæringen er skrevet med JavaScript, bør du kunne bruke de samme teknikkene og konseptene i nesten hvilket som helst spillutviklingsmiljø.
Det er flere måter å blande et sett med elementer på, som vist i dette innlegget. Selv om det er alle gyldige alternativer, er den ene metoden jeg alltid har brukt, implementert av Fisher-Yates Shuffle Algorithm.
Jeg liker denne metoden fordi den gjør en "in place" shuffle uten å måtte opprette et nytt array (eller hvilken datastruktur du tilfeldigvis bruker).
Hvis du ga Wikipedia-siden en rask gjennomgang, har du sett det nevner et par forskjellige metoder for å implementere algoritmen. Den vi skal bruke, kalles "Modern Method":
For å blande et array a av n elementer (indeks 0 ... n-1): for jeg fra (n - 1) ned til 1 sett j til et tilfeldig tall med 0 ≤ j ≤ jeg bytter a [j] og en [i ]
Jeg har satt sammen en visuell demonstrasjon som viser trinnene algoritmen tar. Forhåpentligvis gjør den ovennevnte forklaring klarere:
Oversette dette til a til loop ville se slik ut:
var noenArray = [1,2,3,4,5,6,7,8,9]; var theLength = someArray.length - 1; var toSwap; // Indeksen vi vil bytte (dvs. tilfeldig tall) var temp; // En midlertidig variabel for å holde referanse til indeksvariabelen jeg peker på for (i = theLength; i> 0; i--) toSwap = Math.floor (Math.random () * i); temp = someArray [i]; someArray [i] = someArray [toSwap]; someArray [toSwap] = temp;
Grunnen til at vi trenger temp variabel er fordi vi trenger referanse til det første elementet. Hvis vi ikke hadde en referanse til det første elementet, da da vi byttet det andre elementet med det første, ville vi miste det første elementet. Siden det første elementet nå tilsvarer det andre, da vi byttet den første med det andre, ville det være "det andre elementet", siden det andre elementet er nå på førsteplassen. Ved å ha en referanse til det første elementet kan vi deretter sette det andre elementet lik det i stedet.
Den ovennevnte demonstrasjonen er hyggelig for en visuell fremstilling av hvordan algoritmen fungerer, men for å sette den til virkelig verdensbruk, vil vi nå bruke den til å blande noen virtuelle kort. Nedenfor er koden.
Accentsconagua
$ (funksjon () var serverString = "http://source.tutsplus.com/gamedev/authors/JamesTyner/FisherYates/src/images/"; var kort = []; var jeg; 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 ") på ('klikk', shuffle); var theLength = cards.length - 1; var toSwap; var tempCard; funksjonshuffle () console.log "Kort før shuffle:" + kort); for (i = theLength; i> 0; i--) toSwap = Math.floor (Math.random () * i); tempCard = kort [i]; kort ] = kort [toSwap]; kort [toSwap] = tempCard; console.log ("Kort etter shuffle:" + kort); drawCards ();); Her lager vi et kort med tretten kort, og deretter blandes dem når shuffle-knappen er trykket. Fisher-Yates Shuffle-algoritmen er implementert i tilfeldig rekkefølge() funksjon.
Jeg har opprettet en annen demo for å vise dette i aksjon, men du kan også prøve det selv med filene som følger med i denne opplæringen, som kan lastes ned.
Fisher-Yates Shuffle-algoritmen er en av flere måter å implementere shuffling i dine applikasjoner. Det er ikke nødvendig å lage nye arrayer, da det gjør shuffle på plass. Jeg er en stor fan av denne shuffle-algoritmen, og kanskje er du nå også.
Takk for at du leser, og jeg håper du har funnet denne opplæringen nyttig.
"; drawCards (); $ (" # shuffle ") på ('klikk', shuffle); var theLength = cards.length - 1; var toSwap; var tempCard; funksjonshuffle () console.log "Kort før shuffle:" + kort); for (i = theLength; i> 0; i--) toSwap = Math.floor (Math.random () * i); tempCard = kort [i]; kort ] = kort [toSwap]; kort [toSwap] = tempCard; console.log ("Kort etter shuffle:" + kort); drawCards (););