Procedural Map Generation System

[IDokan]

Procedural Map Generation System in UE5.4 (Similar to Slay the Spire)

Description
Implement a procedurally generated map system in Unreal Engine 5.4 using C++. The map should resemble the structure of Slay the Spire and feature an entry node, final node, and multiple middle nodes, allowing players to choose paths. The system will generate layers of nodes with randomized connections, ensuring a path from the entry to the final node with a boss encounter.

---

Requirements

Map Layout

• Map Template: A 7x15 irregular isometric grid (grid formed by triangles) is generated as a template. This grid includes floors (horizontal rows of nodes) where rooms (nodes) can be positioned.
• Rooms (Nodes): Each node is a visitable location and includes types like entry, middle, and final (boss) nodes.
• Paths: Connections between nodes, ensuring paths do not cross.
• Floors: Each layer of rooms on the same horizontal level represents a floor.
• Boss Room: A final boss node positioned at the top after generating all other nodes and layers.

Generation Process

1. Starting Node: Randomly select two distinct rooms (nodes) on the first floor as starting locations, providing players with multiple path options.
2. Layer Connections: Nodes on each floor connect to the next floor. Each node has paths to up to three closest nodes on the floor above. This process is repeated across six floors, adding variety and choice for players.
3. Rule for Starting Nodes: Ensure the two nodes selected on the first floor are distinct, preventing duplicate starting points and ensuring variety.
4. Pathfinding Check: Validate that a path exists from the entry node to the final boss node. If no path exists, regenerate or add fallback connections.

Optimization and Debugging

• Node Types and Event Types: Apply specific types to nodes after generation to increase replayability.
• Visual Debugging: Implement debugging tools to display node and path layouts in the Unreal Engine editor.

---

Reference

Link to Slay the Spire Map Generation Example

---

Tasks

• [x] Define a MapNode class with properties like NodeType, layer, and connection data.
• [x] Create procedural node generation logic with connections that meet the map structure rules.
• [x] Implement a check to ensure at least one valid path exists from entry to the final node.
• [x] Add visual debugging tools to view the generated map structure in the editor.
• [ ] Automatically set scroll offset based on current map node index.
• [ ] Test path generation and optimize node type assignments to enhance variety.

[IDokan]

I was suspicious of performance calling FSlateDrawElement::MakeLines in UMapWidget::NativePaint(), because calling draw call a lot causes severe performance issues.

As far as I investigated it, I conclude it is safe to use in reasonable loops. I attached below research.

A loop through path_points_num caused 0.007ms. A loop through path_points_num * 1000 caused 2ms.

[IDokan]

In C++, need to override NativePaint instead of OnPaint function to draw a shape in Widget space. Because OnPaint is a function for Blueprint, OnPaint is not able to override in C++.

In order to modify drawing order using above approach, should handle multiple widgets. Layer modification is not helpful on the issue.

[IDokan]

Pause this task for a while until we are ready to implement Event level, Boss level, and Shop level or such things...