AI决策算法之GOAP(二)

发表于2018-02-26
评论0 3.1k浏览

AI决策算法之GOAP(一)的结尾给大家介绍了实现GOAP的实现算法的四个类,下面就给大家介绍对应四个类的代码实现。


GOAP 的主要逻辑:

1.Agent的状态机初始化Idle状态

2.Idel状态根据IGoap提供的数据,通过Planer得到最优路线

3.Agent的状态机转换状态到PerformAction状态

4.PerformAction状态解析路线,执行路线的动作队列

5.如果动作需要到范围内,切换到MoveTo状态移动到目标范围,否则执行动作队列

6.当全部动作执行完毕,告诉IGoap目标达成,转换到Idle状态


接着实现 IGoal,Agent,Action,Planer,FSM


Action

namespace MyGoap  
{  
    public abstract class Action : MonoBehaviour  
    {  
        #region 字段  
        private HashSet<KeyValuePair<string, object>> preconditions; // 先行条件  
        private HashSet<KeyValuePair<string, object>> effects;       // 造成的影响  
        private bool inRange = false;                                // 是否在动作的可行范围内  
        public float cost = 1f;                                      // 消耗的成本  
        public GameObject target;                                    // 执行动作的目标,可以为空  
        #endregion  
        #region 属性  
        public bool IsInRange { get { return inRange; } set { inRange = value; } }  
        public HashSet<KeyValuePair<string, object>> Preconditions  
        {  
            get  
            {  
                return preconditions;  
            }  
        }  
        public HashSet<KeyValuePair<string, object>> Effects  
        {  
            get  
            {  
                return effects;  
            }  
        }  
        #endregion  
        #region 接口  
        /// <summary>  
        /// 构造函数:初始化  
        /// </summary>  
        public Action()  
        {  
            preconditions = new HashSet<KeyValuePair<string, object>>();  
            effects = new HashSet<KeyValuePair<string, object>>();  
        }  
        /// <summary>  
        /// 基类重置  
        /// </summary>  
        public void DoReset()  
        {  
            inRange = false;  
            target = null;  
            Reset();  
        }  
        /// <summary>  
        /// 继承类重置  
        /// </summary>  
        public abstract void Reset();  
        /// <summary>  
        /// 是否完成动作  
        /// </summary>  
        /// <returns></returns>  
        public abstract bool IsDone();  
        /// <summary>  
        /// 由代理检索动作最优目标,并返回目标是否存在,动作是否可以被执行  
        /// </summary>  
        /// <param name="target"></param>  
        /// <returns></returns>  
        public abstract bool CheckProcedualPrecondition(GameObject agent);  
        /// <summary>  
        /// 执行动作  
        /// </summary>  
        /// <param name="agent"></param>  
        /// <returns></returns>  
        public abstract bool Perform(GameObject agent);  
        /// <summary>  
        /// 是否需要在范围内才能执行动作  
        /// </summary>  
        /// <returns></returns>  
        public abstract bool RequiresInRange();  
        /// <summary>  
        /// 增加先行条件  
        /// </summary>  
        /// <param name="key"></param>  
        /// <param name="value"></param>  
        public void AddPrecondition(string key,object value)  
        {  
            preconditions.Add(new KeyValuePair<string, object>(key, value));  
        }  
        /// <summary>  
        /// 移除先行条件  
        /// </summary>  
        /// <param name="key"></param>  
        public void RemovePrecondition(string key)  
        {  
            KeyValuePair<string, object> remove = default(KeyValuePair<string, object>);  
            foreach(var kvp in preconditions)  
            {  
                if (kvp.Key.Equals(key))  
                    remove = kvp;  
            }  
            //如果被赋值了  
            if (!default(KeyValuePair<string, object>).Equals(remove))  
                preconditions.Remove(remove);  
        }  
        /// <summary>  
        /// 增加造成的效果  
        /// </summary>  
        /// <param name="key"></param>  
        /// <param name="value"></param>  
        public void AddEffect(string key, object value)  
        {  
            effects.Add(new KeyValuePair<string, object>(key, value));  
        }  
        /// <summary>  
        /// 移除造成的效果  
        /// </summary>  
        /// <param name="key"></param>  
        public void RemoveEffect(string key)  
        {  
            KeyValuePair<string, object> remove = default(KeyValuePair<string, object>);  
            foreach (var kvp in effects)  
            {  
                if (kvp.Key.Equals(key))  
                    remove = kvp;  
            }  
            //如果被赋值了  
            if (!default(KeyValuePair<string, object>).Equals(remove))  
                effects.Remove(remove);  
        }  
        #endregion  
    }  
}  


IGoap
namespace MyGoap  
{  
    public interface IGoap   
    {  
        /// <summary>  
        /// 获取现在所有状态  
        /// </summary>  
        /// <returns></returns>  
        HashSet<KeyValuePair<string, object>> GetState();  
        /// <summary>  
        /// 创建新的目标状态集合  
        /// </summary>  
        /// <returns></returns>  
        HashSet<KeyValuePair<string, object>> CreateGoalState();  
        /// <summary>  
        /// 没有找到可以完成目标的路线  
        /// </summary>  
        /// <param name="failedGoal"></param>  
        void PlanFailed(HashSet<KeyValuePair<string, object>> failedGoal);  
        /// <summary>  
        /// 找到可以完成目标的一系列动作  
        /// </summary>  
        /// <param name="goal"></param>  
        /// <param name="actions"></param>  
        void PlanFound(HashSet<KeyValuePair<string, object>> goal, Queue<Action> actions);  
        /// <summary>  
        /// 动作全部完成,达成目标  
        /// </summary>  
        void ActionsFinished();  
        /// <summary>  
        /// 计划被一个动作打断  
        /// </summary>  
        /// <param name="aborterAction"></param>  
        void PlanAborted(Action aborterAction);  
        /// <summary>  
        /// 移动到目标动作位置  
        /// </summary>  
        /// <param name="tagetAction"></param>  
        /// <returns></returns>  
        bool MoveAgent(Action tagetAction);  
    }  
}  

Planer
namespace MyGoap  
{  
    public class Planer   
    {  
        /// <summary>  
        /// 计划出最优路线  
        /// </summary>  
        /// <param name="agent">把代理传进来</param>  
        /// <param name="availableActions">当前可行动作</param>  
        /// <param name="currentState">当前状态</param>  
        /// <param name="goal">目标</param>  
        /// <returns></returns>  
        public Queue<Action> Plan(GameObject agent,HashSet<Action> availableActions,HashSet<KeyValuePair<string,object>> currentState,HashSet<KeyValuePair<string,object>> goal)  
        {  
            foreach (var a in availableActions)  
                a.DoReset();  
            //排除不可行动作  
            HashSet<Action> usableActions = new HashSet<Action>();  
            foreach (var a in availableActions)  
                if (a.CheckProcedualPrecondition(agent))  
                    usableActions.Add(a);  
            List<Node> leaves = new List<Node>();  
            //由当前状态开始计算,并把结果添加到路线集合里  
            Node start = new Node(null, 0, currentState, null);  
            bool success = BuildGraph(start, leaves, usableActions, goal);  
            if (!success)  
                return null;  
            //得到成本最小的路线  
            Node cheapest = null;  
            foreach(Node leaf in leaves)  
            {  
                if (cheapest == null)  
                    cheapest = leaf;  
                else  
                {  
                    if (leaf.CostNum < cheapest.CostNum)  
                        cheapest = leaf;  
                }  
            }  
            //链表遍历法遍历最后一个节点,并把每一个动作往前插入,因为越后面节点的动作是越后面要执行的  
            List<Action> result = new List<Action>();  
            Node n = cheapest;  
            while(n != null)  
            {  
                if(n.Action != null)  
                {  
                    result.Insert(0, n.Action);  
                }  
                n = n.Parent;  
            }  
            //把链表转换为队列返回回去  
            Queue<Action> queue = new Queue<Action>();  
            foreach(Action a in result)  
            {  
                queue.Enqueue(a);  
            }  
            return queue;  
        }  
        /// <summary>  
        /// 策划者计划主要算法  
        /// </summary>  
        /// <param name="parent">父节点</param>  
        /// <param name="leaves">路线集合</param>  
        /// <param name="usableActions">可行动作</param>  
        /// <param name="goal">目标状态</param>  
        /// <returns></returns>  
        private bool BuildGraph(Node parent,List<Node> leaves,HashSet<Action> usableActions,HashSet<KeyValuePair<string,object>> goal)  
        {  
            bool foundOne = false;  
            // 遍历所有可行动作  
            foreach(var action in usableActions)  
            {  
                // 如果当前状态匹配当前动作前置条件,动作执行  
                if(InState(action.Preconditions,parent.State))  
                {  
                    //造成效果影响当前状态  
                    HashSet<KeyValuePair<string, object>> currentState = PopulateState(parent.State, action.Effects);  
                    //生成动作完成的节点链,注意成本累加  
                    Node node = new Node(parent, parent.CostNum + action.cost, currentState, action);  
                    //如果当前状态存在要完成的目标状态  
                    if(InState(goal,currentState))  
                    {  
                        //增加可行方案路线  
                        leaves.Add(node);  
                        foundOne = true;  
                    }  
                    else  
                    {  
                        //否则该可行动作排除,用其他动作由 该节点 继续搜索接下去的路线  
                        HashSet<Action> subset = ActionSubset(usableActions, action);  
                        bool found = BuildGraph(node, leaves, subset, goal);  
                        if (found)  
                            foundOne = true;  
                    }  
                }  
            }  
            return foundOne;  
        }  
        #region 帮助方法  
        /// <summary>  
        /// 移除目标动作并返回移除后的动作集合  
        /// </summary>  
        /// <param name="actions"></param>  
        /// <param name="removeTarget"></param>  
        /// <returns></returns>  
        private HashSet<Action> ActionSubset(HashSet<Action> actions,Action removeTarget)  
        {  
            HashSet<Action> subset = new HashSet<Action>();  
            foreach(var a in actions)  
            {  
                if (!a.Equals(removeTarget))  
                    subset.Add(a);  
            }  
            return subset;  
        }  
        /// <summary>  
        /// 目标状态集合是否全在该目标集合内  
        /// </summary>  
        /// <param name="state"></param>  
        /// <param name="isExistStates"></param>  
        /// <returns></returns>  
        private bool InState(HashSet<KeyValuePair<string,object>> state,HashSet<KeyValuePair<string,object>> isExistStates)  
        {  
            bool allMatch = true;  
            foreach (var s in isExistStates)  
            {  
                bool match = false;  
                foreach(var s2 in state)  
                {  
                    if(s2.Equals(s))  
                    {  
                        match = true;  
                        break;  
                    }  
                }  
                //如果出现一个不匹配  
                if (!match)  
                {  
                    allMatch = false;  
                    break;  
                }  
            }  
            return allMatch;  
        }  
        /// <summary>  
        /// 将目标状态集合更新到原集合里,没有的增加,存在的更新  
        /// </summary>  
        /// <param name="currentState"></param>  
        /// <param name="stateChange"></param>  
        /// <returns></returns>  
        private HashSet<KeyValuePair<string,object>> PopulateState(HashSet<KeyValuePair<string,object>> currentState,HashSet<KeyValuePair<string,object>> stateChange)  
        {  
            HashSet<KeyValuePair<string, object>> state = new HashSet<KeyValuePair<string, object>>();  
            foreach (var s in currentState)  
                state.Add(new KeyValuePair<string, object>(s.Key, s.Value));  
            foreach(var change in stateChange)  
            {  
                bool exists = false;  
                foreach(var s in state)  
                {  
                    if(s.Equals(change))  
                    {  
                        exists = true;  
                        break;  
                    }  
                }  
                if(exists)  
                {  
                    //删除掉原来的,并把改变后的加进去  
                    state.RemoveWhere((KeyValuePair<string, object> kvp) => { return kvp.Key.Equals(change.Key); });  
                    KeyValuePair<string, object> updated = new KeyValuePair<string, object>(change.Key,change.Value);  
                    state.Add(updated);  
                }  
                else  
                {  
                    state.Add(new KeyValuePair<string, object>(change.Key, change.Value));  
                }  
            }  
            return state;  
        }  
        #endregion  
        /// <summary>  
        /// 策划者用于存储数据的帮助节点  
        /// </summary>  
        private class Node  
        {  
            public Node Parent;                                      // 上一个节点  
            public float CostNum;                                    // 总消耗成本  
            public HashSet<KeyValuePair<string, object>> State;      // 到这个节点的现有状态  
            public Action Action;                                    // 该节点应该执行的动作  
            public Node(Node parent,float costNum,HashSet<KeyValuePair<string,object>> state,Action action)  
            {  
                Parent = parent;  
                CostNum = costNum;  
                State = state;  
                Action = action;  
            }  
        }  
    }  
}  


FSM

namespace MyGoap  
{  
    /// <summary>  
    /// 堆栈式有限状态机  
    /// </summary>  
    public class FSM  
    {  
        //状态堆栈  
        private Stack<FSMState> stateStack = new Stack<FSMState>();  
        //状态委托  
        public delegate void FSMState(FSM fsm, GameObject go);  
        //执行状态  
        public void Update(GameObject go)  
        {  
            if (stateStack.Peek() != null)  
                stateStack.Peek().Invoke(this, go);  
        }  
        //压入状态  
        public void PushState(FSMState state)  
        {  
            stateStack.Push(state);  
        }  
        //弹出状态  
        public void PopState()  
        {  
            stateStack.Pop();  
        }  
    }  
}  


Agent

namespace MyGoap  
{  
    public class Agent : MonoBehaviour  
    {  
        #region 字段  
        private FSM stateMachine;                 //状态机  
        private FSM.FSMState idleState;  
        private FSM.FSMState moveToState;  
        private FSM.FSMState performActionState;  
        private HashSet<Action> availableActions; //可行动作  
        private Queue<Action> currentActions;     //当前需要执行的动作  
        private IGoap dataProvider;                 
        private Planer planer;  
        #endregion  
        #region 属性  
        /// <summary>  
        /// 是否有动作计划  
        /// </summary>  
        private bool HasActionPlan { get { return currentActions.Count > 0; } }  
        #endregion  
        #region Unity回调  
        void Start()  
        {  
            stateMachine = new FSM();  
            availableActions = new HashSet<Action>();  
            currentActions = new Queue<Action>();  
            planer = new Planer();  
            InitDataProvider();  
            InitIdleState();  
            InitMoveToState();  
            InitPerformActionState();  
            stateMachine.PushState(idleState);  
            LoadActions();  
        }  
        void Update()  
        {  
            stateMachine.Update(this.gameObject);  
        }  
        #endregion  
        #region 接口  
        /// <summary>  
        /// 初始化空闲状态  
        /// </summary>  
        private void InitIdleState()  
        {  
            idleState = (fsm, go) =>  
                {  
                    HashSet<KeyValuePair<string, object>> currentState = dataProvider.GetState();  
                    HashSet<KeyValuePair<string, object>> goal = dataProvider.CreateGoalState();  
                    //计算路线  
                    Queue<Action> plan = planer.Plan(gameObject, availableActions, currentState, goal);  
                    if (plan != null)  
                    {  
                        currentActions = plan;  
                        //通知计划找到  
                        dataProvider.PlanFound(goal, plan);  
                        //转换状态  
                        fsm.PopState();  
                        fsm.PushState(performActionState);  
                    }  
                    else  
                    {  
                        //通知计划没找到  
                        dataProvider.PlanFailed(goal);  
                        //转换状态  
                        fsm.PopState();  
                        fsm.PushState(idleState);  
                    }  
                };  
        }  
        /// <summary>  
        /// 初始化移动到目标状态  
        /// </summary>  
        private void InitMoveToState()  
        {  
            moveToState = (fsm, go) =>  
                {  
                    Action action = currentActions.Peek();  
                    //如果没目标且又需要移动,异常弹出  
                    if(action.RequiresInRange() && action.target != null)  
                    {  
                        //弹出移动和执行动作状态  
                        fsm.PopState();  
                        fsm.PopState();  
                        fsm.PushState(idleState);  
                        return;  
                    }  
                    //如果移动到了目标位置,弹出移动状态  
                    if (dataProvider.MoveAgent(action))  
                        fsm.PopState();  
                };  
        }  
        /// <summary>  
        /// 初始化执行动作状态  
        /// </summary>  
        private void InitPerformActionState()  
        {  
            performActionState = (fsm, go) =>  
                {  
                    //如果全部执行完毕,转换到空闲状态,并且通知  
                    if (!HasActionPlan)  
                    {  
                        fsm.PopState();  
                        fsm.PushState(idleState);  
                        dataProvider.ActionsFinished();  
                        return;  
                    }  
                    Action action = currentActions.Peek();  
                    //如果栈顶动作完成,出栈  
                    if (action.IsDone())  
                        currentActions.Dequeue();  
                    if(HasActionPlan)  
                    {  
                        action = currentActions.Peek();  
                        //是否在范围内  
                        bool inRange = action.RequiresInRange() ? action.IsInRange : true;  
                        if(inRange)  
                        {  
                            bool success = action.Perform(go);  
                            //如果动作执行失败,转换到空闲状态,并通知因为该动作导致计划失败  
                            if(!success)  
                            {  
                                fsm.PopState();  
                                fsm.PushState(idleState);  
                                dataProvider.PlanAborted(action);  
                            }  
                        }  
                        else  
                        {  
                            fsm.PushState(moveToState);  
                        }  
                    }  
                    else  
                    {  
                        fsm.PopState();  
                        fsm.PushState(idleState);  
                        dataProvider.ActionsFinished();  
                    }  
                };  
        }  
        /// <summary>  
        /// 初始化数据提供者  
        /// </summary>  
        private void InitDataProvider()  
        {  
            //查找当前物体身上继承自IGoap的脚本  
            foreach(Component comp in gameObject.GetComponents(typeof(Component)))  
            {  
                if(typeof(IGoap).IsAssignableFrom(comp.GetType()))  
                {  
                    dataProvider = (IGoap)comp;  
                    return;  
                }  
            }  
        }  
        /// <summary>  
        /// 获取身上所有的Action脚本  
        /// </summary>  
        private void LoadActions()  
        {  
            Action[] actions = gameObject.GetComponents<Action>();  
            foreach (var a in actions)  
                availableActions.Add(a);  
        }  
        #endregion  
    }  
}  

如社区发表内容存在侵权行为,您可以点击这里查看侵权投诉指引