What is This Algorithm Called?

Authoring
#1

Here is a fun thread where we can ask what an algorithm or design pattern is called, thus letting us research the 40+ years on algorithms and implement it in our games.

I am trying to come up with an array of six numbers. It represents characters talking. The first one is picked by the player and inserted in the first (0th) spot of the array.

The other five should be random and not repeat.

It’s sort of like a sorting algorithm but I feel there is a proper name for generating a random list of six numbers. Anyone recall?

#2

If you’re rearranging a list of items into random order, or picking a subset in random order, it’s shuffling. You could start with a list of numbers from 1 to 1000, shuffle the list, then take the first 5 items.

If the number of items you’re choosing from is too big for that – say, you want lots of unique random numbers between 1 and 2 billion – then you could try a linear feedback shift register, as mentioned in one of the answers here.

But for a list this short, the naive solution is probably good enough: generate a random number, scan through your list to see if it’s already in there, and add it if not; repeat until you have enough items.

2 Likes
#3

You are DA MAN. Thanks, Jesse!

I’ll post my solution first chance I get – there is a part to it that has a bad code smell. I wrote it right after writing my message though, so when I take a look at shuffling and linear feedback shift register I might figure out why.

#4

You can also use a less algorithmic but simpler solution, depending on your needs: move the characters from offstage to the room in your story as you select them, thus ensuring there are no repeats. (Of course this depends on the details of your game, it was just the first thing that came to mind.)

#5

@vaporware, yeah, I guess the very quickest depends on how many numbers you need. But as I have a 5000 entry table in one of my own games, and it doesn’t really bog Inform down, time saving isn’t super critical.

That said, I never considered running the Fisher Yates shuffle for just a few terms as in the linear feedback shift register. I figured just picking numbers til there were no duplicates were okay.

A small mathy tangent: for those familiar with the birthday paradox, you have a <1/2 chance of any repeats as long as you choose up to 38 of 1000, and in general the number of chooses = roughly square root of (# of possibilities * 2 ln 2)

#6

This is from way back, but this is the solution I came up with. I hate a lot about it. I don’t like the fact that I initialize the array to a garbage character (99 in this case) and that I am using a flag to note if the number appears or not.

routine RandomizePartyOrderForTalking(starterCharacter)
{
!// starterCharacter needs to be a number.

local x, y, randNumber, usedFlag

	!// We need to use 1 through 6 at first.
	starterCharacter++

	!// Let's initialize the array to all zeroes.
	for(x=0; x<6; x++) 
	{
		RandomPartyOrder[x] = 99
	}

	!// Set the first slot to the starterCharacter
	RandomPartyOrder[0] = starterCharacter

	!// We're gonna go through the last five slots.
	for(x=1; x<6; x++) 
	{

		while RandomPartyOrder[x] = 99
		{
			usedFlag = false

			randNumber = random(6)

			for(y=0; y<6; y++)
			{
				if (RandomPartyOrder[y] = randNumber)
				{
					usedFlag = true
				}
			}

			if usedFlag = false
			{
				RandomPartyOrder[x] = randNumber
			}
		}
	}

	!// Decrement them all by one

	for(x=0; x<6; x++)
	{
		!//print "Initial:" ;
		!//print number RandomPartyOrder[x] 
		RandomPartyOrder[x] = (RandomPartyOrder[x]-1)
		!//print "After: " ;
		!//print number RandomPartyOrder[x]
	}

}
#7

One other odd bit is that Hugo has a random routine that starts from 1 to whatever number you specify. The array of the characters for the game, of course, begins at zero. I don’t know what the comments reflect it. But yeah, any ideas to make this more elegant, I am all ears. Java 8 makes this pretty easy (and readable) but I think that there is a better way to do this in Hugo, too!

#8

Me being me, I would make an object-based solution. I would make an object called talk_order. Then I would make 5 objects for chars 2-6 (you said 1 always goes first, right?), like

object char2talk
{
in talk_order
misc 2
}

Then I would call Roodylib’s MixObjects to sort them whenever they needed to be reordered.

MixObjects(talk_order)

Then I would call the relevant character quips based on the order of the children of talk_order.