Using Heaps in a Computer Game Implementation – Fibonacci Heap Inventory System

Game world: "Пут кроз краљевство Аспире" ("Journey Through the Kingdom of Aspire") — this code implements the player inventory system described in the 13С112АСП2 – ДЗ3 brief. Last project of Algorithms and Data Structures 2

Project Overview

• Solves the coursework problem "Употреба хипова у имплементацији компјутерске игре" (Using Heaps in a Computer Game), modelling how the warrior manages gems while travelling through Aspire.
• Keeps diamonds in a blue Fibonacci max-heap and moissanites in a red Fibonacci min-heap so the player always reaches the most valuable diamond and the least valuable moissanite in amortized O(log n).
• Provides both an interactive console menu and batch execution of scripted command files, matching the assignment requirement to support simulations.
• Implements the variant where i = 1 and j = 0: Fibonacci heaps are mandatory, and the rare trader command R[k] removes the k most valuable diamonds.

Code Layout

• asp2dz3.cpp: Fibonacci-node structures, heap operations, command parser, and gameplay engine.
• Commands10.txt, Commands20.txt, Commands30.txt, custom.txt: ready-made command sequences used to demonstrate and test the inventory logic.
• 13S112ASP2_DZ3_2425.pdf: original Serbian assignment specification with storyline, requirements, and command descriptions.

Gameplay Flow

• Program prints the menu mandated by the brief, then loops until the user types exit.
• Command helper strips whitespace, accepts tokens like D[75], and extracts numeric parameters for further processing.
• BlueBag (max Fibonacci heap) stores diamond values; RedBag (min Fibonacci heap) stores moissanite values. Each bag maintains a circular root list, supports consolidation, and can enumerate all keys for reporting.
• Engine coordinates all inventory actions: creating/donating bags, adding gems, handling traders and bakers, printing border inspection reports, migrating items when a thief appears, and recursively executing scripts via F[file].
• The thief scenario (L) fulfils the brief’s instruction to move everything into whichever bag initially holds more items (blue on ties) so the other bag can be shown empty.

Command Reference

• V: buy both bags (initialise empty Fibonacci heaps for diamonds and moissanites).
• B: gift both bags (destroy current heaps and discard their contents).
• D[x]: insert a diamond of value x into the blue max-heap.
• M[x]: insert a moissanite of value x into the red min-heap.
• T: trade with a weapons merchant by extracting the maximum diamond.
• P: trade with a baker by extracting the minimum moissanite.
• G: border patrol check; prints counts, extrema, raw contents, and a sorted view of both bags.
• L: thief encounter; migrates all gems into the larger bag (blue on ties) and empties the other.
• R[k]: rare weapons trader; removes up to k most valuable diamonds and reports total loot sold.
• F[path]: load and execute additional commands from a text file (enables simulations and grading scripts).
• exit: leave the interactive loop.

Build And Run

• Compile with a C++17-capable toolchain, e.g. g++ -std=c++17 asp2dz3.cpp -o heap_game.
• Run the program (heap_game) and enter commands manually or call F[filename] to replay a scripted scenario.
• Sample scripts: Commands10.txt (intro), Commands20.txt (expanded trades), Commands30.txt (thief-heavy), custom.txt (comprehensive mix).