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 ...
}

Answer 3

When you have a bunch of if statements, usually they can be refactored using polymorphism combined with the state pattern:

As an introduction, please watch the following video from Misko Hevery (you will love it)

http://www.youtube.com/watch?v=4F72VULWFvc&feature=player_embedded#!

This is a summary from the presentation:

Most if's can be replaced by polymorphism (subclassing)

This is desirable because:

• Functions without ifs are easier to read than with ifs
• Functions without ifs are easier to test
• Related branches of ifs end up in the same subclass

Use Polymorphism (Subclasses)

• If you are checking an object should behave differently based on its state
• If you have to check the same if condition in multiple places

Use if

• Bounds checking primitive objects (>,<, ==, !=)
• ... other uses but today we focus on avoiding if

Polymorphic solution is often better because

• New behavior can be added without having the original source code
• Each operation / concern is separated in a separate file
• Makes it easy to test / understand

EDIT

At first sight using the state pattern with polymorphism, the solution would look more complex because it implies you will need more classes than before, but the trade-off is much much better, as long as you start writing tests for this kind of code you will find that's easier to test, easier to read and understand, and therefore, easier to maintain and extend (right now you just posted about movement to the right or left, but imagine if later you need to move up and down, if you do not refactor your code now, adding new functionality will be a real PITA)

You would have something like:

// represents the current position
class MyClass
{
  public int X;
  public int Y;
}
abstract class NodeMoving
{
   abstract void Move();
   abstract bool IsValid(MyClass myclass);
}
abstract class NodeMovingLeft : NodeMoving
{
   override void Move()
   {
      // add code to move left
      if(this.IsValid(MyClass myclass))
      {
         // move
      }
   }
}
abstract class NodeMovingRight : NodeMoving
{
   override void Move()
   {
      // add code to move right
      if(this.IsValid(MyClass myclass))
      {
         // move
      }
   }
}
// and then start modeling the different states
class RightFree : NodeMovingRight
{
   override bool IsValid(MyClass myclass)
   {
      // add condition to validate if the right is free
   }
}
// combining conditions
class PushedLeft : NodeMovingLeft
{
   override bool IsValid(MyClass myclass)
   {
      // code to determine if it has been pushed to the left
   }
}
class LeftFree : PushedLeft
{
   override bool IsValid(MyClass myclass)
   {
      // get condition to indicate if the left is free
      var currentCondition = GetCondition();
      // combining the conditions
      return currentCondition && base.IsValid(myClass);
   }
}

You will need to add the properties needed in order to calculate the conditions and perform the movement

It's worth to note how small the methods are, (yes you will have more than before) but they can be tested in isolation really easy

Edit 2 -- adding priority

Well now that we have a simple state machine, we need to evaluate the priorities, one way to do it (and I would like to hear ways to improve it) is by using a priority queue:

http://www.codeproject.com/Articles/13295/A-Priority-Queue-in-C

It would look something like:

    // you could place the priorities in a service to reuse it
    var priorities = new HashSet<NodeMoving>();

    priorities.Add(new RightExists());
    priorities.Add(new PushedLeft());

    var currentPosition = new MyClass { X = 1, Y = 2 };

    foreach (var priority in priorities)
    {
        if (priority.IsValid(currentPosition))
        {
            priority.Move();
            break;
        }
    }

    // output is: RightExists

    // now changing the priority order
    foreach (var priority in priorities.Reverse())
    {
        if (priority.IsValid(currentPosition))
        {
            priority.Move();
            break;
        }
    }

    // output is: PushedLeft

Answer 4

Use the state pattern. Draw a state diagram that contains all your different states and the allowed transitions between them. When you code it have a state subclass for each node. Each state node / class will decide on the inputs and make drive the appropriate transition to the next allowed state. I don't think you can avoid the multiplicity of states you mention.

Answer 5

Would this not work:

if(!leftExists) {
    if(rightExists) {
        GoRight();
    } else {
        // Panic!
    }
} else if(!rightExists) {
    GoLeft();
} else if(rightFree || leftFree && !(rightFree && leftFree)) {
    if(rightFree) {
        GoRight();   
    } else {
        GoLeft();
    }
} else if(pushedRight) {
    // Assumption: pushedLeft and pushedRight cannot both be true?
    GoRight();
} else {
    // PushedLeft == true, or we just prefer to move left by default
    GoLeft();
}   

Right now, it is a similar amount of code, but the difference being that we've eliminated the common conditions, so adding additional conditions no longer affects each branch - just insert it at the desired priority.

Answer 6

I'd stick with a modification of your solution.

Have you thought about making GoLeft into a function which also return whether or not left exists? Unless it's a complicated function, and you are calling this a LOT and testing shows that it needs to be optimized, that's what I'd do.

If you do that, then this becomes the following. It's basically what you're doing, but easier to read.

I'm sure I'll get downvotes for this since it's not OO and doesn't use the command pattern, but it does answer the question, and it is easy to read ;) For a more complicated problem, I'd think about using those answers, but for this particular problem, I would stick with a simple answer.

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

Answer 7

To get a grip on this, i recommend the following measures:

1. decide which of the statements that are combined in the if statements weigh more

2. untangle the if statements, resulting in nested if statements like

   if (moveRight) 
   {
       if (pushedleft)
       {
           /// ...
       }
   }
   

3. when you have this, start packing all condidional logic into methods, e.g. HandleMoveRight

4. having done this, you can start extracting classes, ending up in a command pattern.

Now you have no more problems in adding extra functionality and complexity is flat.

Answer 8

I think the state pattern is the right approach as recommended by @john2lob. You also want some sort of decision tree approach to the determine the next transition on actions of the events 'push' / 'free' / 'exists'. BTW: what's the difference between 'free' and 'exists'?