There’s a first time for everything

And this week was the first time I got a game on the App Store, the game is called Fall in Cave, I learned a lot while developing this game. 

I will be posting pieces of code that I used in my game that you can use on your projects, for example the way I handle music and sound effects.

Some details of the game:

  • Was developed in Xcode using SpriteKit
  • Graphics were done in aseprite 
  • Music and sound effects are from SoundJay

I was trying to make a game that you can play wherever you are, a “high-score” game, with a retro feel, simple to play but hard to master.

This will not be my only game, even if this one doesn’t get too much attention I will continue making games, because I love doing it. 

Counting Sort

Counting sort is so clever that it blew my mind, it doesn’t even use if clauses, this sorting algorithm doesn’t use comparisons. This algorithm can sort integer elements in the range 0 - k (k being exclusive)  where k it’s a known number. This is a great sorting algorithm when we have a large set of data in a range (0-k). It uses three arrays and has three for loops:

  1. We fill a helper array of size k where every index in the helper array represents an element of the original array, and the value is the number of times that element is present in the original array. For example, if the number 0 appears 4 times in the original array, the index 0 of the helper array will contain a 4.
  2. Using the information we have in the helper array, for every index of the helper array, we count how many elements are less or equal than that index, and we save that value in the corresponding index of the helper array. For example, if the number 0 appears 2 times, and the number 1 appears 3 times, in the helper array in the index 0 we are going to have the value 2, and in the index 1 we are going to have the value 5.
  3. We fill up the result array by grabbing an element of the original array and placing it in it’s correct position on the result array, and every time we do that, we decrement the counter corresponding to that value in the helper array. 

Pseudocode

let arr be an array of integers of range 0-max
let res be an array of integers of the same length that arr
let max be the largest number of arr + 1
let tmp be an array of length max filled with zeros
for i=0 while i=0 k--
    res[tmp[arr[k]]-1] = arr[k]
    tmp[arr[k]] = tmp[arr[k]]-1

Implementations

C (Apple LLVM version 5.1 (clang-503.0.40), compiled with gcc -ansi)

#include <stdio.h>

int main()
{
	int arr[] = {5,2,4,6,1,3,0,5,0,4,2};
	int arrlength = sizeof(arr)/sizeof(arr[0]);
	int res[arrlength];
	int max = 7;
	int tmp[max];
	for(int h = 0; h<max; h++)
	{
		tmp[h] = 0;
	}
	for(int i=0; i<arrlength; i++)
    {
        tmp[arr[i]] = tmp[arr[i]]+1;
	}
   	for(int j=1; j<max; j++)
	{
        tmp[j] = tmp[j] + tmp[j-1];
	}
    for(int k=arrlength-1; k>=0; k--)
	{
		res[tmp[arr[k]]-1] = arr[k];
		tmp[arr[k]] = tmp[arr[k]]-1;
	}
	
	for(int l=0; l<arrlength; l++)
	{
		printf("%d ",res[l]);
	}
	printf("\n");
}

Java 1.7

public class CountingSort{

    public static void countingSort(int arr[], int res[], int max){
        int tmp[] = new int[max];

        for(int i=0; i<arr.length; i++){
            tmp[arr[i]] = tmp[arr[i]]+1;
        }
        for(int j=1; j<max; j++){
            tmp[j] = tmp[j] + tmp[j-1];
        }
        for(int k=arr.length-1; k>=0; k--){
            res[tmp[arr[k]]-1] = arr[k];
            tmp[arr[k]] = tmp[arr[k]]-1;
        }
    }

    public static void main(String []args){
        int array[] = {5,2,4,6,1,3,0,5,0,4,2};
        int result[] = new int[array.length];
        int max = 7;

        CountingSort.countingSort(array,result,max);

        for(int i : result){
            System.out.print(i+" ");
        }
        System.out.println();
    }

}

Python 2.7.5

def counting_sort(arr,res,max):
    tmp = [0]*max
    for i in range(0,len(arr)):
        tmp[arr[i]] = tmp[arr[i]]+1
    for j in range(1,max):
        tmp[j] = tmp[j] + tmp[j-1]
    for k in range(len(arr)-1,-1,-1):
	res[tmp[arr[k]]-1] = arr[k]
	tmp[arr[k]] = tmp[arr[k]]-1

array = [5,2,4,6,1,3,0,5,0,4,2]
result = [0]*len(array)

counting_sort(array,result,7)
print result

Quicksort

This algorithm is often the best choice for sorting, because it’s remarkably efficient on average. It is a divide and conquer algorithm.

  • Divide: We partition the array in two subarrays.
  • Conquer: We sort the two subarrays by making recursive calls to the algorithm.

Example gif from wikipedia

Quicksort example from wikipedia

Quicksort example from wikipedia

Pseudocode (from wikipedia)

quicksort(A, i, k):
    if i < k:
    p := partition(A, i, k)
    quicksort(A, i, p - 1)
    quicksort(A, p + 1, k)

// left is the index of the leftmost element of the subarray
// right is the index of the rightmost element of the subarray (inclusive)
// number of elements in subarray = right-left+1
partition(array, left, right)
    pivotIndex := choose-pivot(array, left, right)
    pivotValue := array[pivotIndex]
    swap array[pivotIndex] and array[right]
    storeIndex := left
    for i from left to right - 1
        if array[i] ≤ pivotValue
            swap array[i] and array[storeIndex]
            storeIndex := storeIndex + 1
    swap array[storeIndex] and array[right]  // Move pivot to its final place
    return storeIndex

let arr be an unsorted array of integers
quicksort(arr,0,arr.length-1)

Implementations

C (Apple LLVM version 5.1 (clang-503.0.40), compiled with gcc -ansi)

#include <stdio.h>

void quicksort(int array[],int left, int right)
{
	if(left < right)
	{
		int q = partition(array,left,right);
		quicksort(array,left,q-1);
		quicksort(array,q+1,right);
	}
}

int partition(int array[],int left, int right)
{
	int x = array[right];
	int i = left - 1;
	for(int j=left; j<right; j++)
	{
		if(array[j] <= x)
		{
			i++;
			int temp = array[i];
			array[i] = array[j];
			array[j] = temp;
		}
	}
	int temp = array[++i];
	array[i] = array[right];
	array[right] = temp;
	return i;
}

int main()
{
	int arr[] = {5,2,4,6,1,3};
	int arrlength = sizeof(arr)/sizeof(arr[0]);
	quicksort(arr,0,arrlength-1);
	for(int i=0; i<arrlength; i++){
		printf("%d ",arr[i]);
	}
	printf("\n");
}

Java 1.7

public class QuickSort{

	public static void quickSort(int []array,int left, int right){
		if(left < right){
			int q = partition(array,left,right);
			quickSort(array,left,q-1);
			quickSort(array,q+1,right);
		}
	}

	public static int partition(int array[],int left,int right){
		int x = array[right];
		int i = left - 1;
		for(int j=left; j<right; j++){
			if(array[j]<=x){
				i++;
				int temp  = array[i];
				array[i] = array[j];
				array[j] = temp;
			}
		}
		int temp = array[++i];
		array[i] = array[right];
		array[right] = temp;
		return i;
	}

	public static void main(String []args){
		int arr[] = {5,2,4,6,1,3};
		QuickSort.quickSort(arr,0,arr.length-1);
		for(int i : arr){
			System.out.print(i+" ");
		}
		System.out.println();
	}
}

Python 2.7.5

def quicksort(array,left,right):
    if left < right:
        q = partition(array,left,right)
        quicksort(array,left,q-1)
        quicksort(array,q+1,right)

def partition(array,left,right):
    x = array[right]
    i = left - 1
    for j in range(left,right):
        if array[j] <= x:
            i = i + 1
	    temp = array[i]
            array[i] = array[j]
            array[j] = temp
    temp = array[i+1]
    array[i+1] = array[right]
    array[right] = temp
    return i + 1

arr = [5,2,4,6,1,3]
quicksort(arr,0,len(arr)-1)
print arr

Selection Sort

In the last post we implemented the Insertion Sort, today’s sorting algorithm is only good for a small number of elements, but it’s slower than the Insertion Sort. 

In Selection Sort we first find the smallest number in the array and exchange it for the first element, then we find the smallest number in the sub array [1,n], an exchange it for the second element, we repeat this until the n – 1 element.

Example gif from wikipedia

Selection sort example from wikipedia

Selection sort example from wikipedia

Pseudocode

let arr be an unsorted array of integers
    for i = 0 while i<arr.length-1 i++
        key = arr[i]
        indexOfSmallest = i;
        for j = i+1 while j<arr.length j++
            if key > arr[j]
                key = arr[j]
                indexOfSmallest = j
        arr[indexOfSmallest] = arr[i]
        arr[i] = key

Implementations

C (Apple LLVM version 5.1 (clang-503.0.40), compiled with gcc -ansi)

#include <stdio.h>
int main()
{
	int arr[] = {5,2,4,6,1,3};
	int arrlength = sizeof(arr)/sizeof(arr[0]);

	for(int i=0; i<arrlength-1; i++)
	{
		int key = arr[i];
		int indexOfSmallest = i;
		for(int j=i+1; j<arrlength; j++)
		{
			if(key>arr[j])
			{
				key = arr[j];
				indexOfSmallest = j;
			}
		}
		arr[indexOfSmallest] = arr[i];
		arr[i] = key;
	}

	for(int k=0; k<arrlength; k++){
		printf("%d ",arr[k]);
	}
	printf("\n");
}

Java 1.7

public class SelectionSort{
	
	public static void main(String []args){
		int arr[] = {5,2,4,6,1,3};

		for(int i=0; i<arr.length-1; i++){
			int key = arr[i];
			int indexOfSmallest = i;
			for(int j=i+1; j<arr.length; j++){
				if(key>arr[j]){
					key = arr[j];
					indexOfSmallest = j;
				}
			}
			arr[indexOfSmallest] = arr[i];
			arr[i] = key;
		}

		for(int i : arr){
			System.out.print(i+" ");
		}
		System.out.println();
	}	

}

Python 2.7.5

arr = [5,2,4,6,1,3]

for i in range(0,len(arr)-1):
    key = arr[i]
    indexOfSmallest = i
    for j in range(i+1,len(arr)):
        if key > arr[j]:
            key = arr[j]
            indexOfSmallest = j
    arr[indexOfSmallest] = arr[i]
    arr[i] = key

print arr

See you on the next post!

Insertion Sort

In this post, I feel like talking about the insertion sort.

In the aforementioned sort, we take an element, we are going to call this element the key. We take the key and compare it to the element in the left, if the element of the left is greater than the key, they exchange places, if they exchanged places then we compare the key to the element in the left (if there is one), if the element on the left is not greater than the key (or if there are no more elements in the left) we take the next element as the key. Rinse and repeat until we run out of elements. The first element we take as the key is the second element.

This algorithm is efficient for sorting a small number of elements.

Example gif from wikipedia

Insertion sort example from wikipedia

Insertion sort example from wikipedia

Pseudocode

let arr be an unsorted array of integers
    for i = 1 while i<arr.length i++
        key = arr[i]
        j = i -1
        while j>=0 and arr[j]>key
            arr[j+1] = arr[j]
            j--
        arr[j+1] = key

Implementations

C (Apple LLVM version 5.1 (clang-503.0.40), compiled with gcc -ansi)

#include<stdio.h>

int main()
{
	int arr[] = {5,2,4,6,1,3};
	int arrlength = sizeof(arr)/sizeof(arr[0]);
	for(int i=1; i<arrlength; i++)
	{
		int key = arr[i];
		int j = i - 1;
		while(j>=0 && arr[j]>key)
		{
			arr[j+1] = arr[j];
			j--;
		}
		arr[j+1] = key;
	}

	for(int k=0; k<arrlength; k++){
		printf("%d ",arr[k]);
	}
	printf("\n");
}

Java 1.7

public class InsertionSort{

	public static void main(String []args){
		int arr[] = new int[]{5,2,4,6,1,3};

		for(int i=1; i <  arr.length; i++){
			int key = arr[i];
			int j = i - 1;
			while(j>=0 && arr[j]>key){
				arr[j+1] = arr[j];
				j--;
			}
			arr[j+1] = key;
		}

		//let's print the sorted array

		for(int i : arr){
			System.out.print(i+" ");
		}
		System.out.println();
	}
}

Python 2.7.5

arr = [5,2,4,6,1,3]

for i in range(1,len(arr)):
    key = arr[i]
    j = i - 1
    while j>=0 and arr[j]>key:
        arr[j+1] = arr[j]
        j = j - 1
    arr[j+1] = key

print arr

Im currently reading Introduction to algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.

Tapity Tapper (My iOS Flappy Bird Clone using Sprite Kit): The Last One

You can find an index of this series here.

So we are going to wrap up this series with this post.

If you have tried to run the project on the iPad simulator or in an actual iPad, you may notice that all the objects are tiny, this is because the screen of the iPad is bigger, so we need to use bigger sprites.

The fix that I used for this, is quick and dirty.

Also now the “pipes” are randomized:

-(void)addObstacles{
float obstacleWidth = self.size.height/10.0;
float gap = (self.size.height/10.0)*4;
float minHeight = self.size.height/10.0;
float changeableSpace = self.size.height - gap - minHeight*2;
float pieceOfChangeableSpace = changeableSpace / 8 ;
float randomValue = arc4random()%(9);
float upperObstacleHeight =minHeight + randomValue*pieceOfChangeableSpace;
float lowerObstacleHeight =minHeight + (8-randomValue)*pieceOfChangeableSpace;

SKSpriteNode *upperObstacle = [SKSpriteNode spriteNodeWithColor:[UIColor greenColor] size:CGSizeMake(obstacleWidth, upperObstacleHeight)];

SKSpriteNode *lowerObstacle = [SKSpriteNode spriteNodeWithColor:[UIColor greenColor] size:CGSizeMake(obstacleWidth, lowerObstacleHeight)];

upperObstacle.position = CGPointMake(self.size.width+obstacleWidth/2, self.size.height-upperObstacle.size.height/2);

lowerObstacle.position = CGPointMake(self.size.width+obstacleWidth/2, lowerObstacle.size.height/2);

SKAction *moveObstacle = [SKAction moveToX:-obstacleWidth/2 duration:2.0];

[upperObstacle runAction:moveObstacle completion:^(void){
self.scoreLabel.text =[NSString stringWithFormat:@"%d", [self.scoreLabel.text integerValue]+1];
[upperObstacle removeFromParent];
}];
[lowerObstacle runAction:moveObstacle completion:^(void){
[lowerObstacle removeFromParent];
}];

//collision detection
upperObstacle.physicsBody = [SKPhysicsBody bodyWithRectangleOfSize:upperObstacle.size];
//we don't want this object to be animated by the physics engine
upperObstacle.physicsBody.dynamic = NO;
upperObstacle.physicsBody.categoryBitMask = JCColliderTypeObstacle;
//same with the lower obstacle
lowerObstacle.physicsBody = [SKPhysicsBody bodyWithRectangleOfSize:lowerObstacle.size];
lowerObstacle.physicsBody.dynamic = NO;
lowerObstacle.physicsBody.categoryBitMask = JCColliderTypeObstacle;
[self addChild:upperObstacle];
[self addChild:lowerObstacle];
}

And also in the snippet above you can see that we added a label to keep the score.

score

As always, you can find the complete code on Github.

Just so you know. . .

I will post the next and final post of Tapity Tapper over the next weekend (I promise) this week (June 16-22, I am so sorry for the delay ).

I also will update the JCInput later that week this month.

In order to prevent this post from being totally useless, I will leave a list of fun things to do:

Also if you happen to be one of the very few readers of this blog, tell me in the comments or in a tweet what do you want to see next. See you soon.