有限状态机在游戏中的应用

游戏里经常有各种AI行为，例如怪物砍人，玩家自动挂机等等。假设有这样的简易场景

场景里的一只怪物平时就在洞口巡逻。当遇到敌人的时候，如果比对方强大，就揍敌人；如果比敌人弱，就绕道逃跑。

用switch或if语句，很简易实现上面的需求

enum State {
    Patrol,
	RunAway,
	Attack
};

void onUpdate(State currState) {
	
	switch(currStage) {
		case Patrol: {
			if (seeEnemy()) {
				if (StrongerThanEnemy) {
					changeState(Attack);
				} else {
					changeState(RunAway);
				}
			}
			break;
		}
		case Attack: {
			// 快死啦
			if (willDieSoon()) {
				changeState(RunAway);
			} else {
				if (enemyDie()) {
					changeState(Patrol);
				}
			}
			break;
		}
		case RunAway: {
			if (safeNow()) {
				changeState(Patrol);
			}
			break;
		}
	}

}

乍看一下，这样实现的合理的。但在实际应用场合中，如果碰到状态复杂的情况，这样的代码就变成了恶梦。

有两种比较简单的方法来实现游戏ai。一种是行为树，也叫决策树。另外一种，就是今天要讲的方法，即有限状态机。

一个有限状态机，是一种具有有限数量状态的智能体。在给定的状态下接受某些事件，就能从一个状态切换到另外一个状态。一个有限状态机，在任何时刻都只能处于一种状态。

最简单的状态机，可以通过灯的开关来理解。灯有两种状态，开或关。在开的状态接受点击事件，就会切换成关闭状态；在关的状态下接受点击事件，就会切换成打开状态。

状态变换表

一个用于组织状态和影响状态切换的方法就是制定一个状态变换表。

在设计ＡＩ的时候，一定要清楚状态的变换流程，不然很容易使智能体陷入某一个状态而走不出来。

下面我们使用设计模式里的“状态模式”来实现有限状态机的代码。

对于每一个状态，我们至少需要三个方法。

public interface State {
	
	/**
	 * 切换至新状态
	 * @param creature
	 */
	void onEnter(Creature creature);
	
	/**
	 * 离开当前状态
	 * @param creature
	 */
	void onExit(Creature creature);
	
	/**
	 * 每一个tick跑的业务
	 * @param creature
	 */
	void execute(Creature creature);

}

给出一个攻击的状态实现，其他状态代码类似

public class AttackState implements State {

	@Override
	public void onEnter(Creature creature) {
		// 进入攻击状态
		
	}

	@Override
	public void onExit(Creature creature) {
		// 离开攻击状态
	}

	@Override
	public void execute(Creature creature) {
		Player player = (Player)creature;
		Scene scene = player.getScene();
		Monster monster = scene.getMonster();
		player.changeHp(-monster.getAttack());
		monster.changeHp(-player.getAttack());
		System.err.println("邂逅敌人，快使用双截棍，哼哼哈兮。"
				+ "我方血量["+ player.getHp() + "]"
				+ "敌方血量["+ monster.getHp() + "]");

	}

}

状态切换规则(Transition抽象类)，需要绑定开始状态和结束状态，以及抽象方法用于判断智能体在当前的状态下能否发生转换。

public abstract class Transition {

	/**　开始状态 */
	private State from;
	/** 结束状态　*/
	private State to;
	
	public Transition(State from, State to) {
		this.from = from;
		this.to = to;
	}
	
	/**
	 * 条件判定
	 * @param creature
	 * @return
	 */
	public abstract boolean meetCondition(Creature creature);

	public State fromState() {
		return this.from;
	}
	
	public State toState() {
		return this.to;
	}
	
}

给出一种状态的实现，其他代码类似

public class Attack2RunTransition extends Transition {

	public Attack2RunTransition(State from, State to) {
		super(from, to);
	}

	@Override
	public boolean meetCondition(Creature creature) {
		// 如果当前在攻击状态，且攻击力比怪物低，那就赶紧逃命吧
		Player player = (Player)creature;
		Scene scene = player.getScene();
		return  player.getHp() < 50 	// 快死啦
				|| player.getAttack() > scene.getMonster().getAttack()
				|| Math.random() < 0.4	; //有概率逃跑，增大随机事件
	}

}

有限状态机（智能体业务执行者）

public class FiniteStateMachine {
	
	private State initState;
	
	private State currState;
	/** 各种状态以及对应的转换规则 */
	private Map<State, List<Transition>> state2Transtions = new HashMap<>();
	/** 为了支持ai暂停 */
	private volatile boolean running = true;
	/** 恢复ai超时时间　*/
	private long freezeTimeOut;

	public void addTransition(Transition transition) {
		List<Transition> transitions = state2Transtions.get(transition.fromState());
		if (transitions == null) {
			transitions = new ArrayList<>();
			state2Transtions.put(transition.fromState(), transitions);
		}
		transitions.add(transition);
	}
	
	public State getInitState() {
		return initState;
	}

	public void setInitState(State initState) {
		this.initState = initState;
	}

	public void enterFrame(Creature creature) {

		if (this.currState == null) {
			this.currState = this.initState;
			this.currState.onEnter(creature);
		}

		Set<String> passed = new HashSet<>();
		String clazzName = this.currState.getClass().getName();

		for (; ;) {

			if (!running) {
				if (freezeTimeOut > 0 && System.currentTimeMillis() > freezeTimeOut) {
					running = true;
				} else {
					break;
				}

			} 

			this.currState.execute(creature);
			if (passed.contains(clazzName)) {
				break;
			}
			passed.add(clazzName);

			List<Transition> transitions = state2Transtions.get(this.currState);
			for (Transition transition:transitions) {
				if (transition.meetCondition(creature)) {
					this.currState.onExit(creature);
					this.currState = transition.toState();
					this.currState.onEnter(creature);
				}
			}
		}

	}
	
	/**
	 * 暂停ai
	 * @param timeout
	 */
	public void freeze(long timeout) {
		this.freezeTimeOut = System.currentTimeMillis() + timeout;
	}

}

示例代码

public class AiTest {
	
	public static void main(String[] args) throws Exception {
		Player player = new Player(100, 15);
		Monster monster = new Monster(120, 10);
		
		Scene scene = new Scene();
		scene.setPlayer(player);
		scene.setMonster(monster);
		
		player.setScene(scene);
		monster.setScene(scene);
		
		State patrolState = new PatrolState();
		State attackState = new AttackState();
		State runState = new RunAwayState();
		
		Transition transition1 = new Patrol2AttackTransition(patrolState, attackState);
		Transition transition2 = new Attack2RunTransition(attackState, runState);
		Transition transition3 = new Atttack2PatrolTransition(attackState, patrolState);
		Transition transition4 = new Run2PatrolTransition(runState, patrolState);
		
		FiniteStateMachine fsm = new FiniteStateMachine();
		fsm.setInitState(patrolState);
		
		fsm.addTransition(transition1);
		fsm.addTransition(transition2);
		fsm.addTransition(transition3);
		fsm.addTransition(transition4);
		
		while (true) {
			fsm.enterFrame(player);
			Thread.sleep(500);
		}
			
		
	}

}

代码运行结果(限于篇幅，部分截图不可见)

其他辅助代码

生物类(Creature)，玩家与怪物的父类

public abstract class Creature {
	
	protected long hp;
	
	protected int attack;
	
	private Scene scene;

	public Creature(long hp, int attack) {
		this.hp = hp;
		this.attack = attack;
	}

	public long getHp() {
		return hp;
	}

	public void setHp(long hp) {
		this.hp = hp;
	}
	
	public void changeHp(long changeHp) {
		this.hp += changeHp;
	}

	public int getAttack() {
		return attack;
	}

	public void setAttack(int attack) {
		this.attack = attack;
	}
	
	public Scene getScene() {
		return scene;
	}

	public void setScene(Scene scene) {
		this.scene = scene;
	}
	
	public boolean isDie() {
		return this.hp <= 0;
	}

}

玩家类。怪物类与它相似，换个名字即可

public class Player extends Creature {
	

	public Player(long hp, int attack) {
		super(hp, attack);
	}

	@Override
	public String toString() {
		return "Player [hp=" + hp + ", attack=" + attack + "]";
	}
	
}

场景类

public class Scene {
	
	private Player player;
	
	private Monster monster;

	public Player getPlayer() {
		return player;
	}

	public void setPlayer(Player player) {
		this.player = player;
	}

	public Monster getMonster() {
		return monster;
	}

	public void setMonster(Monster monster) {
		this.monster = monster;
	}

}

　分层有限状态机

如果某个状态本身又是由一系统小状态组成的，那么为了方便管理，我们可以使用分层次的有限状态机（HierarchicalFiniteStateMachine）。例如攻击状态，可细分为跟踪敌人->选择技能->战斗。这里就不展开了。

工程git路径 --> mmorpg框架