游戏算法-游戏AI行为树，python实现

参考文章：Behavior trees for AI: How they work (gamedeveloper.com)

本文主要参考上述wei'zProject Zomboid 的开发者 Chris Simpson文章的概念，用伪代码实现代码例子

AI概述

    游戏AI是对游戏内所有非玩家控制角色的行为进行研究和设计，使得游戏内的单位能够感知周围环境，并做出相应的动作表现的技术。游戏AI作为游戏玩法的一大补充，在各种游戏中都有广泛的应用，比如可以和玩家交互聊天的NPC，按照特定规则寻路的怪物，与玩家进行战斗对抗的机器人等。

目前实现游戏AI的算法有

有限状态机

AI行为树

还有其他比较少用的规则式AI，甚至神经网络等
 

行为树AI基本概念

        游戏行为树（Behavior Trees, BT）是一种用于游戏AI的设计模式。它通过模拟行为树来描述AI的行为和决策过程，以实现更加智能和自然的游戏AI。

游戏行为树由多个节点组成，每个节点代表一个行为或决策。它们按照特定的方式连接在一起，形成一个树状结构。在行为树中，根节点是AI的起点，通过遍历子节点来决策AI的行为。

节点有以下三种状态：

成功 success

失败 failure

运行 running

行为树节点有三种主要原型

组合控制节点 -Composite：

一种将多个子节点组合在一起的节点，用于实现复杂的行为和决策逻辑

主要包括

次序节点-Sequences：并行执行多个子节点，直到所有子节点都返回True或者任意一个子节点返回False为止

选择节点-Selector：按照顺序执行子节点，当某个子节点返回success时，停止执行并返回success

修饰节点-Decorator：

一种特殊的节点，它不执行具体的行为或决策，而是修饰其它节点的行为或决策

主要包括：

逆变节点-Inverter：它可以将子节点的结果倒转，比如子节点返回了 Failure，则这个修饰节点会向上返回 Success，以此类推。

重复节点-Repeater：重复执行其子节点指定的次数或者一直重复执行，直到其子节点返success或者failure

叶节点-Leaf：

树的最末端——叶子，就是这些 AI 实际上去做事情的命令或者是做一些判断

主要包括

条件节点-Condition：判断条件是否满足，如果满足则返回success，否则返回failure

行为节点-Action：执行某个具体的动作或行为，例如移动、攻击、使用技能等

节点表示

次序节点 ->Walk to Door (Success) ->次序节点（Running） ->Open Door (Success)  ->次序节点（运行中） ->Walk through Door (Success) ->次序节点（Running） ->Close Door (Success) ->次序节点（Running） -> 向次序节点的父节点返回 Success。

例如，考虑上一节中提到的逆变器装饰器：

在功能上与前面的示例相同，这里我们展示了如何使用逆变器来否定任何测试，从而为您提供一个 NOT 门。这意味着你可以大幅减少测试角色或游戏世界条件所需的节点数量。

三、伪代码实现

节点基类：

# 行为树节点基类
class BaseNode(object):
	def __init__(self):
		self.status = None  # 节点的执行结果: 成功 success 失败 failure 运行 running

	def execute(self, who):
		# 执行
		pass

叶子节点：行为节点

# 叶子节点-行为节点：吃食物
class EatFoodNode(BaseNode):
	def __init__(self, target):
		super(EatFoodNode).__init__()
		self.target = target  # 食物目标

	def execute(self, who):
		# 吃食物
		# who.eat_foot(self.target)
		self.status = "success"

# 叶子节点-行为节点：打开门
class OpenDoorNode(BaseNode):
	def __init__(self, target):
		super(OpenDoorNode).__init__()
		self.target = target  # 打开目标

	def execute(self, who):
		# 执行打开门动作
		# who.open_door(self.target)
		self.status = "success"

叶子节点：条件节点

# 叶子节点-条件节点：检查是否饥饿
class CheckHungryNode(BaseNode):
	def __init__(self, hungry_val):
		super(CheckHungryNode).__init__()
		self.hungry_val = hungry_val  # 生命值阈值

	def execute(self, who):
		# 检查生命值是否小于阈值
		if self.hungry_val > who.hungry_val:
			self.status = "success"
		else:
			self.status = "failure"


# 叶子节点-条件节点：检查是否有食物
class CheckHasFoodNode(BaseNode):
	def __init__(self, food):
		super(CheckHasFoodNode).__init__()
		self.food = food  # 目标食物

	def execute(self, who):
		# 检查目标距离是否小于最大距离
		if who.has_food(self.food):
			self.status = "success"
		else:
			self.status = "failure"
   
   # 叶子节点-条件节点：敌人是否在周围
class CheckEnemiesAroundNode(BaseNode):
	def __init__(self, enemies):
		super(CheckEnemiesAroundNode).__init__()
		self.enemies = enemies  # 敌人

	def execute(self, who):
		# 敌人是否在周围
		if who.AroundHasEnemies(self.enemies):
			self.status = "success"
		else:
			self.status = "failure"

组合控制节点：序列节点

# 组合控制节点：序列节点
class SequenceNode(BaseNode):
	def __init__(self, children):
		super(SequenceNode).__init__()
		self.children = children  # 子节点列表

	def execute(self, who):
		for child in self.children:
			child.execute(who)
			if child.status == "failure":
				self.status = "failure"
				return
		self.status = "success"

组合控制节点：选择节点

# 组合控制节点：选择节点
class SelectorNode(BaseNode):
	def __init__(self, children):
		super(SelectorNode).__init__()
		self.children = children

	def execute(self, who):
		for child in self.children:
			child.execute(who)
			if child.status == "success":
				self.status = "success"
				return
		self.status = "failure"

装饰节点：逆变节点

# 装饰节点，逆变节点
class NOT_DecoratorNode(BaseNode):
	def __init__(self, child):
		super(DecoratorNOT).__init__()
		self.child = child
	
	def execute(self, who):                      
		status = self.child.execute(who)
		if status == "success"
			self.status = "failure"
		elif status == "failure":
			self.status = "success"
			

例子一：

饥饿的时候，且有食物的时候，没有敌人在周围，就吃食物

# 角色对象
class Player(object):
	def __init__(self):
		self.hungry_val = 0  # 饥饿度
		self.food = "fish"  # 食物


def main():
	# 首先定义行为树的结构
	root = SequenceNode([
		# 饥饿的时候
		CheckHungryNode(50),
		# 有鱼时候
		CheckHasFoodNode("fish"),
		# 敌人不在周围
		NOT_DecoratorNode(CheckEnemiesAroundNode("李宏伟")),
		# 老墨吃鱼
		EatFoodNode("fish"),
	])
	
	who = Player()
	# 然后在主循环中执行行为树
	while True:

		# 执行行为树
		root.execute(who)

		# 根据行为执行结果更新状态
		if root.status == "success":
			who.hungry_val = random.randint(1, 100)
			who.food = random.randint(1, 100)
		# 等待一段时间后再次执行行为树
		time.sleep(1)

例子二：

	# 行为树的结构如下
	root = SequenceNode([
		WalkToDoor(),
		SelectorNode([
			OpenDoor(),
			SequenceNode([
					UnlockDoor(),
					OpenDoor("self"),
					]),
			SmashDoor(),
				]),
		WalkThroughDoor(),
		CloseDoor(),		
	])