Collision

Now that we have some terrain that we can draw to the screen as well as manipulate, the next thing we ideally want to achieve is have worms be able to interact with it.

If we want this to be possible then we need to generate some way of recording and generating data about what should and should not be collided with.

The other thing that we need to do is make sure that the way we store this information is always accessible to Matt’s physics system so the worms can interact with the terrain.

The Theory

In theory generating the terrain collisions should not be too bad. We are going to use a pixel perfect solution so we will need to get data on every individual pixel. The question becomes how then do we decide if a pixel is solid or not?

In order to answer this we simply need to look at what our render target actually is, a container for pixels that act as solid terrain. We don’t not store the background images in our render target, meaning that if the pixel is visible on our render target we want it to be solid.

Every pixel contains a red, green, blue and alpha value which is used to make up its colour and transparency. To check if a pixel is invisible/non-existent we just need to check if its alpha value is 0. This means we can say that if it is not equal to zero then it must be solid.

Then we just check for every pixel in the render target and store the result and we have our data.

The Implementation

Because all we want to know is if a pixel is solid or not we can store this data as a bool array and store it in our terrain data. The next step is to provide some more friendly functions that others can access so we create some functions that allow us to get and set the pixel data in the area at a certain x and y pos:

bool Terrain2D::getSolidValue(int _xpos, int _ypos)
{
    return is_solid_map[_ypos * terrain_width + _xpos];
}

void Terrain2D::setSolidValue(int _xpos, int _ypos, bool _val)
{
     is_solid_map[_ypos * terrain_width + _xpos] = _val;
}

This is simple enough but the hard part is actually generating this data to begin with. We want to populate this data as soon as the collision exists so that the worms do not clip through the floor instantly. So what we can do is when the terrain is first drawn to the render target we can loop through the content of the render target and generate the data then.

We don’t want to create too much clutter in the game.cpp render function though so we will make the collision a function call in the terrain data.

m_terrainData->generateStartingSolids(m_terrain,m_d3dContext.Get(),m_GD);

Now for the biggest issue, processing time. Because the image we are using for the background is 1080x1920 we need to look through 2,073,600‬ pixels and check if their alpha value is 0 or not. This process is easily doable with one loop however it can take several seconds to do correctly which would cause the game to hang when launched. This time could take upwards of 15 seconds! The problem is the actual logic we are running is still quite simple so it was hard to think of ways to speed up what basically is just a if statement being called on each pixel. The solution I found however was threading.

I found that splitting the pixels into 4 seperate threads and then combining the results together was much much faster.

Here is how I did it:

void Terrain2D::generateStartingSolids(RenderTarget* _terrain, ID3D11DeviceContext* _deviceContext, GameData* _GD)
{
    _terrain->Map(_deviceContext);

    int total_pixels = 0;
    int solid_pixels = 0;

    auto start = std::chrono::system_clock::now();
    debug_logger->writeLine(DebugLogger::outputLocations::TERRAIN, DebugLogger::outputTypes::MESSAGE, ("Loading innit terrain collision, this could take a while..."));

    const int num_of_threads = 4;
    int incrementer = terrain_height / num_of_threads;

    std::thread threads[num_of_threads];

    for (int i = 0; i < num_of_threads; i++)
    {
        threads[i] = std::thread(&Terrain2D::constructSolidByChunk, this, incrementer * i, incrementer * (i + 1) - 1, _terrain, _GD);
        debug_logger->writeLine(DebugLogger::outputLocations::TERRAIN, DebugLogger::outputTypes::MESSAGE, ("Lanching thread: " + to_string(i) + "..."));
    }

    for (int i = 0; i < num_of_threads; i++)
    {
        threads[i].join();
    }

    for (int i = 0; i < terrain_width * terrain_height; i++)
    {
        total_pixels++;
        if (is_solid_map[i])
            solid_pixels++;
    }

    auto end = std::chrono::system_clock::now();
    std::chrono::duration<double> time_passed = end - start;
    debug_logger->writeLine(DebugLogger::outputLocations::TERRAIN, DebugLogger::outputTypes::MESSAGE, ("Threading opertaions completed in " + to_string(time_passed.count()) + " seconds"));
    debug_logger->writeLine(DebugLogger::outputLocations::TERRAIN, DebugLogger::outputTypes::MESSAGE, (to_string(solid_pixels) +" Solid pixels detected out of a total of " + to_string(total_pixels)));


    _terrain->Unmap(_deviceContext);
}

Firstly I need the render target on the CPU so we can access the raw pixel data later, but first we set up some debug information for later such as the total pixel and solid pixel count so that we can tell if things are working as we might expect. We then also set up a stopwatch system so that we can check how long this operation lasts.

We use a specific number of threads that we can modify and then determine an incrementer which will be used by our threads so they can find out which parts of the image they need to read.

Next we create an array of threads and for each thread we use a fancy function pointer to allow our threads to call the construct solid by chunk function and pass in the relevant parameters.

Then we tell the threads to join back in order.

Finally we go through the map and count how many pixels there are and which ones are solid.

Then we end the stopwatch and unmap the data.

Let’s have a look at the construct solid by chunk function:

void Terrain2D::constructSolidByChunk(int starting_row, int ending_row, RenderTarget* _terrain, GameData* _GD)
{
    for (int row = starting_row; row < ending_row; row++)
    {
        for (int col = 0; col < terrain_width; col++)
        {
            bool is_Solid = (_terrain->GetPixel(col, row, _GD)->A() > 0);
            setSolidValue(col, row, is_Solid);
        }
    }
}

This function simply loops through all of the pixels it’s been told to check and determines if each pixel it checks is solid by testing if the alpha value is greater than 0. Then it sets the solid value in our array, and because the threads never examine the same pixels and thus never try to write into the array at the same place at the same time we can safely say this is thread safe.

Here is the result of using threads:

The operation went from 15 seconds to 0.0479 seconds!

Side note:

As of yet every time we want to update our collision we would need to re-check every pixel, which is not ideal. For now I will leave it like this as currently it is not noticable, however I will need to refine this later for when the terrain is deformed by weapons. We also have an issue with the viewport as it was not correctly containing the content in the render target until we expanded it to be a bigger size, now that it is bigger everything works as it should!