1

I have a base type of Entity, and multiple implementations, Enemy, Bunker, Projectile

I have separated these entities into their own containers so I can pass them to different classes to perform different actions on them. However it is becoming clear now this may not have been the best approach. I am currently writing the collisions between the Projectile and Enemy/Bunker. As they have their own separate lists I'm having to write multiple functions to handle the collisions.

The enemies are stored in a 2d grid using std::vector<std::vector<std::unique_ptr<Enemy>>>

The bunkers are stored in a vector std::vector<std::unique_ptr<Bunker>>

The projectiles are stored in a vector std::vector<std::unique_ptr<Projectile>>

Here are the collision functions so far

Projectile -> Enemy collisions

void ProjectileEnemyCollisions()
{
    auto projectileIterator = projectiles.begin();

    while (projectileIterator != projectiles.end()) {
        auto enemyRowIterator = enemies.begin();
        while (enemyRowIterator != enemies.end()) {
            std::vector<std::unique_ptr<Enemy>>const& column = *enemyRowIterator;
            auto enemyColumnIterator = column.begin();

            while (enemyColumnIterator != column.end()) {
                if (projectiles.size() == 0) {
                    break;
                }

                std::unique_ptr<Projectile>const& projectile = *projectileIterator;
                std::unique_ptr<Enemy>const& enemy = *enemyColumnIterator;

                if (m_collisionManager->Collision(projectile->GetBoundingBox(), enemy->GetBoundingBox())) {

                    //collision

                }
                else {
                    ++enemyColumnIterator;
                }
            }
            ++enemyRowIterator;
        }

        if (projectiles.size() != 0) {
            if (projectileIterator != projectiles.end())
                ++projectileIterator;
        }

    }

}

Projectile -> Bunker collisions

void ProjectileBunkerCollisions()
{
    auto projectileIterator = projectiles.begin();

    while (projectileIterator != projectiles.end()) {

        std::unique_ptr<Projectile> const& projectile = *projectileIterator;

        auto bunkerIterator = bunkers.begin();

        while (bunkerIterator != bunkers.end()) {

            if (projectiles.size() == 0) {
                break;
            }

            std::unique_ptr<Bunker> const& bunker = *bunkerIterator;

            if (m_collisionManager->Collision(projectile->GetBoundingBox(), bunker->GetBoundingBox())) {

                //collision

            }
            else {
                ++bunkerIterator;
            }


        }

        if (projectiles.size() != 0) {
            if (projectileIterator != projectiles.end()) {
                ++projectileIterator;
            }
        }
    }
}

All of these types are of Entity, so is there a more efficient way to iterate over them? I feel like having three loops for the enemies, and then having another two loops to check the bunkers seems counter-intuitive. I'm unsure which approach is better, grouping all the entities into a single container and then iterating over them once, or separating them out into different containers like I have now, but having to iterate over them multiple times.

I have also split up the entities so that I don't have to pass around data that isn't required, i.e. for the enemy specific logic, it only requires Enemy objects.


Entity.h

    class Entity {

    friend class MovementManager;

    public:
        Entity(std::unique_ptr<Sprite> sprite) : m_sprite(std::move(sprite)) {

        };

        virtual void Update(DX::StepTimer const& timer) = 0;
        virtual void DealDamage(int damage) = 0;

        bool IsDead() {
            return m_health == 0;
        }

        Sprite& GetSprite() const {
            return *m_sprite;
        }

        XMFLOAT3 GetPosition() const {
            return m_position;
        }

        BoundingBox const& GetBoundingBox() {
            return *m_boundingBox;
        }


    protected:
        std::unique_ptr<Sprite> m_sprite;
        std::unique_ptr<BoundingBox> m_boundingBox;

        XMFLOAT3 m_position;
        XMFLOAT3 m_scale;
        XMFLOAT3 m_rotation;

        int32_t m_health;

        XMFLOAT3 m_velocity;
        XMFLOAT3 m_maxVelocity;
        XMFLOAT3 m_slowdownForce;
        float m_movementSpeed;
        float m_movementStep;


    };

Most recent implementation using the idea from the comments

void HandleCollisions()
{
    std::vector<std::shared_ptr<Projectile>>const& projectiles = m_projectileManager->GetProjectiles();
    std::vector<std::vector<std::shared_ptr<Enemy>>>const& enemies = m_enemyManager->GetEnemies();
    std::vector<std::shared_ptr<Bunker>>const& bunkers = m_bunkerManager->GetBunkers();

    std::vector<std::unique_ptr<EntityBoundingBox>> boundingBoxes;
    //projectiles
    for (std::shared_ptr<Projectile>const& projectile : projectiles) {
        std::unique_ptr<EntityBoundingBox> boundingBox = std::make_unique<EntityBoundingBox>(projectile->GetBoundingBox(), std::weak_ptr<Entity>(projectile));
        boundingBoxes.push_back(std::move(boundingBox));
    }

    //enemies
    for (unsigned int i = 0; i < enemies.size(); ++i) {
        for (unsigned int j = 0; j < enemies[i].size(); ++j) {
            std::unique_ptr<EntityBoundingBox> boundingBox = std::make_unique<EntityBoundingBox>(enemies[i][j]->GetBoundingBox(), std::weak_ptr<Entity>(enemies[i][j]));
            boundingBoxes.push_back(std::move(boundingBox));
        }
    }

    //bunkers
    for (std::shared_ptr<Bunker>const& bunker : bunkers) {
        std::unique_ptr<EntityBoundingBox> boundingBox = std::make_unique<EntityBoundingBox>(bunker->GetBoundingBox(), std::weak_ptr<Entity>(bunker));
        boundingBoxes.push_back(std::move(boundingBox));
    }

    CheckEntityCollisions(boundingBoxes);
}

void CheckEntityCollisions(std::vector<std::unique_ptr<EntityBoundingBox>>& boundingBoxes) {

    for (std::unique_ptr<EntityBoundingBox>& entity1 : boundingBoxes) {
        for (std::unique_ptr<EntityBoundingBox>& entity2 : boundingBoxes) {
            if (entity1 == entity2) continue;

            //if the entity has already been removed, continue
            auto tmp = entity1->GetEntity().lock();
            auto tmp2 = entity2->GetEntity().lock();
            if (!tmp || !tmp2) {
                continue;
            }

            if (m_collisionManager->Collision(entity1->GetBoundingBox(), entity2->GetBoundingBox())) {
                m_eventManager->Fire(Events::EventTopic::COLLISIONS_ENTITY_HIT, { { (void*)&entity1 }, { (void*)&entity2 } });
            }

        }
    }
}
  • Maybe separate the position and size of the enemy from the enemy? That way you can have a single list of objects that have a public method called "collideWith(otherThing)". This new class could have a bunch of sub types per enemy, and hold a reference to the strongly typed enemy object, which then performs the collision logic. – Greg Burghardt Jan 4 at 17:53
  • @GregBurghardt Thanks for the response. Currently my Entity class holds all of that information including things like speed, health etc... Also my entity holds the geometry for that specific entity so it's quite important in terms of updating/rendering. Are you saying I should just move the data (position, health, speed, size) to another class and then reference it? I have added the Entity class to the OP for more clarity. – jjmcc Jan 4 at 18:00
  • I was thinking you could pull the size and position into its own class, something like "EntityBoundingBox" (or named better). You could create sub classes specific to each kind of entity if need be (e.g. BunkerBoundingBox). The public methods would be things like "collide", and might also hold other collision relevant info like velocity, and whether or not the wrapped entity may receive damage. – Greg Burghardt Jan 4 at 18:07
  • 1
    Design questions aside, it is better to assign bounding boxes for everything that are capable of collision, and to give all these bounding boxes to a data structure capable of detecting box-based collisions (intersections) efficiently, such as a quad tree (of rectangles). Not doing so means the code run much more slowly, as efficient spatial data structures have lower runtime complexity than brute-force pairwise collision checks. If two entities have non-box-based collision rules, it is still better to create an inflated bounding box around them, for faster prescreening. – rwong Jan 4 at 18:41
  • Use one main list with the actual objects to handle these cross-over problems, then turn your specific lists into references to the objects instead of owning them directly to make their original intention still handy. – Patrick Hughes Jan 4 at 21:22
1

We can handle things pretty simply with templates. CheckCollisions will progressively unwrap and iterate through vectors until it reaches a unique_ptr to the target. Because it's templated it'll work on both Bunker objects and Enemy objects. Does this solve the problem?

template<class Target>
void CheckCollision(Projectile const& proj, std::unique_ptr<Target> const& target) {
    if(m_collisionManager->Collision(projectile.GetBoundingBox(), target->GetBoundingBox())) {
    //Handle collision 
    }
}
template<class Target>
void CheckCollision(Projectile const& proj, std::vector<Target> const& targets) {
    for(Target const& target : targets) {
        CheckCollision(proj, targets)
    }
}
template<class Target>
void CheckCollision(std::vector<std::unique_ptr<Projectile>> const& projectiles, std::vector<Target> const& targets) {
    for(auto const& projectile_ptr : projectiles) {
        CheckCollision(*projectile_ptr, targets); 
    }
}

void handleCollisions() {
    if(projectiles.size() == 0) return; 
    CheckCollision(projectiles, enemies); 
    CheckCollision(projectiles, bunkers);
}
  • Thanks for the answer! This is much better than what I've currently got. I've actually changed the implementation now which I'll update my OP with but this looks nicer. Although how would this handle the removal of a projectile? For example when I detect a collision (enemy, projectile), I remove both of them immediately. Do you think this would cause any problems? – jjmcc Jan 5 at 11:48
  • @jjmcc You can't remove things from a vector while iterating through it without messing up the iteration. In the luckiest circumstances (where no shrinking happens), that will cause items to be skipped. There is a way to eliminate items while copying and processing from one vector to another vector. But my suggestion is to add a flag to each object indicating whether it's deleted (pending), and to do the actual deletion (vector filtering) afterwards. – rwong Jan 10 at 1:40
  • @rwong Yeah that would be my next thought, just saves an extra iteration if I could do it while iterating. Are you sure it's not possible? I thought vector.erase returns the next valid iterator and then you can check if it's valid or not. – jjmcc Jan 10 at 14:56
  • @jjmcc You might be right: I was over-conservative. The section of page about iterator invalidation says that iterators before the erased item aren't being invalidated, which means implementations are not allowed to do a "shrink_to_fit" as part of "erase", and the erase indeed returns the iterator to the next remaining item, which allows your code to continue processing. Note, however, the end() iterator changes after erase, which means you must call end() every time. – rwong Jan 12 at 0:11

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.