EUVIMEDEUVIMED entdecken
Crossref

Constraining the Expressive Range of Shortest Paths

Samuel Randall, Mahsa Bazzaz, Seth Cooper

Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment · 08.11.2026 · 22 (1) · 342-349

DOI: 10.1609/aiide.v22i1.43592 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, online erschienen am 08.11.2026. Verfasst von Samuel Randall und 2 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Expressive range metrics are often used to evaluate procedural level generators. Solution-path related metrics require using an agent that plays the level, often by finding a single shortest path through the level. However, there may be multiple shortest paths with different metrics. Additionally, in expressive range analysis, it is common to repeatedly generate levels for the agent to evaluate, which may be inefficient when a desired metric value is known. Recently, constraint-based approaches, which can solve for both a level and an example solution path, have been used to constrain metrics in generated levels. This example solution path, however, may not correspond to the one a shortest-path agent would take. We extend that work with path-state reachability, and the constraint that all shortest paths through a level have some desired expressive range metric value. We view agent-evaluated metrics as properties of paths through a reachability graph on locations in the level, and augment locations in the graph with path length and state-based information relevant to the metrics. We use this path-state reachability graph in the constraint problem to ensure that there is a path through the level with the desired metric value, and that any path with a different metric value is longer (or, in some cases, does not exist). We apply this to various path-based expressive range metrics in a top-down exploration game and platformer game, and compare to levels generated without path-state reachability. We find that the path-state reachability takes longer to generate levels, but may be more efficient for metric values that are less likely to be generated by chance.

Zitieren

APA

Randall, S., Bazzaz, M., & Cooper, S. (2026). Constraining the Expressive Range of Shortest Paths. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 22(1), 342-349. https://doi.org/10.1609/aiide.v22i1.43592

Vancouver

Randall S, Bazzaz M, Cooper S. Constraining the Expressive Range of Shortest Paths. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment. 2026;22(1):342-349. doi:10.1609/aiide.v22i1.43592

BibTeX
@article{Randall2026,
  author = {Randall, Samuel and Bazzaz, Mahsa and Cooper, Seth},
  title = {Constraining the Expressive Range of Shortest Paths},
  journal = {Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment},
  year = {2026},
  volume = {22},
  number = {1},
  pages = {342--349},
  doi = {10.1609/aiide.v22i1.43592}
}
Kostenlos starten →