Implement SkillTree data structure with SkillNode, prerequisites, tiers, and tree traversal #227

New issue

Open

opened 2026-03-16 01:40:12 +00:00 by freemo · 0 comments

freemo commented

2026-03-16 01:40:12 +00:00

Owner

Metadata

Key	Value
Parent Epic	#223 — Skill Tree Data Model & Storage
Legendary	#198 — Character Progression & Skills
Branch	`feature/m4-skill-tree-data-structure`
Commit Message	`feat(skills): implement SkillTree data structure with SkillNode, prerequisites, tiers, and tree traversal`
Points	8
Priority	High
MoSCoW	Must Have

Background and Context

The skill system in Aethyr requires a flexible, graph-based data structure to represent skill trees. Each discipline (Combat, Survival, Crafting, Social, Magic) has its own tree of skill nodes arranged in tiers with prerequisite chains. The SkillTree class serves as the central data model that all other skill-related features depend on.

The SkillTree holds a directed acyclic graph (DAG) of SkillNode objects. Each SkillNode represents a single learnable skill with progression levels. Nodes are connected by prerequisite relationships — a player must reach a certain level in prerequisite nodes before unlocking dependent ones.

This is the foundational building block for the entire Character Progression & Skills legendary. Every subsequent issue in this legendary depends on this data structure being correct and performant.

Expected Behavior

SkillNode class with attributes:
- name (String) — unique identifier for the node (e.g., "combat", "swordplay").
- discipline (Symbol) — the root discipline this node belongs to (:combat, :survival, etc.).
- tier (Integer) — the depth level in the tree (0 = root, 1 = first branch, etc.).
- prerequisites (Array of Hash) — list of {name: "node_name", level: N} entries required to unlock this node.
- xp_required (Integer) — XP needed per level, default 10000.
- current_xp (Integer) — current XP accumulated toward next level (player-specific, not stored here).
- max_level (Integer) — maximum achievable level for this node, default 10.
- description (String) — human-readable description of the skill.
SkillTree class with methods:
- initialize(nodes: []) — build the tree from a list of SkillNode definitions.
- lookup(name) — find a node by name, returns SkillNode or nil. O(1) via hash lookup.
- list_by_discipline(discipline) — return all nodes for a given discipline, sorted by tier.
- check_unlockable(player) — return all nodes the player meets prerequisites for but hasn't unlocked.
- children_of(node_name) — return all nodes that have node_name as a prerequisite.
- root_nodes — return all tier-0 nodes.
- validate! — verify no circular dependencies, all prerequisites reference existing nodes.
Graph Integrity:
- The tree is a DAG — validate! raises SkillTree::CyclicDependencyError if cycles are detected.
- All prerequisite references must resolve to existing nodes — validate! raises SkillTree::MissingPrerequisiteError otherwise.

Acceptance Criteria

SkillNode class exists at lib/aethyr/core/skills/skill_node.rb with all specified attributes.
SkillTree class exists at lib/aethyr/core/skills/skill_tree.rb with all specified methods.
lookup is O(1) using an internal @nodes_by_name hash.
list_by_discipline returns nodes sorted by tier ascending.
check_unlockable correctly evaluates prerequisite levels against player skill data.
validate! detects cyclic dependencies and missing prerequisites.
children_of returns correct dependents for any node.
All classes are in the Aethyr::Core::Skills module namespace.

Subtasks

Create lib/aethyr/core/skills/skill_node.rb with the SkillNode class and all attributes.
Create lib/aethyr/core/skills/skill_tree.rb with the SkillTree class.
Implement initialize to build @nodes_by_name hash and @nodes_by_discipline grouped hash.
Implement lookup(name) with O(1) hash access.
Implement list_by_discipline(discipline) with tier sorting.
Implement check_unlockable(player) that inspects player.info["skills"] for prerequisite levels.
Implement children_of(node_name) by scanning prerequisites.
Implement root_nodes returning tier-0 nodes.
Implement validate! with cycle detection (topological sort) and missing-prerequisite checks.
Define custom error classes: CyclicDependencyError, MissingPrerequisiteError.
Docs: Update YARD comments on affected classes and methods. Update relevant Docusaurus documentation pages if applicable.
Tests (Cucumber): Add tests/unit/skill_tree.feature covering node lookup, discipline listing, unlockable checking, cycle detection, missing prerequisite detection, children traversal.
Tests (Cucumber Integration): Add integration feature in tests/integration/ for skill tree loading and validation.
Tests (Profiling): Run bundle exec rake unit_profile and verify no performance regressions.
Quality: Verify coverage >=97% via bundle exec rake unit. If coverage is <97% then review the current unit test coverage report at build/tests/unit/coverage/ and use it to write new Cucumber based unit tests to improve code coverage. Specifically, write Cucumber/Gherkin style unit tests that are descriptively named and specifically improve coverage on whichever file has the most uncovered lines by writing tests that will target the uncovered lines in the report. Once that is done rerun bundle exec rake unit to verify all tests pass and coverage is above >=97%. Only mark this as complete once coverage is >=97%, if not repeat this task as many times as is needed until coverage reaches >=97%.
Quality: Run bundle exec rake (default task: unit tests with coverage) and bundle exec rake integration, fix any errors if needed ensuring both pass across entire code base, do not ignore any failure even if it seems unrelated to this commit, fix it.

Definition of Done

This issue is complete when:

All subtasks above are completed and checked off.
A Git commit is created where the first line of the commit message matches the Commit Message in Metadata exactly, followed by a blank line, then additional lines providing relevant details about the implementation.
The commit is pushed to the remote on the branch matching the Branch in Metadata exactly.
The commit is submitted as a pull request to master, reviewed, and merged before this issue is marked done.

## Metadata | Key | Value | |-----|-------| | **Parent Epic** | #223 — Skill Tree Data Model & Storage | | **Legendary** | #198 — Character Progression & Skills | | **Branch** | `feature/m4-skill-tree-data-structure` | | **Commit Message** | `feat(skills): implement SkillTree data structure with SkillNode, prerequisites, tiers, and tree traversal` | | **Points** | 8 | | **Priority** | High | | **MoSCoW** | Must Have | ## Background and Context The skill system in Aethyr requires a flexible, graph-based data structure to represent skill trees. Each discipline (Combat, Survival, Crafting, Social, Magic) has its own tree of skill nodes arranged in tiers with prerequisite chains. The `SkillTree` class serves as the central data model that all other skill-related features depend on. The `SkillTree` holds a directed acyclic graph (DAG) of `SkillNode` objects. Each `SkillNode` represents a single learnable skill with progression levels. Nodes are connected by prerequisite relationships — a player must reach a certain level in prerequisite nodes before unlocking dependent ones. This is the foundational building block for the entire Character Progression & Skills legendary. Every subsequent issue in this legendary depends on this data structure being correct and performant. ## Expected Behavior 1. **SkillNode** class with attributes: - `name` (String) — unique identifier for the node (e.g., `"combat"`, `"swordplay"`). - `discipline` (Symbol) — the root discipline this node belongs to (`:combat`, `:survival`, etc.). - `tier` (Integer) — the depth level in the tree (0 = root, 1 = first branch, etc.). - `prerequisites` (Array of Hash) — list of `{name: "node_name", level: N}` entries required to unlock this node. - `xp_required` (Integer) — XP needed per level, default 10000. - `current_xp` (Integer) — current XP accumulated toward next level (player-specific, not stored here). - `max_level` (Integer) — maximum achievable level for this node, default 10. - `description` (String) — human-readable description of the skill. 2. **SkillTree** class with methods: - `initialize(nodes: [])` — build the tree from a list of SkillNode definitions. - `lookup(name)` — find a node by name, returns `SkillNode` or `nil`. O(1) via hash lookup. - `list_by_discipline(discipline)` — return all nodes for a given discipline, sorted by tier. - `check_unlockable(player)` — return all nodes the player meets prerequisites for but hasn't unlocked. - `children_of(node_name)` — return all nodes that have `node_name` as a prerequisite. - `root_nodes` — return all tier-0 nodes. - `validate!` — verify no circular dependencies, all prerequisites reference existing nodes. 3. **Graph Integrity:** - The tree is a DAG — `validate!` raises `SkillTree::CyclicDependencyError` if cycles are detected. - All prerequisite references must resolve to existing nodes — `validate!` raises `SkillTree::MissingPrerequisiteError` otherwise. ## Acceptance Criteria - [ ] `SkillNode` class exists at `lib/aethyr/core/skills/skill_node.rb` with all specified attributes. - [ ] `SkillTree` class exists at `lib/aethyr/core/skills/skill_tree.rb` with all specified methods. - [ ] `lookup` is O(1) using an internal `@nodes_by_name` hash. - [ ] `list_by_discipline` returns nodes sorted by tier ascending. - [ ] `check_unlockable` correctly evaluates prerequisite levels against player skill data. - [ ] `validate!` detects cyclic dependencies and missing prerequisites. - [ ] `children_of` returns correct dependents for any node. - [ ] All classes are in the `Aethyr::Core::Skills` module namespace. ## Subtasks - [ ] Create `lib/aethyr/core/skills/skill_node.rb` with the `SkillNode` class and all attributes. - [ ] Create `lib/aethyr/core/skills/skill_tree.rb` with the `SkillTree` class. - [ ] Implement `initialize` to build `@nodes_by_name` hash and `@nodes_by_discipline` grouped hash. - [ ] Implement `lookup(name)` with O(1) hash access. - [ ] Implement `list_by_discipline(discipline)` with tier sorting. - [ ] Implement `check_unlockable(player)` that inspects `player.info["skills"]` for prerequisite levels. - [ ] Implement `children_of(node_name)` by scanning prerequisites. - [ ] Implement `root_nodes` returning tier-0 nodes. - [ ] Implement `validate!` with cycle detection (topological sort) and missing-prerequisite checks. - [ ] Define custom error classes: `CyclicDependencyError`, `MissingPrerequisiteError`. - [ ] Docs: Update YARD comments on affected classes and methods. Update relevant Docusaurus documentation pages if applicable. - [ ] Tests (Cucumber): Add `tests/unit/skill_tree.feature` covering node lookup, discipline listing, unlockable checking, cycle detection, missing prerequisite detection, children traversal. - [ ] Tests (Cucumber Integration): Add integration feature in `tests/integration/` for skill tree loading and validation. - [ ] Tests (Profiling): Run `bundle exec rake unit_profile` and verify no performance regressions. - [ ] Quality: Verify coverage >=97% via `bundle exec rake unit`. If coverage is <97% then review the current unit test coverage report at `build/tests/unit/coverage/` and use it to write new Cucumber based unit tests to improve code coverage. Specifically, write Cucumber/Gherkin style unit tests that are descriptively named and specifically improve coverage on whichever file has the most uncovered lines by writing tests that will target the uncovered lines in the report. Once that is done rerun `bundle exec rake unit` to verify all tests pass and coverage is above >=97%. Only mark this as complete once coverage is >=97%, if not repeat this task as many times as is needed until coverage reaches >=97%. - [ ] Quality: Run `bundle exec rake` (default task: unit tests with coverage) and `bundle exec rake integration`, fix any errors if needed ensuring both pass across **entire** code base, do not ignore any failure even if it seems unrelated to this commit, fix it. ## Definition of Done This issue is complete when: - All subtasks above are completed and checked off. - A Git commit is created where the **first line** of the commit message matches the Commit Message in Metadata exactly, followed by a blank line, then additional lines providing relevant details about the implementation. - The commit is pushed to the remote on the branch matching the **Branch** in Metadata exactly. - The commit is submitted as a **pull request** to `master`, reviewed, and **merged** before this issue is marked done.