Packing strategy that assigns tiles to palettes using BFS/DFS backtracking with a fallback matrix. More...
#include <backtracking_strategy.hpp>
Public Member Functions | |
| BacktrackingStrategy ()=default | |
| BacktrackingStrategy (gsl::not_null< const UserDiagnostics * > diag) | |
| Constructs in preset matrix mode with diagnostics support. | |
| BacktrackingStrategy (SearchAlgorithm algorithm, std::size_t node_cutoff, std::size_t best_branches, bool smart_prune, const UserDiagnostics *diag=nullptr) | |
| Constructs with explicit search parameters for single-configuration mode. | |
| ChainableResult< PackingOutput > | pack (const PackingInput &input) const override |
| Packs tiles into palettes using BFS/DFS backtracking search. | |
| std::string | name () const override |
| Returns the name of this strategy. | |
 Public Member Functions inherited from porytiles::PackingStrategy | |
| virtual | ~PackingStrategy ()=default |
Detailed Description
Packing strategy that assigns tiles to palettes using BFS/DFS backtracking with a fallback matrix.
This strategy systematically explores the solution space for valid palette assignments using depth-first and breadth-first search with backtracking. A fallback matrix of 48 configurations (varying cutoff limits, branch limits, and search algorithms) is tried in sequence until a solution is found.
BFS uses visited-state deduplication and a dual-queue heuristic (high-overlap assignments prioritized) to efficiently explore the state space. DFS uses in-place mutation with undo for memory efficiency.
This strategy is designed to solve instances that defeat greedy heuristics like Overload-and-Remove, such as gTileset_General from pokefirered.
Based on Porytiles1's palette_assignment.cpp, with two key improvements:
- Authoritative DFS subset shortcut. When a tile's colors are already a subset of some palette, Porytiles1 had no general subset shortcut for primary tilesets. It processed the tile as a normal candidate. Our implementation detects the subset case and immediately recurses without modification. Critically, the result is returned directly (no fallthrough to the candidate loop). A non-authoritative version that fell through caused exponential blowup: the covering palette appeared as the first candidate (union is a no-op), re-exploring the same subtree. At K levels with subset matches, total work became O(2^K) times the necessary amount.
- DFS in-place mutation with undo. Porytiles1 copied the entire palette vector for each DFS branch. We save and restore only the single modified palette, reducing per-node allocation overhead.
The strategy supports two modes:
- Preset matrix mode (default): Iterates through 48 known-good configurations (varying cutoffs, branch limits, and algorithms) until a solution is found. Use this when the input characteristics are unknown.
- Single-config mode: Runs a single search with caller-specified parameters. Use this when you know which settings work for your input, or for targeted testing and tuning.
Definition at line 50 of file backtracking_strategy.hpp.
Constructor & Destructor Documentation
◆ BacktrackingStrategy() [1/3]
|
default |
◆ BacktrackingStrategy() [2/3]
|
inlineexplicit |
Constructs in preset matrix mode with diagnostics support.
Uses the full 48-configuration preset matrix (default behavior) and emits a remark via the provided diagnostics when a successful configuration is found.
- Parameters
-
diag Diagnostics interface for emitting remarks about successful search parameters.
Definition at line 63 of file backtracking_strategy.hpp.
◆ BacktrackingStrategy() [3/3]
|
inlineexplicit |
Constructs with explicit search parameters for single-configuration mode.
When constructed with this constructor, the strategy runs a single search with the provided parameters instead of iterating through the preset configuration matrix.
- Parameters
-
algorithm The search algorithm to use (DFS or BFS). node_cutoff Maximum number of nodes to explore before giving up. best_branches Maximum number of candidate branches per node ( SIZE_MAXfor unlimited).smart_prune Whether to cap candidates after the first zero-intersection palette. diag Optional diagnostics interface for emitting remarks about successful search parameters.
- Precondition
node_cutoffmust be greater than zero.
Definition at line 79 of file backtracking_strategy.hpp.
Member Function Documentation
◆ name()
|
inlineoverridevirtual |
Returns the name of this strategy.
- Returns
- "Backtracking"
Implements porytiles::PackingStrategy.
Definition at line 109 of file backtracking_strategy.hpp.
◆ pack()
|
overridevirtual |
Packs tiles into palettes using BFS/DFS backtracking search.
In preset matrix mode, tries 48 search configurations (DFS and BFS with varying cutoffs and branch limits) until a valid assignment is found. In single-config mode, runs one search with the configured parameters. The search state is a compact vector of ColorSets (one per palette), and tile-to-palette mappings are reconstructed after a solution is found.
- Parameters
-
input The packing input containing tiles, hints, fixed slots, and constraints
- Returns
- A PackingOutput on success, or an error if all configurations fail
Implements porytiles::PackingStrategy.
Definition at line 573 of file backtracking_strategy.cpp.
The documentation for this class was generated from the following files:
- porytiles/include/porytiles/domain/packing/services/backtracking_strategy.hpp
- porytiles/lib/domain/packing/services/backtracking_strategy.cpp
