Master Pac-Man Design: Programmed Graph Rewriting with Time

Want to design captivating games? Discover how to use programmed graph transformation with time for simulation-based design, creating immersive experiences.

This article explores using the Discrete Event System Specification (DEVS) formalism to model and simulate the classic game of Pac-Man. This approach allows modeling both game dynamics and player behavior, enabling you to fine-tune game parameters for optimal playability through simulation.

The Power of Timed Graph Transformation

Programmed graph transformation makes complex systems modelling scalable. By incorporating time, we can simulate reactive systems like computer games with greater realism. We will show the advantages of reusing a discrete-event modeling/simulation formalism to describe transformation control, using the PacMan example.

Pac-Man: A Case Study in Game Design

Pac-Man offers a simplified yet effective model for demonstrating timed, programmed graph transformation for simulation-based design.

The Pac-Man Language: Abstract & Concrete

The Pac-Man language consists of five key elements:

• PacMan: The player-controlled character.
• Ghost: The enemy characters.
• Food (Pellets): The items PacMan consumes.
• GridNode: The locations within the maze.
• ScoreBoard: Tracks the player's score.

AToM3 allows visual modeling of game elements and their relationships.

Pac-Man Semantics: Graph Transformation Rules

The game's logic is defined through graph transformation rules:

• Ghost Kills PacMan: Removes PacMan when a Ghost occupies the same GridNode.
• PacMan Eats Food: Removes Food and updates the score when PacMan occupies the same GridNode.
• Ghost Movement: Defines how Ghosts move across the GridNode network.
• PacMan Movement: Defines how PacMan moves across the GridNode network

These rules, with assigned priorities, govern the game's dynamics.

DEVS: Capturing System Behavior

DEVS allows for modular, hierarchical modeling of discrete event systems. It provides a rigorous basis for compositional modeling and the simulation of discrete event systems.

Atomic vs. Coupled Models: The Building Blocks

• Atomic Models: Describe the behavior of individual reactive system components.
• Coupled Models: Combine multiple DEVS sub-models (atomic or coupled) connected through ports and channels.

This structure allows for complex system representation.

How DEVS Controls Graph Rewriting

Graphs are embedded in DEVS events, with transformation rules in atomic DEVS blocks. This creates a transformation pipeline, connecting visual modelling with rules. Our approach comprises a number of transformations. First, we model a collection of transformation rules in domain-specific notation. Second, we build a hierarchical model of the Modelled and Modular Timed Graph Transformation language, in the MoTif (Modular Timed model transformation) visual modelling language. Third, the MoTif model gets compiled into a DEVS model. Finally, all generated code is linked and presented to a DEVS simulator which performs the transformation and produces a trace.

Pac-Man DEVS Model: A Deep Dive

The Pac-Man model incorporates a User block with control logic and transformation rules. By embedding graphs in DEVS events and individual transformation rules into atomicDEVS blocks, the program is able to play Pac-Man.

Modelling the Player: Beyond Game Dynamics

To accurately assess “playability”, a player's behavior needs to be explicitly modeled, allowing autonomous game runs and facilitating parameter adjustments for player types and game factors. This includes factors such as reaction time which is critical to playability performance measure.

Explicit Player Modelling in Game Design

By modelling the player and the game, different player modelling or levels can be compared with respect to playability. DEVS modularity permits user block refinement into User Interaction which sends control and User Behaviour which simulates the player. We will explore how to model both the game and player in programmed graph rewriting with time.

Next Steps: Simulating and Optimizing Playability

With explicit player and game models, simulation experiments can be performed to determine optimal game configurations. This allows for data-driven design decisions, improving game playability and user experience.