Hello and welcome to what I hope will be the first in many blog posts from me with coding tips and tricks (or trips and ticks, as we often say). Our artist, Anya, has been bugging me to do this for ages, and I was recently told to get on it by the ace Dave Voyles – so here we are!

I’ve been working in games for over 20 years now and it’s amazing how many little things you learn and then just assume everyone knows. I’ve shown a few of them, usually with the words “You know this, right?” only to be looked upon as some sort of sage with arcane knowledge brought from the code-gods of old. I am not a sage, I’ve just been around a bit. I think it also helps that I started programming at a very different time when performance was a big thing and so knowing a good, solid, and more importantly quick solution was key.

So where to start? Well, how about with my favourite trick of all time. It’s not particularly useful now, but it gives you an idea of where I’m coming from. Back in the 80s, computers didn’t have many registers (if you know what those are – Wiki page on registers is here) and moving stuff around in memory was very slow. One of the things you frequently needed to do was to swap two numbers. You have two numbers, and you want to know which is the biggest and which the smallest. You might do it this way:

	if(Value1 > Value2)
	{
		Temp = Value1;
		Value1 = Value2;
		Value2 = Temp;
	}

Here we know that Value1 and Value2 will be swapped if Value1 is bigger. The problem here is that it’s using a third value to store the temporary swapped value. So we need somewhere to store this third value, what if we don’t have anywhere (which was quite often).

The solution is a nice bit of bit operation trickery. Who knows what Exclusive Or (XOR) does? It’s like an OR but not if the two bits are both 1.

	0 XOR 0	= 0
	0 XOR 1	= 1
	1 XOR 0	= 1
	1 XOR 1	= 0

In C# (my favoured language), the XOR operation is specified using the ^ character, which is lovingly called the hat symbol. So here’s the trick. To swap two values without using a third, you do this.

	if(Value1 > Value2)
	{
		Value1 ^= Value2;
		Value2 ^= Value1;
		Value1 ^= Value2;
	}

It’s madness but it works. Essentially you are swapping them over by storing the differences between two values. So let’s run a little example:

	Value1		=	1	0	1	1	=	11
	Value2		=	0	1	0	1	=	5

Value1 ^= Value2;
	Value1		=	1	1	1	0	=	14
Value2 ^= Value1;
	Value2		=	1	0	1	1	=	11
Value1 ^= Value2;
	Value1		=	0	1	0	1	=	5

It’s magic (and cool). Not too useful now (we don’t need to worry about the extra temporary overhead), but it’s a nice trick and shows you that sometimes stepping back from the problem (and knowing a bit about logic operations) can help you get what you want.

So how about something more useful? You have a random integer and you want another one, but you don’t want the same one. For those that don’t know, the % symbol represents a modulo operation. It makes sure that the number falls in the range stated. I’ve seen many occasions where it’s looked like this.

	while(NewValue != OldValue)
	{
		NewValue = Rand() % 20;
	}

So keep on choosing until we get a different one. Not good though as it could get stuck there (it won’t for long, but you get my drift). There is, however, an easier solution. If you know (in this case) that you have 20 possible values and have already chosen 1, then there are 19 left. So why not choose a random one of those 19, then add it to what you have (and making sure you don’t overflow).

	NewValue = (OldValue + (Rand() % 19)) % 20;

Easy and really useful (I use it all the time). It was this little trick, in fact, that made me think about writing this blog, as I showed it to someone recently and I got the “this is dark magic” face.

Let’s do one more. You have an array of numbers and you want to choose one from it randomly each time. The problem here is that you don’t want to repeat what you chose before. Again I’ve seen people creating new arrays of what’s left or looping the search to make sure the next choice is different.

	Array = 20, 15, 2, 8, 9

So to choose a value, you would do:

	Choice = Array[ Rand() % List.Length ]

Here’s the trick to just use the same list again:

	ItemsLeft = Array.Length
	while(ItemsLeft   > 0)
	{
		ChoiceIndex = Rand() % ItemsLeft ;
		Choice = Array[ ChoiceIndex  ];
		… Do whatever processing you want here

	Array[ ChoiceIndex ] = Array[ ItemsLeft - 1 ];
	ItemsLeft = ItemsLeft - 1;
	}

What you are doing is reusing the slot you just chose (by copying in the last slot value) and then remembering you have one less to choose from. No need for an extra list, super quick.

I think that’s it for now. I have plenty more left. Not just little code tricks, but also things that are worth investigating and systems to put in place to make your development life easier. If you have any questions or requests, drop me a line.

 

2 Comments:

  1. Clive May 29, 2014 Reply

    Sat over the road in bucks (nursing some nasty sun burn from lands end) I love that random number generator. I think I saw something similar in a course book on discrete mathematics (book had to be good for something) the reason I remember it is the name… Who wouldnt remember an algorithm called ‘Blum Blum Shub’ :-) great post Richard.

    • Profile photo of Richard Weeks
      Richard Weeks June 02, 2014 Reply

      Ha. Cheers. Yeah, I showed Will (our coder) the trick and he gave we the looks of “that’s too easy”. Going to do another one later this week.

Leave a Comment!

Your email address will not be published. Required fields are marked *

Please prove you\'re human: *

Skip to toolbar