Team07

Link to proposal

Team Name: High Seas

Game Name: Archipelago

Archipelago is a Survival/Exploration game which takes place in an archipelago of islands, each with a different biome. The player sets out to find out what’s contained within a chest on the island they shipwrecked on. The keys are scattered across the islands: the snow island, the jungle island, and the desert island.

Opon being shipwreaked, the player must learn to survive in this new world. They must gather resources and learn to adapt to any challanges they may face

Puzzles are key to progressing the game, its unkown who placed them there as a test

The old man may seem a bit crazy, but he has this strange chest next to him, find out what he wants and he may reveal whats inside

Here we have the start area where the player first finds themselves in

Uncovering the old man and the secrets of the chest are the main focus of our story

Completing puzzles and activities on both islands is how the player can obtain the items needed to progress the story

Repairing the bridge needed to access the next island, it's been some time since it's been used and is in disrepair.

Once getting to the dessert island, the oasis holds another secret puzzle

This repo enforces local formatting and static analysis with Git hooks:

• pre-commit: runs git clang-format --staged --style=file.
• pre-push: runs clang-tidy on changed translation units (.c/.cc/.cpp/.cxx/.m/.mm).

You need:

• clang-format
• clang-tidy
• git-clang-format (required by pre-commit hook)

macOS (Homebrew):

brew install llvm

Ubuntu/Debian:

sudo apt update
sudo apt install clang-format clang-tidy clang-tools

Windows (LLVM installer):

1. Install LLVM from the official installer.
2. Make sure LLVM bin is on PATH (example: C:\Program Files\LLVM\bin).

Verify:

clang-format --version
clang-tidy --version
git clang-format --help

clang-tidy needs compile_commands.json.

From repo root:

cmake CMakeLists.txt

From repo root:

git config core.hooksPath .githooks

This enables:

• .githooks/pre-commit
• .githooks/pre-push

• Linux: hooks run directly with /bin/sh.
• Windows: hooks run through Git for Windows shell. Use Git Bash (or a Git-enabled terminal) for commits/pushes.

Run format on staged changes:

git clang-format --staged --style=file

Run tidy on a file:

clang-tidy -p <build_dir> src/main.cpp

Fix tidy on all files in src (warning takes long):

# Linux
git ls-files src | grep -E '\.(c|cc|cpp|cxx|m|mm)$' | xargs -n 1 clang-tidy -p build -fix
# Windows
git ls-files src | Where-Object { $_ -match '\.(c|cc|cpp|cxx|m|mm)$' } | ForEach-Object { clang-tidy $_ -p build -fix }

Run format on all files in src:

# Linux
git ls-files src | grep -E '\.(c|cc|cpp|cxx|m|mm|h|hh|hpp|hxx)$' | xargs clang-format -i --style=file
# Windows
git ls-files src | Where-Object { $_ -match '\.(c|cc|cpp|cxx|m|mm)$' } | ForEach-Object { clang-format -i --style=file }

Notes:

• pre-push requires compile_commands.json in the root folder
• Header-only changes do not directly invoke clang-tidy because it runs on translation units.

Our two biggest important engagement criteria is Exploration and Resource Gathering/Crafting.

We added more guidance to the player in the form of more notes, visual environment props and object placement so they get lost less often and have more concrete goals. The tutorial has also been tweaked to help guide the player better. This is due to the feedback we've gotten that people feel lost and thus discouraged from interacting with the game itself near the beginning.

We added another puzzle and maze as new activities to the game, as well as polish existing ones. This helps add more to the Exploration aspect of our game.

Vitials system is more in depth, while also increasing the number of items that the player can use to survive. This encourages the player to go out into the world to find items in order to sustain their stats, and adds a depth of challenge for foraging items. We also added ways to craft these items, like the bottled water, to also encourage interacting with the crafting side of our game for better items.

We added many more sounds, animations, and music to make the game feel more mysterious and set the mood of our world. This helps with the immersion of our game.

There are no memory leaks. With safe software coding pratices and running though our code with memory leak checkers, we have comfirmed we have none. See related section in M3

Our code is optimized. We have high FPS and it is optimized for a release build. There are no visible stutters in game. See related section in M3

Creatures find pathfinding with A* with consideration of dynamic colliders and word boundaries. If they ever get stuck they simply try to find another path.

See Mesh Assets and Texture/Image Assets sections below

Sound assets & music downloaded from: Youtube, https://gamesounds.xyz/, freesound.org, https://pixabay.com/

All meshes used were either produced by hand by our team members in Blender or generated via a python script that reads the pixels of images inputed to create points that is then triangulated

A majority of our tilesets come from a particular asset pack Here. These are the the tiles predominantly used for every other part of the map. The tileset used for the majority of the Desert Island is Here

As for our sprites, most are sourced from various Itch.io creators: zedpxl (Forest sprites i.e. trees, bushes, other flora), axulart (player character), buddy-games (hearts HUD icon), sainguinpixels (Hotbar icons), gracitation (notes paper), duckhive (slime, cow, goose), grayger26 (chicken), micaellebritto (skeleton), inspired-goblin (mimic, chest), glionox & polar-34 (various icons for different items), chrisppop (bottle and water bottle)

We also have other assets created by Team Members: peyton (twig#1, water and food UI elements), alex (main screen BG, attack slash animation, twig#2), blake (puzzle sprites for moon puzzle and maze, tree roots, axe, hammer, shell sword, coconut, sand dune), gurma (death animations for player and creatures), perry (damaged bridge)

Assets that come from other sources were chosen or kept based on how similar their art style was to this pack. AI art also followed this same philosophy.

Cutscenes, Map and some other Icons are generated with Claude, ChatGPT, Gemini, PixieHaus

Inclusion of maze in this milestone

The bounds of the maze are defined wthin Tiled, ergo an explicit size that would easily work well with classical maze generation algorithmns do not work here (as in theory, the bounds could easily be non-rectangular).

So the maze is generated using a modified variant of Primm's Algorithmn from an initial set of tiles that are all set to 'closed', where each time a tile (context variant of the abstract node here) is visited, its neighbors are in fact the tiles that have a one tile gap between them and the current tile. This is to ensure a maze that does not take too many small turns (which would create overly thin walls). Each step also makes sure that the tiles 'can be destroyed'; i.e., the wall is not on a boundary, and that creating tha path would not destroy too much of the existing walls between open cells. For selected neighbors that do satisfy these requirements, these are registered into a list of upcoming tiles to look at, which is shuffled at the start of each iteration step before picking the first tile. After going through the tiles, a final check is made to ensure that the tile can safely be opened up without breaking too many walls, before it is set to open.

Of course, this is not perfect, so Cell Automaton style cleanup work is done afterwards to refine the maze; A first pass checks all the nodes that have exactly one open tile adjacent to them; these tend to be dead ends, and closing them off helps keep the walls thicker. However, this is also a bit overly aggressive, so the next pass then goes over (remaining) tiles that fit this description and instead 'expands' outwards as done in the first algorithmn, but notably not in a recursive manner, which maximized the degree that paths tunnel into the walls of the maze without starting to make the walls too thin. The biggest goal here is to avoid paths.

Of course, need to ensure that the maze has a valid entrance (and terminal point). So the starting tile is selected along a boundary as is used as the first current node; note that it is also the only tile allowed to be open along the edges of the maze. An end tile is picked after the rest of the maze is generated, along a predetermined boundary edge, but this time making sure that the selected end tile is within 2 tiles of an open tile of the maze; this is to ensure that the 'goal' of the maze is generated on a tile that is right along the boundary, but not outside it (effectively, an exit that would lead to a valid path is picked, it's just not opened given the way the maze works in this game).

Above we see one of the new puzzle additions. The mimic puzzle rewards the player with a useful early game reward while also provinding some challange to obtain it

The maze is a challange as you are sent through a labyrinth with obscured vision. Not to mention its infested with skeletons! Reach the end to obtain an amazing reward and to progress the story.

As the player collects more items, they discover more recipes. The items help them to progress further in the game. For example:

• Discovering wooden axe allows players to obtain logs, which helps repair the bridg to reach the desert island
• Discovering shell sword allows players to increase their damage to mobs, preventing them from dying
• Discovering flashlight allows players to traverse in the dark with more visibility

As the player explores around the world, they will encounter special world objects to reveal more of the story, including:

• Players can interact with the old man, which hints the progression direction ("I used to leave notes around hoping someone would find them", "I always loved hearing that music by the column")
• Upon finishing the puzzles, notes are spawned, which reveals the next progression direction
• Upon finish repairing the bridge, the player grants access to the exploration of desert island

From the beginning of the project we understood how important proper memory management is. As such, we took measure from M1 to ensure memory safe code was the only code entering our repo. We enforce strict memory correctness rules through clang-tidy which runs as a linter before all pushes into our repo. Through this we ensure that minimal lifetime is managed by our team. We have no uses of new or delete in our project and minimal use of pointers. Where we do use pointers we make them unique where possible.

As a second defense we have enabled -fsanitize on all debug builds of archipelago.

As a final layer of defense we also use _CrtDumpMemoryLeaks in all debug builds.

Similarly to Memory Management our group understands the importance of writing performant code from the get-go. Although we do follow the mentality of don't optimize early we make an effort to consider the runtime of the code entering out game. This in combination with profiling throughout M1 and M2 has lead us to have relatively good performance coming into M3. To take things to the next level, we made use of the Superluminal profiler as well as MSVC's profiler to identify bottlenecks in the game. We faced two major performance bottlenecks in this milestone.

1. Physics: We were running physics simulations on all motions and collision checks between all colliders. To fix this we use early exits based on proximity to the player and between entities.
2. Rendering: As seen in the screenshot below, rendering was out biggest performance bottleneck. The biggest win in this milestone was the addition of instance rendering for all sprites in the game and strict culling of entities out of FOV.

Next Steps: We can improve render performance even more by reducing calls to the OpenGL driver by caching Vertix Attributes and Uniforms. Something we plan on doing in M4.

[5] Particle systems: Advanced

• Add leaves falling particle for trees
• Adds slash effect for player attacking
• Team member involved: Perry Huang

https://github.students.cs.ubc.ca/user-attachments/assets/1690f0be-e374-48bf-b227-eead204c05ed

Various Particle VFX in the game

[19] Reloadability: Basic

• Saves the complete game state (completed tutorials, player status, world object locations) by saving components in the ECS
• Loads all these game state back to the game when requested
• Team member involved: Peyton Belchetz

https://github.students.cs.ubc.ca/user-attachments/assets/8959e4a6-479e-4837-8d75-33581699c68d

Demonstration of the reload feature of the game (as well a pause menu & main menu)

[27] Story elements: Basic

• Cutscenes are played when a new game is started
• Notes are spawned after a puzzle is completed, telling the players the next steps to be done
• When player finishes all the puzzles, the player is requested to return to the old man, obtain the reward from chest, and become the old man (the player is the old man all along because he has dementia).
• Team member involved: Jeanette Hu, Yik Fung Cheung

https://github.students.cs.ubc.ca/user-attachments/assets/0dcf551e-60cc-4e41-9455-a7d1a8c3c22c

Old Man (NPC Character that can be spoken to)

https://github.students.cs.ubc.ca/user-attachments/assets/9f5fc116-f2c1-44b7-8ba0-50611f884696

Notes that guide the player (obtained at certain milestone, currently from this puzzle)

https://github.students.cs.ubc.ca/user-attachments/assets/d40c2799-f253-4f91-9f87-7ef4347ce014

Cutscene at the start of the game

For M2, our core engagement criteria list is:

• Crafting:

  • Add more item sprites as icons to replace pure text implementation of the crafting UI from milestone 1 inside inventory and crafting windows to make these menus less cluttered visually (satisfied)

• Exploration:

  • Redesigned the map to include proper landmarks as a way to improve the exploration aspect of the game (satisfied)
  • Add cute sprites, animations, and sound for various type of creatures, moving around the map. (satisfied)
  • Add various type of sound effects for creatures to enhance gaming engagement experience. (satisfied)

• Combat:

  • Add simple player attack effect and simpple enemy getting hurt effect to make the game visual more engaging. (satisfied)

• Puzzles:

  • Add a fun, simple music puzzle for player to solve. (satisfied)

• Others:

  • Add an HUD for the player to see their health, the item they are holding, and the world time in real time. (satisfied)
  • Add in-game notifications to show players important changes and updates happening in-game. (satisfied)
  • Give the player an small interactive tutorial teaching them the basic control system. (satisfied)

All creatures except the mimic when far away from the player will switch in between idle and wandering states, where idle means they stay in place and wandering refers to them choosing a target destination and then walking to it.

For chickens and cows, when they are at full health, they will do the aforementioned two things. However, if it gets damaged by the player, it will flee away from player.

For rabbits, it also chooses between idle and wandering, but will also flee from the player when they get too close to them. They return to their normal behaviour when farther away from the player.

Geese will wander and idle. However, when the player attacks, they will agro and attack the player back.

Skeletons, and Slime all wander and idle. The slime and skeleton will attack the player should they get too close to them.

All skeletons, slimes and geese will flee when their health is <= 1.

Animations are implemented using spritesheets. The animations are loaded as a single spritesheet texture and make use of the offset to render the frames of the animation. Animations are implemented in player walking, creatures walking, and attack (slash) animation.

The game also integrated some audio assets, played respectively when the player is walking sound, opening the map, picking up items, attacking creatures, swiping tools, and completing puzzles. There are also audios played positionally for as creature sounds.

Mehses are stored as .obj files within assets/meshes/ folder. When game starts, physics system loads all meshes from this folder using physics.json configuration file to determine which files to look for. Each .obj file is read and converted into a trianglemesh (essentially a vector of size-3 arrays of points). Only uses v- information and f- information from .obj file. Each entry is stored in a string-trianglemeh map to fetch.

When an entity that wants meshcollision is to be created, it will fetch a copy of a trianglemesh from this map, and append it to its Collider which stores both the AABB and trianglemesh(es) associated with an entity. This associated trianglemesh(es) will be updated as the object moves.

During collision checking, if two AABBs are colliding, the collision system will check if they have trianglemeshes as well. If one or more have a mesh, then the collision system will move onto mesh-involved collision checking.

For the purposes of this system, there is little difference between a trianglemesh and an AABB. So even if there's only one mesh, the system will essentially convert the other entity's AABB into a mesh. Each 'Mesh' is simply a collection of vectors that share edges; A triangle has the advantage of each point always sharing an edge with another point while the converted AABB mesh is ordered in a way to ensure that each point shares an edge with the point before and after it (as well as first sharing with last). So the system begins to perform Separating Axis Theorem (SAT) between every triangle combination of the first and second mesh, or all triangles on the mesh against the AABB mesh quad.

Given two collections of points, the system now simply loops over each point in each collection, forming a pair between the current and the next point (or last & first), and then getting the normal vector between these two points; Every point of both collections is then projected onto the normal line, and the collision system finds the 'bounding points' (relative to the line) of each collection, checking if there is overlap. If there is an overlap, this means that on this axis the two shapes are in fact overlapping.

As according to SAT, two shapes only collide when it is impossible to draw any line between them (i.e. every single normal line that is projected to has an overlap between the two shapes). So finding any case where there is no overlap will immediately return false for whether or not they collide, but otherwise returns true once all combinations have been iterated through. Of course, this is only for when there is a mesh, as if neither shapes have an mesh, then the result of collision just depends on their original AABB check.

When the player hits "F" key, the Frames-per-second (FPS) counter will be shown in the top left corner of the game, along with frame time and 1% low FPS. If the player hits "F" key again, the texts will disappear.

At the beginning of the game, there are key sprites spwaning around the player, guiding the player to try to hit the corresponding keys on their keyboard. After the player hits the correct key shown on the screen, the key sprites slowly disapper, and the game shows them what is going to happen after those keys are pressed.

[1] Simple rendering effects: Basic

• Outline effect on interactable items by using Gaussian-like kernel to grow the outlines from the original sprite.
• Team member involved: Yik Fung Cheung

[23] Audio Feedback: Basic

• Add audio feedback for background music, player walking sound, item pick up sound, completing puzzle sound, tools swiping sound, map opening sound, and huring creature sound. Background music and sounds are played using the SDL library.
• Team member involved: Peyton Belchetz

Compared to M1, M2's map is redesigned. It is using new tile assets, and filled with various kinds of creatures, that are all behaving differently.

Compared to M1, M2 now displays a Game HUD(Heads-Up Display), showing the player Health, System time/tide state, and active item slots.

In M2, the crafting menu is more graphic than the M1 crafting menu. The item name and its recipe was displayed as texts in M1, but they are now displayed as item icons.

In M2, the inventory menu is more graphic than the M1 inventory menu. The item name and amount was displayed as texts in M1, but they are now displayed as item icons.

In M2, the player can left click when equipping a weapon tool to attack various types of creatures. There are simple attacking effects showing when the player hurts the creature

In M2, when the game starts, there are simple tutorial sprites around the player as they proceed in game, showing them what to do next such as WASD key icons as a movement controls tutorial. The tutorial sprites disappear once the player pressed the corresponding keys.

• Players can explore on the island, move around by WASD, and collect resources by pressing E.

• The resources players collected can be crafted into tools inside the crafting menu window (open by pressing C), which help them explore the island further.

• There is a time system which performs a day-night cycle, showing player whether they are in the middle of the day or at night.

• Mobs will chase the player. If player has crafted a sword, they can attack enemies and kill them.
• Note: we haven't implemented collisions of mobs so they can go through trees and player.

• Rendered twigs, rocks and trees with sprites.
• Rendered a movable player sprite.

• The player position, rotation and scale is passed to the render system and the system will craft a model matrix based on these information.
• A tween animation utilizes 2D transformation, changing the position, rotate, and scale, with an interpolation formula.
• Twigs are spawned in random rotation (and position).

• Upon collected a resource, a tween animation of the resource will move upward, scales up, and reduce opacity, which indicates that the player has picked up that resource.
• Upon chopping down a tree, the tree falls down, and reduces opacity afterwards, indicating that the player has chopped that tree.

Define a struct called Keyframe (under tween/keyframe.cpp):

struct Keyframe {
    float time;
    // Change in position (not actual location)
    vec3 position;
    // Change in scale (vec2(1.f) is the base)
    vec2 scale;
    // Change in rotation
    vec3 rotation;
    // EXACT color transition (not offset)
    vec4 color;
    // Blending function
    EasingFunction* func;
    // ... (constructor omitted)
};

There are several attributes:

• time: denotes the time required to spend to fully reach this keyframe, in milliseconds
• position: denotes the position to offset from the base position
• scale: denotes the scale to multiply from the base scale
• rotation: denotes the change of rotation from the base rotation
• color: denotes the EXACT color to reach in this keyframe
• func: the easing function to transit from previous keyframe to this keyframe

There is the custom type EasingFunction for the variable func, which is a std::function<float(float)> (a function that accepts one float parameter and returns a float).

These EasingFunctions accept a parameter p, which is the current percentage of completion in time (e.g: if the time required to reach this keyframe is 2 seconds and we have passed 1 second, then p equals to 0.5 (50% completed)), and return the percentage of the current keyframe that should be blended with the previous keyframe.

Since we are only doing linear interpolation, given p, the function should return p (because the function is lienar).

EasingFunction linear = [](float p) -> float { return p; };

With the Keyframe struct, we can stack these keyframes together and form a chain of transitions. We store them as a Tween struct (core/ecs/components.hpp):

// Tween component which all stores keyframes
// The first keyframe defines the initial state
struct Tween {
    bool destroy_on_complete;
    float timer;
    int index;
    Keyframe curr_state;
    std::vector<Keyframe> keyframes;
    // ... (constructor omitted)
};

There are several attributes:

• destroy_on_complete: destroys the entity when the tween animation is completed
• timer: the current time it has passed, in milliseconds
• index: the keyframe index the entity is reaching to
• curr_state: a Keyframe cache for the current blended keyframe
• keyframes: the list of keyframes to transit, in choronological order.

With the Tween component, we can attach these components to an entity, and have a system ( under systems/tween_system.cpp) to iterate through all the entities with that component and update the interpolation state.

void TweenSystem::step(float dt) {
    auto& entities = registry.tweens.entities;
    auto& components = registry.tweens.components;

    for (int i = 0; i < entities.size(); i++) {
        // Do some stuff to update the interpolation state...
    }
}

For each step, the system increments the timer of all Tween components.

auto& entity = entities[i];
auto& tween = components[i];

// Update internal timer
tween.timer += dt;

Then, we check whether we need to move to the next keyframe based on the value of the timer. We decrement the timer when we move to the next keyframe.

// Move on to the next keyframe if needed
while (tween.index < tween.keyframes.size() &&
        tween.timer > tween.keyframes[tween.index].time) {
    tween.timer -= tween.keyframes[tween.index].time;
    tween.index++;
}

If we reach the end of the list of keyframes, we store them in the clear list and clear them after we have iterated all the Tween components.

if (tween.index == tween.keyframes.size()) {
    // Destroy tween component since it's done
    clear_list.emplace_back(entity, tween.destroy_on_complete);
    continue;
}

If not, we have to update the curr_state of the Tween component by calling update_state function (which is doing the blending part).

void TweenSystem::update_state(Tween& tween) {
    // Obtain the keyframes
    auto& state = tween.curr_state;
    auto& prev_frame = tween.keyframes[tween.index - 1];
    auto& next_frame = tween.keyframes[tween.index];

    // Calculate the blending function
    auto time = tween.timer;
    auto p = (*state.func)(time / next_frame.time);

    // Update the attributes
    state.scale = (1.f - p) * prev_frame.scale + p * next_frame.scale;
    state.position = (1.f - p) * prev_frame.position + p * next_frame.position;
    state.rotation = (1.f - p) * prev_frame.rotation + p * next_frame.rotation;
    state.color = (1.f - p) * prev_frame.color + p * next_frame.color;
}

Even with the updated Tween component, we still need to let the RenderSystem know that we have these changes from the component. Luckily, we can just simply check if the entity contains a Tween component, and update the model_matrix and pass the Keyframe (for the color part). We add this check under the render function in systems/render_system.cpp.

// ...
if (registry.tweens.has(entity)) {
    auto& tween = registry.tweens.get(entity);
    transform.position += tween.curr_state.position;
    transform.scale *= tween.curr_state.scale;
    transform.rotation += tween.curr_state.rotation;
    render_sprite(texture, transform, tween.curr_state);
} else {
    render_sprite(texture, transform);
}

[20] External Integration: Basic

• Integrated Dear ImGui (external library) with our OpenGL rendering system using GLFW and OpenGL3 backends, implemented toggleable inventory (Q key) and crafting (C key) UI windows that render on top of our game's multi-layer framebuffer system each frame.
• Team member involved: Jeanette Hu, Peyton Belchetz

[21] Camera Controls: Basic

• The camera follows the center position of the player by translating the camera matrix using the player position.
• Team member involved: Yik Fung Cheung

The player moves around with WASD keys, collecting resources with the E key including twigs, pebbles, scattered around the map.

The player can open the Crafting Menu window by pressing the key C, and click the "Craft" button under the to-be-crafted item if there is enough resources collected.

The player can open the Inventory Menu window by pressing the key Q, and check the number of items they have.

The player can be situated at dawn or midnight, for example.