Using Your Memory (Any Blitz, Any Level)

Blitz3D Forums/Blitz3D Tutorials/Using Your Memory (Any Blitz, Any Level)

Douglas

(Posted 2004) [#1]

TITLE: Using Your Memory (Any Blitz, Any Level)

DESCRIPTION: These are just some random examples on using memory to save CPU time and make code look nice. The action game programmer probably will not run into many instances where you can use memory to make things simpler, but a puzzle game programmer might. The first 4 problems are all things I've run into when making puzzle games.

>>>>>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>>>>> PROBLEM 1: N0n-Repeating Random Numbers
>>>>>>>>>>>>>>>>>>>>>>>>

Fill a 1,000,000 element array with random integers from 1 to 1,000,000 such that no integer is repeated.

A first intuition might be to pick a random number and test it aginst all the numbers we have picked so far until you find a random number that hasn't already been choosen. And do that for each element. In BlitzBasic this might look like:

Dim array(1000000)

For i=1 To 1000000
	Repeat
		new=True
		number=Random(1,1000000)
		For j=1 To i-1
			If array(i)=array(j) Then new=False
		Next
	Until new=True
Next

But, imagine trying to place the last number. We have 1 number left, and the chances of picking it are 1 in a million. And for each number we pick we have 999,999 comparison tests. Thats too much time.

Make a 1,000,000 element array that will hold all the numbers we have left to choose. We will maintain this array so that if we still have N numbers to pick, the first N elements of this array will contain these numbers (not neccessarily in order).

***NOTE: We are going to choose random elements where the numbers will be, not randomly choose the numbers themselves.

When we choose a random element, we will put the value of the N'th element (the last of the unchoosen numbers) in the spot we just choose. This removes the choosen number from the unchoosen numbers, and keeps that last number in the pool when N decreases by 1 on the next pass.

For example, say we have 5 numbers not a million. Our unused numbers array will start off like:

1,2,3,4,5

Lets say we pick a random element 2. 2 is whats in element 2. Now we put the 5 where the 2 is so our unused numbers array looks like:

1,5,3,4,5

We still have 4 numbers left we havent picked, and the first 4 elements of this array are these numbers. So picking a random element from 1 to 4 we know will give us an unused number without any comparison tests like in the first way we solved this problem. In BlitzBasic this might look like:

Dim array(1000000)
Dim unused(1000000)

For i=1 To 1000000
	unused(i)=i
Next

For i=1 To 1000000
	element=Random(1,1000000-(i-1))
	array(i)=unused(element)
	unused(element)=unused(1000000-(i-1))
Next

>>>>>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>>>>> PROBLEM 2: 1->2 & 2->1
>>>>>>>>>>>>>>>>>>>>>>>>

We have a varrible x thats either a 1 or a 2 and we want to flip it.

A first intuition might be:

If x=1 Then
	x=2
Else
	x=1
EndIf

Other methods include:

x=3-x	;Note:  you can always flip 2 numbers by subtracting from their sum

x=(2*x) Mod 3

x=(x Mod 2)+1

But, by setting up a 2 element array:

Dim flip(2)
flip(1)=2
flip(2)=1

We can just say:

x=flip(x)

You would really want to do it this way if x could be more than just 1 or 2 and their was no pattern in changing x's value.

>>>>>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>>>>> PROBLEM 3: Greatest Number Less Than Or Equal To
>>>>>>>>>>>>>>>>>>>>>>>>

Lets say we have some numbers: 3,6,7,10,14

And we want to find the greatest number less than or equal to some number x. If x is 13, then the answer would be 10 in the above case.

You can make some type of algorithm to hunt for the number. Or you can make an array that looks like: 0,0,3,3,3,6,7,7,7,10,10,10,10,14

So that the x'th element has the answer for x.

>>>>>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>>>>> PROBLEM 4: Find A Number And Move It
>>>>>>>>>>>>>>>>>>>>>>>>

Lets say we have an array of numbers 1 to 9 in no specific order:

array1=3,6,1,2,4,9,7,8,5

And we want to move a number, say 9 to the left. Then we would swap the 9 and the 4.

But, hunting for the 9 would be a pain. Lets make another array so that we can jump right to it. This second array will hold the location for each number in array1. To correspond with the above array1, it would look like:

array2=3,4,1,5,9,2,7,8,6

For instance, the 1 is in the 3rd element in array1, so we give the first element a value of 3 in array2. The 9 (which is what we want) is the 6th element in array1. So, array2(9)=6.

If we want to swap the 9 with whatever is to the left of it, our BlitzBasic code might look like:

leftNumber=array1(array2(9)-1)
array1(array2(leftNumber))=9
array1(array2(9))=leftNumber
array2(9)=array2(leftNumber)
array2(leftNumber)=array2(leftNumber)+1

>>>>>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>>>>> PROBLEM 5: Sorting
>>>>>>>>>>>>>>>>>>>>>>>>

Lets say we want to put the numbers:

3,4,1,2,7,9,10,11,14,13,12

in order. Notice the 5,6, and 8 are missing. Instead of using quick sort or insertion sort, you could make a 14 element array and put the 3 in element 3, the 4 in 4, ... , and the 14 in 14 so it would look like:

1,2,3,4,0,0,7,0,9,10,11,12,13,14

Then shift all the numbers after the first 0 (where the missing 5 would go) to the left 1, after the 2nd 0 to the left 2, etc... So the first 11 elements would look like:

1,2,3,4,7,9,10,11,12,13,14

If numbers could repeat you would could make an N by 2 matrix to hold the number of a certain type of number. So 1,3,4,1,3,5 might look like:

1,0,3,4,5
2,0,2,1,1 (since there are 2 1's and 2 3's)

If you had alot of gaps, you might want to use the radix sort which works digit by digit. Do an internet search for more info. And, even with the radix sort there is a way to use memory to make it twice as fast as I have seen most people do it.

>>>>>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>>>>> GENERAL TID-BITS
>>>>>>>>>>>>>>>>>>>>>>>>

Sometimes people make an array for Sin and Cos and precalculate 360 degrees or so, so they can just copy the values later on without having to do actually Sin and Cos calculations. It's called a look-up table.

And, a long time ago I used to program in Basic on a TI calculator. It interpreted and was extremely slow. And for some reason, If tests were extra slow. I tried to avoid them at all costs. We had the GetKey command. And I would build an array with the elements of the movement keys holding the direction, so I didn't need 4 If tests like If key=34 Then direction=1. It could just be direction=array1(array2(key)) where array2 held the element to get the direction from in array1. That way if no key was pressed or a non-movement key was pressed, it would refere to the element of array1 that held the direction you were already heading. And to make sure you couldn't go through a wall, no If tests were used either. You had an array that held your old and current locations. Where there was no wall, the wall value refered to your current location, and where there was, to your old location. Luckly BlitzBasic isn't like that.

Floyd

(Posted 2004) [#2]

Your first example, 'shuffling' an array, doesn't need a second array to track usage.
It can be done simply like this:

N = 9

Dim array(N)

For i=1 To N
	array(i)=i
Next

For i=1 To N-1        ; put random array element into position i
	k = Rand(i,N)
	temp = array(i) : array(i) = array(k) : array(k) = temp
Next

For i = 1 To N
	Print array(i)
Next

WaitKey : End

Douglas

(Posted 2004) [#3]

Good call.

This way is actually a tiny fraction faster though cause it doesn't need to use that temp varrible to swap.

Dim array(1000000)
Dim unused(1000000)

For i=1 To 1000000
	unused(i)=i
Next

For i=1 To 1000000
	element=Random(i,1000000)
	array(i)=unused(element)
	unused(element)=unused(i)
Next

eBusiness

(Posted 2004) [#4]

I think that I have a TI 83 game to rewrite :)

MrCredo

(Posted 2004) [#5]

1.000.000 random numbers?

no problem

1) create dim-array
DIM array(1000000)

2) set values:

for i=1 to 1000000
array(i)=i
next

3) swap values

for i=1 to 1000000
nr=rand(1,1000000) ;can rand handle large numbers?
tmp=array(i)
array(i)=array(nr)
array(nr)=tmp
next

that's it - you need only 1 array

eBusiness

(Posted 2004) [#6]

Take your time to read what Floyd posted

rdodson41

(Posted 2004) [#7]

I think that I have a TI 83 game to rewrite :)

I think i have a few TI-83 games to rewrite =)

Neochrome

(Posted 2004) [#8]

Using memory like that i do use it for Cos and Sin commands
it speeds up about 50th of a second a game that uses Cos and Sin a lot this little trick would realy help!