It's really fascinating seeing the parallels between young Arvi struggling to learn programming because it uses all those weird unfamiliar english words, and then many years later making a game about figuring out how weird english words work via trial and error to solve puzzles by change the world's programming.
I had no idea this was the same dude who made Environmental Station Alpha. That’s crazy. This guy has made two absolute masterpieces of game design. Before Hollow Knight came out ESA was my favorite metroidvania of all-time and I highly recommend it to anyone who even slightly enjoys the genre.
And he worked on Noita, which is easily one of the most unique takes on the roguelike genre of the past decade. This man is a genius. I can’t wait to see what he does in the future.
Hey Arvi, hopefully you see this comment. Maybe you've already realised this but the 'if' conditional is even worse than your example at the end shows. That example is complicated, but it is ultimately solvable quite easily: is the rock on the flag, is it facing right, is baba... etc. I've got a shorter and much 'simpler' but actually much worse one for you... Baba is you if rock is push if wall is stop. How do you parse that, logically? That probably breaks your whole system for reasons that you can hopefully see. It's conditional on another conditional (a nested conditional). The intuitive human-language parsing would be equivalent to "if there is another rule that says rock is push if wall is stop, then baba is you, regardless of whether wall is actually stop or rock is actually push (and this rule does not make rock push or wall stop even though it contains the sub-clauses "rock is push" and "wall is stop" within it)". And that's a relatively 'simple' instantiation of the fundamental problem, and before we deal with questions of how 'if' can be placed. What about "if Baba is you if rock is push if wall is stop rock is stop if grass is you if flag is win"? And so on... Plus negations get more complicated once you have conditionals too, because the placement of the negation matters a lot. You have to account for "Baba is not you if rock is push" and "Baba is you if not rock is push" and "Baba is you if rock is not push", among other possibilities just from inserting one 'not' (all different things according to the way your system parses 'not', even though the second and third might sound the same!) Then of course you can insert more negations and combine this with the previous 'nested conditional' problem and have "not Baba is not you if not rock is not push if not wall is not stop", etc (which, I think, is way more complicated to parse than either "not Baba is not you | not rock is not push | not wall is not stop" or "Baba is you if rock is push if wall is stop"). Oh and (maybe less of an issue from a parsing issue but potentially a real challenge from a programming point of view, I would guess) what about paired conditionals like "Baba is you if rock is push | rock is push if baba is you"? Suppose those are the only rules at the start of a level. Does the game just crash as it infinitely bounces back and forth between trying to verify the two conditionals? Does it default to treating them as both true because they would satisfy each other if one is true? Does it default to treating them both as false because they would fail to satisfy each other if one is not true? Or even just multiple conditionals that might make each other true: how does the game know in which order to verify them, and does it make multiple passes (with each subsequent pass verifying any conditionals that were satisfied in a previous pass), so that if it checks "Baba is you if flag is win" first, finds it to be inconclusive, and then later on checks "flag is win," it goes back, verifying the first statement on the basis of the second? You could need quite a lot of passes being made with every move if you have multiple nested and paired conditionals and so on. Just pointing out that your example is the least of your worries with 'if'!
> "Baba is you if rock is push if wall is stop". How do you parse that, logically? You decide on an associativity rule and stick to it. The essence of the thing you're pointing out is not fundamentally more complicated than deciding whether to parse "a minus b minus c" as "(a minus b) minus c" or "a minus (b minus c)", just replace "minus" with "if". One might feel like "a if b and c" should mean the same as "(a if b) if c", but that might interact in challenge ways with rules like "baba is you if rock is flag and wall is push": should the condition parse as the two rules "rock is flag and wall" and "flag and wall is push"? Does that then mean that "baba is you" holds only if those two overlapping rules are on the board somewhere? So if you want "a" to be conditional on both "b" and "c", I think "a if b if c" is the least complicated way of expressing it. That means implications nest on the right, like "b => (c => a)", and not on the left, "(b => c) => a". An implication of this choice: "a if b if c" means the same as "a if c if b". More complicated things can be expressed if you make the opposite choice, i.e. if "a if b if c" means "a if (b if c)", but it also gets a _lot_ harder for the players to reverse engineer (i.e. learn) this rule. So I think "(a if b) if c" is the best choice. [Using 'and' in its normal logical sense and not its Baba sense, "b => (c => a)" means the same as "(b and c) => a", and it's well known that "x and y" means the same as "y and x". For those unfamiliar with this notation, "x => y" means "x implies y" or "if x is true then y is true" or "x is _only_ true if y is true". These three statements are all equivalent.] > What about paired conditionals like "Baba is you if rock is push | rock is push if baba is you"? I'd say do the logically sound thing: treat all the unconditional things as true first, then for every conditional rule "a if b", add "a" to the list of true things if "b" is true according to what's already on the list (and delete the "a if b" rule from the list of not-yet-evaluated rules). Continue doing this until you've checked all rules without adding one [i.e. until you reach a fixed point]. That way, every condition of every active conditional rule is satisfied, and (subject to this constraint) you maximize the number of active conditional rules. (IIRC this is what Datalog programs mean.) If you start with n conditional rules and each pass over the list removes at least one rule, each rule is checked at most n times, so you do at most n^2 rule checks. I figure in most levels n < 10, so this is really no problem performance-wise. > Plus negations get more complicated Given how many keen observations you have made, I'm surprised you didn't give an example like this: "baba is you not if flag is win", where the "not" goes before (and presumably modifies) the "if". By my intuition about ordinary English, this should make the "baba is you" rule deactivate whenever "flag is win". However, consider a level with only two rules: "X not if Y" and "Y not if X". Rules X and Y can't logically be active simultaneously; it's logically fine for any one of them to be active; nothing about the rules gives us a reason to prefer one over the other. I guess there's a meta-rule: rules have a precedence system, where for example "rock is rock" takes precedence over "rock is Z" for all non-rock Z, and negative rules ("baba is not you") takes precedence over positive rules ("baba is you"). You could also add the meta-rule "all preexisting rules take precedence over all newly created rules". Then it's fine if you can create "X not if Y" and "Y not if X" _during_ play; the level editor just needs to reject levels where both of those rules start on the board. Or else add a tie breaker where longer rules beat shorter rules and rules that start earlier on the grid (in normal reading order) beat rules that start later on the grid and (finally) horizontal rules beat vertical rules. Although the game no longer simply implements logic (or something like that), at least it does something well-defined.
I'm currently working on a game where I might need to do something similar, now I know it's called an interpreter and I can research this properly, thank you!
@@EmperorsNewWardrobe An interpreter `i` is a program which takes a program `p` as input and runs `p` (on whatever input to `p` the user provides). This is distinct from a compiler, which is a program `c` which takes a program `p` as input and outputs a program `q` such that `p` and `q` do the same thing in all cases. Reasons for compiling: the machine only runs machine language. By compiling to machine language before running your program, you can save the time overhead of interpreting when you run the program. Or, you want to run your code in a web browser and they only run javascript, but you've written your program in some other language.
50:44 is the slide with all the nastiest examples. As far as I understand: (1) if a set of words (and letters) form a rule, the word/letter squares must be horizontally or vertical contiguous. That is, they can't have gaps or be scattered all over the level, you have to connect them. (2) every rule contains exactly one copy of the word 'is', either in a single square or as two letters I-S. (3) when considering a sequence of squares, every substring of squares which form a syntactically valid rules is treated as a rule. For example, given "W-A-L-L [is] [stop]" produces two rules, "wall is stop" and "all is stop". This is somewhat in conflict with Arvi's statement around 55:00: by my understanding, the sequence "Baba is grass and rock is push" produces four rules, "Baba is grass", "Baba is grass and rock", "grass and rock is push" and "rock is push". Note that the two latter rules do not conflict and the last one is redundant. Also, "X is Y and Z" is confusing if X, Y and Z are all object types, so the second rule needs clarification on its own before we consider its interactions with the first rule. Given this, I think the following might be fruitful approach to parsing: (a) in every sequence of word/letter squares, find every occurence of 'is' (including I-S). (b) for every 'is', grow the rule outward. (c) for every span of words to the left of 'is', if that span could be a prefix of a rule, add the leftmost coordinate of the span to a list (d) for every span of words to the right of 'is', if that span could be a suffix of a rule, add the rightmost coordinate of the span to a list (e) for every pair of (starting, ending) coordinates: if that whole combined span is a valid rule, add it to the list of active rules Also, in step (e), monomorphize the double-word squares, i.e. make one copy of the rule for each word in a double-word square, and test each copy for syntactic validity independently of the other copies. Note that this can blow up exponentially in the number of double-word squares. If the exponential blow-up becomes a problem, one could consider a rules representation which includes double-words. This shifts the exponential blow-up to the process of iterating over all the monomorphized rules, which we might never do if the rules adjudication doesn't require it. Testing whether there exists a rule that applies to a specific situation (e.g. "is grass stop?") likely won't require this exponential blow-up. But the code will be more complicated. Maybe the structure of the rules is such that they form a regular language. In that case, throw automata theory at the problem until it is solved. Note that you can model the double-word squares as a two-element regular language; if you do, you have to do language intersection queries instead of string matching queries. But, you know, throw automata theory at the problem. Fun stuff to think about.
Hi Arvi! I built my own mental model of the rule system while playing and looked through the Lua code a few weeks back. I wondered why it's so complicated, but in our playthrough we have just arrived at the introduction of "NOT", so we haven't seen the really complex stuff yet. This video probably helps with understanding the code. The rules are not just difficult for you to parse but for the player as well, even at the early stage of the game. One example are asymmetrical rules like FLOAT, where objects with this quality can be pushed but do not push themselves. This behavior is totally unexpected and illogical. A huge issue is the precedence of rules. This is also often relevant but there is no explanation or logic to it from a player point of view but simply something to figure out and remember. I also found an interesting corner case with MOVE whereas the move order of multiple moving objects matters. The move order is something that does exist and you can find it through experimentation but it's not something that is in any way visualized but it can make or break a solution. I think what you have there is a 'pile of rules' problem. Rather than having a small set of rules that work well together in interesting ways and levels built around that you piled on more and more rules. Sure you get some interesting and certainly lots of unexpected interactions out of it, but at the same time a lot of unwanted situations as well. It is not only hard to implement correctly, it is also hard for the player to understand, to make a mental model and to reason about.
There are no intended solutions that rely on movement order. You also don't seem to understand what FLOAT does, it's pretty simple and straightforward. It just stops overlap interactions with non-floating objects, nothing asymmetrical or illogical about it. Your mental model of the ruleset has to be flexible, you have to be able to separate what you actually know from what you're just assuming. You had a false assumption about the way FLOAT works, and instead of figuring out what that false assumption was you just cry inconsistency.
@@Oneiroclast Whether intended or not, there are solutions that do rely on movement order. Solutions people do stumble upon and get very confused by. What is "Float just stops overlap interactions" even supposed to mean? Nonfloat objects can push float objects. Float objects can not push nonfloat objects. There you go, inconsistent and rather illogical.
@@sirdiealot7805 That's 100% wrong though. Float objects can both push and be pushed by non-float objects. It just stops things like hot/melt and open/close, things that require 2 objects to occupy the same space. Interactions that don't require objects to occupy the same space like PUSH and STOP are unaffected. Open up the game and test it yourself. You can be smug or you can be wrong, but don't be both.
At one point in the game we can write Not Baba Is Not You, and this acts as if we wrote Baba Is You. This confuses me. Shouldn't it just act to disable all other objects from being You?
Spoilers Below: I think you’re probably thinking of level ???-05 “Scale”, where one possible solution is forming NOT ROCK IS NOT YOU, which allows you to control a rock (as ROCK IS YOU is elsewhere) but avoid controlling a skull that would break FLAG IS WIN.
@@foxtro7 No I think the level he's talking about is that one level where you have to put a not before baba is not you to prevent it from preventing baba being you.
hey, haven't watched the video yet but I wanted to say: after playing Baba is You I tried to implement it's rule system, because I really liked it and I used parser combinators haha :D I used monogame with F# also
I also immediately thought of that. I think that a good starting point for the lexing algorithm would be: in each row of words/letters: locate all verbs (including verbs made of letters), take all possible strings of various lengths before and after the verb (taking into account overlapping words), filter those sets to get only valid objects/qualities for given verb, remove objects that are suffixes of other objects and qualities that are prefixes of all qualities, and done. You have all the sentences. For example, let's do the BABA (IS/ON) (GRASS/YOU) IS MOVE example: First IS: objects: [BABA] → [BABA] → [BABA] qualities: [GRASS, GRASS IS, GRASS IS MOVE, YOU, YOU IS, YOU IS MOVE] → [YOU, GRASS] → [YOU, GRASS] resulting sentences [ BABA/IS/YOU, BABA/IS/GRASS] Second IS: objects: [BABA IS GRASS, BABA IS YOU, BABA ON GRASS, BABA ON YOU, IS YOU, IS GRASS, ON YOU, ON GRASS, YOU, GRASS] → [BABA ON GRASS, GRASS] → [BABA ON GRASS] qualities: [MOVE] resulting sentences [ BABA ON GRASS/IS/MOVE] This algorithm would also find the rules in that BABA IS GRASS AND ROCK IS PUSH example: [BABA/IS/GRASS AND ROCK, GRASS AND ROCK/IS/PUSH] The validation and parsing of objects and qualities could be done with some easy depth-first parser. This even includes single-letter tiles. Removal of "shorter" objects/qualities can be done naively with some O(n²) algorithm. This could be easily expanded to support IF, the conditional clause could be validated with a parser, because it's easier to see if something is a valid sentence than to find the "longest" sentence. Of course after that you would have to mark the verbs in the conditional clause as already taken by the root sentence. This could lead to a fun mechanic where [GRASS IS MELT IF BABA IS WIN] could be changed to mean [BABA IS WIN] by moving GRASS (as the first IS MELT IF would no longer form any sentence and therefore it would do nothing, including not making the second IS a condition). Of course that's only parsing, implementing IF so that it works in the game is another and more complicated thing.
@@jvcmarc Finnish and similar languages are agglutinative languages, wherein syllables can be added to words to create never-ending words, just by changing the pronunciation of various syllables. What confused me the most (though I can still comprehend it) is how he called the Object the "subject" ... when it was the Subject, in a SVO (subject-verb-object) language like German or English or other Western European languages. He might have called the Subject the "object" instead (the opposite)... I forgot! anyway, it's still not hard to decipher when making a basic sentence in a language which is derived from Proto-Indo-European (Greek and Latin) like most or all western european languages. The languages like Finnish, Hungarian, and Korean/Japanese are agglutinative languages. Wikipedia has info about all the various types of languages. I think like Suomi (Finnish) and Hungarian, Turkish also originated in an ancient language group called Ugric (rather than PIE). I don't know if Turkish is agglutinative. Wikipedia does...
While watching this I can't help but find some flaws in his approach: - cheking for Object Verb Quality, when "is" is the only word that applies quality to objects, all other "Verbs" are just between Objects - I don't see a reason for the multiple passes and the huge complexity - the parser should basically just always look for all the possible sentences and discard those that are entirely contained in some other sentence, and add the rest to rules - the internal structure could be more divorced from the text-based in-game representation, for example instead of storing 1=Baba, 2=Is, 3=You, just store subject=Baba, effect=You, Baba Is You And Has Key And Door would be subject=Baba, effect=You, contains=[1=Key, 2=Door]
It's really fascinating seeing the parallels between young Arvi struggling to learn programming because it uses all those weird unfamiliar english words, and then many years later making a game about figuring out how weird english words work via trial and error to solve puzzles by change the world's programming.
@@MadsterV halfway to an interpreter more like. (Compiler does a lot of more complex stuff that an interpreter can directly rely on)
@@MadsterV By 'AST diagram' do you mean the one at 50:50? To me that just looks like a trie.
I had no idea this was the same dude who made Environmental Station Alpha. That’s crazy. This guy has made two absolute masterpieces of game design. Before Hollow Knight came out ESA was my favorite metroidvania of all-time and I highly recommend it to anyone who even slightly enjoys the genre.
And he worked on Noita, which is easily one of the most unique takes on the roguelike genre of the past decade. This man is a genius. I can’t wait to see what he does in the future.
I think he looks like an alternate universe version of Sandor Clegane where he's a programmer instead.
The explanation at 12:50 didn't need Baba is You off screen, that rule is already there on the slide.
A completionist speaks
Honestly really interesting presentation:) ty for keeping these talks, even during these trying times
Genius Dev: "Baba Yaga is made in Lua..."
Me, a ROBLOX Dev: SO YOU'RE SAYING IT'S POSSIBLE
tip 1: use globals
me and the rest of the roblox devs be modding baba is you
Writing a dsl when you didnt even notice it's a dsl... Amazing
Hey Arvi, hopefully you see this comment. Maybe you've already realised this but the 'if' conditional is even worse than your example at the end shows. That example is complicated, but it is ultimately solvable quite easily: is the rock on the flag, is it facing right, is baba... etc. I've got a shorter and much 'simpler' but actually much worse one for you...
Baba is you if rock is push if wall is stop. How do you parse that, logically? That probably breaks your whole system for reasons that you can hopefully see. It's conditional on another conditional (a nested conditional). The intuitive human-language parsing would be equivalent to "if there is another rule that says rock is push if wall is stop, then baba is you, regardless of whether wall is actually stop or rock is actually push (and this rule does not make rock push or wall stop even though it contains the sub-clauses "rock is push" and "wall is stop" within it)". And that's a relatively 'simple' instantiation of the fundamental problem, and before we deal with questions of how 'if' can be placed. What about "if Baba is you if rock is push if wall is stop rock is stop if grass is you if flag is win"? And so on...
Plus negations get more complicated once you have conditionals too, because the placement of the negation matters a lot. You have to account for "Baba is not you if rock is push" and "Baba is you if not rock is push" and "Baba is you if rock is not push", among other possibilities just from inserting one 'not' (all different things according to the way your system parses 'not', even though the second and third might sound the same!) Then of course you can insert more negations and combine this with the previous 'nested conditional' problem and have "not Baba is not you if not rock is not push if not wall is not stop", etc (which, I think, is way more complicated to parse than either "not Baba is not you | not rock is not push | not wall is not stop" or "Baba is you if rock is push if wall is stop").
Oh and (maybe less of an issue from a parsing issue but potentially a real challenge from a programming point of view, I would guess) what about paired conditionals like "Baba is you if rock is push | rock is push if baba is you"? Suppose those are the only rules at the start of a level. Does the game just crash as it infinitely bounces back and forth between trying to verify the two conditionals? Does it default to treating them as both true because they would satisfy each other if one is true? Does it default to treating them both as false because they would fail to satisfy each other if one is not true? Or even just multiple conditionals that might make each other true: how does the game know in which order to verify them, and does it make multiple passes (with each subsequent pass verifying any conditionals that were satisfied in a previous pass), so that if it checks "Baba is you if flag is win" first, finds it to be inconclusive, and then later on checks "flag is win," it goes back, verifying the first statement on the basis of the second? You could need quite a lot of passes being made with every move if you have multiple nested and paired conditionals and so on.
Just pointing out that your example is the least of your worries with 'if'!
I think the answer is, don't allow qualities after 'if'. Only allow statements of fact. Allow "…if rock is on flag", don't allow "…if rock is melt".
> "Baba is you if rock is push if wall is stop". How do you parse that, logically?
You decide on an associativity rule and stick to it. The essence of the thing you're pointing out is not fundamentally more complicated than deciding whether to parse "a minus b minus c" as "(a minus b) minus c" or "a minus (b minus c)", just replace "minus" with "if".
One might feel like "a if b and c" should mean the same as "(a if b) if c", but that might interact in challenge ways with rules like "baba is you if rock is flag and wall is push": should the condition parse as the two rules "rock is flag and wall" and "flag and wall is push"? Does that then mean that "baba is you" holds only if those two overlapping rules are on the board somewhere?
So if you want "a" to be conditional on both "b" and "c", I think "a if b if c" is the least complicated way of expressing it. That means implications nest on the right, like "b => (c => a)", and not on the left, "(b => c) => a". An implication of this choice: "a if b if c" means the same as "a if c if b".
More complicated things can be expressed if you make the opposite choice, i.e. if "a if b if c" means "a if (b if c)", but it also gets a _lot_ harder for the players to reverse engineer (i.e. learn) this rule. So I think "(a if b) if c" is the best choice.
[Using 'and' in its normal logical sense and not its Baba sense, "b => (c => a)" means the same as "(b and c) => a", and it's well known that "x and y" means the same as "y and x". For those unfamiliar with this notation, "x => y" means "x implies y" or "if x is true then y is true" or "x is _only_ true if y is true". These three statements are all equivalent.]
> What about paired conditionals like "Baba is you if rock is push | rock is push if baba is you"?
I'd say do the logically sound thing: treat all the unconditional things as true first, then for every conditional rule "a if b", add "a" to the list of true things if "b" is true according to what's already on the list (and delete the "a if b" rule from the list of not-yet-evaluated rules). Continue doing this until you've checked all rules without adding one [i.e. until you reach a fixed point].
That way, every condition of every active conditional rule is satisfied, and (subject to this constraint) you maximize the number of active conditional rules. (IIRC this is what Datalog programs mean.)
If you start with n conditional rules and each pass over the list removes at least one rule, each rule is checked at most n times, so you do at most n^2 rule checks. I figure in most levels n < 10, so this is really no problem performance-wise.
> Plus negations get more complicated
Given how many keen observations you have made, I'm surprised you didn't give an example like this: "baba is you not if flag is win", where the "not" goes before (and presumably modifies) the "if". By my intuition about ordinary English, this should make the "baba is you" rule deactivate whenever "flag is win".
However, consider a level with only two rules: "X not if Y" and "Y not if X". Rules X and Y can't logically be active simultaneously; it's logically fine for any one of them to be active; nothing about the rules gives us a reason to prefer one over the other.
I guess there's a meta-rule: rules have a precedence system, where for example "rock is rock" takes precedence over "rock is Z" for all non-rock Z, and negative rules ("baba is not you") takes precedence over positive rules ("baba is you").
You could also add the meta-rule "all preexisting rules take precedence over all newly created rules". Then it's fine if you can create "X not if Y" and "Y not if X" _during_ play; the level editor just needs to reject levels where both of those rules start on the board. Or else add a tie breaker where longer rules beat shorter rules and rules that start earlier on the grid (in normal reading order) beat rules that start later on the grid and (finally) horizontal rules beat vertical rules.
Although the game no longer simply implements logic (or something like that), at least it does something well-defined.
This guy is writing an interpreter without even knowing :)
Cool talk and cool game tho
I'm currently working on a game where I might need to do something similar, now I know it's called an interpreter and I can research this properly, thank you!
What is an interpreter exactly?
@@EmperorsNewWardrobe An interpreter `i` is a program which takes a program `p` as input and runs `p` (on whatever input to `p` the user provides).
This is distinct from a compiler, which is a program `c` which takes a program `p` as input and outputs a program `q` such that `p` and `q` do the same thing in all cases.
Reasons for compiling: the machine only runs machine language. By compiling to machine language before running your program, you can save the time overhead of interpreting when you run the program. Or, you want to run your code in a web browser and they only run javascript, but you've written your program in some other language.
50:44 is the slide with all the nastiest examples.
As far as I understand:
(1) if a set of words (and letters) form a rule, the word/letter squares must be horizontally or vertical contiguous. That is, they can't have gaps or be scattered all over the level, you have to connect them.
(2) every rule contains exactly one copy of the word 'is', either in a single square or as two letters I-S.
(3) when considering a sequence of squares, every substring of squares which form a syntactically valid rules is treated as a rule. For example, given "W-A-L-L [is] [stop]" produces two rules, "wall is stop" and "all is stop". This is somewhat in conflict with Arvi's statement around 55:00: by my understanding, the sequence "Baba is grass and rock is push" produces four rules, "Baba is grass", "Baba is grass and rock", "grass and rock is push" and "rock is push". Note that the two latter rules do not conflict and the last one is redundant. Also, "X is Y and Z" is confusing if X, Y and Z are all object types, so the second rule needs clarification on its own before we consider its interactions with the first rule.
Given this, I think the following might be fruitful approach to parsing:
(a) in every sequence of word/letter squares, find every occurence of 'is' (including I-S).
(b) for every 'is', grow the rule outward.
(c) for every span of words to the left of 'is', if that span could be a prefix of a rule, add the leftmost coordinate of the span to a list
(d) for every span of words to the right of 'is', if that span could be a suffix of a rule, add the rightmost coordinate of the span to a list
(e) for every pair of (starting, ending) coordinates: if that whole combined span is a valid rule, add it to the list of active rules
Also, in step (e), monomorphize the double-word squares, i.e. make one copy of the rule for each word in a double-word square, and test each copy for syntactic validity independently of the other copies. Note that this can blow up exponentially in the number of double-word squares.
If the exponential blow-up becomes a problem, one could consider a rules representation which includes double-words. This shifts the exponential blow-up to the process of iterating over all the monomorphized rules, which we might never do if the rules adjudication doesn't require it. Testing whether there exists a rule that applies to a specific situation (e.g. "is grass stop?") likely won't require this exponential blow-up. But the code will be more complicated.
Maybe the structure of the rules is such that they form a regular language. In that case, throw automata theory at the problem until it is solved. Note that you can model the double-word squares as a two-element regular language; if you do, you have to do language intersection queries instead of string matching queries. But, you know, throw automata theory at the problem.
Fun stuff to think about.
Great talk. Interesting as well as inspiring.
HYPE
Hi Arvi!
I built my own mental model of the rule system while playing and looked through the Lua code a few weeks back.
I wondered why it's so complicated, but in our playthrough we have just arrived at the introduction of "NOT", so we haven't seen the really complex stuff yet.
This video probably helps with understanding the code.
The rules are not just difficult for you to parse but for the player as well, even at the early stage of the game.
One example are asymmetrical rules like FLOAT, where objects with this quality can be pushed but do not push themselves. This behavior is totally unexpected and illogical.
A huge issue is the precedence of rules. This is also often relevant but there is no explanation or logic to it from a player point of view but simply something to figure out and remember.
I also found an interesting corner case with MOVE whereas the move order of multiple moving objects matters. The move order is something that does exist and you can find it through experimentation but it's not something that is in any way visualized but it can make or break a solution.
I think what you have there is a 'pile of rules' problem. Rather than having a small set of rules that work well together in interesting ways and levels built around that you piled on more and more rules. Sure you get some interesting and certainly lots of unexpected interactions out of it, but at the same time a lot of unwanted situations as well. It is not only hard to implement correctly, it is also hard for the player to understand, to make a mental model and to reason about.
your comment seems to have been posted five times
@@fdagpigj Thanks. Weird. I'll delete the others.
There are no intended solutions that rely on movement order. You also don't seem to understand what FLOAT does, it's pretty simple and straightforward. It just stops overlap interactions with non-floating objects, nothing asymmetrical or illogical about it. Your mental model of the ruleset has to be flexible, you have to be able to separate what you actually know from what you're just assuming. You had a false assumption about the way FLOAT works, and instead of figuring out what that false assumption was you just cry inconsistency.
@@Oneiroclast Whether intended or not, there are solutions that do rely on movement order. Solutions people do stumble upon and get very confused by.
What is "Float just stops overlap interactions" even supposed to mean?
Nonfloat objects can push float objects.
Float objects can not push nonfloat objects.
There you go, inconsistent and rather illogical.
@@sirdiealot7805 That's 100% wrong though. Float objects can both push and be pushed by non-float objects. It just stops things like hot/melt and open/close, things that require 2 objects to occupy the same space. Interactions that don't require objects to occupy the same space like PUSH and STOP are unaffected. Open up the game and test it yourself. You can be smug or you can be wrong, but don't be both.
Awesome conf
At one point in the game we can write Not Baba Is Not You, and this acts as if we wrote Baba Is You. This confuses me. Shouldn't it just act to disable all other objects from being You?
That isn’t what happens. Not Baba Is Not You means everything that isn’t a baba is not you. What you’re thinking of is Baba Is Not Not You.
@@theawesomepanda1lance241 Yeah, I think I probably either misremembered or misinterpreted what I saw.
Spoilers Below:
I think you’re probably thinking of level ???-05 “Scale”, where one possible solution is forming NOT ROCK IS NOT YOU, which allows you to control a rock (as ROCK IS YOU is elsewhere) but avoid controlling a skull that would break FLAG IS WIN.
@@foxtro7 No I think the level he's talking about is that one level where you have to put a not before baba is not you to prevent it from preventing baba being you.
an inspiration to us all :3
There is a point where one should give up on re-inventing everything from scratch and read up on some existing theory :-)
right? I have the feeling that a CS degree would help. Is there something specific you have in mind? Notion or a book.
well thats just less fun.
@@Czeckie Automata theory, parsing, context-free grammars, regular expressions, lexers, tokenization.
I would've started from verbs when looking for sentences. That might simplify it.
This talk sounds like a parser design challenge. It might have a perfect solution as a parser combinator...
@@killymxi wow so smart
hey, haven't watched the video yet but I wanted to say: after playing Baba is You I tried to implement it's rule system, because I really liked it
and I used parser combinators haha :D
I used monogame with F# also
I also immediately thought of that. I think that a good starting point for the lexing algorithm would be: in each row of words/letters: locate all verbs (including verbs made of letters), take all possible strings of various lengths before and after the verb (taking into account overlapping words), filter those sets to get only valid objects/qualities for given verb, remove objects that are suffixes of other objects and qualities that are prefixes of all qualities, and done. You have all the sentences.
For example, let's do the BABA (IS/ON) (GRASS/YOU) IS MOVE example:
First IS: objects: [BABA] → [BABA] → [BABA] qualities: [GRASS, GRASS IS, GRASS IS MOVE, YOU, YOU IS, YOU IS MOVE] → [YOU, GRASS] → [YOU, GRASS] resulting sentences [ BABA/IS/YOU, BABA/IS/GRASS]
Second IS: objects: [BABA IS GRASS, BABA IS YOU, BABA ON GRASS, BABA ON YOU, IS YOU, IS GRASS, ON YOU, ON GRASS, YOU, GRASS] → [BABA ON GRASS, GRASS] → [BABA ON GRASS] qualities: [MOVE] resulting sentences [ BABA ON GRASS/IS/MOVE]
This algorithm would also find the rules in that BABA IS GRASS AND ROCK IS PUSH example: [BABA/IS/GRASS AND ROCK, GRASS AND ROCK/IS/PUSH]
The validation and parsing of objects and qualities could be done with some easy depth-first parser. This even includes single-letter tiles.
Removal of "shorter" objects/qualities can be done naively with some O(n²) algorithm.
This could be easily expanded to support IF, the conditional clause could be validated with a parser, because it's easier to see if something is a valid sentence than to find the "longest" sentence. Of course after that you would have to mark the verbs in the conditional clause as already taken by the root sentence. This could lead to a fun mechanic where [GRASS IS MELT IF BABA IS WIN] could be changed to mean [BABA IS WIN] by moving GRASS (as the first IS MELT IF would no longer form any sentence and therefore it would do nothing, including not making the second IS a condition). Of course that's only parsing, implementing IF so that it works in the game is another and more complicated thing.
@@jvcmarc Finnish and similar languages are agglutinative languages, wherein syllables can be added to words to create never-ending words, just by changing the pronunciation of various syllables.
What confused me the most (though I can still comprehend it) is how he called the Object the "subject" ... when it was the Subject, in a SVO (subject-verb-object) language like German or English or other Western European languages. He might have called the Subject the "object" instead (the opposite)... I forgot! anyway, it's still not hard to decipher when making a basic sentence in a language which is derived from Proto-Indo-European (Greek and Latin) like most or all western european languages.
The languages like Finnish, Hungarian, and Korean/Japanese are agglutinative languages. Wikipedia has info about all the various types of languages. I think like Suomi (Finnish) and Hungarian, Turkish also originated in an ancient language group called Ugric (rather than PIE). I don't know if Turkish is agglutinative. Wikipedia does...
Baba is an alteration of the english language
While watching this I can't help but find some flaws in his approach:
- cheking for Object Verb Quality, when "is" is the only word that applies quality to objects, all other "Verbs" are just between Objects
- I don't see a reason for the multiple passes and the huge complexity
- the parser should basically just always look for all the possible sentences and discard those that are entirely contained in some other sentence, and add the rest to rules
- the internal structure could be more divorced from the text-based in-game representation, for example instead of storing 1=Baba, 2=Is, 3=You, just store subject=Baba, effect=You, Baba Is You And Has Key And Door would be subject=Baba, effect=You, contains=[1=Key, 2=Door]
@@Christopher-zr1ib me
Verbs are also used in the editor-exclusive "feeling" and also in "facing"
*The rule is english*
uhhh huh???? ( what )
Baba is snooze