Demo 4 - BSP Dungeon

The Dungeon Example. Other C++ source files omitted.

View the GIGL source file in the Git repo

Instructions:

• • As a demo, the first step is to try compiling and running the given project. For instructions and tips about demos please refer to [Here]. This demo needs OpenGL and SDL.

  • The C++ code are hard coded with two versions of dungeon generation setups, to switch between the versions, there are two group of code in "main.cpp" that are of concern, Line 139 - Line 140 and Line 172 - 173. Only one from each of the group of the three lines should be activated at any instant.

    • For generating regular dungeons (with no boss room), only activate Line 139 and Line 172.

    • For generating boss dungeons (each with exactly one boss room), only activate Line 140 and 173.

  • When running the demo, it will first ask for an integer as a random seed, then ask for an integer the size (side length of a square) of the dungeon, then the minimum size and maximum size (side length) of unit area (one-room area), finally the minimum distance (wall thickness) from the edge of a room to the edge of the area it is in. It then will open a window for rendering. The requirement for the input is that the max unit area size must be much bigger than the twice of the minimum unit area size (or more precisely, should be bigger than the twice of the sum of the minimum size plus the minimum wall thickness). Violating this requirement may result in unpredictable results.

  • The operations in the new rendering window (please click on that window to focus) include:

    • Pressing enter, which re-generates a new dungeon with the same setup, and the seed for the new one will be in the original command line window.

    • Moving the camera with key J (left), L (right), K (down), I (up), which is only effective when the generated dungeon is larger than the window.

  • The same random seed might not give the exactly same result across different environments (difference in C++ library for RNG). The results shown in the figure is done on a Windows machine with Visual Studio 2015, with the regular dungeons displayed be with random seeds 2244, 5216, 55108 respectively, and the boss dungeon displayed be with random seeds 55455, 89828, 17907 respectively, and all with the dungeon size be 400, the minimum and maximum unit area size be 50 and 200, and the minimum wall thickness be 5. In addition, the development of GIGL might also change some of the ordering of getting random numbers which might also affect the concrete results. Nevertheless, statistically, the results should be of the same distribution, as the semantics of the GIGL code does not change.

  • After the demo is working, you may want to try further reading the GIGL code and/or the notes below to get a better understanding of GIGL's syntax and semantics.

Comments/Notes:

• • The complexity of this example mainly comes from concrete details from the problem, such as making sure that the rooms and corridors are properly placed while still maintain maximum randomization possibilities. Particularly, guaranteeing corridors are actually connects valid room parts under the framework needs some ingenuity. All these parts are not using domain specific part of GIGL but are almost just C++ code. On one hand, it means that GIGL can collaborate with large non domain specific code well; on the other hand, it might also indicates some potential future direction for GIGL, i.e. having some machine learning part to help automatically figure out a large proportion of C++ code needed for those tasks based on some simple specification (which is a very challenging problem of course).

  • Here the (parametrizable) item grammar encoded is

  • DungeonArea := hDivide(DungeonArea , DungeonArea , Corridor)

  • | vDivide(DungeonArea , DungeonArea , Corridor)

  • | tArea(Room)

  • | bossArea(BossRoom),

  • where "Corridor", "Room", "BossRoom" are terminal types (albeit a pointers) defined in some other (C++) code.

  • There are 9 node attributes, two variable attributes and seven functional attributes.

  • • The two variable attributes are "bound_box" for help view culling optimization, and "room_range" (Line 17 - 18). They are used for help corridor collision point computation optimization.

    • Four of the functional attributes are "GetContactFromLeft", "GetContactFromBottom", "GetContactFromRight" and "GetContactFromTop" (Line 19 - 22). They are used for corridor collision point computation.

    • Three of the functional attributes are "Draw", "DrawPart" and "DrawAll" (Line 23 - 25). They are used for rendering. The implementation of Draw is included in the node block as it applies for all type of nodes in the same way.

  • The < disable auto_prob_noneg > part on Line 2 means that in this item type, it disables the automatic correction of negative probability to zero (which otherwise would be implicitly executed). This is only for the purpose of runtime optimization (which may not actually be a bottleneck here), based on the fact that we know no rule probability values would be set to be negative here. This serves as an example of adjusting item type options in GIGL. For more details out item type options, please refer to [Here].

  • GIGL naturally maintains the hierarchical structure generated with the item grammar, which can often be exploited as acceleration data structures. Here it is used both in accelerating corridor collision point computation within the item generation process, and in accelerating view culling in rendering after the item is generated. The detailed mechanism can be seen in the implementation of those seven functional attributes. The effect of acceleration are tested and discussed in our paper.

  • Here we introduce another important way to control or rather constrain the stochastic expansion process. That is, with rule pre-selectors. It is always put in a special rule called default rule.

    • A default rule (Line 38 - 50) can appear once for each nonterminal type. In general, it contains information that applies to all actual rules (i.e. those in the item grammar) for expanding this nonterminal type.

    • Pre-selector (Line 39 - 48) defines a block of statements that are executed before stochastically selecting which rule to expand through. There are several special type of statement allowed in pre-selector, e.g. the forbid statements on Line 40, 41, 43, 45, 47 (the transfer to X parts on Line 45 and 46 means add the original probability of the forbidden rules to rule X), that forbid some rules to be selected based on the local conditions. For more details please refer to [Here].

    • Pre-generator (Line 49) defines a block of statements that is shared between the generators of all actual rules for expanding this nonterminal type, and is concatenated in front of the definition of the generator for each of those individual rule. In this sense this is just some helper for reducing code repetition. It is often used to assign some variable attribute (e..g. the "bound_box" here) when the assignment method is the same for all actual rules for expanding this nonterminal type. Here, the statement in the pre-generator cannot be put in the pre-selector because in the pre-selector, the rule has not been chosen which means the node has not be created yet, so its attributes like "bound_box" cannot be accessed.

  • Theoretically speaking, manipulation of rule probabilities in the pre-selectors can often be reproduced by using the lambda configuration feature introduced in the Quiz example earlier, however in different cases it might be more natural to choose one approach over the other. A detailed discussion about this topic can be seen at [Here].