A more elegant way to write decision making code which evaluates multiple inputs with different priorities?

Question

I'm writing some decision-making AI for a game, and I've come up with the following piece of code.

if(pushedLeft && leftFree && leftExists)
    GoLeft();
else if(pushedRight && rightFree && rightExists)
    GoRight();
else if(leftFree && leftExists)
    GoLeft();
else if(rightFree && rightExists)
    GoRight();
else if(pushedLeft && leftExists)
    GoLeft();
else if(pushedRight && rightExists)
    GoRight();
else if(leftExists)
    GoLeft();
else if(rightExists)
    GoRight();
// else do nothing...

That's a pretty long stream of if statements, with similar conditionals!

Note that it makes this nice pattern:

L1 L2 L3  -> L
R1 R2 R3  -> R
   L2 L3  -> L
   R2 R3  -> R
L1    L3  -> L
R1    R3  -> R
      L3  -> L
      R3  -> R
(nothing) -> 0

The aim of this code is to decide whether the object should move left or right (or not at all), based on some incoming state information. Each piece of information has a different priority. I could write it in an ordered list like this:

Highest Priority
----------------
Don't ever move into an invalid space
Prefer to move into an unoccupied space
Prefer to move in the push direction
Prefer to move left
----------------
Lowest Priority

It seems obvious that adding additional information inputs upon which to make this decision will double the number of conditionals. And doubling the number of potential values for those inputs (eg: allowing up/down/left/right) will double the number of conditionals as well. (So this is n×m² conditionals, right?)

So my question is:

Is there a nice, satisfying, elegant way to code this?

I'm thinking that there must be a nice "n×m" way to do it (edit: I had "n+m" here originally, but that seems impossible as there are n×m input conditions). Something that is applicable to both my code here, and to the problem in general?

Preferably something that will perform just as well or better than the conditional version above. Ideally something that avoids heap allocations - important for use in game development scenarios (although these can always be optimised away with caching and the like, if necessary).

And also: Are there any "Googleable terms" for this problem? I suspect that this is not an uncommon problem - but I don't know of a name for it.

---

Update: An idea thanks to Superpig's answer, is to calculate a score for the various options. Something like this:

int nothingScore = 1 << 4;
int leftScore = (1 << 1) + (pushedLeft ? 1 << 2 : 0) + (leftFree ? 1 << 3 : 0) + (leftExists ? 1 << 5 : 0);
int rightScore = (pushedRight ? 1 << 2 : 0) + (rightFree ? 1 << 3 : 0) + (rightExists ? 1 << 5 : 0);

There's certianly a nicer way to write the scoring code (and alternate ways to score it, too). And then there's still the matter of selecting what to do once the score is calculated. And, of course, there may be a better method entirely that doesn't involve scoring.

---

Update 2: I've posted and accepted my own answer here (because Superpig's isn't a complete solution, and so far no other answer is even remotely on the right track). Rather than scoring the various outputs, I've chosen an option-elimination approach using a bit-field. This allows a decision to be made using only a single integer for memory.

Answer 1

This is essentially a classification problem; you want something like a decision tree (or behaviour tree). You're trying to take a bunch of discrete inputs for the situation (validity, freeness, push direction, etc) and classify the result as "up, down, left or right."

I suspect that if you want something of greater or equal performance to the long chain of if statements - at least in terms of instruction count / number of comparisons done - then you will have to make your comparisons in the manner you're doing there. Approaches like calculating a score for all directions and then checking the maximum, or recursively partitioning a list of moves into preferred and non-preferred, will all end up doing more work than a pure comparison sequence.

You could just build a lookup table, I think. You've got 4 bits indicating whether a direction is valid, 4 bits indicating whether a direction is occupied, and 2 bits indicating the push direction, for 10 bits in total - so that's 1024 different situations, and the behaviour in each one can be described with just 2 bits (so, 1 byte) - making the total table size 1024 bytes.

A single entry would be a structure like this:

union DecisionSituation
{
    unsigned short Index;
    struct
    {       
        bool ValidLeft : 1;
        bool ValidRight : 1;
        bool ValidUp : 1;
        bool ValidDown : 1;
        bool OccupiedLeft : 1;
        bool OccupiedRight : 1;
        bool OccupiedUp : 1;
        bool OccupiedDown : 1;
        Direction PushDirection : 2; 
    } Flags;
}

You'd describe your situation by filling out the flags in that structure, and then reading the 'Index' value to get your lookup table index.

Edit: Also, regarding your scoring function, because you're doing strict bit-patterns, I think you can skip all the ternary operators:

int leftScore = (leftExists << 4) | (leftFree << 3) | (pushedLeft << 2) | 1;
int rightScore = (rightExists << 4) | (rightFree << 3) | (pushedRight << 2) | 0;

// Find the highest scoring direction here

// If none of the scores are at least (1 << 4) it means none of them existed
if(highest score < (1 << 4)) return nothing;

// otherwise just return the highest scoring direction

Answer 2

The most important thing is to have the code that declares what the inputs are and their relative priorities be simple, short and elegant. Here is one way to write that code:

PreferencedDecisionMaker pdm = new PreferencedDecisionMaker();
pdm.Push(false, leftExists, rightExists, upExists, downExists);
pdm.Push(0);
pdm.Push(false, leftFree,   rightFree,   upFree,   downFree  );
pdm.Push(false, pushedLeft, pushedRight, pushedUp, pushedDown);
pdm.Push(1);
switch(pdm.Decision)
{
    case 1: GoLeft();  break;
    case 2: GoRight(); break;
    case 3: GoUp();    break;
    case 4: GoDown();  break;
}

Here the inputs are declared in essentially a tabular format. The priority of each input is defined by the ordering of the rows. Each column corresponds to a possible output.

The "complexity" of this code is n×m.

(Although I've used indentation to make this look like a table, more complicated input conditions won't allow each row to exist neatly on a single line. This doesn't matter: the important bit is that there are only n×m declarations. Being able to make it look like a table when the conditions are short is just a nice bonus.)

Less important is the actual behind-the-scenes code to make the decision (the PreferencedDecisionMaker type). There are a few ways to calculate the best output decision based on priority. Superpig suggested scoring, which is good. But I've ended up going for an option-elimination approach using a bit-field. I've posted my code for this below.

Using a bit-field has the big advantage of not needing to allocate heap memory for arrays. The only downside is that it's limited to 32 options.

The following code hasn't been thoroughly tested. And I haven't filled out all 32 versions of the Push method. It uses a mutable struct, which is "naughty" - converting it to an immutable struct should be straightforward. Or you could make it a class - but then you lose the benefit of avoiding heap allocation.

struct PreferencedDecisionMaker
{
    private uint availableOptionsBits;

    private static readonly int[] MultiplyDeBruijnBitPosition = {
        0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
        31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
    };

    public int Decision
    {
        get
        {
            uint v = availableOptionsBits;

            // Find position of lowest set bit in constant time
            // http://stackoverflow.com/a/757266/165500
            return MultiplyDeBruijnBitPosition[((uint)((v & -v) * 0x077CB531U)) >> 27];
        }
    }

    private void InternalPush(uint preference)
    {
        if(availableOptionsBits == 0)
            availableOptionsBits = preference;
        else
        {
            uint combinedBits = availableOptionsBits & preference;
            if(combinedBits != 0)
                availableOptionsBits = combinedBits;
        }
    }

    public void Push(int option)
    {
        if(option < 0 || option >= 32) throw new ArgumentOutOfRangeException("Option must be between 0 and 31");
        InternalPush(1u << option);
    }

    // ... etc ...
    public void Push(bool p0, bool p1, bool p2, bool p3, bool p4) { InternalPush((p0?1u:0u) | ((p1?1u:0u)<<1) | ((p2?1u:0u)<<2) | ((p3?1u:0u)<<3) | ((p4?1u:0u)<<4)); }
    // ... etc ...
}