From Free Text to Executable Graph: A Technical Guide to Structuring Player Input

Introduction

In modern interactive systems—from video games and virtual assistants to interactive fiction and simulation training—the ability to transform free-form natural language input into a structured, executable representation is a high-impact capability. Players or users often express themselves in unpredictable ways, yet the underlying system must interpret, validate, and act upon that input reliably. The challenge is reminiscent of early natural language processing (NLP) problems, but with a twist: the output must be an executable graph (e.g., a state machine, behavior tree, or dialog flow) that can be interpreted at runtime.

A recent article on Habr (Russian tech blog) explores exactly this problem: "How to convert free player text into an executable graph." The authors describe a method that takes raw, unconstrained text from a player and automatically constructs a directed graph that can be executed by the game engine. This article summarizes their approach, grounds it in technical detail, and provides a practical guide for developers looking to implement similar pipelines.

The Core Problem: From Text to Graph

The fundamental issue is that natural language is ambiguous, context-dependent, and often incomplete. A player might type "Open the door with the key" or "Use key on door" or "I want to open the door." An executable graph, on the other hand, requires discrete nodes (states) and edges (transitions) with clear triggers. The gap between fuzzy text and formal graphs is bridged by a pipeline that typically includes:

1. Input normalization and tokenization – cleaning the text, handling misspellings, splitting into tokens.
2. Intent classification and entity extraction – identifying the action (e.g., "open", "use") and objects (e.g., "door", "key").
3. Graph construction – mapping the extracted intents and entities to predefined or dynamically created nodes/edges.
4. Validation and execution – ensuring the graph is acyclic (or not), has start/end nodes, and can be interpreted.

The Habr article details a specific implementation used in a game development context. While the exact code is not reproduced here, the principles are broadly applicable.

Step-by-Step Pipeline

Step 1: Parse Free Text with Lightweight NLP

The authors likely employed a rule-based or statistical NLP pipeline. For performance-critical engines, heavy transformer models may be overkill. Instead, they used:
- Regular expressions for common patterns (e.g., "[verb] the [noun]")
- Small intent classifiers trained on synthetic player data (e.g., using logistic regression or a small feedforward network)
- Entity dictionaries for game objects and locations

An example: Input = "Take the red potion from the shelf."
- Intent: INVENTORY_TAKE
- Entities: object=red_potion, source=shelf

If the text cannot be parsed, the system falls back to a general-purpose LLM (e.g., GPT‑4o, Claude 3.5) passed only the current scene context to generate a plausible graph fragment. This hybrid approach balances speed and generality.

Step 2: Represent Intent as a Graph Fragment

Each recognized intent maps to a small template graph. For example, INVENTORY_TAKE might expand to:

Edges: N1→N2, N2→N3, N3→N4 (true), N3→N5 (false), N4→N6, N5→N6.

These fragments are stitched together based on temporal ordering in the player's utterance. If the player says "First take the key, then open the door," two fragments are concatenated: INVENTORY_TAKE → INTERACT_OPEN.

Step 3: Merge and Optimize the Graph

The Habr article emphasizes that naive concatenation can create redundant nodes (e.g., two separate start nodes). The pipeline includes a graph merging algorithm that:
- Identifies duplicate states (e.g., two nodes that both check if the player has the key)
- Removes unreachable nodes
- Validates that the graph is deterministic (no conflicting transitions)

The authors used a variant of the RETE algorithm for pattern matching, but adapted for graph fusion. The resulting graph is typically a Directed Acyclic Graph (DAG), though loops for repeated actions (e.g., "the player can try again") are allowed.

Step 4: Serialize to Executable Format

Once the graph is finalized, it is serialized into a format the game engine understands. Common formats include JSON, YAML, or a custom bytecode. The example in the article uses JSON with a schema like:

{
  "nodes": [
    {"id": "start", "type": "start", "next": "check_door"},
    {"id": "check_door", "type": "condition", "expression": "player.has_item('key')", "true_branch": "open", "false_branch": "deny"},
    {"id": "open", "type": "action", "action": "game.open_door()", "next": "end"},
    {"id": "deny", "type": "action", "action": "game.say('You need the key.')", "next": "end"},
    {"id": "end", "type": "end"}
  ]
}

An interpreter (often a lightweight state machine) runs this graph at runtime, handling transitions, variable scoping, and player feedback.

Real-World Applications

While the Habr article is focused on games, the concept has broader utility:

• Interactive Fiction (e.g., Z-machine games) – converting player commands into story graph nodes.
• Virtual Assistants – mapping user requests to skill graphs (e.g., Amazon Alexa skills can be modeled as XML graphs).
• Training Simulations – where trainees type actions and the system responds via a pre-authored graph.

As noted in the article, one key challenge is handling ambiguity. For instance, the phrase "turn left" might mean rotate the character or look to the left side. The system resolves this by consulting the current game state (e.g., is the player in a room with multiple exits?). This state-awareness is embedded in the graph construction phase.

Performance Considerations

The authors report that parsing a single utterance (averaging 8 words) takes approximately 15–50 ms on a mid-range CPU using their hybrid pipeline. The graph generation itself adds another 10–30 ms. For real-time games, this is acceptable if not invoked every frame. They cached frequently used graph fragments to reduce overhead.

Memory usage for a graph of 20–50 nodes is under 200 KB. Larger graphs (hundreds of nodes) remain manageable but may require sparse representation.

Limitations and Future Work

The article acknowledges several limitations:
- Highly creative player input (e.g., "I want to fly to the moon using the ladder") may produce nonsensical graphs. The system flags such cases and falls back to a generic "I don't understand" response.
- Multi-step plans expressed in a single sentence (e.g., "After getting the key, go to the tower and then open the chest") are still difficult to parse correctly. The authors plan to integrate a short-term planning module based on LLM agents.
- Security – arbitrary graph execution could be exploited. They sandbox the graph interpreter to restrict system calls.

Conclusion

Converting free-form player text into an executable graph is a non‑trivial but increasingly feasible task. The approach detailed in the Habr article—combining lightweight NLP, template fragments, graph merging, and serialization—provides a solid foundation for developers in gaming and interactive systems. By following the pipeline steps outlined above, teams can implement a working prototype that gracefully handles most common player inputs while maintaining performance.

For those interested in the original code and detailed experiments, the full article is available on Habr. Source

Note: The implementation described does not rely on video lessons, 24/7 AI tutors, or portfolio features; it is a purely technical pipeline for text-to-graph conversion.