1
\$\begingroup\$

I have a system where I'm sifting through a large number and variety of objects in my game, looking for objects that match an arbitrary search criteria that can be simple or complex.

For example, suppose a Foo has three integer properties, A, B, and C. I might search the list of Foo objects three times. First, I want to find a Foo where A>5. Second, I might want to find a Foo where A<B or B=8. Third, I might want to find a Foo where A=2, B=6, C>A, and C<B. The point is that I could arbitrarily pass any of a very wide set of conditions into the search.

Now here's my problem. In all cases, if I can't find an item that matches these criteria, I want to create a new Foo that does match, and add it to the list of Foo objects.

The thing I'm wrestling with is figuring out an underlying system of representing conditions that allows me to then create an item that directly matches those conditions. So far I've got two ideas, neither of which I'm a fan of:

  • Repeatedly generate random Foo objects across the span of possible properties, until applying the criteria to one of them results in true. Given the possible permutations involved, this feels like an absolute performance nightmare, and would probably require a ton of caching logic to track what possibility spaces have already been tried.
  • Establish a list of individual conditions with isolated variables (such as a GreaterThan condition with the referenced property that indicates whether the property is A, B, or C; and the target value) and create a corresponding declaration (Make [property] a random value between [targetValue] and [propertyMax]). Not only is this incredibly tedious, but I'm also not really confident I understand how it would work, particularly in C# but more generally also. This feels like self-reading code and that's something I have no experience with.

My question is, basically, what designs and techniques can I use to address this sort of issue - the need to create objects that match criteria, when those criteria could be arbitrary? Surely this has come up in other projects. What kinds of constraints or frameworks are applied to make this doable?

\$\endgroup\$
8
  • \$\begingroup\$ How do you want to handle impossible criteria? Is it prevented already on input validation or does your algorithm need to detect it itself? (like a<b, b<c, c<a) \$\endgroup\$ Commented Feb 15, 2021 at 19:24
  • \$\begingroup\$ That's a very good question! Currently I don't detect it; since I have direct control over the criteria, I've just been proofreading them, but that's an increasingly less sustainable approach as the project grows. Having the criteria fail during search, whether impossible or not, is fine. But creating an object from criteria, which is the new thing I'm working on, is obviously bad if the criteria are impossible! I would want to be able to know when I'm creating an object that it's failing the criteria and throw an assert so I can investigate. \$\endgroup\$ Commented Feb 15, 2021 at 19:32
  • \$\begingroup\$ This makes me think that some kind of block-by-block approach to the criteria is called for. I may want to step through each of A<B, B<C, and C<A, and detect at the point of C<A that it is impossible to perform the setting of values without breaking a previous condition. \$\endgroup\$ Commented Feb 15, 2021 at 19:34
  • \$\begingroup\$ The problem sounds not that hard. All you need to do is sort the input from small to big. Given the example A=2, B=6, C>A, and C<B you get a, c, b. Set your fixed values -> 2, c, 6. Now all you need is a random in range of (2+1, 6-1). In case you have only a, b, c and nothing fixed, random would look like a = (0, maxValue - countFollowElements), b= (a+1, maxValue -countFollowElements - 1) etc \$\endgroup\$ Commented Feb 15, 2021 at 19:36
  • \$\begingroup\$ Ah - the example integer properties of A, B, and C are just illustrative, and so are the conditions of <, >, =. In reality I'm dealing with item properties in a game, so the conditions are more like "Item is in Bob's house", "Item is a Book", "Item is worth 500 coin or more". These may be less liable to direct contradition, which might be why I haven't thought of it much, but contradictions aren't impossible - I might for example end up with "Item is in Bigtown" and "Item is held by Bob" when Bob is in Smallville rather than Bigtown. \$\endgroup\$ Commented Feb 15, 2021 at 19:48

1 Answer 1

Reset to default
2
\$\begingroup\$

As luck would have it, a colleague recently showed me a project called CatSAT, which seems to do exactly what you're looking for.

CatSAT is a declarative language embedded in C# that makes it easy to write simple procedural content generators for games, such as character generators, enemies, etc. Being declarative means you tell it the space of possibilities for the generated objects, along with whatever constraints (requirements) you want to apply to them, and the system will automatically find random instances that satisfy the constraints without you having to write a specialized generator algorithm.

As an example of the kind of thing it does:

As a simple example, suppose we want to generate a party of 3 non-player characters. Characters have:

  • Three possible races (human, electroid, insectoid)
  • Four possible classes (fighter, magic user, cleric, thief).
  • Humans additionally have one of 3 possible nationalities
  • Clerics have one of 4 possible religions.

In addition, there are constraints on the possible solutions:

  • Party members should have different classes.
  • Electroids can’t be clerics.
  • One of the religions is outlawed in one of the nations
  • Another religion is mandatory in one of the other nations.

This can be written as a 17-line ASP program.

CatSAT can then take this statement of the problem in an Answer Set Programming -like dialect and stochastically sample possible parties that meet all of these constraints, by providing valid assignments of values to the variables of "party member 1 race, party member 1 class, etc..."

You can read the paper describing the problem domain and CatSAT's approach here. The full C# source code and a precompiled DLL compatible with Unity are available for free, and under a permissive license that lets you use it in your own commercial projects.

\$\endgroup\$
1
  • \$\begingroup\$ Fascinating! This definitely sounds like it's on the track I'm looking for. Great timing. And it was made for ProcJam, too, a jam I love. Thank you so much - I will definitely read the paper to try to wrap my head around the problem domain more fully, since I don't feel I have a clear grasp on it yet. \$\endgroup\$ Commented Feb 15, 2021 at 19:52

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.