I’m working on a new parser based IF system. The system is in JavaScript and creates client-side applications that run in the web browser. I need to pick an appropriate algo for the rule engine. I’ve been looking at the RETE algo, but I’m wondering if it’s overkill for the use case. I don’t want to go super complicated if I can achieve sub one second response time for a large work of IF with a simpler solution.
So, how many nouns and rules are typical in a large work of IF? The count should include nouns and rules that are built into the system as well as custom nouns and rules added by the user.
By “nouns”, do you mean “objects” or “dictionary words”? (For example, if there’s a brass lantern in the game, do you count that as one object or three words “brass”, “lantern”, “lamp”?)
By “rules”, do you mean specifically action rules (that run in response to player input), or also rules that run on their own every turn, or when the game starts up, etc?
Yes, by noun I mean object, story elements that relate to one another. For rules I’m mostly concerned with action rules and rules that run every turn. I’m less concerned about start up rules since those only run once.
Classical parser systems were very careful that the parser never had to consider every object in the game for a single command. Only the maximum number of objects in scope mattered, and of course that was usually “objects in one room”. Then authors would be equally careful not to add too many objects to scope at once.
(I7 messed that up, because those were the Moore’s Law years. Caused me some trouble for Hadean Lands on mobile.)
Max objects in a room, well, the typical number is like a dozen because most IF games (by count) are very small! It’s a power law, which means averages are unhelpful.
The same logic may or may not apply to rules. Your basic one-room I7 game has, hm, I’m not sure how to count this, possibly 360 rules? But nothing in the game has to run through the list of all of them. (The compiler does but that’s another problem.)
Again, your basic one-room I7 game seems to apply about 50 rules in the course of a GET LAMP.
I’m not sure routines is the right measure. I’m asking for the number of match patterns that would trigger a routine. Maybe they are the same thing. Maybe they aren’t.
I think it was Knuth who said “premature optimisation is the root of all evil”.
So I suggest make your parser as simple as possible, and get it working well, handling the myriad tricky things that a parser needs to handle (e.g. disambiguation is a real beast). THEN worry about performance.
I believe in that, but I don’t want to get to the end of the project and then realize the data structures I’ve chosen don’t scale well for a realistically sized gamed. That’s why I’m trying to get a sense of scale. I don’t want to make a toy system.
The system is based on pattern matching. For example:
reify.scene`when player carries _something_ and #something is cold.`
.action((match=>
{
blah blah blah
})
The scene method is essentially the rule condition (the pattern) and the action method is the rule’s production. So what I’m asking is for a reasonably large game how many patterns (including default patterns built into the system) would be expected and how many story elements (objects, rooms, people, etc.) would be expected.
I’m not asking about how many patterns would be tested per turn, although that’s a legitimate question and depends greatly on choice of algorithm.
It seems like what you’re trying to measure isn’t a metric I often see used. You might have better luck finding a decent-sized game with source code and measuring it yourself. (Adventure has a lot of ports, for instance.)
Is this something that gets checked every turn? Or only when the player types a command that results in them carrying something?
That would be a good approach. I had planned to port Colossal Cave Adventure as a test of the system anyhow, but is that considered a large game?
In this system, a rule is a scene plus its a action. Another way to say it is that a rule is a pattern (match condition) paired with a production. So, despite the sugar-coating in the terminology I’ve chosen, this is essentially an Expert System. The rules are triggered whenever there is a change to the facts of the story world, which usually, although not necessarily, the result of player input. Facts describe the relationships between story elements and consist of a predicate and 2 or more elements. A story element is typically a noun or an adjective. player carries ring is an example of a fact.
Typically only a small number of facts change (are asserted or retracted) per turn. What I want to avoid is checking all the patterns each turn. This can be done through implementing some indexing or implementing a full-blown version of the Rete algorithm. I’m a little intimidated by Rete and so I’m trying to figure out if it’s truly necessary before investing more time in trying to implement it.
For context, I’ve already implemented a pretty decent CFG parser in support of the DSL (Domain Specific Language) that is used for selecting elements and interacting with the story world.
Much though i agree there are a lot of optimisations possible, suppose it did a million rules per turn. Would that that be too slow? I’m amazed by the speed of modern systems and would not be surprised that even 1e6 rules could be processed in well under 1 second.
I second this, if we’re talking about modern systems. I don’t usually give this a lot of thought but I just gathered some rough stats from the Javscript parser I’m working on. My current dev game’s world has about 275 objects in it, where each object has hundreds of inherited prototype properties. Maybe thousands? For sake of discussion, I’ll ballpark it at 500 per object, which means 275 objects * 500 properties = 100k properties. Between verbs, nouns, prepositions, etc, I guess the game knows something on the order of 2000 words.
I just did a quick test on my oldest machine, a 2015 MacBook. Initialization of the game takes about 220ms. Every turn does a diff of the entire current world state (all those 100k properties) against the initial world state and that takes about 100ms. Asking “where is x”, which runs a parser loop (compare each word of input against 2000 words) and scans the entire world lookup for x (compare against 275 objects), takes about 40ms. All of that happens one time per player input, which is like, nothing, in terms of CPU demands. (Chrome’s Performance tab tells me my “Interaction to Next Paint” needs improvement because my total script time took a quarter of a second, but I’m not measuring in time to paint, so nuts to that.)
By contrast I’ve worked on graphical websites and apps that paint the entire screen every 20ms while simultaneously handling real time user input, streaming A/V, and running network operations. It seems to me that the resource needs of any text based parser system are minuscule compared to even running Gmail, which is silently running a constant stream of network operations and keeping a local db of hundreds of messages.
I would say just build your thing and see how well it performs without starting out worrying about limitations. If you’re NOT getting sub one second responses on a modern machine, you may be doing something in a particularly inefficient way. For my part, for a very long time I was using JSON.stringify() and JSON.parse() in my diff operations and that did give me something like a 2 second init, until I figured that out and switched tactics, because those conversions are relatively time consuming in bulk operations.
(Of course if you’re talking about building to a TRS-80 or whatever, forget I said anything.)
Thanks, this is nicely specific and reassuring. I’m targeting modern browsers and that implies modern systems. So no, this is most definitely not a retro-computing project, despite the subject matter.
If I can’t get the Rete thing figured out, I’ll just stick to a little bit of indexing and stop worrying.
Your system sounds cool. Is there anywhere I can check it out?
Yes, I have a public facing website, with the huge caveat that it is still very much a work in progress. I’ve talked about it and shared screenshots, but I haven’t released it or invited people to try it, and it still has big glaring omissions and needs a ton of beta testing.