Posts

Showing posts from June, 2015

The Snake Game

Image
This time we're going to look at the elegant algorithm behind the classic Snake game.


# Definition First, we need a matrix and some constants to label the blocks, which are described bellow:

HEADfollows input or block directionscreates BODY blocksBODYrepresents the body of the snakeTAILfollows block directionschanges TAIL to VOIDchanges BODY to TAILFOODsuspends TAIL actionsVOIDrepresents an empty block
Initially, the matrix is created with all the blocks labeled asVOID.


# Illustration After we have the matrix, we need to create the snake itself and the food source. Currently, the snake has no BODY, only the HEAD and the TAIL, both with a left (⬅) direction specified:
FOODHEAD
⬅TAIL


After applying the HEAD definition, the HEAD moves to the left by one block and creates a new BODY block in its old position:

FOODHEAD
⬅BODY
⬅TAIL


Following the TAIL definition, the TAIL moves to the left by one block and replaces the BODY label with TAIL and the old TAIL with VOID:

FOODHEAD
⬅TAIL


If…

Image auto-cropper

Image
Back to image territory, to prove again that the 2D land is awesome. :-)


In this post we're going to talk about image cropping and how to do this generically for any background color, even for backgrounds that have variations of the same color.
# Finding the background color First, we need an algorithm to detect the background color, then we need to find where the background ends in all four parts of the image.
The background color detection is the simplest part. We can take a pixel from one corner of the image and assume that this is the background color.
To validate or invalidate this assumption, we have to test each edge of the image, pixel by pixel, to see if all pixels are about the same color. A clever way is by sampling pixels in larger steps and spiraling-in slowly until we checked all the pixels from a given row or column.
For example, if we have a row of 100 pixels wide, the steps that we'll take in order to check the pixels, are the following:
1020304050607080901009…