【代码设计】有限状态机FSM

作者：卡卡西0旗木

泰斗原文：点击查看

有限状态机（FSM）是一个广为人知但真正理解的人却不多的概念。很多人虽然编写了 FSMState、FSM 这样的类，但仍然手动处理状态的跳转和执行等操作。实际上，对于程序员而言，对基础和概念的理解至关重要，真正理解透彻后，做任何事情都会变得容易。

如果对状态机不太了解，可以查看维基百科的解释：有限状态机。简单来说，FSM 可以看作是一个图，图中的每个节点代表一个状态，图还定义了节点在接收到特定输入时会跳转到的目标节点。

如果到这里你还不理解 FSM，建议反复阅读上述介绍，再来看代码也不迟。

1. 定义一个状态类

组成状态机的基本元素之一就是状态，下面我们定义一个状态类：

/**
*
* @author cjunhong
* @email [email]john.cha@qq.com[/email]
* @date 2014年12月2日 下午5:45:54
*/
public class FiniteState<T> {

private final int state;
private IFiniteStateExecutor<T> stateExecutor;

/**
* @param state
*/
public FiniteState(int state) {
this.state = state;
}

/**
*
* @param fightStateMachine
* @param t
* @param now
* @param duration
*/
public void doState(FiniteStateMachine<T> fightStateMachine, T t, long now, int duration) {
stateExecutor.execute(fightStateMachine, t, now, duration);
}

/**
* @param stateExecutor
*            the stateExecutor to set
*/
public void setStateExecutor(IFiniteStateExecutor<T> stateExecutor) {
this.stateExecutor = stateExecutor;
}

/**
* @return the state
*/
public int getState() {
return state;
}

/*
* (non-Javadoc)
*
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
return "FightState [state=" + state + "]";
}

/**
* 当切换到状态的时候调用
*/
public void onInit(FiniteStateMachine<T> stateMac, T t, long now, int duration) {
stateExecutor.onInit(stateMac, t, now, duration);
}
}

这个类很简单，state 属性在每个状态机中保持唯一，用于标识一个状态值。stateExecutor 属性则表示在该状态下要处理的行为，例如在巡逻状态下，要控制角色走动，那么 stateExecutor 就是实现走路逻辑的代码。

2. 状态的行为

如果状态机仅仅实现状态的跳转，而状态本身没有任何行为，那么它的实际意义并不大。我们更多地希望在特定状态下执行特定的操作。因此，我们将“做什么事”这个概念抽象成一个接口 IFiniteStateExecutor：

/**
*
* @author cjunhong
* @email [email]john.cha@qq.com[/email]
* @date 2014年12月2日 下午10:20:47
*/
public interface IFiniteStateExecutor<T> {

/**
*
* @param fightStateMachine
* @param hoster
* @param now
* @param duration
*/
void execute(FiniteStateMachine<T> fightStateMachine, T hoster, long now, int duration);

/**
*
*/
void onInit(FiniteStateMachine<T> stateMac, T t, long now, int duration);

}

这个接口很简单，定义了行为初始化和执行的方法。

3. 状态机核心

前面说了这么多，还没有涉及到真正的状态机处理。不过，细心的同学可能已经发现，上面的代码中都引用了一个 FiniteStateMachine 类，没错，这个类正是状态机的核心。下面是该类的代码：

/**
*
* @author cjunhong
* @email [email]john.cha@qq.com[/email]
* @date 2014年12月2日 下午5:41:37
*/
public class FiniteStateMachine<T> {

private static final Logger LOGGER = LoggerFactory.getLogger(FiniteStateMachine.class);

private final List<FiniteStateTransaction<T>> TRANSACTION_LIST_HOLDER = new ArrayList<FiniteStateTransaction<T>>(0);

private FiniteState<T> lastState;
private FiniteState<T> currentState;
private Map<Integer, FiniteState<T>> allState = new HashMap<>();
private Map<FiniteState<T>, List<FiniteStateTransaction<T>>> transactions = new HashMap<>();

private Map<String, Integer> intParams = new HashMap<>();
private Map<String, Boolean> boolParams = new HashMap<>();
private Map<String, Long> longParams = new HashMap<>();
private IFiniteStatesProcesser<T> statesProcesser;
private IOnFiniteStateChangeProcesser<T> onStateChangeProcesser;

public FiniteStateMachine( IFiniteStatesProcesser<T> statesProcesser,
IOnFiniteStateChangeProcesser<T> onStateChangeProcesser) {
if (statesProcesser == null) {
statesProcesser = new IFiniteStatesProcesser<T>() {
@Override
public void process(FiniteStateMachine<T> stateMachine,
FiniteState<T> currentState,
T t,
long now,
int duration) {
}
};
}
this.statesProcesser = statesProcesser;
if (onStateChangeProcesser == null) {
onStateChangeProcesser = new IOnFiniteStateChangeProcesser<T>() {
@Override
public void onChange( FiniteStateMachine<T> stateMachine,
T fightScene,
FiniteState<T> oldState,
FiniteState<T> newState) {
}
};
}
this.onStateChangeProcesser = onStateChangeProcesser;

}

/**
* 将一个状态设置为默认状态
*
* @param state
*/
public void setDefaultState(int state) {
FiniteState<T> fightState = allState.get(state);
if (fightState == null) {
throw new NullPointerException("Can not found such state " + state + " as default state.");
}
setDefaultState(fightState);
}

/**
* 设置参数
*
* @param key
* @param value
*/
public void setInteger(String key, int value) {
intParams.put(key, value);
}

public void setBoolean(String key, boolean value) {
boolParams.put(key, value);
}

public void tick(T t, long now, int duration) {
if (lastState != currentState) {
currentState.onInit(this, t, now, duration);
LOGGER.info("Change State -- old state=" + lastState + ", new state=" + currentState);
onStateChangeProcesser.onChange(this, t, lastState, currentState);
lastState = currentState;
}
currentState.doState(this, t, now, duration);
processOnCurrentState(currentState, t, now, duration);
checkCurrentState();
}

/**
*
* @param currentState
* @param t
* @param now
* @param duration
*/
public void processOnCurrentState(FiniteState<T> currentState, T t, long now, int duration) {
statesProcesser.process(this, currentState, t, now, duration);
}

/**
* 检查当前状态，并在需要的时候进行跳转。
*/
private void checkCurrentState() {
FiniteState<T> state = null;
List<FiniteStateTransaction<T>> list = transactions.get(currentState);
for (FiniteStateTransaction<T> t : list) {
if (t.check(intParams, boolParams, longParams)) {
state = t.getDstState();
break;
}
}
if (state != null && state != currentState) {
currentState = state;
}
}

/**
* 将一个状态设置为默认状态
*
* @param fightState
*/
public void setDefaultState(FiniteState<T> fightState) {
if (fightState == null) {
throw new NullPointerException("Default state can not be null.");
}
currentState = fightState;
}

/**
* 增加一个状态，如果已存在，则不添加。
*
* @param state
* @return 返回当前状态。
*/
public FiniteState<T> addState(int state) {
FiniteState<T> fightState = allState.get(state);
if (fightState == null) {
fightState = new FiniteState<T>(state);
allState.put(state, fightState);

if (transactions.get(fightState) == null) {
transactions.put(fightState, TRANSACTION_LIST_HOLDER);
}
}
return fightState;
}

/**
*
* @param state
* @param executor
* @return
*/
public FiniteState<T> addState(int state, IFiniteStateExecutor<T> executor) {
FiniteState<T> addState = addState(state);
addState.setStateExecutor(executor);
return addState;
}

/**
* 为两个状态之间添加关联。如果两个状态已经存在关联，则返回该关联。
*
* @param src
* @param dst
* @return
*/
public FiniteStateTransaction<T> addTranscation(FiniteState<T> src, FiniteState<T> dst) {
List<FiniteStateTransaction<T>> list = transactions.get(src);
boolean checkContains = true;
if (list == TRANSACTION_LIST_HOLDER) {
list = new LinkedList<>();
transactions.put(src, list);
checkContains = false;
}
FiniteStateTransaction<T> fightTransaction = null;
if (checkContains) {
for (FiniteStateTransaction<T> t : list) {
if (t.getDstState() == dst) {
fightTransaction = t;
break;
}
}
}
if (fightTransaction == null) {
fightTransaction = new FiniteStateTransaction<T>(dst);
list.add(fightTransaction);
}
return fightTransaction;
}

/*
* (non-Javadoc)
*
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
return "FightState<T>Machine [currentState=" + currentState + ", intParams=" + intParams + ", boolParams=" + boolParams + "]";
}

/**
* @return the currentState
*/
public FiniteState<T> getCurrentState() {
return currentState;
}
}

tick 方法是状态机的触发方法，只要在每帧中调用该方法，状态机就会根据输入情况进行状态跳转，并执行当前状态下的行为。tick 方法中调用了 checkCurrentState 方法，该方法用于检查当前状态并进行跳转，下面是 checkCurrentState 方法的代码：

private void checkCurrentState() {
FiniteState<T> state = null;
List<FiniteStateTransaction<T>> list = transactions.get(currentState);
for (FiniteStateTransaction<T> t : list) {
if (t.check(intParams, boolParams, longParams)) {
state = t.getDstState();
break;
}
}
if (state != null && state != currentState) {
currentState = state;
}
}

我们使用 FiniteStateTransaction 类来保存当前状态到其他状态的跳转关系，该类中包含了跳转的条件 ITransactionCondition。

4. 状态跳转 FiniteStateTransaction 的定义

/**
*
* @author cjunhong
* @email [email]john.cha@qq.com[/email]
* @date 2014年12月2日 下午5:50:58
*/
public class FiniteStateTransaction<T> {

private List<ITransactionCondition> list = new LinkedList<>();
private FiniteState<T> dst;

/**
* @param dst
*/
public FiniteStateTransaction(FiniteState<T> dst) {
this.dst = dst;
}

public void addCondition(ITransactionCondition fightCondition) {
list.add(fightCondition);
}

/**
*
* @param intParams
* @param boolParams
* @param longParams
* @return
*/
public boolean check(Map<String, Integer> intParams, Map<String, Boolean> boolParams, Map<String, Long> longParams) {
for (ITransactionCondition c : list) {
if (!c.check(intParams, boolParams, longParams)) {
return false;
}
}
return true;
}

/**
* @return
*/
public FiniteState<T> getDstState() {
return dst;
}

}

可以看到，这个类包含一个条件列表和一个目标状态。check 方法用于检查所有条件是否都满足。

5. 条件的定义

public interface ITransactionCondition {

/**
*
* @param intParams
* @param boolParams
* @param longParams
* @return
*/
boolean check(Map<String, Integer> intParams, Map<String, Boolean> boolParams, Map<String, Long> longParams);

}

6. 条件的一些实现

下面分别实现了布尔值、int、long 类型的条件：

布尔值条件

/**
*
* @author cjunhong
* @email [email]john.cha@qq.com[/email]
* @date 2014年12月2日 下午9:49:55
*/
public class BoolCondition implements ITransactionCondition {

private String key;
private boolean expectValue;

/**
*
* @param key
* @param expectValue
*/
public BoolCondition(String key, boolean expectValue) {
this.key = key;
this.expectValue = expectValue;
}

@Override
public boolean check(Map<String, Integer> intParams, Map<String, Boolean> boolParams, Map<String, Long> longParams) {
Boolean currBool = boolParams.get(key);
if (currBool == null) {
return false;
}
return currBool == expectValue;
}

}

int 类型条件

/**
*
* @author cjunhong
* @email [email]john.cha@qq.com[/email]
* @date 2014年12月2日 下午9:38:25
*/
public class IntCondition implements ITransactionCondition {

public static final byte EQUALS = 0;
public static final byte SMALLER = 1;
public static final byte LARGER = 2;
public static final byte NOT_EQUALS = 3;

private String key;
private byte compareType;
private int compareValue;

/**
*
* @param key
* @param compareType
* @param compareValue
*/
public IntCondition(String key, byte compareType, int compareValue) {
this.key = key;
this.compareType = compareType;
this.compareValue = compareValue;
if (compareType != EQUALS && compareType != LARGER && compareType != SMALLER) {
throw new IllegalArgumentException("compareType can noly be one of the IntCondition.EQUALS、IntCondition.LARGER、IntCondition.SMALLER");
}
}

@Override
public boolean check(Map<String, Integer> intParams, Map<String, Boolean> boolParams, Map<String, Long> longParams) {
Integer integer = intParams.get(key);
if (integer == null) {
return false;
}
switch (compareType) {
case EQUALS:
return integer == compareValue;
case LARGER:
return integer > compareValue;
case SMALLER:
return integer < compareValue;
case NOT_EQUALS:
return integer != compareValue;
}
return false;
}
}

long 类型条件

/**
*
* @author cjunhong
* @email [email]john.cha@qq.com[/email]
* @date 2014年12月2日 下午9:38:25
*/
public class LongCondition implements ITransactionCondition {

public static final byte EQUALS = 0;
public static final byte SMALLER = 1;
public static final byte LARGER = 2;
public static final byte NOT_EQUALS = 3;

private String key;
private byte compareType;
private long compareValue;

/**
*
* @param key
* @param compareType
* @param compareValue
*/
public LongCondition(String key, byte compareType, long compareValue) {
this.key = key;
this.compareType = compareType;
this.compareValue = compareValue;
if (compareType != EQUALS && compareType != LARGER && compareType != SMALLER) {
throw new IllegalArgumentException("compareType can noly be one of the IntCondition.EQUALS、IntCondition.LARGER、IntCondition.SMALLER");
}
}

@Override
public boolean check(Map<String, Integer> intParams, Map<String, Boolean> boolParams, Map<String, Long> longParams) {
Long integer = longParams.get(key);
if (integer == null) {
return false;
}
switch (compareType) {
case EQUALS:
return integer == compareValue;
case LARGER:
return integer > compareValue;
case SMALLER:
return integer < compareValue;
case NOT_EQUALS:
return integer != compareValue;
}
return false;
}
}

7. 其它接口

在 FiniteStateMachine 的构造方法中，传入了两个接口：IFiniteStatesProcesser<T> 和 IOnFiniteStateChangeProcesser<T>。这两个接口分别用于状态机的输入和状态改变时的通知。

IFiniteStatesProcesser 接口

public interface IFiniteStatesProcesser<T> {

/**
*
* @param stateMachine
* @param currentState
* @param hoster
* @param now
* @param duration
*/
void process(FiniteStateMachine<T> stateMachine, FiniteState<T> currentState, T hoster, long now, int duration);
}

IOnFiniteStateChangeProcesser 接口

/**
*
* @author cjunhong
* @email [email]john.cha@qq.com[/email]
* @date 2014年12月7日 下午5:02:03
*/
public interface IOnFiniteStateChangeProcesser<T> {

/**
*
* @param stateMachine
* @param hoster
* @param oldState
* @param newState
*/
void onChange(FiniteStateMachine<T> stateMachine, T hoster, FiniteState<T> oldState, FiniteState<T> newState);

}

8. 怎么用

看了上面这么多代码，可能会让人感到头晕。下面通过一个测试代码来演示如何使用这个状态机：

package com.duoyu001.framework.game.fsm;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import com.duoyu001.framework.game.fsm.condition.impl.BoolCondition;
import com.duoyu001.framework.game.fsm.condition.impl.IntCondition;

/**
*
* @author cjunhong
* @email [email]john.cha@qq.com[/email]
* @date 2015年1月10日 下午9:58:12
*/
public class TestFSM {

private static final Logger LOGGER = LoggerFactory.getLogger(TestFSM.class);

static class Monster {
private boolean target;
private int distance2Target = 800;
private int targetHP = 3;
}

private static final int STATE_WAIT = 0;
private static final int STATE_BATTLE = 1;
private static final int STATE_CHARSE = 2;

private static final String KEY_TARGET_EXIST = "tar";
private static final String KET_DISTANCE = "dis";
private static final String KEY_TARGET_DEAD = "tarDead";

private static final int ATTACK_RANGE = 300;

/**
* @param args
*/
public static void main(String[] args) {
FiniteStateMachine<Monster> finiteStateMachine = new FiniteStateMachine<Monster>( createStatesProcesser(),
createOnStateChangeProcesser());
FiniteState<Monster> wait = finiteStateMachine.addState(STATE_WAIT);
wait.setStateExecutor(new IFiniteStateExecutor<TestFSM.Monster>() {
@Override
public void onInit(FiniteStateMachine<Monster> stateMac, Monster t, long now, int duration) {
}

@Override
public void execute(FiniteStateMachine<Monster> fightStateMachine, Monster hoster, long now, int duration) {
LOGGER.info("待机中");
hoster.target = true;
}
});

FiniteState<Monster> battle = finiteStateMachine.addState(STATE_BATTLE);
battle.setStateExecutor(new IFiniteStateExecutor<TestFSM.Monster>() {
@Override
public void onInit(FiniteStateMachine<Monster> stateMac, Monster t, long now, int duration) {
}

@Override
public void execute(FiniteStateMachine<Monster> fightStateMachine, Monster hoster, long now, int duration) {
LOGGER.info("战斗中, 目标剩余血量=" + hoster.targetHP);
hoster.targetHP--;
if (hoster.targetHP < 0) {
hoster.targetHP = 0;
}
}
});

FiniteState<Monster> charse = finiteStateMachine.addState(STATE_CHARSE);
charse.setStateExecutor(new IFiniteStateExecutor<TestFSM.Monster>() {
@Override
public void onInit(FiniteStateMachine<Monster> stateMac, Monster t, long now, int duration) {
}

@Override
public void execute(FiniteStateMachine<Monster> fightStateMachine, Monster hoster, long now, int duration) {
hoster.distance2Target -= 250;
if (hoster.distance2Target < 0) {
hoster.distance2Target = 0;
}
LOGGER.info("追击中，距离=" + hoster.distance2Target);
}
});

finiteStateMachine.setDefaultState(wait);

// 待机>战斗
// 存在目标
FiniteStateTransaction<Monster> wait2Battle = finiteStateMachine.addTranscation(wait, battle);
wait2Battle.addCondition(new BoolCondition(KEY_TARGET_EXIST, true));

// 追击>战斗
// 和目标的距离小于攻击距离
FiniteStateTransaction<Monster> move2Battle = finiteStateMachine.addTranscation(charse, battle);
move2Battle.addCondition(new IntCondition(KET_DISTANCE, IntCondition.SMALLER, ATTACK_RANGE));

// 追击>待机
// 目标死亡
FiniteStateTransaction<Monster> move2Wait = finiteStateMachine.addTranscation(charse, wait);
move2Wait.addCondition(new BoolCondition(KEY_TARGET_DEAD, true));

// 战斗>移动
// 和目标的距离大于攻击距离
FiniteStateTransaction<Monster> battle2Move = finiteStateMachine.addTranscation(battle, charse);
battle2Move.addCondition(new IntCondition(KET_DISTANCE, IntCondition.LARGER, ATTACK_RANGE));

// 战斗>待机
// 目标死亡
FiniteStateTransaction<Monster> battle2Wait = finiteStateMachine.addTranscation(battle, wait);
battle2Wait.addCondition(new BoolCondition(KEY_TARGET_DEAD, true));

Monster m = new Monster();
for (int i = 0; i < 10; i++) {
finiteStateMachine.tick(m, 0, 0);
}
}

/**
* @return
*/
private static IOnFiniteStateChangeProcesser<Monster> createOnStateChangeProcesser() {
// TODO Auto-generated method stub
return null;
}

/**
* @return
*/
private static IFiniteStatesProcesser<Monster> createStatesProcesser() {
return new IFiniteStatesProcesser<TestFSM.Monster>() {

@Override
public void process(FiniteStateMachine<Monster> stateMachine,
FiniteState<Monster> currentState,
Monster hoster,
long now,
int duration) {
stateMachine.setBoolean(KEY_TARGET_EXIST, hoster.target);
stateMachine.setBoolean(KEY_TARGET_DEAD, hoster.targetHP == 0);
stateMachine.setInteger(KET_DISTANCE, hoster.distance2Target);
}
};
}

}

运行上述代码，会打印以下内容：

23:52:23.682 [main] INFO  c.d.f.game.fsm.FiniteStateMachine - Change State -- old state=null, new state=FightState [state=0]
23:52:23.685 [main] INFO  c.d.framework.game.fsm.TestFSM - 待机中
23:52:23.685 [main] INFO  c.d.f.game.fsm.FiniteStateMachine - Change State -- old state=FightState [state=0], new state=FightState [state=1]
23:52:23.685 [main] INFO  c.d.framework.game.fsm.TestFSM - 战斗中, 目标剩余血量=3
23:52:23.685 [main] INFO  c.d.f.game.fsm.FiniteStateMachine - Change State -- old state=FightState [state=1], new state=FightState [state=2]
23:52:23.685 [main] INFO  c.d.framework.game.fsm.TestFSM - 追击中，距离=550
23:52:23.685 [main] INFO  c.d.framework.game.fsm.TestFSM - 追击中，距离=300
23:52:23.685 [main] INFO  c.d.framework.game.fsm.TestFSM - 追击中，距离=50
23:52:23.685 [main] INFO  c.d.f.game.fsm.FiniteStateMachine - Change State -- old state=FightState [state=2], new state=FightState [state=1]
23:52:23.685 [main] INFO  c.d.framework.game.fsm.TestFSM - 战斗中, 目标剩余血量=2
23:52:23.685 [main] INFO  c.d.framework.game.fsm.TestFSM - 战斗中, 目标剩余血量=1
23:52:23.685 [main] INFO  c.d.f.game.fsm.FiniteStateMachine - Change State -- old state=FightState [state=1], new state=FightState [state=0]
23:52:23.685 [main] INFO  c.d.framework.game.fsm.TestFSM - 待机中
23:52:23.685 [main] INFO  c.d.f.game.fsm.FiniteStateMachine - Change State -- old state=FightState [state=0], new state=FightState [state=1]
23:52:23.685 [main] INFO  c.d.framework.game.fsm.TestFSM - 战斗中, 目标剩余血量=0
23:52:23.685 [main] INFO  c.d.f.game.fsm.FiniteStateMachine - Change State -- old state=FightState [state=1], new state=FightState [state=0]
23:52:23.685 [main] INFO  c.d.framework.game.fsm.TestFSM - 待机中

上述测试例子只是一个简单的怪物 AI，在真实游戏中，AI 会比这个复杂得多，大家可以利用状态机自行进行设计。

需要注意的是，上述代码使用的是 Java 语言，但 FSM 的原理是通用的，大家可以根据需要将其转换为其他语言。毕竟，语言只是工具。