Solving Problems with Algorithms

Last week I was tasked with creating a specific image transition. They wanted the image divided into squares that would flip over revealing the next image. The transition would start on the top left square and proceed in a diagonal line to the bottom right square.

Nevermind the details of how I achieved the transition itself. I want to talk about the algorithm I wrote for this project. The algorithm takes a one-dimensional array and translates it into a two-dimensonal array. The second dimension is an array of indexes that refer to which squares should animate.

There is one catch to it and that is the grid of squares the image is sliced into needs to be a perfect square. The image itself can be a rectangle but my algorithm will only work with an equal number of rows and columns. I'll get to that later.

Here are the variables used in this example:

var ROWS:Number = 5;
var COLS:Number = 5;
var aMap:Array = [];
var aDiagonal:Array = [];
var aSequence:Array = [];
var i:Number;
var j:Number;

My first step was to draw out a five by five grid on a sheet of graph paper. I then labelled each square with its index number. Here is what the linear array would look like in two dimensions:

------------------------
| 0 | 5 | 10 | 15 | 20 |
------------------------
| 1 | 6 | 11 | 16 | 21 |
------------------------
| 2 | 7 | 12 | 17 | 22 |
------------------------
| 3 | 8 | 13 | 18 | 23 |
------------------------
| 4 | 9 | 14 | 19 | 24 |
------------------------

The code to generate that grid looks like this:

for(i=0;i<ROWS;i++)
{
    for(j=0;j<COLS;j++)
    {
        aMap.push(i*ROWS+j);
    }
}

Now that the linear array has been created the diagonal path can be built. With the grid drawn out on graph paper I had to figure out how to approach the problem. I asked myself exactly what was I trying to accomplish. I came up with this:


1) Must start at index zero because that represents the top left square
2) Must find a way of dynamically proceeding in some form of diagonal pattern toward the last index in the array, storing each diagonal pattern in another array as it goes
3) Must touch every index in the array at some point or another
4) Must not touch an index more than once
5) Must not include any junk values like undefined or negative

With this list in mind I determined that some while loops were called for. I chose while loops because my comparison variable i would be incremented in different locations and for different values based on the logic. There would also be some nested while loops represented by j that would take care of the diagonal pattern.

The first step of the algorithm is easy: push the first node into the sequence array. So which square should come next? On the grid it could be one of two squares: 1 or 5. I'm sure logic could be made for either direction but I chose 1. This also lead me to a two part approach to this algorithm. The first part involved taking each square in the leftmost column one by one. The second part picks up where the first part leaves off by processing each square along the bottom row.

Starting with a square in the leftmost column, I know that every square in the topmost row of my grid is evenly divisible by the number of rows in a column. Using modulo against my index variable I can check to see when I reach the top row. Whenever the modulo comparison returns zero I know I can't go any higher and I need to continue on to the next diagonal. Since index zero is already handled I can exclude this one. It would just make things messy anyway.

With each index in the leftmost column we can calculate the index diagonally up and to the right by adding the number of rows in a column minus one. So the first part looks like this:

0
-----------------
1 + (5-1) = 5
5
-----------------
2 + (5-1) = 6
6 + (5-1) = 10
10
-----------------
3 + (5-1) = 7
7 + (5-1) = 11
11 + (5-1) = 15
15
-----------------
4 + (5-1) = 8
8 + (5-1) = 12
12 + (5-1) = 16
16 + (5-1) = 20
20

At this point the sequence array looks like this:

[ [0], [1,5], [2,6,10], [3,7,11,15], [4,8,12,16,20] ]

That's over half of the grid. Unfortunately, the game changes slightly. We've reached the bottom of the leftmost column. Given the indexes that have been touched so far, the next highest number that hasn't been touched just happens to be the index that is exactly one column over from the last one we started from. This begins part two of the algorithm where instead of adding one to start the next diagonal we add the number of rows in a column.

There's also the issue that we can't use modulo to determine the end of a diagonal anymore. I chose to perform a check on the index value itself. If the index I'm working with is greater than the total number of possible squares then I know I've reached the end of the diagonal. In this example the indexes go from 0 to 24 so once we reach 24 that's the end of the algorithm.

The rest of the diagonal grid looks like this:

9 + (5-1) = 13
13 + (5-1) = 17
17 + (5-1) = 21
21
-----------------
14 + (5-1) = 18
18 + (5-1) = 22
22
-----------------
19 + (5-1) = 23
23
-----------------
24

Now the sequence array looks like this:
[ [0], [1,5], [2,6,10], [3,7,11,15], [4,8,12,16,20], [9.13.17.21], [14,18,22], [19,23], [24] ]

At this point every square has been touched once and no bad data has leaked in anywhere. The algorithm successfully generated a diagonal starting in the top left and stopping in the bottom right. Let's look at the code:


/*
the overall index counter used to determine what index starts a diagonal and as a comparison for when to stop the algorithm. i should start at zero and should be considered valid as long as it is less than the number of rows multiplied by the number of columns. In this example i starts at 0 and is valid up to 24.
*/

i = 0;
while(i < ROWS * COLS)
{

/*
The diagonal array temporarily holds indexes for the diagonal currently being solved. Since we're about to start a new diagonal this has to be reset. That's our next line:
*/

aDiagonal = [];

/*
Here the logic splits. Index 0 and index 24 are special cases being the first and last and need to be handled separately.
*/

if(i == 0 || i == ROWS*COLS-1)
{
    /*
    push that node into the sequence
    increment i and continue the loop
    */
    aDiagonal.push(aMap[i]);
    aSequence.push(aDiagonal);
    ++i;
    continue;
}

/*
Incrementing i on index 0 sends us down the leftmost column. Incrementing i on index 24 ends up breaking the main while loop. Since in this code block there's nothing else that we need to do I used the continue keyword to skip to the main while evaluation.

The next block of code contains one of the nested while loops. This block is responsible for building the first half of diagonals.
*/

else if(i < ROWS - 1)
{
    /*
        set the starting node of this diagonal to i
        push the starting node into the diagonal
        while j is not evenly divisible by the number of rows
        increment j by the number of rows minus one
        push the referenced node into the diagonal
        push the diagonal into the sequence
    */
    j = i;
    aDiagonal.push(aMap[j]);
    while(j % ROWS != 0)
    {
        j += ROWS - 1;
        aDiagonal.push(aMap[j]);
    }
    aSequence.push(aDiagonal);
    ++i;
}

/*
All that's left is the other half of the diagonals. Since the logic changes we need another else.
*/

else
{
    /*
        set the starting node of this diagonal to i
        while j is less than the last possible node
        push the node into the diagonal
        increment j by the number of rows minus one
        push the diagonal into the sequence
        increment i by the number of rows to skip to the next column
    */
    j = i;
    while(j < ROWS * COLS - 1)
    {
        aDiagonal.push(aMap[j]);
        j += ROWS - 1;
    }
    aSequence.push(aDiagonal);
    i += ROWS;
}
}

/*
That's the end of the algorithm. Now we can loop through the sequence array and verify that all the indexes are indeed correct diagonals in the correct order.
*/


for(i=0;i<aSequence.length;i++)
{
    trace(aSequence[i]);
}


This algorithm was very easy to write. It's also scalable. What made it easy to write is I followed my plan on paper before writing any code. Performing the loops manually allowed me to see better what I was doing and what code I would need. That allowed me to spot problem areas and resolve them in english before I started working in Actionscript. I think this approach works well not only for algorithms but for coding in general. You can't just start writing code and expect to get anything worthwhile out of it. You have to understand where you're going.

The only problem I have with this algorithm is that if ROWS and COLS are not equal you get wildly inaccurate results. Perhaps the algorithm could be split in two with a check to see if ROWS and COLS are equal. If not, a different algorithm could be used that takes these problems into account. I welcome comments.

I also want to say that I fucking hate writing code in Blogger. Where the fuck is the ubb-style wrapper for code??

Blend Modes as a Mask

today i ran into a problem with gradient masks. the problem seems to be that flash 8 does not appreciate a mask using a gradient to be itself masked by anything else. the effect that such a combination produces is a flickering of stage assets akin to compiling with an error in your code. after much experimentation i google'd something that led me to using the blend mode instead of cacheasbitmap/setmask. it works perfectly and is not a big deal to set up.

take your gradient mask symbol and change the blendmode to alpha (from the post i read erase works too but i haven't tried it since alpha worked). you can change the blendmode in a couple of ways. one way is in the flash ide. there is a blend mode drop down on the properties of the movieclip. another way is by code. reference the movieclip's blendMode property and assign it the string 'alpha'.

MovieClip.blendMode = 'alpha';

place the movieclip / shape being masked on a layer below your 'mask' but do not set either layer as a mask layer.

convert these two layers into its own movieclip.

set the blendmode of this combined movieclip to 'layer' using either of the above methods.

MovieClip.blendMode = 'layer';

if you used the ide to set the blend modes then you will be able to see the effect immediately. if you used code you'll have to compile.

Trigonometric Baby Steps

I've taken my first steps at learning trigonometry this week. I've been working on a game that uses pseudo-trajectory and mathematical collision detection. I thought it a good chance for me to dunk my head into the quicksand that is trig.

My most used function? Math.atan2. I can't recommend it enough for finding angles. The basics of it goes like this:

ObjectA has an X and a Y coordinate and ObjectB also has an X and a Y coordinate. Start with one object (I'll start with ObjectA) and subtract each axis from each other.

var nRun:Number = ObjectA._x - ObjectB._x;
var nRise:Number = ObjectA._y - ObjectB._y;

Math.atan2 takes these two numbers as arguments like so:

var nRadians:Number = Math.atan2(nRise,nRun);

There you have it. You now know, in radians, what angle ObjectA points at ObjectB. If you want to see it in degrees so you can rotate your movie clip:

var nDegrees:Number = nRadians / Math.PI * 180;