编写决策代码的更优雅的方法是评估具有不同优先级的多个输入？

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输入条件).什么东西适用于我的代码,以及一般的问题？

优选地,某些东西的表现与上述条件版本一样好或更好.理想情况下,可以避免堆分配 - 这对于在游戏开发场景中使用很重要(尽管如果需要,这些可以通过缓存等进行优化).

还有:这个问题有"可谷歌的术语"吗？我怀疑这不是一个不寻常的问题 - 但我不知道它的名字.

---

更新:感谢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的不是一个完整的解决方案,至今没有其他的答案,甚至远程正确的轨道上).我没有对各种输出进行评分,而是选择了使用位域的选项消除方法.这允许仅使用单个整数作为存储器来做出决定.

Answer 1

这基本上是一个分类问题; 你想要一个像决策树(或行为树)的东西.你试图为这种情况(有效性,自由度,推动方向等)采取一堆离散输入,并将结果分类为"向上,向下,向左或向右".

我怀疑如果你想要if语句的长链表达更大或相同的表现 - 至少在指令数量/比较数量方面 - 那么你必须以你在那里做的方式进行比较.计算所有方向的分数然后检查最大值,或递归地将移动列表划分为首选和非首选的方法都将比纯粹的比较序列做更多的工作.

我想你可以建立一个查找表.你有4位表示方向是否有效,4位指示方向是否被占用,以及指示插入方向,在总共10位2位-所以这是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;
}

您将通过填写该结构中的标志来描述您的情况,然后读取"Index"值以获取查找表索引.

编辑:另外,关于你的评分函数,因为你正在做严格的位模式,我想你可以跳过所有的三元运算符:

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

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

\n\n

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

\n\n

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

\n\n

这段代码的“复杂度”是n\xc3\x97m。

\n\n

（虽然我使用缩进使其看起来像一个表格，但更复杂的输入条件不会允许每一行整齐地存在于一行中。这并不重要：重要的是只有n\xc3\x97m 声明。当条件很短时能够使其看起来像一个表，这是一个很好的奖励。）

\n\n

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

\n\n

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

\n\n

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

\n\n

struct PreferencedDecisionMaker\n{\n    private uint availableOptionsBits;\n\n    private static readonly int[] MultiplyDeBruijnBitPosition = {\n        0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, \n        31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9\n    };\n\n    public int Decision\n    {\n        get\n        {\n            uint v = availableOptionsBits;\n\n            // Find position of lowest set bit in constant time\n            // http://stackoverflow.com/a/757266/165500\n            return MultiplyDeBruijnBitPosition[((uint)((v & -v) * 0x077CB531U)) >> 27];\n        }\n    }\n\n    private void InternalPush(uint preference)\n    {\n        if(availableOptionsBits == 0)\n            availableOptionsBits = preference;\n        else\n        {\n            uint combinedBits = availableOptionsBits & preference;\n            if(combinedBits != 0)\n                availableOptionsBits = combinedBits;\n        }\n    }\n\n    public void Push(int option)\n    {\n        if(option < 0 || option >= 32) throw new ArgumentOutOfRangeException("Option must be between 0 and 31");\n        InternalPush(1u << option);\n    }\n\n    // ... etc ...\n    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)); }\n    // ... etc ...\n}\n

\n