Game Development – How to Create a Rules and Constraints Engine

finite-state machinegame developmentrules-and-constraints

I want to make a simple game similar to the choose-your-own-adventure books. The player is presented with a narrative text and gets to choose his action from a list of possibilities. This, in turn, leads to a new narrative text, ad infinitum. The only catch is that depending on some previous decisions, the list of possibilities might differ.

At first glance, this sounds like a load of if-else statements, thus implying a rule engine would be in place. But, it also sounds like a finite state machine to me.

I am about to write this in Java or maybe Groovy. I'm currently more interested in the conceptual issues, i.e. how should this be done on a broad level (how do people implement chess or card games, anyway?), but some advice on a specific library in also welcome.

Obviously, the "game engine" from the title does not refer to collision detection or other physics/graphics mechanics, but the logic deciding what options does a player have given the situation and his current state.

Best Answer

Based on what you've said in comments, this is how I would handle it:

Implement the story as a finite state machine, with a twist. Each State is a page of the story, and each Transition is a link from one page to another. But each Transition also has Conditions. The Conditions could be null, in which case the Transition always shows up as an available option, but if not, then they have to be evaluated when the page displays, and if the evaluation returns False, the Transition does not show up.

There are two basic ways you could implement the Conditions. The first is to set up a full-blown script engine inside the game, and then the Condition looks like return player.inventory.contains(GUN). This is initially more complicated to set up, but allows for more advanced scripting.

The second is to hard-code the possible conditions into some sort of object. It could have a RequiredItem field, and if that field has a value, you check to see if the condition is met. This system is simpler to set up. It limits what you can do a lot more than scripting would, but if you don't need the flexibility that a script engine would provide, it's probably a lot easier to use.

Related Solutions

Design – How to program for constraints/rules

These guidelines/idioms are called Constrained Programming, which is not easy thing to do. It is used for modeling and solving combinatorial problems (NP-hard, NP-complete). I can recommend you one book - Principles of Constraint Programming. This book is one of the best books on the subject, but, still, after reading it you still won't be able to apply it in practice.
But, you will be able to do that by getting familiar yourself with Gecode - a toolkit for developing constraint-based systems and applications. Gecode provides a constraint solver with state-of-the-art performance while being modular and extensible.
I can say that this subject is very interesting, I'd say one of the best courses I had during my studies. Btw, the author of Gecode, was my professor, so I was very lucky :)

Game Development – How to Create a Generic Rule Parser for RPG Board Games

What you’re asking for is essentially a domain-specific language—a small programming language for a narrow purpose, in this case defining P&P RPG rules. Designing a language is in principle not difficult, but there is a considerable amount of up-front knowledge that you must gain in order to be at all productive. Unfortunately, there is no central reference for this stuff—you’ve got to pick it up through trial, error, and lots of research.

First, find a set of primitive operations whereby other operations can be implemented. For example:

Get or set a property of the player, an NPC, or a monster
Get the result of a die roll
Evaluate arithmetic expressions
Evaluate conditional expressions
Perform conditional branching

Design a syntax that expresses your primitives. How will you represent numbers? What does a statement look like? Are statements semicolon-terminated? Newline-terminated? Is there block structure? How will you indicate it: through symbols or indentation? Are there variables? What constitutes a legal variable name? Are variables mutable? How will you access properties of objects? Are objects first-class? Can you create them yourself?

Write a parser that turns your program into an abstract syntax tree (AST). Learn about parsing statements with a recursive descent parser. Learn about how parsing arithmetic expressions with recursive descent is annoying, and a top-down operator precedence parser (Pratt parser) can make your life easier and your code shorter.

Write an interpreter that evaluates your AST. It can simply read each node in the tree and do what it says: a = b becomes new Assignment("a", "b") becomes vars["a"] = vars["b"];. If it makes your life easier, convert the AST into a simpler form before evaluation.

I recommend designing the simplest thing that will work and remain readable. Here’s an example of what a language might look like. Your design will necessarily differ based on your specific needs and preferences.

ATK = D20
if ATK >= player.ATK
    DEF = D20
    if DEF < monster.DEF
        monster.HP -= ATK
        if monster.HP < 0
            monster.ALIVE = 0
        end
    end
end

Alternatively, learn how to embed an existing scripting language such as Python or Lua into your application, and use that. The downside of using a general-purpose language for a domain-specific task is that the abstraction is leaky: all the features and gotchas of the language are still present. The upside is you don’t have to implement it yourself—and that is a significant upside. Consider it.

Best Answer

Related Solutions

Design – How to program for constraints/rules

Game Development – How to Create a Generic Rule Parser for RPG Board Games

Related Topic