These authors contributed equally to this work. [3]Lisa Mathew These authors
contributed equally to this work.

1]Department of Computer Science and Engineering, Amal Jyothi College of
Engineering, Kanjirappally, Kottayam, 686 518, Kerala, India

2]Research scholar, APJ Abdul Kalam Technological University, CET Campus,
Thiruvananthapuram, 695 016, Kerala, India

3]Department of Basic Sciences , Amal Jyothi College of Engineering,
Kanjirappally, Kottayam, 686 518, Kerala, India

# On Graph Grammars and Games

Jayakrishna Vijayakumar<EMAIL_ADDRESS><EMAIL_ADDRESS>[  [  [

###### Abstract

Graph grammars form an interesting area of research because of their
versatility in modelling diverse situations with graphs as the structures
which are to be manipulated. A new class of graph grammars, nc-eNCE Graph
Grammars has been introduced recently with an aim of restricting the order of
application of graph production rules, thereby generating different graph
classes using the same set of rules. On the other hand 2D game design using an
algorithmic approach known as procedural content generation has been of
interest recently. In this paper we modify the structure of nc-eNCE graph
grammars with the aim of generating directed graphs. We show that employing
these graph grammars simplifies the design of 2D games. We have also developed
an algorithm which makes use of these graph grammars for generating random
game level layouts ensuring that the players will get a different gaming
experience each time they play.

###### keywords:

Graph Grammars, Confluence, Connection Instructions, Regular Control, Jumping
Graph Grammars, Lock-and-Key Games, Platform Games

3

##  1 Introduction

Puzzle games form a fascinating class of 2D games due to their challenging and
entertaining nature. However the creation of these games traditionally
required immense manpower and time, thereby escalating the cost of developing
these games. In order to avoid boredom on the part of players a game developer
needs to provide new domains to the player so that the game becomes
unpredictable. Making use of algorithms for creating these environments helps
developers to produce new challenges at a lower cost. In this paper we look at
certain categories of 2D games - specifically games having lock-and-key[1]
patterns as challenges.

Any system where items are interconnected in some way, such as a network of
computers, a city and its roads[2], or a group of friends on a social network,
aquatic predatory networks, plant pollinator networks, etc. can be represented
using graphs. As the game design methodology used here is algorithmic in
nature, the best data structure that complements this approach is a graph. In
this paper we employ graph grammars as a mechanism for creating these game
plots/levels. We have designed an algorithm which randomly generates a new
game plot each time the game is played, ensuring a stimulating experience for
the players.

The rest of this paper is organised as follows. Section 2 presents the key
concepts associated with game design and graph grammars required for
understanding the rest of this paper. Sections 3 and 4 develop a modified
version of the nc-eNCE and jumping graph grammars introduced in [3, 4] so as
to deal with directed graphs. Finally Section 5 deals with two dimensional
game generation and shows how the modified graph grammars discussed in
Sections 3 and 4 can be used to generate solvable game plots. It also includes
an algorithm for generating these plots randomly.

##  2 Preliminaries

###  2.1 2D Games

We present some of the fundamental terminology associated with game design.

  * Procedural content generation[5] - the process of using algorithmic concepts to produce game content.

  * Level/Plot[6] \-  Specific area in a gaming environment restricted by the architecture of the game space.

  * Linear Games[7] \-  Games where a player travel over the gaming world in a well established order. The levels/ plots are kept in such a way that a player can only move to a unique plot from his/her current space.

  * Action-Adventure Games[8]- 2D games that have warfare, investigations and puzzle solving. It is typical to incorporate obstacles like mines and fights into a puzzle scenario while setting up an action-adventure game. Classic video games like Beyond Good and Evil, Constantine, etc. come under this category.

  * Logic Puzzles - Solvable challenges which make use of reasoning based only on some prior information which has been provided within the puzzle.

  * Missions - Circumstances in which a player will move along the game environment in order to achieve a specific target by surmounting a number of hurdles.

  * Platform Games -  Games where barriers in a path can be avoided by jumping between different platforms.

###  2.2 Lock-and-Key Puzzles

The games level designs considered in this paper have some common elements and
logic. They can be referred to as lock-and-key puzzles[9]. The components of a
lock-and-key puzzle are explained here.

####  2.2.1 Structure

The structure of these puzzles consists of objects in the form of locks and
keys[1]. A lock is a barrier that restricts the player from advancing across a
level unless a condition is satisfied. A lock has an orientation and
direction. Once it has been opened, the player gains access to a distinct
traversal. Some locks only work in one direction and prevent players from
returning to the previous traversal plot they entered from once they have
passed through. In order to access the lock the player should locate the key.
A key is an item used to open a lock. They can be in the form of switches or
objects. Switches are keys that can open locks without moving them. Keys in
the form of objects need to be selected and placed in the specific area to
open a specific lock. If a player needs to complete a level or goal, then he
needs to open one or more locks which prevents him from achieving it. A player
cannot open a lock unless he has the unique key for that lock and this becomes
the central idea of the puzzle. A lock and key in the actual game world can be
any pair of objects that satisfies the above said properties. A switch to open
a door, a trigger to blast open a cave, a vessel to move across a swift river,
etc. are some scenarios which satisfies the lock and key logic. If it appears
that there is no major obstruction to be considered in the way, a mere lock
and key may be present in the space and be regarded as a part of the
traversal. Even though locks and keys appear in a variety of ways in the
environment of a game, their relationship does not change. The objects that
are to be placed in a puzzle environment layout are of great importance as far
as game playing is concerned.

####  2.2.2 Traversal

A traversal is considered as an interconnected area where a player has the
freedom to move his character to and from any place in that space utilizing
the in-game tools provided. There could be many rooms in that real game space
scenario. On entering a traversal space[8], the player is presented with the
barriers, challenges and constraints that makes the movement a challenging
task. The space contains difficult situations with obstacles in the form of
fighting and platforms for agile movements. A player need to acquire a better
understanding of the plot and a competence to overcome these situations. In
this paper the focus is on abstracting the physical design and concentrating
more on the structure of the game level. We are only interested in the
puzzle’s crucial path for the sake of this study. This implies that the player
may ignore any portion of the mission that they are not needed to complete.

####  2.2.3 Puzzle Graphs

We use graph theory to present a conceptual description of game level and its
structure . This is referred to as a puzzle graph environment. It is a
directed graph with labelled nodes of any of the following four styles.

  * Begin -  At this node the player begins the game/level. Movement to the next traversal point happens after that.

  * End -  The puzzle finishes if the player arrives at this node.

  * Lock -  A player’s movement flexibility is restricted by these nodes. A lock node can be passed through only if all the respective key nodes are activated.

  * Key -  When there is an edge traversing which leads to this node, then a player can use the key node and use it for unlocking the corresponding lock node. Usually key nodes are kept in an active mode in most game designs.

We aim to design solvable puzzle graphs which ensures that the game terminates
in a finite period of time. This is confirmed by checking whether there is a
directed path from the begin node to the end node. An unsolvable puzzle
scenario arises when a key for opening a lock is kept behind the lock node and
hence is unreachable. There can also be situations where a lock does not have
a key at all, preventing the forward movement of the player thereby making the
end node unreachable. We use an algorithmic approach towards generation of
solvable puzzle graphs.

###  2.3 Graph Grammars

The concept of a grammars in formal language theory [10] has motivated
exploration into the possibilities of their application to more complex
structures. Research has proved that this experimentation is worthwhile for
instance by utilizing grammar theory in the generation of planned blueprints
of cities and buildings. Similarly the L- Systems [11] proposed by Lindenmayer
has the ability to create structures that mimic the natural growth of plants.

Graph grammars came about as a result of a graph based approach to formal
grammar theory [12]. Unlike a normal grammar which generates a collection of
strings, a graph grammar is capable of generating a family of graphs which
exhibit some specific characteristics. Graph grammars basically come under two
categories namely edge replacement and node replacement graph grammars [13].
Edge/ Hyperedge replacement graph grammars [14] typically are used to build
hypergraphs wherein multiple nodes get connected to an edge.

There are three parts to a production rule for a graph grammar: the mother and
daughter subgraphs, and the embedding technique [13]. The host graph is the
one to which we apply a production. If the mother subgraph is present in the
host graph, a production can be applied to that graph. The daughter subgraph
is substituted for the the mother subgraph in the host graph. The remainder of
the host graph is then connected to the daughter subgraph in accordance with
the embedding procedure. Formally a graph grammar production rule is of the
form $(M,D,E)$ [13]. In this construct $M$ is the mother subgraph that is
present in the host graph $H$ to which we apply the graph production rule. $D$
is the subgraph that replaces $M$ in $H$. $E$ is the embedding procedure that
determines the new connections between $D$ and the rest of $H$.

Graph grammars primarily have two embedding methods- gluing and connecting, or
in other terms algebraic and algorithmic approaches [15, 16]. More on these
concepts can be found in [12]. Meanwhile a few new variants of graph grammars
had been introduced in [4]. We enhance the concepts of those graph grammars in
order to generate directed graphs which in turn become the base in setting up
the plot for game levels.

As this work involves the usage of node replacement graph grammars [13] and
its enhanced variants, the mother graph consists of a single node. The
following example illustrates the subgraph embedding procedure.

######  Example 1.

Consider the host graph shown in Figure 1 and the graph production rule in
Figure 2. A production rule $p$ is applied only if we have a subgraph in the
host graph isomorphic to the graph on the left of the production rule.
Application of a production rule works in two stages. First we need to remove
the mother node and then we need to embed the right side of the corresponding
production rules using the connection instructions associated with that
production rule. As a result of this we generate a new graph. In our example,
applying production rule $p$ on the host graph removes the node $B$ from the
host graph and embeds the subgraph to the right of $p$ in the remaining
portion of the host graph using the connection instruction
$C=\\{(A,\alpha\mid\beta,3)\\}$. This instruction establishes edges labelled
$\beta$ between the node labelled $A$ which was previously connected to $B$
using edge $\alpha$ and each node numbered $3$in the daughter graph. The two
stages are shown in Figure 3.

1$A$2$B$1$A$$\alpha$$\alpha$ Figure 1: Host graph
$p:$2$B$$\rightarrow$3$C$2$B$$C=\\{(A,\alpha\mid\beta,3)\\}$2$B$$\alpha$$\alpha$
Figure 2: Graph Production Rule
1$A$1$A$1$A$3$C$1$A$2$B$2$B$$\beta$$\beta$$\alpha$$\alpha$ Figure 3: Graph
after the removal of mother node and after the embedding

There are several variants of node replacement graph grammars [13, 17]. Most
of these graph grammars are confluent. This means that there is no restriction
in the order of application of production rules. In contrast, the new variants
introduced in [4] has a function in the form of a regular expression $R(P)$
which controls the order in which the production rules need to be applied in
the host graph and thereby achieves nonconfluentiality in generation of
undirected graph classes.

##  3 Directed Non-Confluent Edge and Node Controlled Embedding (Dnc-eNCE)
Graph Grammar

In this section we present an enhanced variant of $nc-eNCE$ graph grammar
introduced in [4] to derive the class of directed graphs. Here an extra
parameter is added to the connection instruction in order to specify the
direction of the newly created edges. We later use this new graph grammar
variant to generate puzzle graphs [1] which becomes the base for 2D game
design. Formally we have the definition:

######  Definition 1.

A construct $DrncG=(\Sigma,\Delta,\Gamma,\Omega,P,G_{S},R(P))$ is known as an
$Dnc-eNCE$ graph grammar where

  * $\Sigma$ and $\Gamma$ are sets of symbols used to label nodes and edges respectively,

  * $\Delta$ and $\Omega$ are the collections of terminal symbols in $\Sigma$ and $\Gamma$ respectively,

  * A production rule in $P$, $p:A\rightarrow(D,C)$ acting on the mother node $M$ with label $A$ has a collection C of connection instructions $(a,p\mid d\mid q,B)$ associated with it. This indicates that the edge $p$ which connected $x$ (a neighbour of $M$ with label $a$) and $M$ is removed and a new edge $q$ is established between $x$ and $B$ (a node in $D$). The flag $d\in\\{0,1,-1\\}$ indicates the edge direction. $0$ indicates that the connection is bidirectional, $1$ indicate a directed edge from $x$ to $B$ and $-1$ indicate a directed edge from $B$ to $x$.

  * $G_{S}$ is the initial graph,

  * The regular control, $R(P)$, regulates the sequence of application of the production rules.

The graph grammar $ncG$ generates the language

$L(DrncG)={\\{G\in G_{\Delta}|G_{S}\overset{R(P)}{\implies}G\\}}$

Here, all the nodes of graphs in $G_{\Delta}$ are labelled using $\Delta$ and
$G_{S}\overset{*}{\Rightarrow}G$ is as in definition 1. The ordered
application of productions in the sequence $p_{1},p_{2},\cdots,p_{n}$
($p_{1}p_{2}\cdots p_{n}\in L(R(P))$ leads to the generation of graphs
specified by the language of the grammar.

######  Example 2.

Consider $ncG_{W}=(\Sigma,\Delta,\Gamma,\Omega,P,G_{S},R(P))$,
$\Sigma=\\{W,E,a,c,s,e\\}$, $\Delta=\\{a,c,s,e\\}$, $\Gamma=\\{\alpha\\}$,
$\Omega=\\{\alpha\\}$, $P=\\{p_{1},p_{2},p_{3}\\}$, $G_{S}$ is a single node
labelled $W$ and R(P)= $p_{1}p_{2}^{*}p_{3}$. The productions in P are shown
in Figure 4.

2$s$$p_{1}:$1$W$$\rightarrow$5$c$3$a$4$E$$C_{1}=\phi$$p_{2}:$4$E$$\rightarrow$3$a$4$E$$C_{2}=\\{(c,\alpha|1|\alpha,3),(c,\alpha|1|\alpha,4),$$(a,\alpha|-1|\alpha,3),(s,\alpha|1|\alpha,4)\\}$$p_{3}:$4$E$$\rightarrow$6$e$$C_{3}=\\{(c,\alpha|1|\alpha,6),(a,\alpha|-1|\alpha,6),$$(s,\alpha|1|\alpha,6)\\}$$\alpha$$\alpha$$\alpha$$\alpha$$\alpha$$\alpha$$\alpha$
Figure 4: Production rules for directed Wheel graph.

Figure 5 shows the generation of the directed Wheel graph $W_{6}$ using the
grammar $ncG_{W}$.

2$s$2$s$4$E$1$W$$\Rightarrow$$p_{1}$5$c$$\Rightarrow$$p_{2}$5$c$3$a$4$E$3$a$3$a$2$s$2$s$$\Rightarrow$$p_{2}$3$a$5$c$4$E$$\Rightarrow$$p_{3}$3$a$5$c$6$e$3$a$3$a$3$a$3$a$$\alpha$$\alpha$$\alpha$$\alpha$$\alpha$$\alpha$$\alpha$$\alpha$$\alpha$$\alpha$$\alpha$$\alpha$$\alpha$$\alpha$$\alpha$$\alpha$$\alpha$$\alpha$$\alpha$$\alpha$$\alpha$$\alpha$$\alpha$$\alpha$$\alpha$$\alpha$$\alpha$$\alpha$$\alpha$$\alpha$$\alpha$$\alpha$$\alpha$$\alpha$
Figure 5: Generation of the directed Wheel graph $W_{6}$.

##  4 Directed Non-confluent Edge and Node Controlled Embedding Jumping Graph
grammars (Dnc-eNCE-JGG)

We extend the concept of $Drnc-eNCE$ graph grammar in Definition 1 as follows.
Formally, we have:

######  Definition 2.

A $Dnc-eNCE-JGG$ graph grammar is a 7 tuple:
$DrncJGG=\text{(}\Sigma,\Delta,\Gamma,\Omega,$ $P,G_{S},R\text{(}P\text{)}$)
where

  * $\Sigma$ is the set of node labels,

  * $\Delta$ is the set of terminal node labels,

  * $\Gamma$ is the set of edge labels,

  * $\Omega$ is the set of terminal edge labels,

  * The productions in $P$ are either as defined in 1 or of the form $p:A\rightarrow(D,C)$ where $A$ is the label of the mother node and $D$ is the daughter graph. The connection instruction $C$ can be in any one of the following forms

    1. 1.

($a,p\mid d\mid q,B$), where $p$ and $q$ are edge labels, $a$ is the node
label of one of the neighbours of the mother node and $B$ is a node in $D$.
The interpretation is that we find an edge labelled $p$ in the host graph
which had connected a node $x$ labelled $a$ to the mother node and create a
new edge labelled $q$ between $x$ and the node $B$ in the daughter graph. Here
flag $d$ works as in Definition 1.

    2. 2.

$(a,\alpha,b\mid d)$, where $a$ is the node label of one of the nodes in $D$,
$b$ is the label of any of the nodes in remaining graph after removing the
mother node and $\alpha$ is the label of the new edge connecting $a$ and $b$.
The flag $d\in\\{0,1,-1\\}$ indicates the edge direction. $0$ indicates that
the connection is bidirectional, $1$ indicate a directed edge from $b$ to $a$
and $-1$ indicate a directed edge from $a$ to $b$.

  * $G_{S}$ is the start/initial graph,

  * $R(P)$ is a regular control which specifies the order of application of the productions, Hence this grammar becomes restricted or non-confluent.

The language represented by this grammar is

$L\text{(}DrncJGG\text{)}={\\{G\in
G_{\Delta}|G_{S}\overset{R\text{(}P\text{)}}{\implies}G\\}}$

where $G_{\Delta}$ is the set of graphs containing only terminal nodes. Hence
the language of an $DrncJGG$ graph grammar is a set of graphs whose nodes have
terminal labels, generated by applying a series of productions in the order
$p_{1},p_{2},\cdots,p_{n}$ where $p_{1}p_{2}\cdots p_{n}$ is a word in the
language represented by the regular control $R\text{(}P$). The following
example shows the generation of Wheel graphs using $nc-eNCE-JGG$ graph grammar
$ncJW$.

######  Example 3.

Let $ncJS=\text{(}\Sigma,\Delta,\Gamma,\Omega,P,G_{S},R\text{(}P\text{)}$) be
an $nc-eNCE$ graph grammar with, $\Sigma=\\{C,c,a\\}$, $\Delta=\\{a,c\\}$,
$\Gamma=\\{\alpha\\}$, $\Omega=\\{\alpha\\}$, $P=\\{p_{1},p_{2}\\}$, $G_{S}$
is a single node with label $C$ and $R\text{(}P\text{)}=p_{1}^{*}p_{2}$.
Figure 6 shows the production rules and the associated connection instructions
for generating directed star graphs while Figure 7 shows the derivation of
$S_{7}$. Since every edge in the graph has the same label ($\alpha$) we have
omitted the edge labels in the derivation step.

$p_{1}:$$C$$\rightarrow$$a$$C$$C_{1}=\phi$$\alpha$$p_{2}:$$C$$\rightarrow$$c$$C_{2}=\\{(c,\alpha,a|-1)\\}$
Figure 6: Production rules for directed star graph
$C$$\Longrightarrow$$p_{1}$$a$$C$$\Longrightarrow$$p_{1}$$a$$a$$C$$\Longrightarrow$${p_{1}}^{4}$$a$$a$$a$$a$$a$$a$$C$$\Longrightarrow$$p_{2}$$a$$a$$a$$a$$a$$a$$c$
Figure 7: Generation of the star graph $S_{7}$

##  5 2D Game Generation

In this section we illustrate how 2D game plots/levels can be generated using
graph grammars [18]. The thrust is given to lock-and-key and platform
varieties of games. This is achieved by setting up a puzzle structure,
creating a graph grammar to model the layouts and an associated algorithm for
arbitrarily producing game levels. The skeleton of the game is a puzzle
structure with control points (locks and associated keys) which need to be
traversed in a particular order. In order to guarantee that the puzzle is
solvable, the designer uses directed edges between the control points and
ensures that there is a directed path from the start to the destination.

We use the graph grammars introduced in Sections 3 and 4 to generate game
plots. These grammar variants have the extended capability of generating all
the components such as locks and their corresponding keys, multiple key based
locks, misleading paths, traps, bonus sessions, etc. for setting up a puzzle
based graph plot. The plot generation is demonstrated in Example 4. We have
also proposed Algorithm 1 which generates random game plots, given a valid
graph grammar of one of these types.

######  Example 4.

Consider the graph grammar
$ncG_{P}=(\Sigma,\Delta,\Gamma,\Omega,P,G_{S},R(P))$, where
$\Sigma=\\{S,K,R,G,D,b,e,l,k,m\\}$, $\Delta=\\{b,e,l,m,k\\}$,
$\Gamma=\\{\alpha\\}$, $\Omega=\\{\alpha\\}$,
$P=\\{p_{1},p_{2},p_{3},p_{4},p_{5},p_{6},p_{7},p_{8},p_{9}\\}$, $G_{S}$
consists of a single node labelled $S$ and R(P)=
$p_{1}(p_{5}p_{6}(p_{7}p_{8}^{*}p_{9})^{*}p_{3}^{*}p_{4})^{*}p_{2}p_{3}^{*}p_{4}$.
Figure 8 shows the production rules and the associated connection instructions
for generating Puzzle graphs of various forms while Figure 9 and 10 shows the
derivation of two such game plots. Since every edge in the graph has the same
label ($\alpha$) we have omitted the edge labels in the derivation step.

$p_{1}:$1$S$$\rightarrow$2$b$3$G$7$e$$\alpha$$\alpha$$p_{2}:$3$G$$\rightarrow$5$K$6$l$$\alpha$$p_{3}:$5$K$$\rightarrow$5$K$6$l$7$k$$\alpha$$\alpha$$\alpha$$p_{4}:$5$K$$\rightarrow$7$k$$p_{5}:$3$G$$\rightarrow$8$R$3$G$$\alpha$$p_{6}:$8$R$$\rightarrow$5$K$10$m$$\alpha$$p_{7}:$5$K$$\rightarrow$9$D$5$K$$p_{8}:$9$D$$\rightarrow$9$D$6$l$7$k$$\alpha$$\alpha$$\alpha$$p_{9}:$9$D$$\rightarrow$7$k$$C_{1}=\phi$$C_{2}=\\{(b,\alpha,\mid
1\mid\alpha,5),(b,\alpha,\mid
1\mid\alpha,6),(e,\alpha,\mid-1\mid\alpha,6),(m,\alpha,\mid
1\mid\alpha,5),(m,\alpha,\mid 1\mid\alpha,6)\\}$$C_{3}=\\{(b,\alpha,\mid
1\mid\alpha,5),(l,\alpha,\mid-1\mid\alpha,7),(b,\alpha,\mid
0\mid\alpha,6),(m,\alpha,\mid-1\mid\alpha,7)\\}$$C_{4}=\\{(b,\alpha,\mid
1\mid\alpha,7),(m,\alpha,\mid
1\mid\alpha,7),(l,\alpha,\mid-1\mid\alpha,7)\\}$$C_{5}=\\{(b,\alpha,\mid
1\mid\alpha,8),(e,\alpha,\mid-1\mid\alpha,3)\\}$$C_{6}=\\{(b,\alpha,\mid
1\mid\alpha,5),(b,\alpha,\mid
1\mid\alpha,10),(G,\alpha,\mid-1\mid\alpha,10)\\}$$C_{7}=\\{(b,\alpha,\mid
0\mid\alpha,9),(b,\alpha,\mid
1\mid\alpha,5),(l,\alpha,\mid-1\mid\alpha,9)),(l,\alpha,\mid
1\mid\alpha,5)\\}$$C_{8}=\\{\\{(b,\alpha,\mid
1\mid\alpha,9),(l,\alpha,\mid-1\mid\alpha,7),(b,\alpha,\mid
0\mid\alpha,6)\\}$$C_{9}=\\{(b,\alpha,\mid
0\mid\alpha,6),(l,\alpha,\mid-1\mid\alpha,7)\\}$ Figure 8: Production Rules of
$ncG_{P}$
1$S$$\Longrightarrow$$p_{1}$3$G$2$b$4$e$$\Longrightarrow$$p_{2}$6$l$5$K$2$b$4$e$$\Longrightarrow$$p_{3}$6$l$5$K$6$l$2$b$4$e$7$k$$\Longrightarrow$$p_{3}$6$l$6$l$5$K$6$l$2$b$4$e$7$k$7$k$$\Longrightarrow$$p_{4}$6$l$6$l$7$k$6$l$2$b$4$e$7$k$7$k$
Figure 9: Game plot I
1$S$$\Longrightarrow$$p_{1}$3$b$2$G$4$e$$\Longrightarrow$$p_{5}$8$R$2$b$3$G$4$e$$\Longrightarrow$$p_{6}$10$m$5$K$2$b$3$G$4$e$$\Longrightarrow$$p_{3}$10$m$6$l$5$K$2$b$3$G$4$e$7$k$2$b$6$l$10$m$$\Longrightarrow$$p_{3}$6$l$5$K$3$G$4$e$7$k$7$k$$\Longrightarrow$$p_{4}$10$m$6$l$6$l$7$k$2$b$3$G$4$e$7$k$7$k$2$b$6$l$6$l$7$k$7$k$10$m$6$l$$\Longrightarrow$$p_{2}$4$e$7$k$5$K$2$b$6$l$6$l$7$k$7$k$10$m$4$l$$\Longrightarrow$$p_{3}$4$e$7$k$4$l$7$k$4$K$2$b$6$l$6$l$7$k$7$k$10$m$4$l$$\Longrightarrow$$p_{3}$4$e$7$k$4$l$7$k$4$l$4$K$7$k$2$b$6$l$6$l$7$k$7$k$10$m$6$l$$\Longrightarrow$$p_{4}$4$e$7$k$6$l$7$k$6$l$7$k$7$k$
Figure 10:  Game plot II with multiple hierarchical level.

The graph grammars mentioned in section 3 and 4 are designed in such a way
that it ensures that the game plots generated correspond to a solvable puzzle
graph. This is achieved by designing the grammar such that after each
application of a graph production rule the connection instructions ensure that
the daughter graph replacing the mother graph preserves the valid directed
path from node $b$ to node $e$. In both the plots, the valid positive path to
solve the puzzle/ game level is highlighted with red directed edges that
starts from $b$ and ultimately ends in $e$.

Input: $\\{G_{s},P,R(P),limit\\}$

/* List of parameters */

Output: $G$

/* Solvable Random Game Plot/Map */

Function  _GameGen(_$G_{s},P,R(P),limit$_)_

__ /* Main Function */

:

$RE\longleftarrow$ Reg$(R(P),limit)$;

Apply $RE$ on $G_{s};$

return the resultant graph $G;$

End Function

Function  _Reg(_$R(P),limit$_)_

__ /* Regular expression string Generation */

:

foreach  _$*\in R(P)$_ do

Replace $*$ with $PRNG(seed)\%limit;$

end foreach

return $S_{P};$

End Function

Algorithm 1 Random Game Plot/Map Generation

In order to avoid the tedium of manually generating the game plots we use the
procedural content generation process which is described in Algorithm 1. The
function GameGen() which generates the game plot in the form of a puzzle graph
calls the subfunction Reg() which generates a random string from the given
regular expression. The parameters for the GameGen() function are the initial
graph $G_{s}$, the graph production rule set $P$, the regular expression
$R(P)$ and a natural number, $limit$ which gives a maximum value for the
random numbers to be substituted in $R(P)$. The parameters $R(P)$ and $limit$
are passed to $Reg()$. In $Reg()$ function a random number is generated for
every ${}^{\prime}*^{\prime}$ in $R(P)$ which eventually returns a random
string $S_{P}$ corresponding to $R(P)$. Here we use a pseudo random number
generator which takes a randomly chosen seed value given by the designer. The
plots shown in Figure 9 is a result of applying the random string of
production rules $p_{1}p_{2}p_{3}^{2}p_{4}$ in $G_{s}$. The random string of
production rules corresponding to the plot in Figure 10 is
$p_{1}p_{5}p_{6}p_{3}^{2}p_{4}p_{2}p_{3}^{2}p_{4}$.

##  6 Conclusion

We have modified some of the variants of edge and node controlled embedding
graph grammars proposed in [3, 4] to facilitate the generation of directed
graphs. A randomly generated graph plot could serve as the basis for the
design of a level of a game. This would help the designer in their effort to
develop original and authentic puzzle structures that are solvable. The new
approach would enable a game to offer players with a countably infinite number
of puzzles, thereby extending the amount of time players would stay playing
the game. It would be interesting to actually implement these game plots to
design a game. It also remains to be seen whether an algorithm can be
developed to assess a players skills and accordingly generate a random game
plot with a suitable difficulty level. The graph grammar variant mentioned in
section 4 is specifically meant for generating platform games [7] which
involve vertical and horizontal navigation of objects with obstacles in
between. Further the possibility of the application of these grammars in
creating platform game plots with lock and key elements remains to be
investigated.

## Declarations

  * •

Funding: No funding was received for conducting this study.

  * •

Competing interests: The authors has no conflicts of interest to declare that
are relevant to the content of this article.

  * •

Ethics approval: Not applicable

  * •

Availability of data and materials: Not applicable

  * •

Code availability: Not applicable

  * •

Authors’ contributions: Both authors contributed to the study conception and
design. The first draft of the manuscript was written by Jayakrishna
Vijayakumar and both authors commented on previous versions of the manuscript.
Both authors read and approved the final manuscript.

## References

  *   * Ashmore and Nitsche [2007] Ashmore, C., Nitsche, M.: The quest in a generated world. In: Baba, A. (ed.) Proceedings of the 2007 DiGRA International Conference: Situated Play, DiGRA 2007, Tokyo, Japan, September 24-28, 2007. Digital Games Research Association, (2007). http://www.digra.org/wp-content/uploads/digital-library/07311.20228.pdf
  * Parish and Müller [2001] Parish, Y.I., Müller, P.: Procedural modeling of cities. In: Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques, pp. 301–308 (2001)
  * Jayakrishna et al. [2022] Jayakrishna, V., Mathew, L., Mathew, J.: On jumping graph grammars. In: International Conference on Mathematics of Intelligent Computing and Data Science (2022)
  * Vijayakumar et al. [2023] Vijayakumar, J., Mathew, L., Nagar, A.K.: A new class of graph grammars and modelling of certain biological structures. Symmetry 15(2), 349 (2023) https://doi.org/%****␣sn-article.bbl␣Line␣100␣****10.3390/sym15020349
  * Hendrikx et al. [2013] Hendrikx, M., Meijer, S., Van Der Velden, J., Iosup, A.: Procedural content generation for games: A survey. ACM Transactions on Multimedia Computing, Communications, and Applications (TOMM) 9(1), 1–22 (2013)
  * Rouse III [2004] Rouse III, R.: Game Design: Theory and Practice: Theory and Practice. Jones & Bartlett Learning, (2004)
  * Adams [2014] Adams, E.: Fundamentals of Game Design. Pearson Education, (2014)
  * Dormans [2010] Dormans, J.: Adventures in level design: generating missions and spaces for action adventure games. In: Proceedings of the 2010 Workshop on Procedural Content Generation in Games, pp. 1–8 (2010)
  * Dormans and Bakkes [2011] Dormans, J., Bakkes, S.: Generating missions and spaces for adaptable play experiences. IEEE Transactions on Computational Intelligence and AI in Games 3(3), 216–228 (2011)
  * Hopcroft and Ullman [1979] Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley, (1979)
  * Lindenmayer [1968] Lindenmayer, A.: Mathematical models for cellular interactions in development ii. simple and branching filaments with two-sided inputs. Journal of Theoretical Biology 18(3), 300–315 (1968)
  * Rozenberg [1997a] Rozenberg, G.: Handbook of Graph Grammars and Computing by Graph Transformation vol. 1. World scientific, (1997)
  * Rozenberg [1997b] Rozenberg, G.: Node replacement graph grammars. In: Engelfriet, J., Rozenberg, G. (eds.) Handbook of Graph Grammars and Computing by Graph Transformation, pp. 1–94. World Scientific, (1997). Chap. 1
  * Habel and Kreowski [1986] Habel, A., Kreowski, H.: May we introduce to you: Hyperedge replacement. Springer, Graph Grammars and Their Application to Computer Science. Graph Grammars 1986. Lecture Notes in Computer Science, Volume 291, 15–26 (1986)
  * Ehrig [1978] Ehrig, H.: Introduction to the algebraic theory of graph grammars (a survey). In: Claus, V., Ehrig, H., Rozenberg, G. (eds.) Graph-Grammars and Their Application to Computer Science and Biology, International Workshop, Bad Honnef, October 30 - November 3, 1978. Lecture Notes in Computer Science, Vol 1073, pp. 1–69. Springer, (1978)
  * Ehrig [1986] Ehrig, H.: Tutorial introduction to the algebraic approach of graph grammars. In: Ehrig, H., Nagl, M., Rosenfeld, A., Rozenberg, G. (eds.) Graph Grammars and Their Application to Computer Science. Graph Grammars 1986. Lecture Notes in Computer Science, Vol 291, pp. 3–14. Springer, (1986)
  * Kukluk et al. [2007] Kukluk, J.P., You, C.H., Holder, L.B., Cook, D.J.: Learning node replacement graph grammars in metabolic pathways. In: BIOCOMP, pp. 44–50 (2007)
  * Durrheim [2022] Durrheim, M.S.: Puzzle generation for action-adventure games using graph grammars. dissertation, University of the Witwatersrand, Johannesburg, Faculty of Science, University of the Witwatersrand, Johannesburg, (March 2022)