0
\$\begingroup\$

I am working on a system to procedural generate a house using this article. I am trying to understand how grammars work and are made I have found very little information on the topic online. From my understanding a grammar is like a rule and you can for example recursively iterate through a model and add a part to it based on that rule then repeat that process for each rule. Is this the right idea? If not can you provide a explanation or some resources explaining it? Also can grammars be made simply by using a few if statements to determine where something should be or is there something more special about them? I saw a video explaining how they use grammars to make compilers and parse the code. It looked like they were using a custom format to define the grammars. Is this something related and also is this the same type of grammar? If so what is the purpose of using a grammar in my case of procedural generating a house they seam like they are unrelated for generating the placement of rooms?

\$\endgroup\$
1
\$\begingroup\$

Grammars might not be the best here. There's a fundamental difference between what compilers do and what you want to do: the applying direction.

When doing compiling, grammars are used to check whether the code is put together in a compilable way. Let's say your grammar has an expression rule, that can be basically anything from function calls to basic math and you want to implement for loops. The easiest method is to also define a block rule which consists of a list of expressions and use that for the loop. But you might also want to add single-expression (blockless or one-line) for loops (for (a in b) doThis();), then you also let the for loop be followed by an expression. Something like the following:

expression:
    // Stuff

multi-expression:
    [expression] ([multi-expression] || [nothing])

block:
    [opening bracket] [multi-expression] [closing bracket]

for-loop:
    [for-loop-body] ([block] || [expression])

Where ([a] || [b]) gives a choice between the two. This lets you create pseudo-recursion where rules can apply to arbitarily long token chains (like in the case of the multi-expression helper rule, which can apply to one, two or more expressions).

The problem with this is that using these to test strings is easy, but generating them is hard, since there are usually infinite possibilities. You might not want trees that take seconds to generate, because rng happened to choose the repeating path over and over again.

A good alternative as mentioned by Bram in the comments is to use an L-system. L-systems are very close to lexical grammars, but they are separated into stages. Each stage you take every letter, apply the production rules and output the new string. You can stop whenever you want, extract the constants and do what you want to do with them.

However, traditional L-systems usually only generate self-similar fractals. This can be solved by making some rules randomly choose between two or more options for the letters (like when doing trees for instance, a branch could either abruptly stop by generating a constant/terminator or branch further)

\$\endgroup\$
  • \$\begingroup\$ First thank you so much for you long thorough response it was very helpful. I spent the past couple hours researching L-Systems and from my understanding I would use a L-System to represent the shape of a building by draw instructions. Is this correct? In the article linked to in the post under the Graph Generation section they said they use the grammars to represent the layout of the rooms and they save them in a graph data structure using nodes and edges to represent rooms and paths between rooms. How would this hold information such as the type of room, size etc. as well as \$\endgroup\$ – Robert Harbison Dec 24 '18 at 9:19
  • \$\begingroup\$ the path between rooms? \$\endgroup\$ – Robert Harbison Dec 24 '18 at 9:19
  • \$\begingroup\$ @RobertHarbison if you actually take the time to read the article, it says that only the graph (the basic connection structure of the house) is generated by the grammar. The exact place and sizes are determined later by evenly distributing them and then growing them using the Monte Carlo method. \$\endgroup\$ – Bálint Dec 24 '18 at 13:27
  • \$\begingroup\$ Yes correct I mistyped I know that the graph is used to store the basic layout of the house but I am unclear what the use of L-System is in this case because I don't see how to use and convert the output to something usable for saving the structure into a graph. \$\endgroup\$ – Robert Harbison Dec 24 '18 at 13:40
  • \$\begingroup\$ The L-system should consist of nodes, for instance the start node could be the house, and then make the ruleset generate a room from that, then each room should split into multiple, smaller ones. Kind of like how th recursive division algorithm works \$\endgroup\$ – Bálint Dec 24 '18 at 13:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.