Homework 2 Notes

1. Instructions

This assignment is about creating the Cave and Dungeon. We will also add more functionality to the Denizen class. However, the derived classes of Denizen will be unchanged.

  • Cave:

    • Cave is a class that represents a single cave in the dungeon.
    • Attributes:
      • id: a unique identifier for the cave
      • tunnels: a std::unordered_map<int, std::weak_ptr<Cave>> of the caves that are adjacent to this cave
      • denizens: a std::set<std::shared_ptr<Denizen>, CompareThings> of the denizens that are currently in this cave
    • Methods:
      • void ConnectTo(const std::shared_ptr<Cave> &destination): adds a tunnel to the destination cave.
      • int GetCaveId(): returns the cave's id.
      • std::vector<int> GetConnectedIds(): returns a vector of the ids of the caves that are connected to this cave.
      • void AddDenizen(const std::shared_ptr<Denizen> &newDenizen): adds a denizen to the cave.
      • bool HasDenizens(): returns true if the cave has any denizens.
      • bool HasDenizen(const DenizenIdentifier &identifier): returns true if the cave has a denizen with the given identifier.
      • IDungeon &GetDungeon() returns a reference to the dungeon that this cave is in. There is of course only one dungeon. This method is used to call the methods of the dungeon.
      • The will be more methods in the future, but these are the ones that are needed for this assignment.

  • Dungeon:

    • Dungeon is a class that represents the entire dungeon. It is in charge of managing all the caves and the denizens. Dungeon is actually a derived class of IDungeon, which is an interface that is used by the Cave class to call the methods of the dungeon.
    • Attributes:
      • provider: a std::shared_ptr<IRandomProvider> that is used to generate random numbers.
      • caveDenizens: a std::unordered_map of all the caves in the dungeon.
      • caves: a std::unordered_map of all the denizens in the dungeon.
    • Methods:
      • const std::shared_ptr<Cave> &FindCave(int caveId): use the caves attribute to find the cave with the given id and return a pointer to it.
      • void AddDenizen(const std::shared_ptr<Denizen> &newDenizen): add a denizen a random cave.
      • void AddToCave(const std::shared_ptr<Denizen> &denizen, int caveId): add a denizen to a specific cave.
      • There will be more methods in the future, but these are the ones that are needed for this assignment.

  • Context:

    • Context is a class that represents the current state of the game. It is in charge of managing the game state and notifying the user of changes.
    • Attributes:
      • random_provider: a std::shared_ptr<IRandomProvider> that is used to generate random numbers.
      • There will be other attributes in the future that handle state changes and user notifications.

  • IRandomProvider:

    • IRandomProvider is an interface that provides a method for generating random numbers. The whole game is designed such that we can implement the concrete class independently of the rest of the game.
    • Methods:
      • int MakeRandomCave(): returns a random number between 1 and 20.
      • int MakeRandomTunnel(): returns a random number between 0 and 2.
      • float MakeRandomNumber(): returns a random number between 0 and 1.

At the end of the assignment, our directory structure should look like this (disregard the VS project files if you're using a different IDE):

.
├── Assignment2Solution.sln
├── CppUnitLite
│   ├── CppUnitLite.vcxproj
│   ├── Failure.cpp
│   ├── Failure.h
│   ├── Main.cpp
│   ├── Makefile
│   ├── Test.cpp
│   ├── Test.h
│   ├── TestHarness.h
│   ├── TestRegistry.cpp
│   ├── TestRegistry.h
│   ├── TestResult.cpp
│   ├── TestResult.h
│   ├── WFailure.cpp
│   ├── WFailure.h
│   └── XxxTest.cpp
├── HuntTheWumpusLib
│   ├── Arrow.cpp
│   ├── Arrow.h
│   ├── Bat.cpp
│   ├── Bat.h
│   ├── Cave.cpp
│   ├── Cave.h
│   ├── Context.h
│   ├── Denizen.cpp
│   ├── Denizen.h
│   ├── Dungeon.cpp
│   ├── Dungeon.h
│   ├── HuntTheWumpusLib.vcxproj
│   ├── HuntTheWumpusLib.vcxproj.user
│   ├── Hunter.cpp
│   ├── Hunter.h
│   ├── Makefile
│   ├── Pit.cpp
│   ├── Pit.h
│   ├── RandomProvider.h
│   ├── Wumpus.cpp
│   └── Wumpus.h
├── Makefile
└── UnitTestHuntTheWumpus
    ├── Makefile
    ├── TestArrow.cpp
    ├── TestBat.cpp
    ├── TestCave.cpp
    ├── TestDungeon.cpp
    ├── TestHelperDungeon.h
    ├── TestHelperRandomProvider.h
    ├── TestHelperTestEnvironment.cpp
    ├── TestHelperTestEnvironment.h
    ├── TestHunter.cpp
    ├── TestPit.cpp
    ├── TestThingInCave.cpp
    ├── TestWumpus.cpp
    ├── UnitTestHuntTheWumpus.cpp
    ├── UnitTestHuntTheWumpus.vcxproj
    ├── UnitTestHuntTheWumpus.vcxproj.filters
    └── UnitTestHuntTheWumpus.vcxproj.user

2. Implementing Cave

Take a look at Cave.h:

#pragma once

#include "Denizen.h"

#include <memory>
#include <set>
#include <unordered_map>
#include <vector>

namespace HuntTheWumpus
{
    class IDungeon;

    struct CompareThings
    {
        bool operator()(const std::shared_ptr<Denizen> &thing1, const std::shared_ptr<Denizen> &thing2) const;
    };

    class Cave
    {
    public:
        explicit Cave(int caveId, IDungeon &dungeon);
        ~Cave() = default;

        void ConnectTo(const std::shared_ptr<Cave> &destination);

        const std::weak_ptr<Cave> &GetConnectedCave(int caveId);

        int GetCaveId() const { return m_caveId; }

        std::vector<int> GetConnectedIds() const;

        void AddDenizen(const std::shared_ptr<Denizen> &newDenizen);

        bool HasDenizens() const { return !m_denizens.empty(); }
        bool HasDenizen(const DenizenIdentifier &identifier) const;

        IDungeon &GetDungeon() const { return m_dungeon; }

        Cave() = delete;
        Cave(const Cave&) = delete;
        Cave(Cave&&) = delete;
        Cave& operator=(const Cave&) = delete;
        Cave& operator=(Cave&&) = delete;

    private:
        int m_caveId;
        IDungeon &m_dungeon;

        std::set<std::shared_ptr<Denizen>, CompareThings> m_denizens;
        std::unordered_map<int, std::weak_ptr<Cave>> m_tunnels;
    };
}

Several things to note here:

  • The constructor is marked explicit. This is a good practice to follow for single-argument constructors, as it prevents the compiler from performing implicit conversions that may lead to unexpected behavior. For example, if we had a function that took a Cave as an argument, the compiler would not allow us to pass in an int instead.

  • The destructor is marked default. This is because STL containers such as std::set and std::unordered_map will automatically call the destructor of their elements when they are destroyed. Therefore, we don't need to explicitly call the destructor of m_denizens and m_tunnels.

  • The other constructors and assignment operators are marked delete. This is because each Cave is unique and should not be copied or moved. Having control over the copy and move semantics of our classes is important for preventing bugs and memory leaks.

  • The CompareThings struct is a functor that is used to compare two Denizen objects. It is used by the std::set container to sort the denizens in the cave. The std::set can actually also take a function or lambda function as an argument, but the functor approach is more flexible since it can have state. The functor is implemented in Cave.cpp:

bool CompareThings::operator()(const std::shared_ptr<Denizen>& thing1, const std::shared_ptr<Denizen>& thing2) const
{
    return thing1->GetPriority() > thing2->GetPriority();
}

where GetPriority() is a new method that we will add to the Denizen class later.

  • ConnectTo and AddDenizen are implemented using the emplace method of their respective containers. This is more efficient than using insert because it avoids the creation of temporary objects.
void Cave::ConnectTo(const std::shared_ptr<Cave>& destination)
{
    m_tunnels.emplace(destination->GetCaveId(), destination);
}

    void Cave::AddDenizen(const std::shared_ptr<Denizen>& newDenizen)
{
    m_denizens.emplace(newDenizen);
}
  • The GetConnectedIds method takes advantage of several C++17 features. It is implemented using a range-based for loop, with the help of structured bindings for unpacking the key-value pairs of the m_tunnels map. The use of auto helps to avoid the need to explicitly specify the type of the iterator. The use of emplace_back is more efficient than push_back. The caveIds vector is returned by value, which is fine because the compiler will perform copy elision (return-value optimization) to avoid the unnecessary copy.
std::vector<int> Cave::GetConnectedIds() const
{
    std::vector<int> caveIds;

    for (auto&& [caveId, cave] : m_tunnels)
    {
        caveIds.emplace_back(caveId);
    }

    return caveIds;
}
  • std::ranges::find_if returns an iterator to the first element in the range that satisfies the predicate. If no such element is found, it returns an iterator to the end of the range, i.e., m_denizens.end(). The lambda function captures the identifier argument by reference ([&]), and the const qualifier ensures that the lambda function does not modify the captured variable.
bool Cave::HasDenizen(const DenizenIdentifier &identifier) const
{
    const auto found = std::ranges::find_if(m_denizens, [&](const auto &denizen)
    {
        return denizen->GetIdentifier().m_category == identifier.m_category;
    });

    return found != m_denizens.end();
}

3. Implementing Dungeon

Take a look at Dungeon.h:

#pragma once

#include "Denizen.h"
#include "Cave.h"

#include <memory>
#include <unordered_map>

namespace HuntTheWumpus
{
    class IDungeon
    {
    public:

        IDungeon() = default;
        virtual ~IDungeon() = default;

        virtual const std::shared_ptr<Cave> &FindCave(int caveId) = 0;

        IDungeon(const IDungeon &) = default;
        IDungeon(IDungeon &&) = default;
        IDungeon &operator=(const IDungeon &) = default;
        IDungeon &operator=(IDungeon &&) = default;
    };

    class Dungeon final : public IDungeon
    {
    public:

        explicit Dungeon(Context &providers);
        ~Dungeon() override = default;

        const std::shared_ptr<Cave> &FindCave(int caveId) override;

        Dungeon(const Dungeon &) = delete;
        Dungeon(Dungeon &&) = delete;
        Dungeon &operator=(const Dungeon &) = delete;
        Dungeon &operator=(Dungeon &&) = delete;

    private:

        void Initialize(Context &providers);
        void AddDenizen(const std::shared_ptr<Denizen> &newDenizen);
        void MakeTunnels() const;
        void AddToCave(const std::shared_ptr<Denizen> &denizen, int caveId);

        Context &m_providers;
        std::unordered_map<DenizenIdentifier, std::shared_ptr<Denizen>, DenizenIdentifierHasher> m_caveDenizens;
        std::unordered_map<int, std::shared_ptr<Cave>> m_caves;
    };
}

Several things to note here:

  • The Dungeon is initialized with a Context object, which is a class that represents the current state of the game. Under the hood, the constructor calls the Initialize method, which is implemented as follows:
Dungeon::Dungeon(Context& providers)
    : m_providers(providers)
{
    Initialize(providers);
}

void Dungeon::Initialize(Context& providers)
{
    for (auto idx = 1; idx <= 20; ++idx)
    {
        m_caves.emplace(idx, std::make_shared<Cave>(idx, *this));
    }

    MakeTunnels();

    AddDenizen( std::make_shared<Bat>(0, m_providers) );
    AddDenizen( std::make_shared<Bat>(1, m_providers) );
    AddDenizen( std::make_shared<Wumpus>(0, m_providers) );
    AddDenizen( std::make_shared<Pit>(0, m_providers) );
    AddDenizen( std::make_shared<Pit>(1, m_providers) );

    // Put the hunter in a random empty cave.
    auto hunterPlaced = false;

    while (!hunterPlaced)
    {
        const auto hunterCave = providers.m_random.MakeRandomCave();

        if (m_caves[hunterCave]->HasDenizens())
        {
            continue;
        }

        AddToCave(std::make_shared<Hunter>(providers), hunterCave);

        hunterPlaced = true;
    }
}
  • The m_caves map is initialized with 20 caves, each with a unique id. The m_caveDenizens map is empty at this point.
  • Then, MakeTunnels is called to connect the caves together. The network of caves is illustrated below:

Cave Network

and the implementation of MakeTunnels is as follows:

void Dungeon::MakeTunnels() const
{
    const std::vector<std::pair<int, std::vector<int> > > tunnelPairs {
        { 1, {2, 5, 8} },
        { 2, {1, 3, 10} },
        { 3, {2, 4, 12} },
        { 4, {3, 5, 14} },
        { 5, {1, 4, 6} },
        { 6, {5, 7, 15} },
        { 7, {6, 8, 17} },
        { 8, {1, 7, 9} },
        { 9, {8, 10, 18} },
        { 10, {2, 9, 11} },
        { 11, {10, 12, 19} },
        { 12, {3, 11, 13} },
        { 13, {12, 14, 20 } },
        { 14, {4, 13, 15} },
        { 15, {6, 14, 16} },
        { 16, {15, 17, 20} },
        { 17, {7, 16, 18} },
        { 18, {9, 17, 19} },
        { 19, {11, 18, 20} },
        { 20, {13, 16, 19} }
    };

    for (auto&& [caveId, neighborIds] : tunnelPairs)
    {
        const auto cave = m_caves.at(caveId);

        for (auto&& neighborId : neighborIds)
        {
            const auto neighbor = m_caves.at(neighborId);
            cave->ConnectTo(neighbor);
        }
    }
}
  • Notice how all other denizens are added using the AddDenizen method (add to a random cave), but the hunter is added using the AddToCave method (add to a specific cave). This is because we want to ensure that the hunter is placed in an empty cave. In my opinion, those methods can be better named as AddDenizenToRandomCave and AddDenizenToCave, respectively. They are implemented as follows:
void Dungeon::AddDenizen(const std::shared_ptr<Denizen>& newDenizen)
{
    auto denizenPlaced = false;

    while (!denizenPlaced)
    {
        const auto denizenCave = m_providers.m_random.MakeRandomCave();

        // Verify that cave does not have a like Denizen in it.
        if (m_caves[denizenCave]->HasDenizen(newDenizen->GetIdentifier()))
        {
            continue;
        }

        AddToCave(newDenizen, denizenCave);

        denizenPlaced = true;
    }
}

void Dungeon::AddToCave(const std::shared_ptr<Denizen>& denizen, const int caveId)
{
    m_caveDenizens.emplace(denizen->GetIdentifier(), denizen);

    const auto cave = m_caves.at(caveId);

    denizen->EnterCave(cave);
    cave->AddDenizen(denizen);
}
  • The FindCave method is implemented using the at method of the m_caves map. This is because we want to throw an exception if the cave is not found. The at method will throw an std::out_of_range exception if the key is not found. The output of m_caves.at(caveId) is a std::shared_ptr<Cave>. Here we prefix auto with const, the deduced type becomes a const-qualified version of the original type.

4. Implementing Context and IRandomProvider

Take a look at Context.h:

#pragma once

namespace HuntTheWumpus
{
    class IRandomProvider;

    struct Context
    {
        IRandomProvider &m_random;
    };
}

It is a simple struct that contains a reference to an IRandomProvider object. There will be more attributes in the future, but this is all we need for this assignment.

The IRandomProvider interface is implemented in RandomProvider.h:

#pragma once

namespace HuntTheWumpus
{
    class IRandomProvider
    {
    public:

        IRandomProvider() = default;
        virtual ~IRandomProvider() = default;

        // Produce random numbers in the [1, 20] range uniformly.
        virtual int MakeRandomCave() = 0;

        // Produce random numbers in the [0, 2] range uniformly.
        virtual int MakeRandomTunnel() = 0;

        // Produce random number in the range [0, 1] range uniformly.
        virtual float MakeRandomNumber() = 0;

        IRandomProvider(const IRandomProvider &) = default;
        IRandomProvider(IRandomProvider &&) = default;
        IRandomProvider &operator=(const IRandomProvider &) = default;
        IRandomProvider &operator=(IRandomProvider &&) = default;
    };
}

So, there is actually no concrete implementation of IRandomProvider in the HuntTheWumpusLib project. Instead, we will create a test implementation in the UnitTestHuntTheWumpus project. This is because we want to be able to control the random numbers that are generated during testing. The test implementation is as follows:

class TestRandomProvider final : public HuntTheWumpus::IRandomProvider
{
public:
    TestRandomProvider() = default;
    ~TestRandomProvider() override = default;

    int MakeRandomCave() override
    {
        if(m_sequence == m_randomCaveSequence.end())
        {
            m_sequence = m_randomCaveSequence.begin();
        }

        return *m_sequence++;
    }

    void SetCaveSequence( std::vector<int> &&sequence )
    {
        m_randomCaveSequence = sequence;
        m_sequence = m_randomCaveSequence.end();
    }

    int MakeRandomTunnel() override { return 0; }
    float MakeRandomNumber() override { return m_desiredRandomNumber; }

    float m_desiredRandomNumber = 0.0f;

    std::vector<int> m_randomCaveSequence;
    std::vector<int>::const_iterator m_sequence = m_randomCaveSequence.end();

    TestRandomProvider(const TestRandomProvider&) = delete;
    TestRandomProvider(TestRandomProvider&&) = delete;
    TestRandomProvider& operator=(const TestRandomProvider&) = delete;
    TestRandomProvider& operator=(TestRandomProvider&&) = delete;
};

And then we can pass this TestRandomProvider object to the Context object in our unit tests:

TestRandomProvider m_provider;
HuntTheWumpus::Context m_context { m_provider };

And then we can set the desired random cave sequence in our unit tests before creating the Dungeon object:

m_provider.SetCaveSequence({ 1, 2, 3, 4, 5, 6 });
HuntTheWumpus::Dungeon dungeon { m_context };