Homework 1 Notes

1. Instructions

This assignment is about creating the Denizen classes, which represent the entities in the game.

The Denizen class is the base class for all denizens in the game:

Denizen - The base class for all denizens in the game.
DenizenIdentifier - A structure that uniquely identifies a denizen. It contains the following properties:
- category - An enum that can be one of the following values: Bat, Pit, Wumpus, Hunter, Arrow.
- instance - An integer that uniquely identifies the denizen within its category.
And overloads the following operators: * operator<=> - Compares two DenizenIdentifier objects. * operator== - Compares two DenizenIdentifier objects.

DenizenProperties - A structure that contains the following 5 boolean properties for a denizen:

Property	`Pit`	`Wumpus`	`Hunter`	`Arrow`	Description
`CarryableByBats`			✓		Whether the denizen can be carried by bats.
`FatalToWumpus`				✓	Whether the denizen is fatal to the Wumpus.
`FatalToHunter`	✓	✓		✓	Whether the denizen is fatal to the hunter.
`EdibleByWumpus`			✓		Whether the denizen is edible by the Wumpus.
`ReportMovement`			✓		Whether the denizen reports its movement.

The following classes are derived from the Denizen class, and for this assignment, we will only need to define its constructor.

Wumpus - A denizen that is the target of the game.
Bat - A denizen that can move the hunter to a random room.
Pit - A denizen that can kill the hunter.
Hunter - The player of the game.
Arrow - A projectile that the hunter can shoot.

Lastly, we will need to define a DenizenIdentifierHasher structure that implements operator() that returns a unique hash for a DenizenIdentifier. Remember to create unit tests for each class, and verify that an instantiated object has the correct identifiers and properties.

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):

.
├── Assignment1Solution.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
│   ├── Denizen.cpp
│   ├── Denizen.h
│   ├── HuntTheWumpus.vcxproj.filters
│   ├── HuntTheWumpusLib.vcxproj
│   ├── Hunter.cpp
│   ├── Hunter.h
│   ├── Makefile
│   ├── Pit.cpp
│   ├── Pit.h
│   ├── Wumpus.cpp
│   └── Wumpus.h
├── Makefile
└── UnitTestHuntTheWumpus
    ├── Makefile
    ├── TestArrow.cpp
    ├── TestBat.cpp
    ├── TestDenizen.cpp
    ├── TestHunter.cpp
    ├── TestPit.cpp
    ├── TestWumpus.cpp
    ├── UnitTestHuntTheWumpus.cpp
    ├── UnitTestHuntTheWumpus.vcxproj
    └── UnitTestHuntTheWumpus.vcxproj.filters

2. Implementing `Denizen`

The Denizen class is the base class for all denizens in the game:

#pragma once

#include <compare>
#include <memory>

namespace HuntTheWumpus
{
    class Denizen
    {
    public:
        Denizen(const DenizenIdentifier& identifier, DenizenProperties &&properties);
        virtual ~Denizen() = default;

        // Properties of Thing
        const DenizenProperties &Properties() const { return m_properties; }

        const DenizenIdentifier &GetIdentifier() const { return m_identifier; }

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

    protected:

        DenizenIdentifier m_identifier;
        DenizenProperties m_properties;
    };
}

Several things to note:

Abtract class: The Denizen class is abstract, so we can't instantiate it directly. However, we still define a constructor because we want to have control over how the derived classes are instantiated. This also allows us to avoid duplicating code in the derived classes.
Design choice of constructor parameters: The interesting design choice of the parameter of the constructor Denizen(const DenizenIdentifier& identifier, DenizenProperties &&properties). The identifier parameter is passed by const reference, which accepts both lvalues and rvalues. However, the properties parameter is passed by rvalue reference, which only accepts rvalues. This is because we envision the derived classes to be instantiated in the following ways:

Pit::Pit(const int pitInstance)
    : Denizen({ Category::Pit, pitInstance }, { false, false, true, false, false })
{
}

Default destructor: The properties of the Denizen class are all value types that are automatically destroyed when the object is destroyed. Therefore, we don't need to define a destructor.
Deleted copy and move constructors and assignment operators: Each instance of a denizen is unique, and must only be instantiated with the constructor. Therefore, we delete the copy and move constructors and assignment operators to prevent the compiler from generating them.
Protected member variables: The member variables are protected so that the derived classes can access them.

Now, let's implement the DenizenIdentifier structure:

#include <compare>

enum class Category
{
    Wumpus,
    Pit,
    Bat,
    Hunter,
    Arrow
};

struct DenizenIdentifier
{
    Category m_category;
    int m_instance;

    bool operator==(const DenizenIdentifier &other) const;
    std::strong_ordering operator <=>(const DenizenIdentifier &other) const;
};

As introduced in lecture 2, the three-way comparison operator <=> is a new feature in C++20. It returns one of the following values:

std::strong_ordering::less if the left operand is less than the right operand.
std::strong_ordering::equal if the left operand is equal to the right operand.
std::strong_ordering::greater if the left operand is greater than the right operand.

bool DenizenIdentifier::operator==(const DenizenIdentifier& other) const
{
    return *this <=> other == std::strong_ordering::equal;
}

std::strong_ordering DenizenIdentifier::operator<=>(const DenizenIdentifier& other) const
{
    if (m_category == other.m_category)
    {
        return m_instance <=> other.m_instance;
    }

    return static_cast<int>(m_category) <=> static_cast<int>(other.m_category);
}

Notice that we still implement the operator== function, even though the <=> operator already does the same thing. For details, see this StackOverflow answer.

Briefly, in C++, providing a three-way comparison (operator<=>) for objects doesn't automatically mean the compiler knows how to check if they're equal (operator==). They're treated as distinct operations. The main reason is efficiency: checking if two items are equal can sometimes be faster than determining their order, especially with long strings. For example, while ordering might require examining two entire strings, equality might stop as soon as a difference is spotted. If you provide a three-way comparison in your code, but then use the equality operator (==), you should also define or use the default equality check for it to work correctly.

3. Implementing Derived Denizen Classes

For example, the Hunter class is derived from the Denizen class:

#pragma once

#include "Denizen.h"

namespace HuntTheWumpus
{
    class Hunter final : public Denizen
    {
    public:
        Hunter();
        ~Hunter() override = default;

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

We only have to implement the constructor:

#include "Hunter.h"

namespace HuntTheWumpus
{
    Hunter::Hunter()
        : Denizen({ Category::Hunter, 0 }, { true, false, false, true, true })
    {
    }
}

The other derived classes are implemented in a similar fashion. For brevity, I won't include them here.

The derived classes are marked final to prevent further derivation.

4. Implementing `DenizenIdentifierHasher` Structure

It is forseable that we will need to store Denizens in some of maps, which requires a hash function. Therefore, we need to implement a DenizenIdentifierHasher structure that implements operator() that returns a unique hash for a DenizenIdentifier:

struct DenizenIdentifierHasher
{
    size_t operator()(const DenizenIdentifier &id) const;
};

The implementation is a bit complicated:

// See https://stackoverflow.com/questions/35985960/c-why-is-boosthash-combine-the-best-way-to-combine-hash-values/50978188
size_t xorshift(const size_t n, const int i)
{
    return n ^ (n >> i);
}

uint32_t distribute(const uint32_t n)
{
    constexpr uint32_t p = 0x55555555ul; // pattern of alternating 0 and 1
    constexpr uint32_t c = 3423571495ul; // random uneven integer constant; 
    return static_cast<uint32_t>(c * xorshift(p * xorshift(n, 16), 16));
}

size_t hash_combine(const std::size_t seed, const size_t v)
{
    return std::rotl(seed, std::numeric_limits<size_t>::digits / 3) ^ distribute(static_cast<uint32_t>(v));
}

size_t DenizenIdentifierHasher::operator()(const DenizenIdentifier& id) const
{
    auto result = 0ull;

    result = hash_combine(result, std::hash<int>()(static_cast<int>(id.m_category)));

    return hash_combine(result, std::hash<int>()(id.m_instance));
}

Hasing is about summarizing a complex data into a fixed-size value in a predictable way. The hashing algorithm is based on the following StackOverflow answer: C++: Why is boost::hash_combine the best way to combine hash values?

Given: - $p = \text{0x55555555}$ (A pattern of alternating 0 and 1) - $c = \text{3423571495}$ (A random uneven integer constant)

xorshift function: $\text{xorshift}(n, i) = n \oplus (n \gg i)$
Role: The xorshift function is a basic bitwise operation that combines a number with its right-shifted self. This operation helps in "scrambling" the bits of the number, introducing a level of unpredictability and randomness which is often desired in hashing. The function is a rudimentary way to diffuse the input bits across the output.
distribute function: $\text{distribute}(n) = c \times \text{xorshift}(p \times \text{xorshift}(n, 16), 16)$
Role: The distribute function further obfuscates and spreads out the bits of the input. It makes use of the previously mentioned xorshift function and then multiplies the result with two constants $p$ and $c$ . The alternating pattern in $p$ ensures that the multiplication spreads the bits effectively, and $c$ introduces more randomness to the process. The idea is to ensure that similar input values get widely different hash values.
hash_combine function: $\text{hash\_combine}(seed, v) = \text{ROTL}(seed, \frac{\text{max size of size\_t}}{3}) \oplus \text{distribute}(v)$
Role: The hash_combine function is designed to mix two hashes together in a way that's difficult to reverse engineer. It rotates the bits of one hash and then XORs the result with the distributed version of another hash. The rotation ensures that different bits from the seed hash have an impact on the final result, preventing patterns that could arise from simpler combining methods.
DenizenIdentifierHasher::operator() function: $\text{hash}(id) = \text{hash\_combine}(\text{hash\_combine}(0, \text{hash}(id.\text{category})), \text{hash}(id.\text{instance}))$
Role: This function is the main entry point for hashing a DenizenIdentifier object. It first hashes the category of the identifier, then uses that hash value as a seed to combine with the hash of the instance. This ensures both parts of the DenizenIdentifier (category and instance) play a significant role in the final hash value.

Now we can use the DenizenIdentifierHasher structure to create a std::unordered_map:

#include <unordered_map>

std::unordered_map<DenizenIdentifier, std::unique_ptr<Denizen>, DenizenIdentifierHasher> m_denizens;

Homework 1 Notes

1. Instructions

2. Implementing Denizen

3. Implementing Derived Denizen Classes

4. Implementing DenizenIdentifierHasher Structure

2. Implementing `Denizen`

4. Implementing `DenizenIdentifierHasher` Structure