orxSolver

edited February 19 in Projects - Tools

It's been a long time since my first (and last) thread here. I've gotten to a point where I'm trying to work on my game again, an RPG. I needed to figure out a way to make a list of attributes for characters that would be easily configurable, so I thought of creating a solver DSL for defining the relationships between attributes, in any arbitrary order so long as no loops are detected, which could then be attached to arbitrary orxObjects to automatically generate any dependent attributes on that object. The reasoning for this is to have an easy repository for all equations used in the game, which could be reused not just for stats but also damage calculations, or anything else really.

An example using hp, where equipped_list and effects_list are keys on the object that are just lists of other sections that currently affect the character:

[StatSolver]
Equations  = StatEquations
Defaults   = StatDefaults
Update     = change

[StatDefaults]
base_hp      = 10
base_mult_hp = 1
damage_hp    = 0

[StatEquations]
max_hp                = Clamp(0, max_hp_cap, (base_hp * base_mult_hp) + (equipment_mod_hp * equipment_mod_mult_hp))
total_hp              = max_hp + (temporary_mod_hp * temporary_mod_mult_hp) - damage_hp
max_hp_cap            = infinity
equipment_mod_hp      = Sum(equipped_list, equip_modifier_hp, default: 0)
equipment_mod_mult_hp = Sum(equipped_list, equip_modifier_mult_hp, default: 0)
temporary_mod_hp      = Sum(effects_list, temp_modifier_hp, default: 0)
temporary_mod_mult_hp = Sum(effects_list, temp_modifier_mult_hp, default: 0)

This would, given any orx object, generate the attributes base_hp, base_mult_hp, damage_hp, total_hp, max_hp_cap, equipment_mod_hp, equipment_mod_mult_hp, temporary_mod_hp, and temporary_mod_mult_hp on that object.

I've currently got a parser and topological sort working, I've started on setting up a VM for it, but I noticed that the orxConfig API isn't thread safe, which I would need if I wanted to solve for multiple characters in parallel if the equations are referencing lists of config sections, but not if they're just referencing other variables on the object itself, since that can be saved to a hashtable beforehand. The only solutions I can think of so far are either manually doing mutex locks when reading the config (not ideal), duplicating the code from the config module to read values from another section without modifying the config section stack (also not ideal), or just dealing with solving for one object at a time (which limits how much it can be used). Just wondering if there's any tips on this.

Tagged:

Comments

  • Hey @krypto42, sorry for the late reply but I feel like I'll need more brain power in order to give a satisfying reply, and that might have to wait until the weekend as my current week's been quite busy.

    The part I'm still not quite grasping if the need of parallel processing, but I'm sure I'll have it figured out before answering in a couple of days. In any case, even without the section stack, the config wouldn't be thread-safe as it'll modify the current section in order to resolve inheritance.

  • @iarwain said:
    Hey @krypto42, sorry for the late reply but I feel like I'll need more brain power in order to give a satisfying reply, and that might have to wait until the weekend as my current week's been quite busy.

    The part I'm still not quite grasping if the need of parallel processing, but I'm sure I'll have it figured out before answering in a couple of days. In any case, even without the section stack, the config wouldn't be thread-safe as it'll modify the current section in order to resolve inheritance.

    No problem, I'm busy a lot and so don't have much time or energy to work on this as often as I should, so even if you do get back early I might not be able to do anything about it for awhile. Maybe some more explanation would help.

    So after looking through some more threads on the forum, I think I've come to an understanding of the difference in what I'm trying to do vs the standard config system. I'm trying to find a way to make runtime values on objects meet certain constraints, basically the equivalent of functions defined in config, whereas the config system is about defining templates for creating new objects, even though a lot of the examples in the tutorials create a single object from a template, leading to confusion on my part since I wanted to section off accessing the values from config state changes (push/pop from the stack). Essentially I was considering a template as runtime, which was the wrong assumption in the first place.

    I know examples are around here about creating a separate Runtime section to hold those values, but I'm not sure if it would work quite the way I want it with what I'm imagining. I should probably clarify that.

    So what I'm thinking of as an "orxSolver" is like a textual version of an Excel sheet, where it constructs a DAG to determine evaluation order. Every variable is the equivalent of a cell, and each object the solver is attached to is the equivalent of the sheet, so it's a way of defining relationships between runtime variables, not template variables, and would be declarative rather than imperative. If a variable is a list, there would probably have to be a way to determine if it should look up a runtime object or a section for it's value. I'm only looking at math operations at the moment, not anything like string concatenation or even conditionals yet. There should also be a second mode for just updating values, that could be linked to an orxClock for implementing something like health regen, (eg. hp = hp + regen_hp * _DT). The reason I like the mathematical notation for it is because it's fairly easy to understand exactly how values are calculated, not have to worry about ordering them correctly, and be able to change certain game mechanics on the fly without a recompile.

    I've been thinking about it as a new addition to Orx itself, which is why I've been coding it in plain C so far, though I've been prototyping in Ruby first; and I think it's something that would make a useful addition to the codebase since I haven't really seen much about custom runtime variables being set through the config, other than the Runtime section which could get messy very quickly in cases with lots of runtime variables (in my project with what I've planned out so far I'm looking at 100+ variables per character; with a minimum of 3 party characters and an average of 4 - 5 enemies on the screen, that's at least 700+ variables floating around), which is part of the reason I was thinking about trying to make it thread safe in case it needed to be. I've been wondering if I can/should piggyback off the existing orxCommand module or integrating Lua and compiling to that instead of inventing a VM and a bytecode language to go with it, but the former means it couldn't be thread safe while the latter means introducing another dependency, which I didn't necessarily want to do if other people were interested in this becoming a part of Orx.

    So those are my thoughts on it, basically adding a dedicated runtime variable structure to orxObjects, and implementing what amounts to Excel on top of that and wiring it to config. Any thoughts on how I would go about doing that, while still respecting the behavior currently in orxConfig (inheritance, random number generation, commands, etc.), and if anyone is interested in seeing it added to Orx itself?

  • edited February 24

    Thanks for the detailed explanation, now I can frame the whole system better in my head.

    As you've mentioned, the config system isn't meant to host live variables, though it can be done in some cases for convenience sake, not only as with the Runtime examples you've seen earlier, but any section can be used too.
    For example, ScrollEd will keep all the live, serializable objects updated in config, which will then be used to serialize the map to disk and load it later on.

    The case you exposed, regarding the HP update, is a bit more tricky in the sense that this formula can't be used for the variable itself, as it's based on the former value of the variable, ie. hp = hp + regen * dt needs to be stored in a separate entry than hp itself.

    So, leaving the syntax bit aside for now, which can be improved by the mean of a custom command that would then interpret your DSL, I can think of a couple options that would already work in the current state.

    One way to do this, would be to simply have a dedicated section for the runtime object (one could use the object's GUID for its name, for example), which would inherit from the template section used to build the object in the first place. This way you'd also inherit from all the initial state of all your variables.

    Then, regarding the formulas, I can think of two separate use case:

    • a formula that doesn't need the variable's former value, and which could be simply executed, let's take damage output for example, based on the current weapon's damage and a class multiplier
    • a formula that does require its former value, as in the HP regen, in which case we'd store its key in a list that would get peaked once per frame

    So at first we'd have the character's template in config, and its original weapon:

    [Fighter]
    HP = 100
    Weapon = Broadsword
    DamageMultiplier = 0.5
    
    [Broadsword]
    Damage = 5
    

    Once created, we'd also create a "runtime" section using the object's GUID, and inheriting from the template section:

    orxOBJECT *fighter = orxObject_CreateFromConfig("Fighter");
    orxCHAR buffer[20] = {};
    orxString_NPrint(buffer, sizeof(buffer) - 1, "0x%016llx", orxStructure_GetGUID(fighter));
    orxConfig_SetParent(buffer, orxObject_GetName(fighter));
    

    Note that you'd probably want to extract the GUID printing code, merge it with the config push and wrap it into something like orxObject_PushRuntimeSection(orxOBJECT *) as we're going to use it all the time.

    Now reading/writing in the GUID section will use the default values from the template section but will override live values when need be.

    For example, we'd have the damage based on the weapon's one and a multiplier.
    As we're still ignoring the syntax aspect for now, we'll use simple commands to express the relation.
    Completing the Fighter section, we'd have had something like:

    [Fighter]
    Damage = % > @, > Get < DamageMultiplier, > @, > Get < Weapon, > Get < Damage, * < <
    

    The @ command will get the current section but it works with inheritance. That means when used at runtime, it won't return Fighter but the object's GUID, as the current section. This also means that we're going to retrieve the current Weapon, not the original one, if that has changed since the object's creation.

    In code, we'd have:

    orxString_NPrint(buffer, sizeof(buffer) - 1, "0x%016llx", orxStructure_GetGUID(fighter));
    orxConfig_PushSection(buffer);
    orxFLOAT damage = orxConfig_GetFloat("Damage"); // <- That's where the weapon and the multiplier will be retrieved and combined
    orxConfig_PopSection();
    

    Now for the second type of variables, the ones that are updated every update, we'd store them in a FormulaList. We'd thus have something like:

    [Character]
    FormulaList = RegenFormula
    
    [[email protected]]
    Regen = 1.5 ; Assuming constant dt, that's the value incremented per update, to simplify the example formula below for visibility purposes
    RegenFormula = % >> @, > Get < HP, > @, > Get < Regen, > + < <, Set < HP <
    

    As you can see there's no clamping on the value of HP in the formula either, it's simply to show an example and the command syntax is definitely not the most suitable for this kind of use.

    Then in code, once per update, you'd have something like:

    orxString_NPrint(buffer, sizeof(buffer) - 1, "0x%016llx", orxStructure_GetGUID(fighter));
    orxConfig_PushSection(buffer);
    for(orxS32 i = 0, iCount = orxConfig_GetListCount("FormulaList");
        i < iCount;
        i++)
    {
      // Fetching the current formula
      const orxSTRING formula = orxConfig_GetListString("FormulaList", i);
    
      // Applying it
      orxConfig_GetString(formula);
    }
    orxConfig_PopSection();
    

    Of course everything would be more palatable with a DSL instead, which you could either apply yourself or let the lazy command evaluation do it for you by simply defining a Solve custom command. In which case we'd have something like:

    [Fighter]
    HP = % Solve "Weapon.Damage * DamageMultiplier"
    RegenFormula = % Solve "HP = HP * Regen"
    

    Lastly, if you were to use Scroll instead of just vanilla Orx, you wouldn't have to use the GUID at all as all objects are assigned a runtime name that can be directly pushed in config (it's often used):

    At creation, parenting the runtime/instance section with the template one:

    ScrollObject *fighter = CreateObject("Fighter");
    orxConfig_SetParent(fighter->GetName(), fighter->GetModelName());
    

    And to retrieve a property:

    fighter->PushConfigSection(orxTRUE); // <- orxTRUE here means we want to push the "instance" section and not the "template" one
    orxFLOAT damage = orxConfig_GetFloat("Damage");
    fighter->PopConfigSection();
    
  • edited February 26
    I've thought about it a bit, and I like the idea of storing the values according to GUID (didn't consider Scroll for this since I would like full compatibility with base Orx), but on its own doesn't quite work for mutually referential updates. Using regen as an example again, assume we have these formulas (excuse the formatting, I'm on mobile at the moment):

    regen_hp = Max(base_regen_hp, ((max_hp - hp) / 5) - (regen_hp / 2))
    hp = hp + regen_hp

    We also have this beginning state:
    [Fighter]
    hp = 100
    max_hp = 100
    base_regen_hp = 1
    regen_hp = 1

    After the fighter takes 90 damage, but before any updates kick in, the state looks like this:
    [Fighter]
    hp = 10
    max_hp = 100
    base_regen_hp = 1
    regen_hp = 1

    Depending on the formula evaluation order, the next 2 states of the fighter, assuming no changes other than regen occur, would be vastly different.

    Next 2 states if hp is evaluated first:
    [Fighter]
    hp = 11
    max_hp = 100
    base_regen_hp = 1
    regen_hp = 17.3

    [Fighter]
    hp = 28.3
    max_hp = 100
    base_regen_hp = 1
    regen_hp = 5.69

    If regen_hp is evaluated first:
    [Fighter]
    hp = 27.5
    max_hp = 100
    base_regen_hp = 1
    regen_hp = 17.5

    [Fighter]
    hp = 28.5
    max_hp = 100
    base_regen_hp = 1
    regen_hp = 1

    This example is unlikely, but it's to show the behavior of the system at an edge case. In order to allow consistent evaluation order with an arbitrary set of variables, it would need to copy the current state beforehand to do proper calculations, which with the example the next 2 states would look like this:
    [Fighter]
    hp = 11
    max_hp = 100
    base_regen_hp = 1
    regen_hp = 17.5

    [Fighter]
    hp = 28.5
    max_hp = 100
    base_regen_hp = 1
    regen_hp = 1

    Again, though a configuration like this is unlikely, the rules for the DSL should be consistent. I'm thinking in order to do that I'd have to either copy all of the string representations of everything beforehand to another temporary config section, or edit the orxConfig C and header files to add support for getting a read-only copy of the current section state and duplicate the config helpers to work with it outside of the config file. The former would require a lot more config push/pop operations since it would need to read from one section and write to another for every formula, while the latter I wanted to get permission first to create a branch and mess around with the internals to make this work. So far I've just been working in a fresh project and logging the output. I'll create a repo after work and post the link.
  • Here's the repo with my progress so far, it's a little messy, especially with comments, but it will build as long as you generate the project files using premake.
    https://github.com/pschall42/calc_graph

  • @krypto42 said:
    I've thought about it a bit, and I like the idea of storing the values according to GUID (didn't consider Scroll for this since I would like full compatibility with base Orx), but on its own doesn't quite work for mutually referential updates. Using regen as an example again, assume we have these formulas (excuse the formatting, I'm on mobile at the moment):

    regen_hp = Max(base_regen_hp, ((max_hp - hp) / 5) - (regen_hp / 2))
    hp = hp + regen_hp

    Those formulae, however, break the predicate of working with a DAG as they introduce a cycle (regen_hp->hp->regen_hp), hence the issue you mentioned.

    As far as I can tell, if you truly work with a DAG, there shouldn't be any such issue.

    I'll check your repo over next weekend as I'm quite sick at the moment, thanks for the link.

  • Sorry about not getting back to you for awhile, things have been a little hectic lately, and I've been putting off working on this. I've created a fork of orx locally, and I'm thinking of using the orxCOMMAND_VAR structs internally for the solver values, but I'm having trouble figuring out how they work, mainly due to the orxCOMMAND_VAR_TYPE enum. Inspecting things in C is a little clunkier and a lot slower than I'm used to working with Ruby, so far all I've figured out is that the Numeric type is the result doing a math operation, and that any number literals always give the String type, so I don't see how a command variable would ever get Float, U32, S64, etc. types. Can you explain how it works exactly, in C that is?

  • No worries for the delay!

    As you've already noticed orxCOMMAND_VAR is a simple struct with an union that can contain a variable of different type, which is stored in the eType field.

    When evaluating a command, we simply check the command's signature and try to convert the strings accordingly (it happens in the big switch case inside orxCommand.c, line 800). We then replace its string value to its actual type after conversion, in situ.

    Another example is the function orxCommand_ParseNumericalArguments which only handles vectors, floats and uint64s. It takes a list of literal variables and converts them into another list after trying to guess their type (checking first for the syntax of a vector, then uint64 (hexa, octal, binary) and finally going to float if none of the above matches.

    All in all, there's nothing automated about this process in the structure itself, it's a plain old data structure that only holds a single value and its type.

  • So what happens is that every value starts out as the String type, and keeps that value until it is being processed, where it then writes the parsed union value and the new type if it matches the pattern it's searching for, like a vector, integer or float. Then when the arguments are satisfied, it tries to execute the command function with those arguments and assigns the result the type you declare it should have, Numeric in the case of almost all of the math functions, and stores the result as a string instead of as a number value. Does that sound right or am I off a bit?

    If that's the case, the part I was getting tripped up on was only parsing the value at evaluation time then immediately writing the result back as a string instead of a number. Then I could just extract out that switch statement to parse values into it's own function, then use that to compile any numerical values ahead of time.

    So where exactly does the orxCOMMAND_VAR_DEF struct fit in? In my use case I'm thinking I would use it as a stand in for those variables like max_hp, though I'm not entirely sure if that's what it is actually for.

  • edited March 24

    Yes, that's the gist of it.

    orxCOMMAND_VAR_DEF is used to define the variable as part of a command prototype. It's basically just a name and a type used when registering commands, cf. following helper macro:

    /** Command registration helpers
     */
    #define orxCOMMAND_REGISTER_CORE_COMMAND(MODULE, COMMAND, RESULT_NAME, RESULT_TYPE, REQ_PARAM_NUMBER, OPT_PARAM_NUMBER, ...)                                    \
    do                                                                                                                                                              \
    {                                                                                                                                                               \
      orxCOMMAND_VAR_DEF  stResult;                                                                                                                                 \
      orxCOMMAND_VAR_DEF  astParamList[REQ_PARAM_NUMBER + OPT_PARAM_NUMBER + 1] = {{"Dummy", orxCOMMAND_VAR_TYPE_NONE}, __VA_ARGS__};                               \
      orxSTATUS           eStatus;                                                                                                                                  \
      stResult.eType    = RESULT_TYPE;                                                                                                                              \
      stResult.zName    = RESULT_NAME;                                                                                                                              \
      eStatus           = orxCommand_Register(#MODULE"."#COMMAND, &orx##MODULE##_Command##COMMAND, REQ_PARAM_NUMBER, OPT_PARAM_NUMBER, &astParamList[1], &stResult);\
      orxASSERT(eStatus != orxSTATUS_FAILURE);                                                                                                                      \
    } while(orxFALSE)
    
  • Ok, so it's not exactly what I thought it was.

    I'll take a look at using this and see what I can do. Thanks for the info!

  • My pleasure. Don't hesitate if you have other questions.

Sign In or Register to comment.