Graph Topology and Battle Royale Mechanics
3 days ago
- #game design
- #AI techniques
- #graph theory
- Graph topology is used to model city closing mechanics in the game Two Spies, where cities are vertices and travel routes are edges.
- Closing cities affects map playability, with issues like disconnected graphs and path graphs reducing strategic options.
- Disconnected graphs can be avoided by ensuring the remaining graph is connected through breadth-first search.
- Path graphs are less optimal; the Wiener number (sum of shortest paths between nodes) helps quantify graph quality.
- Greedy pruning selects cities to remove based on the lowest Wiener number but can lead to suboptimal graphs later.
- Beam search, an AI technique, looks ahead to avoid local minima, resulting in better long-term graph structures.
- Beam search with a width of 10 outperforms greedy pruning by maintaining a denser core and avoiding traps.
- The approach shows how mathematical methods and classic AI techniques can solve game design challenges.