Hey folks I've just implemented an "Opening Hand" preview in the deck builder on my site, which meant having to write a shuffler. I can recall a couple of threads on here about shuffler writing, so I thought I'd post the code for anyone who might find it useful.
I've replaced some stuff that's specific to my implementation with some more generic placeholder functions - you'll have to write your own functions, for example, for getting the list of cards in a deck, and for determining whether a card is a Commander or is in a Sideboard.
I use prototype.js to add things like array iteration and searching to JavaScript, but the code should be easy enough to port to jQuery.js or something similar
Hope someone can get some use out of it. Feedback is welcome
/**
* Deck shuffler object that allows for reshuffling, destructive card draw and resets.
* Sample Usage:
* var shuffler = new Shuffler();
* var openingHand = shuffler.draw(7);
*/
function Shuffler() {
/**
* Holds the unmodified deck.
*/
this.baseDeck = [];
/**
* Holds a copy of the deck from which cards are drawn. Cards are removed when drawn.
*/
this.activeDeck = [];
/**
* populate() creates an array of the cards in the deck, unshuffled, and sets it as
* the value of the baseDeck property.
*/
this.populate = function() {
var bd = [];
var cardNames = listCardsForDeck(); // Placeholder function that you'll need to write
cardNames.each(function(cardName, i) { // [].each() is from prototype.js
// Don't include cards is they're in the sideboard, or are the commander for the
// deck.
// NB: Write your own implementations of isCardSideboard() and isCardCommander()
if (!isCardSideboard(cardName) && !isCardCommander(cardName)) {
// Another placeholder - cardQuantity() gets the number of copies of the card
// in your deck.
var quantity = cardQuantity(cardName);
for (var i = 0; i < quantity; i++) {
// Add this card to the bd[] array once for each copy in the deck
bd.push(cardName);
}
}
});
this.baseDeck = bd;
};
/**
* shuffle() shuffles the baseDeck[] array
*/
this.shuffle = function() {
// Work on a copy of the array, not the original
var bd = this.baseDeck;
// Create a new array in which to put shuffled cards
var sd = [];
/*
* usedIndices is an anonymous object that stores an array of numeric indices
* that correspond to cards in the base deck. Its purpose is to record which
* cards in the base deck have been copied into the shuffled deck, to prevent
* duplicates.
*/
var usedIndices = {
indices: [],
push: function(val) {
this.indices.push(val);
},
contains: function(val) {
var f = this.indices.find(function(el) { // [].find() is from prototype.js
return el == val;
});
return (f != null && f == val);
}
};
// Using a for loop here instead of [].each() because we're interested in the number of
// cards in the deck, not the individual cards in it.
for (var i = 0; i < bd.length; i++) {
// ca is for card
var c = null;
// idx is for index
var idx = null;
// Keep cycling until c is a card, just in case idx goes out of bounds, by some fluke.
while (c == null || c == undefined) {
// Set idx to a random number between 0 and the number of cards in the deck.
// The -1 turns it into a valid array index.
idx = getRandomInRange(0, (bd.length - 1));
while (usedIndices.contains(idx)) { // Has the index been used before?
// Generate another random index
idx = getRandomInRange(0, (bd.length - 1));
} // Keep generating random indexes until you hit one that hasn't been used
// Get the card at idx
c = bd[idx];
}
// Push that random card into the shuffled deck
sd.push(c);
// Record that idx is now a used index, so we don't get that card again
usedIndices.push(idx);
}
// Overwrite baseDeck[] with the shuffled deck.
this.baseDeck = sd;
};
/**
* draw(count) draws a number of cards equal to count from the top of the active deck, removing
* them from the deck in the process.
*/
this.draw = function(count) {
var d = [];
for (var i = 0; (i < count && i < this.activeDeck.length); i++) {
d.push(this.activeDeck.pop());
}
return d;
};
/**
* Resets the deck to the state where no cards have been drawn.
*/
this.reset = function() {
this.activeDeck = this.baseDeck;
}
/**
* Re-populates the deck from the deck list, re-shuffles it, and resets it.
* Use this after modifying your deck.
*/
this.refresh = function() {
this.populate();
this.shuffle();
this.reset();
}
/**
* Bootstrap the Shuffler when it's created - JavaScrip object constructors are just code
* in the main function body!
*/
this.refresh();
}
// Provides random number
function getRandomInRange(min, max) {
return Math.floor(Math.random() * (max - min + 1)) + min;
}
Private Mod Note
():
Rollback Post to RevisionRollBack
Minouris's Library - Collection manager and deck builder. It's nifty - Check it out!
Your shuffle algorithm is not guaranteed to terminate (I hate probabilistic time complexity analysis, so I'm not going to bother doing so, but you're definitely at Ω(n) so you can do better) and uses O(n) additional storage space. The Fisher-Yates shuffle is an in-place algorithm and Durstenfield's improvement on Fisher-Yates runs in O(n) time.
function FisherYatesShuffle(arr) {
'use strict';
var i, j, tmp;
if (!arr) return;
for (i = 0; i < arr.length; i++) {
j = Math.floor(Math.random() * (arr.length - i) + i); // replace with better random number generation if the Math library is insufficient
// need a random integer j such that i <= j < arr.length
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
Math.random is almost guaranteed to introduce a modulo bias and (the browser-dependent implementation of) the RNG most likely doesn't include enough bits of internal state to fully express all possible permutations of the deck. (It's unlikely for an implementation of Math.random to be capable of representing more than ~1.84e19 different sequences of numbers, but a Commander deck has ~9.33e155 different permutations. Even a Limited deck has ~8.15e47 permutations.) That said, Math.random is probably good enough, is extremely likely to be more random than a real persons shuffling the deck, and other solutions are slower, require additional memory, or both.
I also always recommend hoisting your variables manually; the JS engine is going to do this anyway, and it helps make sure you don't get caught by a "gotcha!" caused by the automatic hoisting. That and using strict mode are two main best practices I try to use when writing JS code.
Depending on your use-case, there's also a version of the Fisher-Yates algorithm to both shuffle the array and initialize it at the same time. See Fisher-Yates shuffle#The inside-out algorithm.
Thanks for the feedback I haven't had to do much random stuff before, so I hadn't come across that algorithm... It does make things quite a bit simpler
Private Mod Note
():
Rollback Post to RevisionRollBack
Minouris's Library - Collection manager and deck builder. It's nifty - Check it out!
First, I'm confused on your use for BaseDeck and ActiveDeck.
You start off by making a pristine array of the deck for BaseDeck.
Then, in the shuffler, you set the BaseDeck as the shuffled copy.
Later you make this.ActiveDeck = this.BaseDeck
In fact, this only works because you repopulate.
Once you make this.ActiveDeck = this.BaseDeck, you've made two variables reference the same object.
If you take a look into your variable after drawing a few, I bet you'll find BaseDeck is missing some cards.
I would keep BaseDeck as a pristine copy of what should be in the deck.
BaseDeck is made during populate, and then shuffle sets ActiveDeck.
Thus, if you want to "redraw", you just skip to shuffle then draw.
Basically, you'd populate when the pages is loaded.
After that, you never need to populate again.
Then, whenever you want a new hand, you just .shuffle()
.Reset() wouldn't be needed at all.
-
Your shuffler is also using a lot of unnecessary power.
Once you reach Shuffle(), the deck is already in an array in BaseDeck.
As such, all you need to do is shuffle the array.
This can be done quickly and easily.
Here's the shuffler that I've used previously:
Shuffling Code
function Shuffle(array) {
var x = array.length, y, i;
while (x) {
i = ~~ (Math.random() * x--);
y = array[x];
array[x] = array[i];
array[i] = y;
}
return array;
}
I've tested it extensively, and it shuffles completely randomly.
Switching it into your prototype setup wouldn't be hard.
Going with my previous Pristine/Library setup:
"array" is taken out of parameter, and instead:
var array = [].concat(this.basedeck);
(this keeps basedeck pristine)
instead of returning array, we:
this.activedeck = array;
-
Your draw also seems "overpowered"
If you're not drawing 1 at a time, a simple splice() works.
Also, you're drawing off the bottom of the library with .pop()
this.draw = function(count) {
var d = [];
for (var i = 0; (i < count && i < this.activeDeck.length); i++) {
d.push(this.activeDeck.pop());
}
return d;
};
Your shuffler is also using a lot of unnecessary power.
Once you reach Shuffle(), the deck is already in an array in BaseDeck.
As such, all you need to do is shuffle the array.
This can be done quickly and easily.
Here's the shuffler that I've used previously:
Shuffling Code
function Shuffle(array) {
var x = array.length, y, i;
while (x) {
i = ~~ (Math.random() * x--);
y = array[x];
array[x] = array[i];
array[i] = y;
}
return array;
}
I've tested it extensively, and it shuffles completely randomly.
This is a variation on Fisher-Yates which I posted above (specifically, it's a version which assumes the RNG is not capable of producing a random integer j such that p <= j < q). It works equally as well as the function I posted, although I'm not a fan of using bitwise operations for integer rounding or coercion. There is no significant speed increase over the function call (there is a speed increase, but it's extremely tiny), while there is significant overhead in code comprehension. That said, if you're set on replacing Math.floor with bitwise operations, I recommend (x | 0) over (~~x), as it cuts you down to one operation instead of two, and missing a single character causes syntax error instead of producing a logic error, which tends to be more difficult to track down.
Your draw also seems "overpowered"
If you're not drawing 1 at a time, a simple splice() works.
Also, you're drawing off the bottom of the library with .pop()
this.draw = function(count) {
var d = [];
for (var i = 0; (i < count && i < this.activeDeck.length); i++) {
d.push(this.activeDeck.pop());
}
return d;
};
This will remove the first COUNT cards from activeDeck.
It then returns these removed cards as an array.
Your code is definitely simpler to read and write, but two things should be noted. Array.prototype.splice runs in O(n) time, some ECMA engines use optimization techniques to reduce that to O(n/c) where c is some constant, but those techniques hurt indexing which can result in slow splices. Array.prototype.pop runs in O(1) time (the O(n) copy costs which exist in Array.prototype.push at engine-defined logarithmic boundaries get folded into garbage collection for pop). In most cases, iterating over several calls to pop will result in the same time complexity as a single call to splice. At the small values for count that are expected for the draw function, the overhead of the extra function calls to pop will make splice run faster in reality, although the difference will be minimal. (At count = 1, though, the pop version will probably be faster, because splice is kinda inefficient. That's something that would need fine testing to be sure of, though.)
The best optimization on this would be to use Array.prototype.slice (always O(n)) and an index variable maintained by the object, not changing the contents of the deck array at all. However, for an array that's never going to have a length more than two orders of magnitude and a function call with count rarely more than one order of magnitude, that's really not worth it. The inefficiencies present in both versions of the draw function are negligible due to the small values at play.
computers are fast enough nowadays to where sloppy code does not really matter in terms of performance. especially if you're running iterations of just 100k or so.
awhile back i used to work for a pathetic software company who's philosophy was: beefupservers > optimizing code
beefing up the servers was cheaper for the company.
Private Mod Note
():
Rollback Post to RevisionRollBack
To post a comment, please login or register a new account.
I've replaced some stuff that's specific to my implementation with some more generic placeholder functions - you'll have to write your own functions, for example, for getting the list of cards in a deck, and for determining whether a card is a Commander or is in a Sideboard.
I use prototype.js to add things like array iteration and searching to JavaScript, but the code should be easy enough to port to jQuery.js or something similar
Hope someone can get some use out of it. Feedback is welcome
Minouris's Library - Collection manager and deck builder. It's nifty - Check it out!
Math.random is almost guaranteed to introduce a modulo bias and (the browser-dependent implementation of) the RNG most likely doesn't include enough bits of internal state to fully express all possible permutations of the deck. (It's unlikely for an implementation of Math.random to be capable of representing more than ~1.84e19 different sequences of numbers, but a Commander deck has ~9.33e155 different permutations. Even a Limited deck has ~8.15e47 permutations.) That said, Math.random is probably good enough, is extremely likely to be more random than a real persons shuffling the deck, and other solutions are slower, require additional memory, or both.
I also always recommend hoisting your variables manually; the JS engine is going to do this anyway, and it helps make sure you don't get caught by a "gotcha!" caused by the automatic hoisting. That and using strict mode are two main best practices I try to use when writing JS code.
Depending on your use-case, there's also a version of the Fisher-Yates algorithm to both shuffle the array and initialize it at the same time. See Fisher-Yates shuffle#The inside-out algorithm.
Two Score, Minus Two or: A Stargate Tail
(Image by totallynotabrony)
Minouris's Library - Collection manager and deck builder. It's nifty - Check it out!
You start off by making a pristine array of the deck for BaseDeck.
Then, in the shuffler, you set the BaseDeck as the shuffled copy.
Later you make this.ActiveDeck = this.BaseDeck
In fact, this only works because you repopulate.
Once you make this.ActiveDeck = this.BaseDeck, you've made two variables reference the same object.
If you take a look into your variable after drawing a few, I bet you'll find BaseDeck is missing some cards.
I would keep BaseDeck as a pristine copy of what should be in the deck.
BaseDeck is made during populate, and then shuffle sets ActiveDeck.
Thus, if you want to "redraw", you just skip to shuffle then draw.
Basically, you'd populate when the pages is loaded.
After that, you never need to populate again.
Then, whenever you want a new hand, you just .shuffle()
.Reset() wouldn't be needed at all.
-
Your shuffler is also using a lot of unnecessary power.
Once you reach Shuffle(), the deck is already in an array in BaseDeck.
As such, all you need to do is shuffle the array.
This can be done quickly and easily.
Here's the shuffler that I've used previously:
Shuffling Code
Switching it into your prototype setup wouldn't be hard.
Going with my previous Pristine/Library setup:
"array" is taken out of parameter, and instead:
var array = [].concat(this.basedeck);
(this keeps basedeck pristine)
instead of returning array, we:
this.activedeck = array;
-
Your draw also seems "overpowered"
If you're not drawing 1 at a time, a simple splice() works.
Also, you're drawing off the bottom of the library with .pop()
It then returns these removed cards as an array.
Just some observations. Hopefully it helps.
No longer staff here.
Your code is definitely simpler to read and write, but two things should be noted. Array.prototype.splice runs in O(n) time, some ECMA engines use optimization techniques to reduce that to O(n/c) where c is some constant, but those techniques hurt indexing which can result in slow splices. Array.prototype.pop runs in O(1) time (the O(n) copy costs which exist in Array.prototype.push at engine-defined logarithmic boundaries get folded into garbage collection for pop). In most cases, iterating over several calls to pop will result in the same time complexity as a single call to splice. At the small values for count that are expected for the draw function, the overhead of the extra function calls to pop will make splice run faster in reality, although the difference will be minimal. (At count = 1, though, the pop version will probably be faster, because splice is kinda inefficient. That's something that would need fine testing to be sure of, though.)
The best optimization on this would be to use Array.prototype.slice (always O(n)) and an index variable maintained by the object, not changing the contents of the deck array at all. However, for an array that's never going to have a length more than two orders of magnitude and a function call with count rarely more than one order of magnitude, that's really not worth it. The inefficiencies present in both versions of the draw function are negligible due to the small values at play.
Two Score, Minus Two or: A Stargate Tail
(Image by totallynotabrony)
awhile back i used to work for a pathetic software company who's philosophy was: beefupservers > optimizing code
beefing up the servers was cheaper for the company.