In a few of my demos I’ve used 2d terrain. I love the effect and its really easy to do especially in 2d. The algorithm I use most is Diamond Square also known as Midpoint Displacement. What’s great about the algorithm besides its easy of use is that it can be used for simple 2d terrain as well as with 3d terrain. For now I will just be talking about generating 2d terrain, in a future article I will discuss how to use the same algorithm to make create height maps that can be used in turn to create 3d terrain.

# algorithm

# Game Related Snippets I always Forget

When I sit down to prototype something new I always find myself looking up the same snippets to do the same types of things. I figured I might as well record them somewhere so I know an easy place to look when I do forget. All the samples will be inÂ Javascript and should be able to be easily converted to any other language.

**Distance Formula**

Obviously a pretty important one, used to tell the distance between 2 objects. Can be used for simple radius collisions as well.

var distance = Math.sqrt((x2 - x1) *(x2-x1) + (y2 - y1) * (y2-y1));

**Move toward an object (Without rotation) with easing**

x += (targetX-x)/speed; y += (targetY-y)/speed;

**Angle Based Movement**

I always see myself needing this one, whether its for an Asteroids clone, or a follow the leader type game.

velX = Math.cos((angle * Math.PI / 180) * thrust); velY = Math.sin((angle * Math.PI / 180) * thrust);

**Friction**

How do I make something slow down if no force is applied?

velX *= .98; //Any val under 1 is suitable for your needs velY *= .98

**2D Matrix**

This is a pretty simple one I know.. but I always seem to forget it. This is how to store a 2d matrix in an array. And how to find a value you need.

// 2d matrix[y * width + x] var arr = [], width = 10; for(x=0; x<width; x++){ for(y=0; y<width; y++){ arr[y * 10 + x] = x + y; //Or whatever value you need to assign } } //Retrieve a value from x:5, y:2 var val = arr[2 * 10 + 5]; //get the x and y from a 1d array var index = 12, x = index % width, // 2 y = Math.floor(index / width); // 1

**Move towards and object at a constant speed**

var tx = targetX - x, ty = targetY - y, dist = Math.sqrt(tx*tx+ty*ty), rad = Math.atan2(ty,tx), angle = rad/Math.PI * 180;; velX = (tx/dist)*thrust; velY = (ty/dist)*thrust;

**Project a point in front of an object**

x + length * Math.cos(angle*Math.PI / 180); y + length * Math.sin(angle*Math.PI / 180);

**Get the angle between objects**

var x = targetX - this.x, y = targetY - this.y; return Math.atan2(x,-y);

**Plot points around a circle**

var rad = 500, total = 50, centerX = 250, centerY = 250; for(var i = 0; i < total; i++){ ctx.beginPath(); ctx.moveTo(centerX,centerX); var x = centerX + rad * Math.cos(2 * Math.PI * i / total), y = centerY + rad * Math.sin(2 * Math.PI * i / total); ctx.lineTo(x, y); ctx.stroke(); ctx.closePath(); }

# Quick Sort algorithm comparison

I’ve been trying to do regular programming exercises lately just to stay sharp and recently I decided to take on sorting algorithms. I used my current language of choice (javascript) and set out to implement the quick sort algorithm. Below is the portion of my code that completes this.

sorting.qSort = function (sortItems, _left, _right) { var left = _left, right = _right, pivot = right; if(right > left){ do{ // From left for(var i = left; i < pivot; i+=1){ left = i; if(sortItems[i] > sortItems[pivot]){ pivot = i; break; } } // From right for(var i = right; i > pivot; i-=1){ right = i; if(sortItems[i] < sortItems[pivot]){ // swap sortItems.swap(i, pivot); pivot = i; break; } } }while((right - left) > 1); this.qSort(sortItems, _left , pivot - 1); this.qSort(sortItems, pivot + 1, _right); return true; } return false; }

The funny thing is really how much quicker this was than the Bubble sort algorithm. The only benefit I can find to bubble sort is it is much faster to implement

sorting.bubSort = function (sortItems) { for(var i = 0; i < sortItems.length; i+=1){ if(sortItems[i] > sortItems[i+1]){ //swap change the incrementor to -1 sortItems.swap(i, i+1); i=-1; } } }

But like many I recommend you never use it. Using quick sort and sorting 2000 items in random order I get an average of 0.08 with bubble sort this increases to 20 seconds! Also I recommend for javascript using the built in sorting function for arrays the below code beat out my implementation of quick sort everytime with an average speed of 0.01 seconds. Of course its also much easier to implement.

sorting.internalSort = function sortNumber(a,b){ return a - b; }

All tests were performed in Chrome. It was a fun exercise overall and helped me brush up on my recursion skills.