Graph-Guided Item Randomizers: Formal Models, Search Strategies, and Metrics for Procedural Game Worlds

• Monisha Rengaraj

  Author

This paper formulates key-item placement in adventure-style games as a reachability problem on directed graphs with rule-constrained edges, introducing formal algorithms that support progression feasibility while enabling controlled randomness. Three placement procedures are defined in this paper: Random Fill, Forward Fill, and Assumed Fill, with Algorithm 1 providing the formal specification of Random Fill; forward and assumed fill are described in prose, with their algorithmic structure outlined. Generalized search routines (including sphere-based progression and a heuristic playthrough simulation) compute accessible regions and derive guidance for item ordering. A world-generation framework and a path-aware complexity score are provided, together with an evaluation suite that quantifies failure rate, runtime, bias orientation, and a composite ''interestingness'' measure decomposed into fun, challenge, satisfyingness, and boredom. Extensive stochastic evaluation on synthetic graphs characterizes algorithmic trade-offs, showing how assumed-knowledge placement improves completeness at higher computational cost while forward expansion scales efficiently with world structure. The study yields prescriptive insights for selecting placement and search strategies by target world topology and desired player experience, offering pseudocode and metrics to support content-generation pipelines in computational game design.

• PDF

Copyright (c) 2026 International Journal of Intelligent Systems and Data Science

This work is licensed under a Creative Commons Attribution 4.0 International License.