Bx Examples Repository

Title: Sokoban

Version: 0.1

Type: Sketch


This example establishes an import/export for a metamodel of the popular board game Sokoban.
It is essentially a bx tree to graph transformation, and the provided TGG implementation shows nicely how to decompose a problem into "patterns" which can then be translated to rules.
In this case the patterns are: (1) the top left field of the board, which has neither a top nor a left neighbouring field, (2) all fields in the first row, which all have no top neighbour but always a left neighbour, (3) all fields in the first column, which all have a top neighbour but no left neighbour, and finally (4) every other field on the board, which all have a top and a left neighbour.


The diagram below shows the AST that can be parsed from the standard textual concrete syntax for Sokoban levels using standard string parsing technology.

The corresponding model (according to a certain IT-inspired metamodel) is depicted below, showing the board structure and some figures on a few fields (Walls, Servers (== Box), Admin (== Sokoban), and Goals).



Consistency Restoration

Properties [optional section]

Variants [optional section]


This is a nice example to showcase incrementality, i.e., being able to handle small changes (moving the figures a few steps) on a huge board efficiently.

References [optional section]

This example is currently the short tutorial for eMoflon, built directly into Eclipse and complete with a pretty GUI, and a parser/unparser so you can really import and export standard Sokoban levels using TGGs - try it out!


Anthony Anjorin.



Artefacts [optional section]

A virtual machine hosted on Share is available with a workspace containing both (Ecore) metamodels, the concrete example used above, and a TGG formalizing the consistency relation as a set of rules:

Unless otherwise stated, the content of this page is licensed under GNU Free Documentation License.