Wavefront Challange, many different ways to skin a cat.

5-12-2018
In my last article, I introduced the wavefront algorithm and it’s relationship to Dijkstra’s algorithm. We also saw how the wavefront was built

My challenge is twofold, first to try to get Timothy Friez’s Wavefront algorithm, faster and secondly, to transform the function into something I can use with Z88dk (as Z88dk does not support 2D arrays).

I have written a Windows C binary to demonstrate the function, available at https://github.com/andydansby/wavefront. Now I do want to point out the obvious, this is experimental software only, used only to test methods to build a wavefront/grassfire method.

In the code that I wrote in this windows binary, I am using a 15×10 array which was done to mimic the array that I am using in my FASE game and I modified the program to reflect that.

Most of the wavefront functions are found in the wavefront.h file. The only exceptions are wavefront functions that I am currently experimenting with that are found in the form1.h. Once I get a function working properly, I place the function into the wavfront.h file.

So, on with our experiment. The first function I will introduce is the original wavefront algorithm coded by Timothy Friez. Here’s the function.

void WavefrontSearch1(unsigned char array1[15][10], int x_size, int y_size)
{
    bool foundWave = true;
    int currentWave = 1; //Looking for goal first

    while(foundWave == true)
    {
        foundWave = false;
        for(int y=0; y < y_size; y++)
        {
            for(int x=0; x  0) //This code checks the array bounds heading WEST
                        if(array1[goal_x-1][goal_y] == 0)  //This code checks the WEST direction
                            array1[goal_x-1][goal_y] = currentWave + 1;
 
                    if(goal_x  0)//This code checks the array bounds heading SOUTH
                        if(array1[goal_x][goal_y-1] == 0) //This code checks the SOUTH direction
                            array1[goal_x][goal_y-1] = currentWave + 1;
 
                    if(goal_y < (y_size - 1))//This code checks the array bounds heading NORTH
                        if(array1[goal_x][goal_y+1] == 0) //This code checks the NORTH direction
                            array1[goal_x][goal_y+1] = currentWave + 1;
                }//end current wave
            }//end X
        }//end Y
    currentWave++;
    }//end while
}

 
Here we have the original routine, with just one small modification, we are pushing the array and array sizes to the function, other than that, there are no significant changes to the function. It runs pretty fast.

The downside to this function is that it is run in 1 shot. You build the wavefront by looking at the current wave number and all neighbors to the current wave are built. The second downside is that it is a 2D array which is not supported in Z88DK.

My first modification to the routine takes the 2D version and makes it into a 1D version. I call it the 1D, nested loop version. It works by taking our 2D array and turns it into a continuous 1D array. It uses an index to reference the array and simulate a 2D environment. 4 additional indexes reference the north, south, east and west of the center.

//This is a 1D nested loop version of WavefrontSearch1
//nested as in x and y loops
void WavefrontSearch3(unsigned char array2[150], int x_size, int y_size)
{
    bool foundWave = true;
    unsigned char currentWave = 1; //Looking for goal first
    while(foundWave == true)
    {
        foundWave = false;
        for(int y=0; y < y_size; y++)
        {
            for(int x=0; x < x_size; x++)
            {
                //Indexes
                int index = x + x_size * y;
                int north = x + x_size * (y - 1);
                int south = x + x_size * (y + 1);
                int east = 1 + x + x_size * y;
                int west = x - 1 + x_size * y;
                if (y  (y_size - 2))
                    south = index;
                if (x > x_size - 2)
                    east = index;
                if (x  0)
                    {
                        if (array2[west] == 0)
                        {
                            array2[west] = currentWave + 1;
                        }
                    }
                    //This code checks the array bounds heading EAST
                    if(goal_x < (x_size - 1))
                    {
                        if(array2[east] == 0)
                        {
                            array2[east] = currentWave + 1;
                        }                            
                    }
                    //This code checks the array bounds heading SOUTH
                    if(goal_y  0)
                    {
                        if (array2[north] == 0)
                        {
                            array2[north] = currentWave + 1;
                        }
                    }
                }//end current wave
            }//end x
        }//end y
        currentWave++;
    }//end while                    
}

 
Although this routine seems to run slightly slower than the original 2D version, it is still rather fast. The slowdown is possibly due to having to use indexes and the small amount of math required to do so. However, since this is now a 1D array, we can use it almost directly with Z88DK. It works in a way similar to the first function as it looks at the current wave and assigns neighbors accordingly. It is still a nested loop and still is done in a single shot.

For my next version, I decided to create an unnested 1D loop. This takes out the X and Y loop and replaces it with a 0 to 150 single loop with a counter to keep track of the X and Y. For some reason, it seems to run slower than the prior version, again, the extra bit of math adds to the run-time. However, there is a plus side to this, as it is built so that the wavefront could be split into smaller pieces and be built over time, so with some modification, could work out well for this game calling the function during every enemy movement call.

//This is a 1D unnested loop version of WavefrontSearch1
//unnested , no seperate x and y loops
void WavefrontSearch4(unsigned char array2[150], int x_size, int y_size)
{
    bool foundWave = true;
    unsigned char currentWave = 1; //Looking for goal first
    int arraysize = x_size * y_size;
    int x = 0;
    int y = 0;

    while(foundWave == true)
    {
        foundWave = false;
        //loop throughout array
        for(int arrayCounter=0; arrayCounter < arraysize; arrayCounter++)
        {
            int index = x + x_size * y;
            int north = x + x_size * (y - 1);
            int south = x + x_size * (y + 1);
            int east = 1 + x + x_size * y;
            int west = x - 1 + x_size * y;

            if(x == x_size)
            {
                x = 0;//set to first column
                y ++;//move down a row
            }
            if(y == y_size)
            {
                y = 0;//set to first row
                x = 0;//set to first column
            }
            if (y  (y_size - 2))
                south = index;            
            if (x > x_size - 2)
                east = index;            
            if (x  0) //This code checks the array bounds heading WEST
                {
                    if (array2[west] == 0)
                    {
                        array2[west] = currentWave + 1;
                    }
                }                
                if(goal_x < (x_size - 1))//This code checks the array bounds heading EAST
                {
                    if(array2[east] == 0)
                    {
                        array2[east] = currentWave + 1;
                    }                            
                }                
                if(goal_y  0)//This code checks the array bounds heading NORTH
                {
                    if (array2[north] == 0)
                    {
                        array2[north] = currentWave + 1;
                    }
                }
            }//end current wave
            x ++;// move over a column
        }//end loop

        currentWave++;
    }//end while
}

My next modification builds on top of the prior modification, and it runs slightly faster. We provide an extra optimization by starting our search close to the first wave. This skips over our blank areas in the array and then starts building the wave to the north-west of the target. However, if your target is near the start of the array, you will see no difference, if the target it close to the end of the array, you will see a speedup.

//This is a 1D unnested loop version of WavefrontSearch1
//unnested , no seperate x and y loops
//this version starts searching nearer to the kernel
void WavefrontSearch5(unsigned char array2[150], int x_size, int y_size)
{
    bool foundWave = true;
    unsigned char currentWave = 1; //Looking for goal first
    int arraysize = x_size * y_size;
    int x = 0;
    int y = 0;
    int goal_x = 0;
    int goal_y = 0;
    int index, north, south, east, west;
    //here is where we will differ, find the goal first
    for(int arrayCounter=0; arrayCounter < arraysize; arrayCounter++)
    {
        index = x + x_size * y;
        if(x == x_size)
        {
            x = 0;//set to first column
            y++;//move down a row
        }
        if(y == y_size)
        {
            y = 0;//set to first row
            x = 0;//set to first column
        }
        if (array2[index] == 1)
        {
            goal_x = x;
            goal_y = y;
            break;
        }
        x++;// move over a column
    }

    //where to start looking for inital kernel
    // another area where we differ, start near where the target is
    int arrayStart = 1 - goal_x + x_size * goal_y;
    if (arrayStart < x_size * y)// 0
        arrayStart = x_size * y;//make sure we don't go past the start of the array on left side of row
    while(foundWave == true)
    {
        foundWave = false;
        //loop throughout array
        for(int arrayCounter = arrayStart; arrayCounter < arraysize; arrayCounter++)
        {
            index = x + x_size * y;
            north = x + x_size * (y - 1);
            south = x + x_size * (y + 1);
            east = 1 + x + x_size * y;
            west = x - 1 + x_size * y;
            if(x == x_size)
            {
                x = 0;//set to first column
                y ++;//move down a row
            }
            if(y == y_size)
            {
                y = 0;//set to first row
                x = 0;//set to first column
            }
            if (y  (y_size - 2))
                south = index;            
            if (x > x_size - 2)
                east = index;            
            if (x  0)
                {
                    if (array2[west] == 0)
                    {
                        array2[west] = currentWave + 1;
                    }
                }
                //This code checks the array bounds heading EAST
                if(goal_x < (x_size - 1))
                {
                    if(array2[east] == 0)
                    {
                        array2[east] = currentWave + 1;
                    }                            
                }
                //This code checks the array bounds heading SOUTH
                if(goal_y  0)
                {
                    if (array2[north] == 0)
                    {
                        array2[north] = currentWave + 1;
                    }
                }
            }//end current wave
            x ++;// move over a column
        }//end loop
        currentWave++;
        arrayStart = 0;// the next time we loop around, have to start at 0
    }//end while
}

This code is longer and more complex (if only by a little), so whereas it runs faster, it takes up more memory. I’m not sure if it is the tradeoff that I want for this game as the speed increase may not be worth the size.

My next version again will take up more memory but builds upon the prior function by pre-seeding the array. The idea behind this function is, since we know where our destination is, we will also know where the next step (wave) is from the first step. We just need to accommodate any barriers and build up the second step. We then iterate over the array and hopefully, the grassfire/wavefront build up faster.

//This is a 1D unnested loop version of WavefrontSearch1
//unnested , no seperate x and y loops
//this version starts searching nearer to the kernel
// as well as pre-seeding the kernel
void WavefrontSearch6(unsigned char array2[150], int x_size, int y_size)
{
    bool foundWave = true;
    unsigned char currentWave = 1; //Looking for goal first

    int arraysize = x_size * y_size;
    int x = 0;
    int y = 0;
    int goal_x = 0;
    int goal_y = 0;
    int index, north, south, east, west;

    //here is where we will differ, find the goal first
    for(int arrayCounter=0; arrayCounter < arraysize; arrayCounter++)
    {
        index = x + x_size * y;
        if(x == x_size)
            {
                x = 0;//set to first column
                y++;//move down a row
            }
        if(y == y_size)
        {
            y = 0;//set to first row
            x = 0;//set to first column
        }

        if (array2[index] == 1)
        {
            goal_x = x;
            goal_y = y;
            break;
        }
        x++;// move over a column
    }

    //here we differ, mark the first wave adjacent to the target
    //now that we know where the goal is, mark the adjacent blocks 
    //with the next step to seed the kernel
    //do this outside any loops
    index = goal_x + x_size * goal_y;
    north = goal_x + x_size * (goal_y - 1);
    south = goal_x + x_size * (goal_y + 1);
    east = 1 + goal_x + x_size * goal_y;
    west = goal_x - 1 + x_size * goal_y;

    currentWave ++;//currentwave should be at 2 now
    
    //Summary: Array index 'south' is used before limits check.
    //Message: Defensive programming: The variable 'south' is used as an array index before it is checked 
    //that is within limits. This can mean that the array might be accessed out of bounds. 
    //Reorder conditions such as '(a[i] && i < 10)' to '(i  -1) && (array2[north] != 255))
        array2[north] = currentWave;

    if ((south < x_size * y_size) && (array2[south] != 255))
        array2[south] = currentWave;

    if ((goal_x  0) && (array2[west] != 255))
        array2[west] = currentWave;
    //done seeding the kernel

    // where to start looking for inital kernel
    // another area where we differ, 
    // start near the northwest of the target
    int arrayStart = (goal_x - 1) + x_size * (goal_y - 2);
    
    // make sure we don't go past the start of the array on left side of row
    // at this point, we know where the goal is and we know
    // that the first wave has been seeded

    //we will then start looking for the next wave to the NorthWest
    //of the destination to start our next wave

    x = goal_x - 1;
    y = goal_y - 2;

    while(foundWave == true)
    {
        foundWave = false;

        //loop through the array, first time to the northwest of the target
        for(int arrayCounter = arrayStart; arrayCounter < arraysize; arrayCounter++)
        {
            index = x + x_size * y;
            north = x + x_size * (y - 1);
            south = x + x_size * (y + 1);
            east = 1 + x + x_size * y;
            west = x - 1 + x_size * y;
                        
            if(x == x_size)
            {
                x = 0;//set to first column
                y++;//move down a row
            }
            if(y == y_size)
            {
                y = 0;//set to first row
                x = 0;//set to first column
            }        

            if (y  (y_size - 2))
                south = index;            
            if (x > (x_size - 2))
                east = index;            
            if (x  0)
                {
                    if (array2[west] == 0)
                    {
                        array2[west] = currentWave + 1;
                    }
                }

                //This code checks the array bounds heading EAST
                if(goal_x < (x_size - 1))
                {
                    if(array2[east] == 0)
                    {
                        array2[east] = currentWave + 1;
                    }                            
                }

                //This code checks the array bounds heading SOUTH
                if(goal_y  0)
                {
                    if (array2[north] == 0)
                    {
                        array2[north] = currentWave + 1;
                    }
                }
                
            }//end current wave

            x++;// move over a column
        }//end loop
        //now that the first two waves are found and seeded
        //we start looking for our next wave from the top
        currentWave ++;
        arrayStart = 0;
    }//end while
}

Even though the concept should be sound, the actual execution of the code reveals two problems. First it is larger than the prior code functions and secondly, it runs slower. This, unfortunately, will not make the cut which is sad, since I spent a while coming up with the idea and coding it. Not all of my ideas are golden.

My next function, I’m going back to some basics and not try to shortcut the system. I am however going to lean the code toward the direction that we will experience with the game. In the prior functions, we look for the destination first before we start building the wavefront. In actuality, we already know where the target is at all times in the game environment, so let’s start out there. This next function uses the prior knowledge of where the target is.

//This is a 1D unnested loop version of WavefrontSearch1
//unnested , no seperate x and y loops
// this assumes we know where the target is.
// this will be closer to the game parameters
void WavefrontSearch7(unsigned char array2[150], int x_size, int y_size, int target_xx, int target_yy)
{
    bool foundWave = true;
    unsigned char currentWave = 1; //Looking for goal first

    int arraysize = x_size * y_size;
    int x = 0;
    int y = 0;

    int index = 0;
    int north = 0;
    int south = 0;
    int east = 0;
    int west = 0;

    int arrayStart = 0;

    while(foundWave == true)
    {
        foundWave = false;

        //loop throughout array
        for(int arrayCounter=arrayStart; arrayCounter < arraysize; arrayCounter++)
        {
            index = x + x_size * y;
            north = x + x_size * (y - 1);
            south = x + x_size * (y + 1);
            east = 1 + x + x_size * y;
            west = x - 1 + x_size * y;

            if(x == x_size)
            {
                x = 0;//set to first column
                y ++;//move down a row
            }
            if(y == y_size)
            {
                y = 0;//set to first row
                x = 0;//set to first column
            }

            if (y  (y_size - 2))
                south = index;
            
            if (x > x_size - 2)
                east = index;
            
            if (x  0)
                {
                    if (array2[west] == 0)
                    {
                        array2[west] = currentWave + 1;
                    }
                }

                //This code checks the array bounds heading EAST
                if(goal_x < (x_size - 1))
                {
                    if(array2[east] == 0)
                    {
                        array2[east] = currentWave + 1;
                    }                            
                }

                //This code checks the array bounds heading SOUTH
                if(goal_y  0)
                {
                    if (array2[north] == 0)
                    {
                        array2[north] = currentWave + 1;
                    }
                }

            }//end current wave

            x++;// move over a column
        }//end loop

        currentWave++;
        arrayStart = 0;
    }//end while
}

This works well and while slightly slower than my wavefront 3 function and even slower than the original routine, it still seems to be the winner, since the function can be broken into chunks, has knowledge of the target of all times and takes up a smaller memory footprint, seems to be the one to use.

As for my challenge to beat the original routine in terms of speed, I failed. However, I now know the routine and Timothy Friez code much better, so my knowledge of the wavefront/grassfire is even better.

Just in case, you were wondering what the functions ran speed-wise, here is an accounting of speeds.

WavefrontSearch1 = 348 ticks
WavefrontSearch3 = 431 ticks
WavefrontSearch4 = 641 ticks
WavefrontSearch5 = 626 ticks
WavefrontSearch6 = 838 ticks
WavefrontSearch7 = 448 ticks

Of course, if you find a technique that might be even faster and can deliver in chunks, please feel free to contact me or better yet, go to my Github page https://github.com/andydansby/wavefront, download the code and start experimenting.

Up next, a different way to build a wavefront after some careful and lengthy observation of the building process.

Advertisements

Author: andydansby

I'm a hobbyist coder working with the ZX Spectrum. Living in New York state near the Syracuse area. I grew up in Virgina. The first computer my parents bought for me was a Timex Sinclair 2068.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s