Split an IronClad level into accessible tiles for AI path-finding.

LevelSplit.cpp

#include "IronClad/Math/Math.hpp"
#include "IronClad/Entity/RigidBody.hpp"

using ic::math;
using ic::obj;

// Splits level into accessible 32x32 rectangles.
std::vector<rect_t> partition(const ic::CLevel& Level)
{
    const std::vector<CRigidBody*>& allEntities = 
        Level.GetPhysicalEntities();

    std::vector<rect_t> pathTiles;
    pathTiles.reserve(allEntities.size() << 4);

    // Iterate over each physical entity.
    for(size_t i = 0; i < allEntities.size(); ++i)
    {
        // Iterate over each entity again, finding the ones directly
        // below the current object (if any) off of both the left and 
        // right edges.
        int32_t l = -1, r = -1;
        float left_low_y = 0.f, right_low_y = 0.f;

        for(size_t j = 0; j < allEntities.size(); ++j)
        {
            // Current is above this one
            if(allEntities[i]->GetY() < allEntities[j]->GetY())
            {
                // Check the left edge.
                // 
                // Our X value is within the range of this object
                if(in_range<float>(
                   allEntities[i]->GetX(),  allEntities[j]->GetX(),
                   allEntities[j]->GetX() + allEntities[j]->GetW()))
                {
                    // If we already have one found, check if this one
                    // is closer.
                    if(l >= 0)
                    {
                        if(allEntities[j]->GetY() < allEntities[l]->GetY())
                        {
                            l = j;
                        }
                    }
                    else
                    {
                        l = j;
                    }
                }

                // Check the right edge.
                // 
                // Our X value is within the range of this object
                if(in_range<float>(
                    allEntities[i]->GetX() + allEntities[i]->GetW(),
                    allEntities[j]->GetX(),
                    allEntities[j]->GetX() + allEntities[j]->GetW()))
                {
                    // If we already have one found, check if this one
                    // is closer.
                    if(r >= 0)
                    {
                        if(allEntities[j]->GetY() < allEntities[l]->GetY())
                        {
                            r = j;
                        }
                        else
                        {
                            r = j;
                        }
                    }
                }
            }
        }


        // Now we create the tiles stretching downward to entities 
        // directly below the current.
        
        float x = allEntities[i]->GetX() - 32;

        // Along the left edge.
        if(l >= 0)
        {
            for(size_t y = allEntities[i]->GetY();
                y < allEntities[l]->GetY();
                y += 32)
            {
                pathTiles.push_back(rect_t(x, y, 32, 32));
            }
        }

        if(r >= 0)
        {
            // Along the right edge.
            x += 32 + allEntities[i]->GetW();

            for(size_t y = allEntities[i]->GetY();
                       y < allEntities[r]->GetY();
                       y += 32)
            {
                pathTiles.push_back(rect_t(x, y, 32, 32));
            }
        }

        int w = allEntities[i]->GetW();

        // In the range [obj.x, obj.x + obj.w), create 32x32 "tiles"
        // that represent an accessible area. These tiles are created
        // above the object.
        for(size_t x = allEntities[i]->GetX(); x < w; x += 32)
        {
            pathTiles.push_back(rect_t(x,
                allEntities[i]->GetY() - 32, 32, 32));
        }
    }

    return pathTiles;
}