3 Generative Design Grammars

A generative design grammar is a set of rules that describe a design style. In this book we show how such a grammar can be developed to design places in 3D virtual worlds. By encoding the design style as a grammar, the rules can be executed to generate many different individual designs sharing the style, in contrast to the current practice of handcrafting each individual design. This chapter presents a framework that provides organizing principles for developing a grammar that addresses the essential considerations in designing places in virtual worlds. The framework specifies the general structure of the design grammar and its basic components: the design rules. Designers can develop their own grammars for designing places in virtual worlds by using our framework to develop rules that describe their own design style. The design and development of specific places in 3D virtual worlds are then realized through the application of the grammar at first to generate the initial design, and next to adapt the design during real-time interactions in virtual worlds, as described in the next chapter.

3.1 Grammars for Rule-based Design

Our concept and development of generative design grammars are inspired by the notion of shape grammars (Stiny, 2008, Stiny & Gips, 1972) – a classic example of how a grammar can capture the style of a design and be used to generate multiple designs within that style. The inspiration comes directly from shape grammars’ suitability as a sound formalism for describing and generating designs in general. Over the last three decades, the theories and applications of shape grammars have been refined and tested in a wide range of design disciplines; for example, paintings and visual arts (Knight, 1994a), architectural design (Stiny & Mitchell, 1978; Duarte, 2005; Eloy & Duarte, 2011), product (furniture) design (Knight, 1994a), engineering design (Shea & Cagan, 1997), and design computing (Gu & Maher, 2003).

3.1.1 Notions of Shape Grammars

Knight (2000) summarizes that a shape grammar is a set of shape rules that can be applied in a step-by-step manner to generate a set or language of designs. A shape grammar is both descriptive and generative. The application of the shape rules generates designs, and the rules themselves are the descriptions of the forms of the generated designs. In general, applications of shape grammars have two main purposes. On one hand, shape grammars can be used as design tools to generate vast varieties of design languages. On the other hand, shape grammars as design analysis tools can be used both to analyze existing designs in order to better understand these designs, and to generate shape rules that produce these designs and other similar designs.

Stiny (1980) defines four basic components of a shape grammar:

• –    S: a finite set of shapes.
• –    L: a finite set of symbols.
• –    R: a finite set of shape rules.
• –    I: initial shape.

Each shape rule follows the form of S_a → S_b. S_a and S_b are two different labeled shapes.

Shape grammar theories have developed over the years to include many extensions, such as parametric grammars (Tapia, 1992), color grammars (Knight, 1994b), description grammars (Stiny, 1981), structure grammars (Carlson et al, 1991), parallel grammars (Knight, 1999), and so on, to address different aspects of design.

3.1.2 Shape Grammars and Design Style

Shape grammars are able to apply simple shape rules to produce designs with rich descriptions. Shape grammars enable different designs that share a similar style to emerge by alternating the sequence of shape rule application. By analyzing existing designs of a specific style, shape grammars can formally describe this style and generate other designs that also share the style. Further, by incorporating additional devices, shape grammars are able to describe and generate new design languages in an extension to the original languages.

To develop a shape grammar to describe and generate a specific style involves the following steps (Knight 1994a):

• –    To define a vocabulary of shapes and a set of spatial relations that are common to the design instances of the style.
• –    To define shape rules that fix the occurrences of the spatial relations.
• –    To provide an initial shape to start the design process.

Following the above steps, a shape grammar can be developed to produce a specific design language. Further, through transformations using rule addition, rule deletion or rule change, this shape grammar can be transformed into a new shape grammar. In this way, a new design language emerges.

3.1.3 Design Constraints in Shape Grammar Application

One critical issue in the application of shape grammars for design is to develop a grammar that produces designs that meet the design goals or constraints. According to Knight (1999), there are two different approaches to achieve that objective. The first approach is to incorporate the constraints into the shape rules so that the generated designs meet the given goals. Knight (1998a) defines different types of shape grammars ranging from unrestricted, standard shape grammars with the least predictable outcomes, to simple, restricted ones with the most predictable outcomes. Producing a shape grammar with more predictable outcomes requires knowledge about constraints and goals while developing the shape grammar. Alternatively, an unconstrained shape grammar generates designs, after which a person or automated process evaluates the designs and selects the ones that meet the specific goals and satisfy the given constraints.

3.2 Generative Design Grammars for Rule-based Place Design in 3D Virtual Worlds

The design and implementation of a generative design grammar is the development of a generative design system – a computational approach for describing, generating and automating design in general. Besides design grammars, generative design systems have also been developed in other forms such as genetic algorithms (Holland, 1992; Ding & Gero, 2001), cellular automata (von Neumann, 1951; Wolfram, 2002) and swarm intelligence (Deneubourg, 1977; Payman, 2004). However, the nature of designing places in 3D virtual worlds as compositions of virtual world objects has made grammars an ideal design formalism for 3D virtual worlds.

We describe generative design grammars for virtual world designs by making a direct comparison to shape grammars for design in general. A shape grammar is a set of shape rules, which can be applied in a step-by-step manner to generate a set or language of designs (Knight, 2000). The nature of shape grammars is both descriptive and generative:

• –    Shapes as the basic components of shape rules, which can be in the form of points, lines, planes, volumes or any combination of the above, are elements of the designs that a shape grammar generate.
• –    Rules as the basic mechanisms for generating designs via shape operations and spatial transformations.

Similarly, a generative design grammar is a set of design rules that can be applied in a step-by-step manner to generate a set or language of place designs specifically for places in 3D virtual worlds. Inheriting the descriptive and generative nature of shape grammars:

• –    A generative design grammar describes place designs in 3D virtual worlds where the basic components of its design rules are virtual world objects.
• –    Place designs in 3D virtual worlds are generated by operations and transformations on virtual world objects that result in compositions that make sense in a virtual world.

These descriptive and generative qualities of design grammars serve the purposes of rule-based place design in 3D virtual worlds by formally specifying the components and processes relevant to designing in virtual worlds.

3.2.1 A Place Design in 3D Virtual Worlds as “Objects in Relations”

A design generated by a shape grammar is viewed as “elements in relations” (Stiny, 1999; 1990). To apply a shape grammar for design generation is basically to identify the “elements” of design, and define and alter (add, subtract or replace) the “relations” among the “elements” via shape rule applications. In this manner, shape grammars can generate complex designs based on simple design elements. This view of design is consistent with the object-oriented nature of virtual worlds. A place design in 3D virtual worlds can be viewed as “objects in relations”.

3D virtual worlds are typical object-oriented systems. Examples of commercial platforms for 3D virtual worlds where the basic components for design and building are 3D objects include the majority of platforms such as Active Worlds, Second Life, and There¹. In these virtual worlds, a design is constructed through the placement and configuration of virtual world objects. Depending on the object definition and classification of the virtual world, an object in a 3D virtual world may refer to a whole virtual place – a “container” object; for example, a virtual gallery or a virtual meeting room. A virtual world object may also refer to a component or an entity in a virtual place, or form a part of the place; for example, a digital picture in a virtual gallery or a wall of the virtual meeting room. Each virtual world object can have an appearance of a 3D geometric model in the virtual world, and together these models provide the visualization of the ambient environment. The virtual world objects then can be configured via scripts or codes to have certain behaviors that enable people to interact with the place and with each other. Therefore, a place design in 3D virtual worlds essentially comprises various virtual world objects that visually and functionally support intended human activities (Gu & Maher, 2003):

• –    Visually/spatially, via the use of the place metaphor, the 3D models are composed to form an ambient environment where people can inhabit and the intended activities can take place online.
• –    Functionally, selected virtual world objects are ascribed with behaviors accordingly to support the intended activities online. Therefore, people’s interactions with the virtual world and among each other become possible.

Similar to the way shape grammars describe and generate designs in general, when designing places in 3D virtual worlds, generative design grammars describe virtual places in terms of virtual world objects and their relations, in the forms of design rules. The rules are applied to generate place designs in 3D virtual worlds in terms of the compositions of virtual world objects. This compositional characteristic of design generation makes generative design grammars an ideal design formalism for place design in 3D virtual worlds.

3.2.2 Design Phases of 3D Virtual Worlds

The view of virtual worlds as functional places that support an extended range of activities online provides a common ground for designing virtual worlds. This common ground highlights two key issues: activities and metaphor. Firstly, virtual worlds exist for certain purposes supporting various professional or social activities. Secondly, virtual world designs apply the metaphor of place. Based on this understanding, designing virtual worlds can be divided into the following four phases:

• –    Layout: the layout of the virtual place defines how areas are related to each other spatially in a way that defines and accommodates specific categories of intended activities in the 3D virtual world.
• –    Objects: each place is then configured with a number of specific virtual world objects, such as walls and floors that provide visual boundaries of the different areas in the place and more generally, objects such as the information desk or paintings that provide visual cues for supporting the intended activities.
• –    Navigation: navigation in virtual worlds can be facilitated with way finding aids and hyperlinks for assisting the users’ movements from one place to another.
• –    Interactions: this part of the design process ascribes certain scripted behaviors to selected virtual world objects so that the users can interact with the objects and with each other by triggering those behaviors.

Through these four design phases, places can be generated in 3D virtual worlds in terms of visualization design (place layout and object design), navigation design and interaction design. These are the four inseparable design phases to provide an integral structure of a virtual place. Due to the use of the place metaphor, some design characterizations of the generated virtual places can find similarities to places in the physical world, for example, different layouts of virtual places and different forms of virtual world objects. However, virtual world designs also have many characteristics that are different from their physical counterparts, especially in terms of navigation and interaction. After all, virtual worlds are networked environments that do not need to be strictly constrained by the metaphor. Designing virtual worlds can go beyond the principles of place design in the physical world.

3.2.3 Addressing Design Requirements of 3D Virtual Worlds

Generative design grammars are able to address both visual/spatial requirements as well as non-visual/spatial requirements for designing places in 3D virtual worlds. Virtual world objects are visualized using 3D models. Because of the use of the place metaphor, these 3D models often depict place or place-like forms. The design requirements that are related to the visual/spatial aspect of virtual worlds are analogous to those of architectural design. There are many successful shape grammar examples of places and designs in the physical world; for example, the Palladian grammar (Stiny & Mitchell, 1978), the Mughul Gardens grammar (Stiny & Mitchell, 1980), the Prairie Houses grammar (Koning & Eizenberg, 1981) and the Siza Houses grammar (Duarte, 1999) that have been developed to generate and/or analyze different architectural examples. Inheriting the capabilities of design description and design generation from shape grammars, generative design grammars are capable of addressing similar kinds of visual/spatial requirements in designing places for 3D virtual worlds.

The design requirements that are related to the functional aspect of virtual worlds are often non-visual/spatial requirements. They are about ascribing scripted behaviors to selected virtual world objects to support the intended activities. For example, a simple behavior might be to display a digital image in a virtual gallery when a virtual canvas is “touched” by a visitor. Unlike physical artifacts, the visualization of a virtual world object and the behaviors of the object in the virtual world are artificially ascribed and associated rather than causally or physically related. The coupling of the two can be determined purely based on the designer’s preferences, although they often make a reference to the adopted place metaphor to maintain a sense of design consistency. Similar kinds of functional problems have been addressed using shape grammars in design. Although shape grammars are spatial, Stiny (1981) demonstrates the use of description functions to address the composition of designs in other terms that are non-spatial; for example, those related to the functions, purposes, uses and meanings of the designs. Knight (1999) further suggests the linkage of an original shape grammar with a parallel description grammar to generate designs (in terms of the composition of shapes) and other non-spatial descriptions in parallel. More recent developments such as discursive grammar (Duarte, 2005) and transformation grammar (Eloy & Duarte, 2011) also aim to address the semantic and syntactic issues in design. Similarly, generative design grammars are more than visual/spatial grammars. We formalize the relevant non-visual/spatial considerations of place design for virtual worlds in our framework by grouping the rules into four different categories to be applied in the four design phases of 3D virtual worlds accordingly, in order to explicitly address both visual/spatial considerations as well as non-visual/spatial considerations.

3.2.4 Capturing Stylistic Characterizations of Virtual Places

A specific style is exemplified when several designs “each create a similar impression” (Stiny & Mitchell, 1978). As discussed above, place design in 3D virtual worlds can be considered in terms of visualization design (place layout and object design), navigation design and interaction design. The results of these four design phases provide an integral set of stylistic characterizations for distinguishing places in 3D virtual worlds. Compared to many novice designs, virtual worlds designed with a specific style in mind will achieve better consistency, making it easier for users to get oriented and interact in the virtual world.

A shape grammar is capable of generating design instances that belong to an existing language of design as well as defining a new language of design. One might not instantly recognize the new design styles defined by shape grammars like the kindergarten grammar (Stiny, 1980); however, the applications of shape grammars have provided examples that analyze many well-known styles of painting, furniture design and architectural design, as well as generate design instances from these well-known styles, or even extend the styles. March and Stiny (1985) use “syntax” and “semantics” as the two major factors to distinguish designs from one another. “Syntax” determines how the shapes are composed to represent the designs. “Semantics” describe the designs in terms of functions, purposes, uses or meanings other than shapes. Design styles that are described and generated using shape grammars are considered primarily in terms of these two factors. The studies of shape grammars address these two factors through the original shape grammar formalism and the use of description functions (Stiny, 1981).

In summary, generative design grammars describe and generate languages of design that capture specific stylistic characterizations. A generative design grammar has different categories of design rules and the rules are applied at different stages to address both visual/spatial and non-visual/spatial considerations. The design rules that address visual/spatial problems are syntactic rules, and the design rules that address non-visual/spatial problems are semantic rules. We describe categories of design rules to specify place design in 3D virtual worlds in terms of syntax or visualization: place layout and object design, and semantics: navigation and interaction.

3.3 Generative Design Grammar Framework

Our generative design grammar framework provides guidelines and strategies for developing generative design grammars. The framework outlines the general structure of a generative design grammar and the general structure of its basic components: design rules. Following the structures suggested in the framework and integrating with different design and domain knowledge, designers will be able to develop their own design grammars for designing places in 3D virtual worlds.

A generative design grammar G is comprised of design rules R, an initial design D_i, and a final state of the design D_f.

G = {R, Di, Df}

(3.1)

The basic components of a generative design grammar are design rules R. The general structure of our grammar for virtual place design comprises four sets of design rules: layout rules R_a, object design rules R_b, navigation rules R_c, and interaction rules R_d.

R = {Ra, Rb, Rc, Rd}

(3.2)

This general structure is determined by four design phases of place design in virtual worlds:

• –    To develop the layout of the place in the virtual world where each sub-area of the place has a purpose that accommodates certain intended activities online.
• –    To configure the virtual place with designed virtual world objects that provide visual boundaries of the place and visual cues for supporting the intended activities.
• –    To specify navigation methods that use way finding aids and hyperlinks for assisting the movements of the users’ avatars between different places in 3D virtual worlds.
• –    To design and activate interactions by ascribing scripted behaviors to selected virtual world objects in the virtual place so that people can interact with the virtual world and with each other.

The four set of design rules: layout rules, object design rules, navigation rules and interaction rules directly correspond to the above four design phases of virtual worlds. The generative design grammar framework is illustrated in Figure 3.1. The sequence of applying the design rules follows the order of layout rules, object design rules, navigation rules and finally interaction rules.

Different generative design grammars can be developed by following this general structure to design places for 3D virtual worlds when defining specific rules that encode the design and domain knowledge for different styles and purposes. The stylistic characterizations of virtual world designs, in terms of the syntax and the semantics, are defined accordingly in these four sets of design rules.

3.4 General Structure of Design Rules

The basic components of a generative design grammar are design rules. The general structure of design rules is similar to the general structure of shape rules. In shape grammars, a shape rule can be defined as:

LHS → RHS

(3.3)

which specifies that when the left-hand-side shape (LHS) is recognized in the design, it will be replaced by the right-hand-side shape (RHS). The replacement of shapes is usually applied under a set of shape operations or spatial transformations. The shapes are labelled (the use of spatial labels and state labels) for controlling the shape rule applications.

Similar to formula 3.3, a design rule of a generative design grammar is defined as:

LHO + sL → RHO

(3.4)

which specifies that when the left-hand-side object (LHO) is recognized in the 3D virtual world, and the state labels sL are matched, the LHO will be replaced by the right-hand-side object (RHO). The term “object” used here can refer to a virtual world object, a set of virtual world objects or virtual world object properties.

The general structure of design rules implies the following two aspects:

• –    State labels are singled out and expressed explicitly as sL in the rule structure. The use of state labels is essential to the application of generative design grammars as they direct the application to ensure that the generated virtual world design satisfies the given design requirements. Each design rule is associated with certain state labels representing specific design contexts. In order for a design rule to be applied, a virtual world object, a set of virtual world objects or virtual world object properties need to be recognized in the 3D virtual world that match the LHO of the design rule, and the design context as represented by the sL of the design rule needs to be relevant to the current design needs, as interpreted by the designers or computational agents.
• –    The basic components of design rules are virtual world objects and their properties, not shapes. Therefore, they are not entirely visual/spatial. As a result, for the interaction rules and parts of the navigation rules, the replacement of LHO with RHO may not change the way an object looks or is placed, but may add scripted behaviors to an existing object.

3.4.1 Layout Rules

Layout rules are the first set of design rules to be applied in the application of a generative design grammar. They are visual/spatial rules that generate the layout of the place according to the kinds of intended activities to be supported in the 3D virtual world. The use of divided virtual areas for different activities provides a way of organizing and allocating activities in the 3D virtual world, and creates a sense of movement for people when changing from one activity to another. Because of the use of the place metaphor, layout problems in 3D virtual worlds can have similar solutions to the ones in the physical world. However, designers have more freedom in making design decisions since virtual worlds do not have to obey physical constraints. In virtual worlds, many layout-related issues, for example, adjacency, do not need to strictly follow their physical counterparts because virtual places can also be hyper-linked.

Figure 3.2 illustrates an example layout rule taken from a generative design grammar for virtual gallery design. In this design rule, the LHO of the design rule is a reception area of the virtual gallery. The rule shows that after it is applied the LHO will be replaced by the RHO: the same reception area with a gallery area added spatially adjacent to the reception.

Symbol represents a reception area of the virtual gallery. Symbol represents a gallery area in the virtual gallery for displaying exhibitions. State label sL=1 indicates that layout rules will always be the first category of design rules to be applied in a generative design grammar. The meaning of state label sL=g1 is to generate a gallery area in the 3D virtual world according to certain specifications (g1). In order for this design rule to be applied the following two conditions need to be met:

• –    A reception area is recognized in the 3D virtual world.
• –    The design contexts represented by sL=g1 (to generate a gallery area in the 3D virtual world according to certain specifications) are related to the current design needs (such as a given design brief or emerging design requirements like the sudden increase of galley visitors), as interpreted by the designers or computational agents.

3.4.2 Object Design Rules

Object design rules are applied after layout rules, they are also visual/spatial rules. After a layout of the virtual place is produced, object design rules further configure the place to provide visual boundaries of the place and visual cues for supporting the intended activities through virtual world object design and placement. Because of the use of the place metaphor, the development of object design rules can also refer to many principles and examples in built environments. Depending on the designers’ preferences, they may choose to simulate a place from the physical world, or to experiment with other alternatives since virtual worlds are in fact free from any physical constraints. However, 3D virtual worlds designed with a consistent use of forms, colors and other visual/spatial elements are arguably more effective in assisting users’ orientation and interaction.

Figure 3.3 shows an example object design rule that generates the visual boundaries for a gallery area in the virtual gallery, and Figure 3.4 shows an example object design rule that arranges the interior of the gallery area with virtual canvas objects for displaying digital images.

In Figure 3.3, state label sL=2 indicates that object design rules will be the second category of design rules to be applied in a generative design grammar, after the layout rules. State label sL=cC means to apply a cold-color scheme (cC) for the interior of the generated virtual place. In order for this object design rule to be applied, the following two conditions need to be met:

• –    The layout generated for the virtual gallery contains a gallery area.
• –    The design contexts represented by sL=cC (to apply a cold-color scheme for the generated virtual place) are related to the current design needs (in terms of design preferences), as interpreted by the designers or computational agents.

In Figure 3.4, state label sL=gIM1 means to arrange a gallery area for displaying digital images using certain configuration settings (gIM1). The application of this object design rule also requires two conditions:

• –    The visual boundaries of a gallery area have been defined in the virtual gallery.
• –    The design contexts represented by sL=gIM1 (to arrange the gallery area for displaying digital images using certain configuration settings) are related to the current design needs (in terms of the exhibition requirements such as the type and quantity of virtual exhibition items), as interpreted by the designers or computational agents.

3.4.3 Navigation Rules

Navigation rules are applied next in a generative design grammar, after layout rules and object design rules. Navigation rules provide way finding aids and hyperlinks in the generated virtual place to assist users’ navigation. Way finding aids in virtual worlds have been studied with direct references to those in built environments (Vinson, 1999; Darken & Sibert, 1996; 1993). There are at least two types of way finding aids that can be integrated into virtual worlds from the built environments:

• –    The use of spatial elements; for example, paths, openings, hallways, stairs, intersections, landmarks, maps, signs and so on.
• –    The use of social elements; for example, the assistance gained from designated guides (i.e. a conversational bot) or other virtual world users.

Besides these way-finding aids originating from built environments, virtual worlds also have their own unique forms of navigation since virtual places can be hyper-linked. Most virtual worlds allow users’ avatars to move directly between any two locations using hyperlinks. The origin of hyperlinks used in virtual worlds can be traced back to the navigation in hypertext systems such as in a web page (Dourish, 1999, Ruddle et al, 1997). Current commercial virtual worlds such as Active Worlds, Second Life and other game engines all support different forms of hyperlinks for connecting virtual places.

Navigation rules are not entirely visual/spatial. The application of these rules involves virtual world object design and placement for defining way-finding aids and hyperlinks in the generated place, which is related to the visual/spatial aspect of designing places in 3D virtual worlds. However, before these object design and placement are conducted, navigation rules are mainly about recognizing the connectivity within the generated place and with other places as well as finding appropriate navigation methods for users to access these places.

Figure 3.5 is an example navigation rule. The LHO of this rule shows that two gallery areas are generated for the virtual gallery, separated without direct access to each other. The RHO of this rule shows that a pair of hyperlinks is created inside these two gallery areas, which allows visitors to travel freely between the two areas. State label sL=3 indicates that navigation rules are the third set of rules to be applied in a generative design grammar, after layout rules and object placement rules.

Figure 3.6 shows the effect of this navigation rule as illustrated in Figure 3.5. The left-hand-side image captures the interior of one of the gallery areas. The right-hand-side image shows that a hyperlink portal is created. In this particular case, the hyperlink portal appears as a color stone on the floor. After appropriate scripted behaviors are ascribed, the portal will take the visitor directly to the other gallery area when it is “stepped” on by the visitors’ avatars.

3.4.4 Interaction Rules

Interaction rules are the final set of design rules to be applied in a generative design grammar. The application of interaction rules ascribes scripted behaviors to selected virtual world objects in the generated place. People can interact with the virtual place and with each other by triggering these behaviors.

Interactions in virtual worlds in general are not well developed. There are examples that derive from various actions in computer games. There are also more advanced attempts; for example, the integration of artificial intelligence. The interaction rules of generative design grammars do not intend to develop new interactions for 3D virtual worlds. The types of interactions generated by these rules will be mainly supplied by the existing virtual world design platforms realized in the forms of different scripted behaviors for virtual world objects. However, by developing the interaction rules, the conventions of triggering these behaviors in virtual worlds can be defined and categorized, for designers to use selectively for different purposes.

Interaction rules are non-visual/spatial rules that recognize selected virtual world objects in the 3D virtual world and ascribe appropriate behaviors to these objects. There can be at least two different types of interaction rules. One supplements object design rules and the other supplements navigation rules. Object design rules define visual boundaries for the generated place as well as design and place purposeful virtual worlds objects in the generated place. The first type of the interaction rule ascribes scripted behaviors to relevant virtual world objects in order to support the intended activities in the generated virtual place. The other type of interaction rule looks for way finding aids and hyperlinks generated by navigation rules and ascribe scripted behaviors to activate them.

Because interaction rules do not operate on a visual/spatial level, they are not appropriate to be expressed using illustrations. Examples of interactions rules are provided in Chapter 5 of this book. They are expressed in the form of “IF… THEN…”, taken from a generative design grammar developed for virtual gallery design. Without getting into the technical details of ascribing behaviors to virtual world objects through scripting, Figure 3.7 shows the effect of an example interaction rule of the first type for supplementing object design rules. The left-hand-side image is the exterior of a virtual building with an empty virtual advertisement board. The right-hand-side image shows the same advertisement board displaying an animation, after the interaction rule is applied, which configures the properties of the virtual advertisement board object using a scripting language to enable the animation to be shown.

3.5 Characteristics of Generative Design Grammars

Generative design grammars adopt the descriptive and generative nature of shape grammars, but modify some of the original shape grammar properties to suit the purpose of designing places in 3D virtual worlds. As design formalisms, they have similarities as well as differences. The characteristics of generative design grammars can be highlighted based on a comparison to shape grammars in general. The comparison is drawn in terms of the following three aspects: grammar components, meeting design requirements, and computation.

Grammar components: in shape grammars, a set of shape rules, an initial shape and a final state constitute a shape grammar (Knight, 1994a). Shape rules are applied recursively in a step-by-step manner to generate designs. Spatial and state labels are used to control the application of shape rules.

• –    In generative design grammars, similarly, a grammar comprises design rules, an initial design and a final state of the design. More specifically, a generative design grammar has four sets of design rules: layout rules, object design rules, navigation rules and interaction rules. They can be categorized as syntactic and semantic rules. Each set of the design rules corresponds to a phase of place design in 3D virtual worlds.
• –    Generative design grammars also use spatial labels and state labels to control the application of design rules. The original use of state labels in a shape grammar is to control the sequence of shape rule applications. In our generative design grammar, this original purpose is maintained so that the design rules can be applied in the sequence of layout rules, object design rules, navigation rules and interaction rules. In addition, a special set of state labels are developed to represent a set of design contexts that relate the current design needs to the application of a design rule. Using these special state labels, the application of the generative design grammar is also able to adapt an existing design to the changing needs of the user inhabiting the virtual place.

Meeting design requirements: as discussed earlier, Knight (1999) points out that there are generally two different ways to connect shape grammars with design goals. The first approach is to integrate the constraints into the shape rules so that the generated designs will meet the given design requirements. The key process here is to add constraints to the original, unrestricted shape grammars to increase the predictability of the designs they generate. The second approach is to develop the original, unrestricted shape grammars and enable the grammar application to be executed without constraints but apply a manual or automated search and test strategy to the generated designs in the end to select the designs that satisfy the given design requirements.

• –    Generative design grammars are restricted. They are similar to set grammars (Stiny, 1982). Set grammars are restricted kinds of shape grammars. According to Knight (1998b), the main difference between set grammars and the original shape grammars is the way designs are decomposed. In a set grammar, each generated design can only be viewed and decomposed in one definite way. In an original shape grammar, each generate design can be viewed and decomposed in unlimited ways. This liberty of the original shape grammars on one hand supports two very important aspects of shape grammars’ generative power: emergence and ambiguity. On the other hand, it also makes it very difficult to predict the behaviors and design outcomes of grammar applications. Similar to designs generated by set grammars, a place in 3D virtual world designed and composed using generative design grammars can be decomposed uniquely into a set of purposeful virtual world objects and their properties. The application of a generative design grammar also needs to be controllable and predictable to a certain extent so that the generated places can be useful in supporting the intended activities, since virtual worlds in the context of this book are essentially functional networked places. The purpose of generating virtual world designs that meet current design needs is given higher priority than supporting emergence and ambiguity in design. However, the level of control should certainly be flexible and adjustable to support different design purposes and tasks.
• –    As discussed earlier, to direct the application of a generative design grammar relies on the use of a special set of state labels. Each design rule in a generative design grammar is associated with at least one of these state labels, which represent a specific design context of designing places in 3D virtual worlds. In order for a design rule to be applied, the LHO of the design rule needs to be matched in the virtual world, and the design context represented by the state label of the rule also needs to match the current design needs. In this manner, the application of the generative design grammar is directed to generate virtual world designs that meet the given design requirements.
• –    Generative design grammar applications can be carried out manually by designers or be automated by computational agents, during real-time interactions in a 3D virtual world. The generated places can be implemented and put into use immediately. These require each generated design to meet the current design needs, and to be implemented with efficiency in order to keep up with the fast pace of real-time interactions in the 3D virtual world. The search and test approach is impractical in this respect, and therefore was not considered further in the context of this book.

Computation: in the initial studies of shape grammars, the design generation is performed by hand. To manually perform the step-by-step application and examine and present different generated design instances, is very time-consuming. Automating this process has many advantages. According to Gips (1999), the automation of shape grammars has at least four different purposes. The most common purpose is to assist the generation of designs from a shape grammar. The other three purposes are to analyze if a given design belongs to the language generated by a certain grammar, to generate a shape grammar based on a corpus of given designs, and to assist designers in designing shape grammars. Gips further points out that the challenge in the automation of shape grammars lies in the tension between the spatial nature of shape grammars and the symbolic nature of the underlying computer representations and processing. In order to implement shape grammars as a computational process or system, it requires a different kind of thinking and representation (Stiny, 2008). Although generative design grammars can be either applied manually by designers or automated by computational agents, they are intended for computer implementations.

In summary, following the above framework, generative design grammars can be developed for designing specific places in 3D virtual worlds. The application of a generative design grammar begins when the current design needs are identified and the initial design D_i is recognized in the 3D virtual world. The appropriate design rules are subsequently selected and applied. The application is terminated when there are no matching rules and the final state of the place design D_i is then generated for the 3D virtual world. Different generative design grammars are able to generate places in 3D virtual worlds with different stylistic characterizations. Different designers and users may adopt them to reflect their own styles and identities in virtual worlds.

References

Carlson C., McKelvey R. and Woodbury R. (1991), An Introduction to Structures and Structure Grammars, Environment and Planning B: Planning and Design, 18, pp. 417-426.

Darken, R.P. and Sibert J.L. (1996), Way Finding Strategies and Behaviours in Large Virtual Worlds, Proceedings of ACM SIGCHI’96, ACM, New York, pp. 142-149.

Darken, R.P. and Sibert, J.L. (1993), A Toolset for Navigation in Virtual Environments, Proceedings of the 6^th Annual ACM Symposium on User Interface Software and Technology, Atlanta, pp 157-165.

Deneubourg, J.L. (1977), Application de l’ordre par fluctuations a la description de certaines etapes de la construction du nid chez les termites, Insect Soc, 24, pp. 117-130.

Ding, L. and Gero, J.S. (2001), The Emergence of the Representation of Style in Design, Environment and Planning B: Planning and Design, 28(5), pp. 707-731.

Dourish, P. (1999), Following Where the Footprints Lead: Tracking Down New Roles for Social Navigation, in A. J. Munro, K. Hook, and B. D. Benyon (eds), Social Navigation of Information Space, Springer, London, pp. 15-34.

Duarte, J. (1999), Democratized Architecture: Grammars and Computers for Siza’s Mass Housing, Proceedings of the International Conference on Enhancement and Promotion of Computational Methods in Engineering and Science, Elsevier Press, Macau, China.

Duarte, J. (2005), A Discursive Grammar for Customizing Mass Housing: the Case of Siza’s Houses at Malagueira, Automation in Construction, 14(2), pp. 265-275.

Eloy, S and Duarte, J. (2011), Transformation Grammar for Housing Rehabilitation, Nexus Network Journal, 13(1), pp. 49-71.

Gips, J. (1999), Computer Implementation of Shape Grammars, NSF/MIT Workshop on Shape Computation, http://www.shapegrammar.org/implement.pdf

Gu, N. and Maher, M.L. (2003), A Grammar for the Dynamic Design of Virtual Architecture Using Rational Agents, International Journal of Architectural Computing, 4(1), pp. 489-501.

Holland, J. H. (1992), Adaptation in Natural and Artificial Systems, MIT Press, Cambridge, MA.

Knight, T.W. (2000), Shape Grammars in Education and Practice: History and Prospects, International Journal of Design Computing, 2 (online).

Knight, T.W. (1999), Applications in Architectural Design, and Education and Practice: Report for NSF/MIT Workshop on Shape Computation, NSF/MIT Workshop on Shape Computation, http://www.shapegrammar.org/education.pdf

Knight, T.W. (1998a), Designing a Shape Grammar, in J.S. Gero and F. Sudweeks (eds), Proceedings of Artificial Intelligence in Design ’98, Kluwer Academic Publishers, The Netherlands, pp. 499-516.

Knight, T.W. (1998b), Shape Grammars, Environment and Planning B: Planning and Design, Anniversary Issue, pp. 86-91.

Knight, T.W. (1994a), Transformations in Design: a Formal Approach to Stylistic Change and Innovation in the Visual Arts, Cambridge University Press, England.

Knight T.W. (1994b), Shape Grammars and Color Grammars in Design, Environment and Planning B: Planning and Design, 21, pp. 705-735.

Koning H. and Eizenberg J. (1981), The Language of the Prairie: Frank Lloyd Wright’s Prairie Houses, Environment and Planning B: Planning and Design, 8, pp. 295-323.

March, W.J. and Stiny, G. (1985), Spatial Systems in Architecture and Design: Some History and Logic, Environment and Planning B: Planning and Design, 12, pp. 31-53.

Payman, A. (2004), Swarm Intelligence, Jet Propulsion Laboratory, Pasadena, CA.

Ruddle, R.A., Payne, S.J., and Jones, D.M. (1997), Navigating Buildings in “Desk-top” Virtual Environments: Experimental Investigations Using Extended Navigational Experience, Journal of Experimental Psychology: Applied, 3(2), pp. 143-159.

Shea, K. and Cagan, J. (1996), Innovative Dome Design: Applying Geodesic Patterns with Shape Annealing, Artificial Intelligence for Engineering Design Analysis, and Manufacturing, 11(5), pp. 379-394.

Stiny, G. (2008). Shape: Talking about Seeing and Doing, MIT Press.

Stiny G. (1999), Commentary: Shape, Environment and Planning B: Planning and Design, 26, pp. 7-14.

Stiny G. (1990), What Is a Design?, Environment and Planning B: Planning and Design, 17, pp. 97-103.

Stiny G. (1982), Spatial Relations and Grammars, Environment and Planning B: Planning and Design, 9, pp. 113-114.

Stiny G. (1981), A Note on the Description of Designs, Environment and Planning B: Planning and Design, 8, pp. 257-267.

Stiny G. (1980), Introduction to Shape Grammars, Environment and Planning B: Planning and Design, 7, pp. 343-351.

Stiny G. and Gips J. (1972), Shape Grammars and the Generative Specification of Painting and Sculpture, in C.V. Freiman (ed), Proceedings of Information Processing 71, North Holland, Amsterdam, pp. 1460-1465.

Stiny, G. and Mitchell, W.J. (1980), The Grammar of Paradise: on the Generation of Mughul Gardens, Environment and Planning B: Planning and Design, 7, pp. 209-226.

Stiny, G. and Mitchell, W.J. (1978), The Palladian Grammar, Environment and Planning B: Planning and Design, 5, pp. 5-18.

Tapia M.A. (1992), Chinese Lattice Designs and Parametric Shape Grammars, The Visual Computer, 9, pp. 47-56.

Vinson, N.G. (1999), Design Guidelines for Landmarks to Support Navigation in Virtual Environments, Proceedings of CHI’99, Pittsburgh, pp. 278-285.

von Neumann, J. (1951), The General and Logical Theory of Automata, in L.A. Jeffress (ed.), Cerebral Mechanisms in Behavior - the Hixon Symposium, John Wiley, New York, NY, pp. 1-41.

Wolfram, S. (2002), A New Kind of Science, Wolfram Media, Champaign, IL.