A few nights ago I was playing Call of Duty Black Ops with some friends of mine. (And despite what they say - I'm a darn good player and always come out with a positive Kill to Death ratio. Honest.) For those of you who haven't done an online game like Black Ops, the basic idea is that you play a round with your friends against a random "room" of people. Each match lasts a few minutes and in the next round a different map will be chosen for you to play with. I greatly simplified that but hopefully those of you who have managed to escape the addiction will get the basics.
So as I said - each game consists of a random map. The game is supposed to pick a map that you didn't play in the last round. Sometimes though - inexplicably - the game does just that. On the other side - sometimes it seems like we will have a play session for a few hours and some maps are never chosen.
As you can imagine, this tends to bug us and becomes something of a hot topic while we play. Being the big nerd I am I spent some time thinking about the code behind choosing the next map. It would be trivial to pick random maps from a list until each map has been chosen. (And if folks want to see an example of that in ColdFusion, just ask.) But it seems like Black Ops tries to do something a bit different. It feels random - but you get repeats. When things work well, you don't repeat a map you just played, but you may repeat a map before another map you haven't hit is picked. As I said, Black Ops seems a bit broken but I can kinda get what it is attempting to do. (And for those of you who play, yes, I'm ignoring the vote system.)
So I gave this some thought and came up with what I thought would be a good formula:
Given a set of maps (or any random object) N.
We want to remember the last few choices.
We will remember Size of N/2 items.
When picking a new item, it must not be in the Remember list.
When chosen, add the item to the Remember list.
If the Remember list is bigger than Size of N/2, pop off the oldest one.
Make sense? Here is an example. Given a set of 10 maps, we will remember the last 5 played. So when a new map is chosen, it is randomly chosen from the list but it cannot be in the last 5. We then add that to the last 5 and pop off the 1st game you played. Here is the ColdFusion code I wrote up. It supports a list of 1 or 2 items which is a bit dumb but I wanted to be complete.
<cfset recentGames = []>
<cfset recentGameSize = fix(arrayLen(gameList)/2)> <cfoutput>Size of recentGames queue will be #recentGameSize#<p></cfoutput> <!--- run 100 tests --->
<cfloop index="x" from="1" to="100"> <!--- If size of games is 1 always return it --->
<cfif arrayLen(gameList) is 1>
<cfset picked = gameList[1]>
<!--- If size is 2, it's very simple logic --->
<cfelseif arrayLen(gameList) is 2>
<cfloop index="y" from="1" to="#arrayLen(gameList)#">
<cfif gameList[y] neq recentGames[1]>
<cfset picked = gameList[y]>
<cfset recentGames[1] = picked>
<cfbreak>
</cfif>
</cfloop>
<!--- Interesting logic is here. --->
<cfelse>
<cfset picked = "">
<cfloop condition="picked eq ''">
<cfset possiblePick = gameList[randRange(1, arrayLen(gameList))]>
<cfif not arrayFind(recentGames, possiblePick)>
<cfset picked = possiblePick>
<cfset arrayPrepend(recentGames, picked)>
<cfif arrayLen(recentGames) gt recentGameSize>
<cfset arrayDeleteAt(recentGames, recentGameSize+1)>
</cfif>
</cfif>
</cfloop>
</cfif> <cfoutput>
<cfif picked is "Nuke Town"><b></cfif>
For round #x# picked was #picked#
<cfif picked is "Nuke Town"></b></cfif>
<br/>
</cfoutput>
<cfflush>
</cfloop>
<cfset gameList = ['Array', 'Cracked', 'Crisis', 'Firing Range', 'Grid', 'Hanoi', 'Havana', 'Jungle', 'Launch', 'Nuke Town', 'Radiation', 'Villa', 'WMD']>
To see an example of this action, click the Demo button below. I made one map, "Nuke Town", bold, as a way to see how often it would show up. (And it just so happens that this is one mine and my friends favorite maps.)
Enjoy. I promise my next blog entry will contain useful ColdFusion code!