c# - 一种更优雅的方式来编写评估具有不同优先级的多个输入的决策代码？

Question

我正在为游戏编写一些决策 AI，并且我想出了以下代码。

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

这是一个相当长的if语句流，具有类似的条件！

请注意，它使这个很好的模式：

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

这段代码的目的是根据一些传入的状态信息来决定对象应该向左还是向右（或根本不）移动。每条信息都有不同的优先级。我可以将它写在这样的有序列表中：

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

很明显，添加额外的信息输入来做出这个决定将使条件的数量增加一倍。并且将这些输入的潜在值的数量加倍（例如：允许上/下/左/右）也将使条件句的数量加倍。（所以这是 n×m ^{2 个}条件，对吧？）

所以我的问题是：

有没有一种很好的、令人满意的、优雅的编码方式？

我认为必须有一个很好的“n×m”方式来做到这一点（编辑：我最初在这里有“n+m”，但这似乎是不可能的，因为有 n×m 输入条件）。适用于我的代码和一般问题的东西？

最好是与上面的条件版本一样好或更好的东西。理想情况下避免堆分配的东西 - 对于在游戏开发场景中使用很重要（尽管如果需要，这些总是可以通过缓存等进行优化）。

还有：这个问题是否有任何“Googleable 条款”？我怀疑这不是一个罕见的问题 - 但我不知道它的名称。

更新：感谢Superpig 的回答，一个想法是计算各种选项的分数。像这样的东西：

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);

肯定有更好的方法来编写评分代码（以及其他评分方法）。然后仍然是计算分数后选择做什么的问题。而且，当然，可能有更好的方法完全不涉及评分。

更新 2：我在这里发布并接受了我自己的答案（因为Superpig的不是一个完整的解决方案，到目前为止，甚至没有其他答案在正确的轨道上）。我没有对各种输出进行评分，而是选择了一种使用位域的选项消除方法。这允许仅使用单个整数作为内存来做出决定。

score 7 · Accepted Answer

这本质上是一个分类问题；您想要决策树（或行为树）之类的东西。您正在尝试为情况（有效性、自由度、推动方向等）获取一堆离散输入，并将结果分类为“上、下、左或右”。

我怀疑，如果您希望长链 if 语句具有更好或相同的性能 - 至少在指令数/完成的比较次数方面 - 那么您将不得不以您在那里进行的方式进行比较。计算所有方向的分数然后检查最大值，或递归地将移动列表划分为首选和非首选等方法，最终都会比纯粹的比较序列做更多的工作。

我认为你可以建立一个查找表。你有 4 位指示方向是否有效，4 位指示方向是否被占用，2 位指示推送方向，总共 10 位 - 所以这是 1024 种不同的情况，每种情况下的行为可以是仅用 2 位（因此，1 字节）描述 - 使总表大小为 1024 字节。

单个条目将是这样的结构：

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

您可以通过填写该结构中的标志来描述您的情况，然后读取“索引”值以获取查找表索引。

编辑：另外，关于你的评分功能，因为你正在做严格的位模式，我认为你可以跳过所有的三元运算符：

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

score 4 · Accepted Answer

最重要的是让声明输入内容及其相对优先级的代码简单、简短且优雅。这是编写该代码的一种方法：

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

这里的输入基本上以表格格式声明。每个输入的优先级由行的顺序定义。每列对应一个可能的输出。

这段代码的“复杂度”是 n×m。

（虽然我使用缩进让它看起来像一个表格，但更复杂的输入条件不允许每一行整齐地存在于一行上。这没关系：重要的是只有 n×m声明。能够在条件很短的情况下使它看起来像一张桌子只是一个不错的奖励。）

不太重要的是做出决定的实际幕后代码（PreferencedDecisionMaker类型）。有几种方法可以根据优先级计算最佳输出决策。Superpig建议评分，这很好。但我最终选择了一种使用位域的选项消除方法。我已经在下面发布了我的代码。

使用位域的一大优势是不需要为数组分配堆内存。唯一的缺点是它仅限于 32 个选项。

以下代码尚未经过彻底测试。而且我还没有填写所有 32 个版本的Push方法。它使用可变结构，这是“顽皮的” - 将其转换为不可变结构应该很简单。或者你可以把它变成一个类——但是你会失去避免堆分配的好处。

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

score 3 · Accepted Answer

当你有一堆if语句时，通常可以使用多态性结合状态模式来重构它们：

作为介绍，请观看 Misko Hevery 的以下视频（你会喜欢的）

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

这是演示文稿的摘要：

大多数 if 可以被多态性（子类化）替换

这是可取的，因为：

没有 ifs 的函数比 ifs 更容易阅读
没有 if 的函数更容易测试
ifs 的相关分支最终在同一个子类中

使用多态性（子类）

如果您正在检查对象应根据其状态表现不同
如果您必须在多个地方检查相同的 if 条件

使用如果

边界检查原始对象 (>,<, ==, !=)
... 其他用途，但今天我们专注于避免 if

多态解决方案通常更好，因为

无需原始源代码即可添加新行为
每个操作/关注点都分隔在一个单独的文件中
易于测试/理解

编辑

乍一看，使用具有多态性的状态模式，解决方案看起来会更复杂，因为这意味着您将需要比以前更多的类，但是权衡要好得多，只要您开始为这种代码编写测试，您会发现它更容易测试，更容易阅读和理解，因此更容易维护和扩展（现在你刚刚发布了关于向右或向左移动，但想象一下，如果你以后需要上下移动，如果你这样做了现在不重构您的代码，添加新功能将是一个真正的 PITA）

你会有类似的东西：

// 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);
   }
}

您将需要添加所需的属性以计算条件并执行移动

值得注意的是这些方法有多小（是的，您将拥有比以前更多的方法），但它们可以很容易地单独测试

编辑 2 - 添加优先级

现在我们有一个简单的状态机，我们需要评估优先级，一种方法（我想听听改进它的方法）是使用优先级队列：

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

它看起来像：

    // 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

score 2 · Accepted Answer

使用状态模式。绘制一个状态图，其中包含所有不同的状态以及它们之间允许的转换。当您编写代码时，每个节点都有一个状态子类。每个状态节点/类将决定输入并使驱动器适当地转换到下一个允许的状态。我认为您无法避免您提到的多个州。

score 1 · Accepted Answer

这行不通：

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();
}

现在，它是相似数量的代码，但不同之处在于我们已经消除了常见的条件，因此添加额外的条件不再影响每个分支 - 只需将其插入所需的优先级。

score 1 · Accepted Answer

我会坚持修改您的解决方案。

你有没有想过把 GoLeft 变成一个函数，它也返回 left 是否存在？除非它是一个复杂的函数，并且你经常调用它并且测试表明它需要优化，否则我会这样做。

如果你这样做，那么这将变成以下内容。这基本上就是你正在做的事情，但更容易阅读。

我敢肯定我会对此投反对票，因为它不是面向对象且不使用命令模式，但它确实回答了问题，并且易于阅读；）对于更复杂的问题，我会考虑使用这些答案，但对于这个特定问题，我会坚持一个简单的答案。

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

score 0 · Accepted Answer

为了解决这个问题，我建议采取以下措施：

决定 if 语句中组合的哪些语句更重

解开 if 语句，导致嵌套 if 语句，如

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

当你有这个时，开始将所有条件逻辑打包到方法中，例如 HandleMoveRight
完成此操作后，您可以开始提取类，以命令模式结束。

现在您在添加额外功能时不再有任何问题，而且复杂性是平的。

score 0 · Accepted Answer

我认为状态模式是@john2lob 推荐的正确方法。您还需要某种决策树方法来确定事件“推送”/“自由”/“存在”的动作的下一个转换。顺便说一句：“免费”和“存在”有什么区别？

c# - 一种更优雅的方式来编写评估具有不同优先级的多个输入的决策代码？

8 回答 8

Related

Reference