Bitfield to compact neighbor information in A* grids.

While working on the speed test for my A* pathfinding assignment, I knew that there were big time saves if I could get the size of the grid node struct as small as possible. Since we could precompute the neighbors of the node to save time later on, a method to store which neighbors are valid nodes and should be calculated was something I wanted. I came up with using a bitfield, since coincidentally there are 8 possible neighbors, and 8 bits in a byte, which meant that I could store whether the neighbor was valid or a wall as a set bit.

This was just to check if the nodes are out of bounds using some given helper functions.

void AStarPather::testComputeNodeNeighbours()
{

   

    allNodes->validNeighbours = { 0 };

    mapSize = terrain->get_map_height();

    auto checkOutOfBounds = [&](int i, int j)
    {
        if (i >= mapSize || j >= mapSize || i < 0 || j < 0)
        {
            return false;
        }
        return true;
    };

Here is where I store the information with simple bitshifting.

    std::cout << mapSize << std::endl;

    for (int i = 0; i < mapSize; i++)
    {
        for (int j = 0; j < mapSize; j++)
        {
            allNodes->posX[i * mapSize + j] = i;
            allNodes->posY[i * mapSize + j] = j;

            if (terrain->is_wall(i, j))
            {
              //just ignore
            }
            else
            {
                int bitPos = 0;
                for (int k = -1; k <= 1; ++k)
                {
                    for (int m = -1; m <= 1; ++m)
                    {

                        //the cell itself
                        if (k == 0 && m == 0)
                            continue;
                        if (checkOutOfBounds(i + k, j + m) && !terrain->is_wall(i + k, j + m))
                        {
                         
                            allNodes->validNeighbours[i * mapSize + j] |= 1 << bitPos;

                        }
                        ++bitPos;
                        // GOES FROM BOTTOM LEFT TO BOTTOM RIGHT
                        // SO 1 = only bottom left
                        // 80 = 5th and 7th which is right and top
                        //
                    }
                }

In this assignment, diagonals are only allowed if there aren't walls beside the diagonal, so we have to clear the bits if there's a wall present.

                auto& c = allNodes->validNeighbours[i * mapSize + j];
                //removing diagonals
                    // Mask to isolate the specific corner walls for checking
                const unsigned char bit2_mask = 1 << 1; // 2nd bit
                const unsigned char bit4_mask = 1 << 3; // 4th bit
                const unsigned char bit5_mask = 1 << 4; // 5th bit
                const unsigned char bit7_mask = 1 << 6; // 7th bit

                // Check each condition and set the appropriate bit if the condition is true
                if (!((c & bit2_mask) && (c & bit4_mask)))
                {
                    c &= ~(1 << 0); // clear bottom left diagonal
                }
                if (!((c & bit2_mask) && (c & bit5_mask)))
                {
                    c &= ~(1 << 2); // clear bottom right diagonal
                }
                if (!((c & bit4_mask) && (c & bit7_mask)))
                {
                    c &= ~(1 << 5); // clear top left diagonal
                }
                if (!((c & bit5_mask) && (c & bit7_mask)))
                {
                    c &= ~(1 << 7); // clear top right diagonal
                }
            }
        }
    }
}

Later, we just have to check each bit by &-ing it with 1, allowing us to save time.

      while (temp != 0 )
        {
            if ((temp) & 1)
            {
                 calFinalCost(counter, parent);
    
            }
            counter++;
            temp >>= 1;
        }