<i>NC-ENCE</i> Graph Grammars: Properties and Application to Game Design

Graph grammars form an interesting area of research due to 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. In the study of automata and grammars, closure properties of the associated languages have been studied extensively. In particular, closure properties of various types of graph grammars have been examined in (Rozenberg and Welzl, Inf. and Control, 1986) and (Rozenberg and Welzl, Acta Informatica, 1986). In this paper, we modify the structure of NC-ENCE graph grammars with the aim of generating directed graphs. We then examine some critical closure properties of the NC-ENCE graph grammars discussed in (Jayakrishna and Mathew, Symmetry 2023) and (Jayakrishna and Mathew, Springer Nature 2025). On the other hand 2D game design using an algorithmic approach known as procedural content generation has been of interest recently. 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.