Pacman2

来自Botzone Wiki
跳转至: 导航搜索

吃豆人2(Pacman2)是Botzone平台上的四人回合制游戏

本游戏是Pacman游戏的改版,主要区别在于增加了一个技能。

作者

原游戏的裁判程序和播放器 zhouhy

改版 zys

故事

话说上古某朝,政局动荡,民不聊生,士人纷纷谈玄说道,修道蔚然成风。此中不乏心智坚毅之士得证长生,是以那穷苦人家常有送子上山、但求仙师点化之事。

...


是日,琼柰派山门外,四位敝衣少年长跪不起。

“去吧,今日还不是本派的收徒之日。”山门外的老者缓缓道,声若洪钟,却不震耳欲聋。

“仙师,请收下我们吧!”少年们的声音稍显喑哑,想必是许久未起,连一口水都没喝上。然而这声音中却透露着丝丝坚毅之意。

是啊,这四个少年的家人将希望都寄于彼身,就算是为了报答家人的养育之恩,也必须坚持下去。

“……”老者看了看他们,一脸无奈之情。少年们垂眉仰头,注目老者,也知老者非铁石心肠,实乃门派规矩难破。

“叮——”不知何处传来一声脆响,如珠玉落盘,悦耳至极。

“呼……也罢,既然那「翠柰木」已然结果,那今日便依门规对你们进行入门考校。”

琼柰派门规有言,「翠柰木」结果瞬间,山门前之人即为有缘之人,可予机会,以「翠柰木」相试,胜者入门,败者遣返。

说罢,四人眼前一花,转瞬便落足于一片小小苗圃之间。环顾四周,尽是迷宫一般的墙面。

目力所及还有奇形怪状的树。那树与凡间之树不同,不仅面有玉色、光泽亮丽,而且居然是寥寥几个平面便勾勒而出,不禁让四人大为赞叹。

“此为本派至宝「翠柰木」,已存活数千年,须得百年方一结果。你们也是好运气,正巧今日有此机缘,实在难得。”

从树下望去,晶莹剔透的玉果散落于各处。

“那么,你们四个,今日将要进行「翠柰木」之试炼。”

老者给他们每人一只奇怪的器物,其型似塔,却又有光芒流溢其中。

“这是你们试炼的防身器物,宝器·金光塔,可放金光,减损他人补益己身,其法有违天道,愿诸位慎用。试炼规则略为繁琐,现便与你们道来,请诸位静听——”

游戏规则

本游戏为四人回合制游戏,在矩形场地上进行。

规则比较复杂,但是#样例程序(C++版本)已经完全实现了规则的所有细节,并且有着充足的注释。

地图

游戏场地的长和宽都是[6, 12)的整数。

游戏场地上的基本单位是格子,每个格子的四周可能具有墙面、格子中央可能有内容。

裁判会自动生成随机地图,随机地图保证整个场地完全连通,场地沿着两条中轴线轴对称,这包括场地的初始道具、墙面、玩家初始位置等。

游戏场地的最外部可能不是封闭的

进行任何计算时,越界的坐标都会通过对宽或高取余而被折算回场地内,换句话说,从场地最下方向下走,可以从场地最上方回来。

人物

每名玩家控制地图上的一个人物。人物只能处于格子中。同一格子中可能有多个人物。

人物的序号在程序中分别是0、1、2、3,在界面上是1、2、3、4.

在地图上,每个人物会被分配一个初始位置。

人物不能穿墙。尝试穿墙将会导致被判定为不合法输入而死亡。

人物的属性有

  • 力量(代码中记为strength):表示自己的实力,游戏结束时仅依据游戏结束瞬间的力量(也包括力量增益)确定名次
  • 增益剩余回合(代码中记为powerUpLeft):表示自己由于使用大豆子而获得的力量增益还剩几回合。
  • 是否死亡

道具

游戏中每个格子上只能有一个道具。

地图生成的时候会有初始道具,对称分布于场地上。

游戏中的道具包括

  • 小豆子:玩家可以食用,永久增加1力量。
  • 大豆子:可以在【LARGE_FRUIT_DURATION】回合内让玩家的力量增加【LARGE_FRUIT_ENHANCEMENT】(目前两个变量的值都是10)
  • 豆子产生器(「翠柰木」):每隔【GENERATOR_INTERVAL】回合,在周围八个方向距离1的格子上尝试,如果格子上没有道具就会放置小豆子。(目前这个变量的值是20)

注意,豆子产生器是障碍物,玩家不能移动到它身上,否则会被判定为不合法输入而死亡。

(实际上这不用考虑,产生地图时会保证豆子产生器被墙完全围住

动作

每回合,玩家需要决定自己人物的行动。行动可以是移动、施放技能,或不动。

移动,即选择上、右、下、左任意一个方向行进一格。

除此之外,人物还可以选择施放技能(「宝器·金光塔」):

  • 每回合可以选择发动,发动则本回合不可移动
  • 发动需要消耗【SKILL_COST】力量,如果力量不足,即发动后力量小于等于0,则属于非法操作。(目前这个变量的值是4)
  • 向指定方向发射一道可以从边界折返可以被墙挡住不会被玩家和道具挡住的金光攻击。
    • 金光的攻击范围不包括发动者本身所在的格子。
  • 在完成移动后被金光击中的玩家会失去【SKILL_COST * 1.5】(向下取整)的力量,这些力量将会等量地转移给攻击者。结算过程中,玩家的力量可以小于0。
    • 本回合非被吃而死的玩家也会参与金光是否击中的判定。换言之,如果这些玩家生前最后所在的位置在金光范围内,那么就会被算作击中。
  • 多道金光同时击中玩家,失去的力量会叠加。
  • 在所有金光完成结算,玩家的力量小于等于0才会被判定为死亡,此时该玩家的力量将会被改为0。
    • 如果玩家具有大豆子的力量增益状态,则这里的力量也包括这部分增益的力量。因此可能会出现大豆子力量增益结束之后因力量小于等于0而死亡的情况。

如果你有兴趣,在选择了行动之后,你还可以提供一个字符串,让人物进行叫嚣。这不会影响你的行动,不过字符串最大长度为40,过长会被自动截断。由于编码问题,建议不要使用中文,或保证输出的中文是经过UTF-8编码。在Botzone上,你可以通过我的Bot页面,增加版本,然后使用在线编辑器上传代码,而不是直接上传代码文件,来保证文件是UTF-8编码。

移动有可能失败,这种失败的情况称为被“恐吓”。当且仅当你将要移动到的格子上有比你力量强大的人物时,你的行动会被系统替换成“不动”。具体流程可以参看#游戏每回合的判定流程

如果你移动到的格子上有道具,那么道具会生效,除非该格子上的玩家超过1个,此时道具无法生效。

战斗

如果一个格子上有多名玩家,而且玩家的力量有不同,那么玩家会进行战斗判定。具体流程可以参看#游戏每回合的判定流程

力量最大的所有玩家是战胜者,其他玩家是战败者。

战败者会失去一半的力量并死亡。(向上取整)

战胜者会获得另一半力量并平分。(向下取整)

游戏每回合的判定流程

  1. 分析输入,所有不合法输入者被杀死,这样死亡的玩家失去所有力量
    • 不合法输入包括移动方向有墙的情况、力量不足以施放技能的情况,也包括程序输出格式不对、超时、超内存等情况。
    • 目的地(考虑边界折回)有比自己力量大的玩家的话,自己的移动会被强制替换为不动(“恐吓”)
  2. 所有选择移动且没有施放技能的玩家向指定方向移动一格(超过边界,则折回到另一侧
  3. 现在检查玩家重叠的情况,如果一个格子上有多个玩家,那么在这几个玩家中
    • 力量最大的玩家(们)将会吞噬其他玩家
    • 被吞噬者将会全部死亡,其分数锁定为各自力量的一半(向上取整
      • 具有大豆子增益效果的玩家,大豆子赋予的力量不会丢失,且再也不会消失
    • 存活者们平分败者力量的另一半(向下取整,平分时也向下取整
    • 此时格子上玩家力量均相等,结束
  4. 施放技能的玩家在指定方向上发射金光
    • 所有技能发动者力量减少【SKILL_COST】
    • 对于每道金光,所有被金光命中的玩家(判定命中时也包括本回合非被吃而死的玩家)力量减少【SKILL_COST * 1.5】(向下取整
    • 对于每道金光,每命中一个玩家(判定命中时也包括本回合非被吃而死的玩家),技能发动者力量增加【SKILL_COST * 1.5】(向下取整
  5. 力量(包括大豆子的增益效果)小于等于0的玩家死亡,力量锁定为0
  6. 豆子产生器工作(超过边界折回,不能生成在产生器上)
  7. 如果玩家所在的格子上有豆子,且仅当格子上只有一个玩家
    • 玩家吃掉小豆,力量增加1
    • 玩家吃掉大豆
      • 如果增益剩余回合还未归零,那么累加【LARGE_FRUIT_DURATION】个回合
      • 如果增益剩余回合为0,力量增加【LARGE_FRUIT_ENHANCEMENT】,并且设置增益剩余回合为【LARGE_FRUIT_DURATION】
  8. 所有玩家的大豆剩余时间减少1,变为0的力量减少【LARGE_FRUIT_ENHANCEMENT】
  9. 力量(包括大豆子的增益效果)小于等于0的玩家死亡,力量锁定为0
  10. 回合序号加一
  11. 如果此时只剩一位玩家,开始进行游戏结束的结算
    • 只剩一位玩家时,该玩家立刻获得场上所有小豆
  12. 回合超限,开始进行游戏结束的结算

分数

玩家的分数由两部分构成。

第一部分是玩家力量所占比例百分比,计算方法如下:

10000 乘以 玩家力量 除以 全场总力量 向下取整 再除以 100
(10000 * gameField.players[_].strength / total) / 100.0

第二部分是玩家在游戏中排名的参数,计算方法如下:

10 乘以 玩家力量(并列)倒数第几
比如1~4号玩家力量分别是23,233,233,2333,那么他们的倒数排名为1,2,2,4,得分为10,20,20,40。

两部分相加的得分即为玩家最终在比赛中的得分。

游戏交互方式

强烈建议初学者直接参看#样例程序(C++版本),样例程序隐藏了具体交互的细节。

Botzone上其他游戏一样,本游戏每步(每次程序运行)限时1秒。

如果需要输出调试信息,请在输出的JSON对象中加debug域(或修改WriteOutput函数的ret["debug"]),调试信息将可在Log可视化工具中查看。

概述

本游戏与Botzone上其他游戏一样,使用相同的交互格式:Bot#交互

另外该游戏是支持初始化数据的游戏。初始化数据格式如下(最好写成单行JSON):

{
	"seed": Number, // 种子。拥有一个种子,就拥有了全世界。
	"width": Number, // 地图的宽度
	"height": Number,  // 地图的高度
	"GENERATOR_INTERVAL": Number,  // 产生器间隔
	"LARGE_FRUIT_DURATION": Number, // 大豆子增益回合数
	"LARGE_FRUIT_ENHANCEMENT": Number, // 大豆子增益力量
	"SKILL_COST": Number, // 施放技能所需力量
	"static": number[][], // 记录场地不变信息的二维数组(解析方法请参看PrepareInitialField)
	"content": number[][] // 记录场地可变信息的二维数组
}

具体交互内容

再次强烈建议初学者直接参看#样例程序(C++版本),样例程序隐藏了具体交互的细节。

第一回合玩家会收到上述的初始化数据,是一个JSON对象。

此后回合玩家收到一个JSON对象,表示每个玩家的动作。具体格式如下:

{
	"0": {
		"action": Number
	},
	"1": {
		"action": Number
	},
	"2": {
		"action": Number
	},
	"3": {
		"action": Number
	}
}

注意死亡的玩家将没有对应的动作信息对象。

每回合玩家也应该输出自己的动作,格式如下:

{
	"action": Number,
	"tauntText": String
}

其中,action是[-1, 8)的整数,分别表示“不动、向上、向右、向下、向左、向上发动技能、向右发动技能、向下发动技能、向左发动技能”五种动作类型。

tauntText是本回合叫嚣的文字。可以留空,超过40个字节部分将会被截断。由于编码问题,建议不要输出中文,或保证输出的中文是UTF-8编码。在Botzone上,你可以通过我的Bot页面,增加版本,然后使用在线编辑器上传代码,而不是直接上传代码文件,来保证文件是UTF-8编码。

样例程序(C++版本)

本地编译和调试的方式请查看 JSONCPP

类的使用方法请参看main函数的写法。注意GameField类不要创建多个对象!

/*
* Pacman2 样例程序
* 作者:zhouhy
* 时间:2016/10/12 12:54
*
* 【命名惯例】
*  r/R/y/Y:Row,行,纵坐标
*  c/C/x/X:Column,列,横坐标
*  数组的下标都是[y][x]或[r][c]的顺序
*  玩家编号0123
*
* 【坐标系】
*   0 1 2 3 4 5 6 7 8
* 0 +----------------> x
* 1 |
* 2 |
* 3 |
* 4 |
* 5 |
* 6 |
* 7 |
* 8 |
*   v y
*
* 【提示】你可以使用
* #ifndef _BOTZONE_ONLINE
* 这样的预编译指令来区分在线评测和本地评测
*
* 【提示】一般的文本编辑器都会支持将代码块折叠起来
* 如果你觉得自带代码太过冗长,可以考虑将整个namespace折叠
*/
 
#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <stack>
#include <stdexcept>
#include "jsoncpp/json.h"
 
#define FIELD_MAX_HEIGHT 20
#define FIELD_MAX_WIDTH 20
#define MAX_GENERATOR_COUNT 4 // 每个象限1
#define MAX_PLAYER_COUNT 4
#define MAX_TURN 100
 
// 你也可以选用 using namespace std; 但是会污染命名空间
using std::string;
using std::swap;
using std::cin;
using std::cout;
using std::endl;
using std::getline;
using std::runtime_error;
 
// 平台提供的吃豆人相关逻辑处理程序
namespace Pacman
{
	const time_t seed = time(0);
	const int dx[] = { 0, 1, 0, -1, 1, 1, -1, -1 }, dy[] = { -1, 0, 1, 0, -1, 1, 1, -1 };
 
	// 枚举定义;使用枚举虽然会浪费空间(sizeof(GridContentType) == 4),但是计算机处理32位的数字效率更高
 
	// 每个格子可能变化的内容,会采用“或”逻辑进行组合
	enum GridContentType
	{
		empty = 0, // 其实不会用到
		player1 = 1, // 1号玩家
		player2 = 2, // 2号玩家
		player3 = 4, // 3号玩家
		player4 = 8, // 4号玩家
		playerMask = 1 | 2 | 4 | 8, // 用于检查有没有玩家等
		smallFruit = 16, // 小豆子
		largeFruit = 32 // 大豆子
	};
 
	// 用玩家ID换取格子上玩家的二进制位
	GridContentType playerID2Mask[] = { player1, player2, player3, player4 };
	string playerID2str[] = { "0", "1", "2", "3" };
 
	// 让枚举也可以用这些运算了(不加会编译错误)
	template<typename T>
	inline T operator |=(T &a, const T &b)
	{
		return a = static_cast<T>(static_cast<int>(a) | static_cast<int>(b));
	}
	template<typename T>
	inline T operator |(const T &a, const T &b)
	{
		return static_cast<T>(static_cast<int>(a) | static_cast<int>(b));
	}
	template<typename T>
	inline T operator &=(T &a, const T &b)
	{
		return a = static_cast<T>(static_cast<int>(a) & static_cast<int>(b));
	}
	template<typename T>
	inline T operator &(const T &a, const T &b)
	{
		return static_cast<T>(static_cast<int>(a) & static_cast<int>(b));
	}
	template<typename T>
	inline T operator -(const T &a, const T &b)
	{
		return static_cast<T>(static_cast<int>(a) - static_cast<int>(b));
	}
	template<typename T>
	inline T operator ++(T &a)
	{
		return a = static_cast<T>(static_cast<int>(a) + 1);
	}
	template<typename T>
	inline T operator ~(const T &a)
	{
		return static_cast<T>(~static_cast<int>(a));
	}
 
	// 每个格子固定的东西,会采用“或”逻辑进行组合
	enum GridStaticType
	{
		emptyWall = 0, // 其实不会用到
		wallNorth = 1, // 北墙(纵坐标减少的方向)
		wallEast = 2, // 东墙(横坐标增加的方向)
		wallSouth = 4, // 南墙(纵坐标增加的方向)
		wallWest = 8, // 西墙(横坐标减少的方向)
		generator = 16 // 豆子产生器
	};
 
	// 用移动方向换取这个方向上阻挡着的墙的二进制位
	GridStaticType direction2OpposingWall[] = { wallNorth, wallEast, wallSouth, wallWest };
 
	// 方向,可以代入dx、dy数组,同时也可以作为玩家的动作
	enum Direction
	{
		stay = -1,
		up = 0,
		right = 1,
		down = 2,
		left = 3,
		shootUp = 4, // 向上发射金光
		shootRight = 5, // 向右发射金光
		shootDown = 6, // 向下发射金光
		shootLeft = 7 // 向左发射金光
	};
 
	// 场地上带有坐标的物件
	struct FieldProp
	{
		int row, col;
	};
 
	// 场地上的玩家
	struct Player : FieldProp
	{
		int strength;
		int powerUpLeft;
		bool dead;
	};
 
	// 回合新产生的豆子的坐标
	struct NewFruits
	{
		FieldProp newFruits[MAX_GENERATOR_COUNT * 8];
		int newFruitCount;
	} newFruits[MAX_TURN];
	int newFruitsCount = 0;
 
	// 状态转移记录结构
	struct TurnStateTransfer
	{
		enum StatusChange // 可组合
		{
			none = 0,
			ateSmall = 1,
			ateLarge = 2,
			powerUpDrop = 4,
			die = 8,
			error = 16
		};
 
		// 玩家选定的动作
		Direction actions[MAX_PLAYER_COUNT];
 
		// 此回合该玩家的状态变化
		StatusChange change[MAX_PLAYER_COUNT];
 
		// 此回合该玩家的力量变化
		int strengthDelta[MAX_PLAYER_COUNT];
	};
 
	// 游戏主要逻辑处理类,包括输入输出、回合演算、状态转移,全局唯一
	class GameField
	{
	private:
		// 为了方便,大多数属性都不是private的
 
		// 记录每回合的变化(栈)
		TurnStateTransfer backtrack[MAX_TURN];
 
		// 这个对象是否已经创建
		static bool constructed;
 
	public:
		// 场地的长和宽
		int height, width;
		int generatorCount;
		int GENERATOR_INTERVAL, LARGE_FRUIT_DURATION, LARGE_FRUIT_ENHANCEMENT, SKILL_COST;
 
		// 场地格子固定的内容
		GridStaticType fieldStatic[FIELD_MAX_HEIGHT][FIELD_MAX_WIDTH];
 
		// 场地格子会变化的内容
		GridContentType fieldContent[FIELD_MAX_HEIGHT][FIELD_MAX_WIDTH];
		int generatorTurnLeft; // 多少回合后产生豆子
		int aliveCount; // 有多少玩家存活
		int smallFruitCount;
		int turnID;
		FieldProp generators[MAX_GENERATOR_COUNT]; // 有哪些豆子产生器
		Player players[MAX_PLAYER_COUNT]; // 有哪些玩家
 
										  // 玩家选定的动作
		Direction actions[MAX_PLAYER_COUNT];
 
		// 恢复到上次场地状态。可以一路恢复到最开始。
		// 恢复失败(没有状态可恢复)返回false
		bool PopState()
		{
			if (turnID <= 0)
				return false;
 
			const TurnStateTransfer &bt = backtrack[--turnID];
			int i, _;
 
			// 倒着来恢复状态
 
			for (_ = 0; _ < MAX_PLAYER_COUNT; _++)
			{
				Player &_p = players[_];
				GridContentType &content = fieldContent[_p.row][_p.col];
				TurnStateTransfer::StatusChange change = bt.change[_];
 
				// 5. 大豆回合恢复
				if (change & TurnStateTransfer::powerUpDrop)
					_p.powerUpLeft++;
 
				// 4. 吐出豆子
				if (change & TurnStateTransfer::ateSmall)
				{
					content |= smallFruit;
					smallFruitCount++;
				}
				else if (change & TurnStateTransfer::ateLarge)
				{
					content |= largeFruit;
					_p.powerUpLeft -= LARGE_FRUIT_DURATION;
				}
 
				// 2. 魂兮归来
				if (change & TurnStateTransfer::die)
				{
					_p.dead = false;
					aliveCount++;
					content |= playerID2Mask[_];
				}
 
				// 1. 移形换影
				if (!_p.dead && bt.actions[_] != stay && bt.actions[_] < shootUp)
				{
					fieldContent[_p.row][_p.col] &= ~playerID2Mask[_];
					_p.row = (_p.row - dy[bt.actions[_]] + height) % height;
					_p.col = (_p.col - dx[bt.actions[_]] + width) % width;
					fieldContent[_p.row][_p.col] |= playerID2Mask[_];
				}
 
				// 0. 救赎不合法的灵魂
				if (change & TurnStateTransfer::error)
				{
					_p.dead = false;
					aliveCount++;
					content |= playerID2Mask[_];
				}
 
				// *. 恢复力量
				_p.strength -= bt.strengthDelta[_];
			}
 
			// 3. 收回豆子
			if (generatorTurnLeft == GENERATOR_INTERVAL)
			{
				generatorTurnLeft = 1;
				NewFruits &fruits = newFruits[--newFruitsCount];
				for (i = 0; i < fruits.newFruitCount; i++)
				{
					fieldContent[fruits.newFruits[i].row][fruits.newFruits[i].col] &= ~smallFruit;
					smallFruitCount--;
				}
			}
			else
				generatorTurnLeft++;
 
			return true;
		}
 
		// 判断指定玩家向指定方向移动/施放技能是不是合法的(没有撞墙且没有踩到豆子产生器、力量足够)
		inline bool ActionValid(int playerID, Direction &dir) const
		{
			if (dir == stay)
				return true;
			const Player &p = players[playerID];
			if (dir >= shootUp)
				return dir < 8 && p.strength > SKILL_COST;
			return dir >= 0 && dir < 4 &&
				!(fieldStatic[p.row][p.col] & direction2OpposingWall[dir]);
		}
 
		// 在向actions写入玩家动作后,演算下一回合局面,并记录之前所有的场地状态,可供日后恢复。
		// 是终局的话就返回false
		bool NextTurn()
		{
			int _, i, j;
 
			TurnStateTransfer &bt = backtrack[turnID];
			memset(&bt, 0, sizeof(bt));
 
			// 0. 杀死不合法输入
			for (_ = 0; _ < MAX_PLAYER_COUNT; _++)
			{
				Player &p = players[_];
				if (!p.dead)
				{
					Direction &action = actions[_];
					if (action == stay)
						continue;
 
					if (!ActionValid(_, action))
					{
						bt.strengthDelta[_] += -p.strength;
						bt.change[_] = TurnStateTransfer::error;
						fieldContent[p.row][p.col] &= ~playerID2Mask[_];
						p.strength = 0;
						p.dead = true;
						aliveCount--;
					}
					else if (action < shootUp)
					{
						// 遇到比自己强♂壮的玩家是不能前进的
						GridContentType target = fieldContent
							[(p.row + dy[action] + height) % height]
						[(p.col + dx[action] + width) % width];
						if (target & playerMask)
							for (i = 0; i < MAX_PLAYER_COUNT; i++)
								if (target & playerID2Mask[i] && players[i].strength > p.strength)
									action = stay;
					}
				}
			}
 
			// 1. 位置变化
			for (_ = 0; _ < MAX_PLAYER_COUNT; _++)
			{
				Player &_p = players[_];
 
				bt.actions[_] = actions[_];
 
				if (_p.dead || actions[_] == stay || actions[_] >= shootUp)
					continue;
 
				// 移动
				fieldContent[_p.row][_p.col] &= ~playerID2Mask[_];
				_p.row = (_p.row + dy[actions[_]] + height) % height;
				_p.col = (_p.col + dx[actions[_]] + width) % width;
				fieldContent[_p.row][_p.col] |= playerID2Mask[_];
			}
 
			// 2. 玩家互殴
			for (_ = 0; _ < MAX_PLAYER_COUNT; _++)
			{
				Player &_p = players[_];
				if (_p.dead)
					continue;
 
				// 判断是否有玩家在一起
				int player, containedCount = 0;
				int containedPlayers[MAX_PLAYER_COUNT];
				for (player = 0; player < MAX_PLAYER_COUNT; player++)
					if (fieldContent[_p.row][_p.col] & playerID2Mask[player])
						containedPlayers[containedCount++] = player;
 
				if (containedCount > 1)
				{
					// NAIVE
					for (i = 0; i < containedCount; i++)
						for (j = 0; j < containedCount - i - 1; j++)
							if (players[containedPlayers[j]].strength < players[containedPlayers[j + 1]].strength)
								swap(containedPlayers[j], containedPlayers[j + 1]);
 
					int begin;
					for (begin = 1; begin < containedCount; begin++)
						if (players[containedPlayers[begin - 1]].strength > players[containedPlayers[begin]].strength)
							break;
 
					// 这些玩家将会被杀死
					int lootedStrength = 0;
					for (i = begin; i < containedCount; i++)
					{
						int id = containedPlayers[i];
						Player &p = players[id];
 
						// 从格子上移走
						fieldContent[p.row][p.col] &= ~playerID2Mask[id];
						p.dead = true;
						int drop = p.strength / 2;
						bt.strengthDelta[id] += -drop;
						bt.change[id] |= TurnStateTransfer::die;
						lootedStrength += drop;
						p.strength -= drop;
						aliveCount--;
					}
 
					// 分配给其他玩家
					int inc = lootedStrength / begin;
					for (i = 0; i < begin; i++)
					{
						int id = containedPlayers[i];
						Player &p = players[id];
						bt.strengthDelta[id] += inc;
						p.strength += inc;
					}
				}
			}
 
			// 2.5 金光法器
			for (_ = 0; _ < MAX_PLAYER_COUNT; _++)
			{
				Player &_p = players[_];
				if (_p.dead || actions[_] < shootUp)
					continue;
 
				_p.strength -= SKILL_COST;
				bt.strengthDelta[_] -= SKILL_COST;
 
				int r = _p.row, c = _p.col, player;
				Direction dir = actions[_] - shootUp;
 
				// 向指定方向发射金光(扫描格子直到被挡)
				while (!(fieldStatic[r][c] & direction2OpposingWall[dir]))
				{
					r = (r + dy[dir] + height) % height;
					c = (c + dx[dir] + width) % width;
 
					// 如果转了一圈回来……
					if (r == _p.row && c == _p.col)
						break;
 
					if (fieldContent[r][c] & playerMask)
						for (player = 0; player < MAX_PLAYER_COUNT; player++)
							if (fieldContent[r][c] & playerID2Mask[player])
							{
								players[player].strength -= SKILL_COST * 1.5;
								bt.strengthDelta[player] -= SKILL_COST * 1.5;
								_p.strength += SKILL_COST * 1.5;
								bt.strengthDelta[_] += SKILL_COST * 1.5;
							}
				}
			}
 
			// *. 检查一遍有无死亡玩家
			for (_ = 0; _ < MAX_PLAYER_COUNT; _++)
			{
				Player &_p = players[_];
				if (_p.dead || _p.strength > 0)
					continue;
 
				// 从格子上移走
				fieldContent[_p.row][_p.col] &= ~playerID2Mask[_];
				_p.dead = true;
 
				// 使其力量变为0
				bt.strengthDelta[_] += -_p.strength;
				bt.change[_] |= TurnStateTransfer::die;
				_p.strength = 0;
				aliveCount--;
			}
 
 
			// 3. 产生豆子
			if (--generatorTurnLeft == 0)
			{
				generatorTurnLeft = GENERATOR_INTERVAL;
				NewFruits &fruits = newFruits[newFruitsCount++];
				fruits.newFruitCount = 0;
				for (i = 0; i < generatorCount; i++)
					for (Direction d = up; d < 8; ++d)
					{
						// 取余,穿过场地边界
						int r = (generators[i].row + dy[d] + height) % height, c = (generators[i].col + dx[d] + width) % width;
						if (fieldStatic[r][c] & generator || fieldContent[r][c] & (smallFruit | largeFruit))
							continue;
						fieldContent[r][c] |= smallFruit;
						fruits.newFruits[fruits.newFruitCount].row = r;
						fruits.newFruits[fruits.newFruitCount++].col = c;
						smallFruitCount++;
					}
			}
 
			// 4. 吃掉豆子
			for (_ = 0; _ < MAX_PLAYER_COUNT; _++)
			{
				Player &_p = players[_];
				if (_p.dead)
					continue;
 
				GridContentType &content = fieldContent[_p.row][_p.col];
 
				// 只有在格子上只有自己的时候才能吃掉豆子
				if (content & playerMask & ~playerID2Mask[_])
					continue;
 
				if (content & smallFruit)
				{
					content &= ~smallFruit;
					_p.strength++;
					bt.strengthDelta[_]++;
					smallFruitCount--;
					bt.change[_] |= TurnStateTransfer::ateSmall;
				}
				else if (content & largeFruit)
				{
					content &= ~largeFruit;
					if (_p.powerUpLeft == 0)
					{
						_p.strength += LARGE_FRUIT_ENHANCEMENT;
						bt.strengthDelta[_] += LARGE_FRUIT_ENHANCEMENT;
					}
					_p.powerUpLeft += LARGE_FRUIT_DURATION;
					bt.change[_] |= TurnStateTransfer::ateLarge;
				}
			}
 
			// 5. 大豆回合减少
			for (_ = 0; _ < MAX_PLAYER_COUNT; _++)
			{
				Player &_p = players[_];
				if (_p.dead)
					continue;
 
				if (_p.powerUpLeft > 0)
				{
					bt.change[_] |= TurnStateTransfer::powerUpDrop;
					if (--_p.powerUpLeft == 0)
					{
						_p.strength -= LARGE_FRUIT_ENHANCEMENT;
						bt.strengthDelta[_] += -LARGE_FRUIT_ENHANCEMENT;
					}
				}
			}
 
			// *. 检查一遍有无死亡玩家
			for (_ = 0; _ < MAX_PLAYER_COUNT; _++)
			{
				Player &_p = players[_];
				if (_p.dead || _p.strength > 0)
					continue;
 
				// 从格子上移走
				fieldContent[_p.row][_p.col] &= ~playerID2Mask[_];
				_p.dead = true;
 
				// 使其力量变为0
				bt.strengthDelta[_] += -_p.strength;
				bt.change[_] |= TurnStateTransfer::die;
				_p.strength = 0;
				aliveCount--;
			}
 
			++turnID;
 
			// 是否只剩一人?
			if (aliveCount <= 1)
			{
				for (_ = 0; _ < MAX_PLAYER_COUNT; _++)
					if (!players[_].dead)
					{
						bt.strengthDelta[_] += smallFruitCount;
						players[_].strength += smallFruitCount;
					}
				return false;
			}
 
			// 是否回合超限?
			if (turnID >= 100)
				return false;
 
			return true;
		}
 
		// 读取并解析程序输入,本地调试或提交平台使用都可以。
		// 如果在本地调试,程序会先试着读取参数中指定的文件作为输入文件,失败后再选择等待用户直接输入。
		// 本地调试时可以接受多行以便操作,Windows下可以用 Ctrl-Z 或一个【空行+回车】表示输入结束,但是在线评测只需接受单行即可。
		// localFileName 可以为NULL
		// obtainedData 会输出自己上回合存储供本回合使用的数据
		// obtainedGlobalData 会输出自己的 Bot 上以前存储的数据
		// 返回值是自己的 playerID
		int ReadInput(const char *localFileName, string &obtainedData, string &obtainedGlobalData)
		{
			string str, chunk;
#ifdef _BOTZONE_ONLINE
			std::ios::sync_with_stdio(false); //ω\\)
			getline(cin, str);
#else
			if (localFileName)
			{
				std::ifstream fin(localFileName);
				if (fin)
					while (getline(fin, chunk) && chunk != "")
						str += chunk;
				else
					while (getline(cin, chunk) && chunk != "")
						str += chunk;
			}
			else
				while (getline(cin, chunk) && chunk != "")
					str += chunk;
#endif
			Json::Reader reader;
			Json::Value input;
			reader.parse(str, input);
 
			int len = input["requests"].size();
 
			// 读取场地静态状况
			Json::Value field = input["requests"][(Json::Value::UInt) 0],
				staticField = field["static"], // 墙面和产生器
				contentField = field["content"]; // 豆子和玩家
			height = field["height"].asInt();
			width = field["width"].asInt();
			LARGE_FRUIT_DURATION = field["LARGE_FRUIT_DURATION"].asInt();
			LARGE_FRUIT_ENHANCEMENT = field["LARGE_FRUIT_ENHANCEMENT"].asInt();
			SKILL_COST = field["SKILL_COST"].asInt();
			generatorTurnLeft = GENERATOR_INTERVAL = field["GENERATOR_INTERVAL"].asInt();
 
			PrepareInitialField(staticField, contentField);
 
			// 根据历史恢复局面
			for (int i = 1; i < len; i++)
			{
				Json::Value req = input["requests"][i];
				for (int _ = 0; _ < MAX_PLAYER_COUNT; _++)
					if (!players[_].dead)
						actions[_] = (Direction)req[playerID2str[_]]["action"].asInt();
				NextTurn();
			}
 
			obtainedData = input["data"].asString();
			obtainedGlobalData = input["globaldata"].asString();
 
			return field["id"].asInt();
		}
 
		// 根据 static 和 content 数组准备场地的初始状况
		void PrepareInitialField(const Json::Value &staticField, const Json::Value &contentField)
		{
			int r, c, gid = 0;
			generatorCount = 0;
			aliveCount = 0;
			smallFruitCount = 0;
			generatorTurnLeft = GENERATOR_INTERVAL;
			for (r = 0; r < height; r++)
				for (c = 0; c < width; c++)
				{
					GridContentType &content = fieldContent[r][c] = (GridContentType)contentField[r][c].asInt();
					GridStaticType &s = fieldStatic[r][c] = (GridStaticType)staticField[r][c].asInt();
					if (s & generator)
					{
						generators[gid].row = r;
						generators[gid++].col = c;
						generatorCount++;
					}
					if (content & smallFruit)
						smallFruitCount++;
					for (int _ = 0; _ < MAX_PLAYER_COUNT; _++)
						if (content & playerID2Mask[_])
						{
							Player &p = players[_];
							p.col = c;
							p.row = r;
							p.powerUpLeft = 0;
							p.strength = 1;
							p.dead = false;
							aliveCount++;
						}
				}
		}
 
		// 完成决策,输出结果。
		// action 表示本回合的移动方向,stay 为不移动,shoot开头的动作表示向指定方向施放技能
		// tauntText 表示想要叫嚣的言语,可以是任意字符串,除了显示在屏幕上不会有任何作用,留空表示不叫嚣
		// data 表示自己想存储供下一回合使用的数据,留空表示删除
		// globalData 表示自己想存储供以后使用的数据(替换),这个数据可以跨对局使用,会一直绑定在这个 Bot 上,留空表示删除
		void WriteOutput(Direction action, string tauntText = "", string data = "", string globalData = "") const
		{
			Json::Value ret;
			ret["response"]["action"] = action;
			ret["response"]["tauntText"] = tauntText;
			ret["data"] = data;
			ret["globaldata"] = globalData;
			ret["debug"] = (Json::Int)seed;
 
#ifdef _BOTZONE_ONLINE
			Json::FastWriter writer; // 在线评测的话能用就行……
#else
			Json::StyledWriter writer; // 本地调试这样好看 > <
#endif
			cout << writer.write(ret) << endl;
		}
 
		// 用于显示当前游戏状态,调试用。
		// 提交到平台后会被优化掉。
		inline void DebugPrint() const
		{
#ifndef _BOTZONE_ONLINE
			printf("回合号【%d】存活人数【%d】| 图例 产生器[G] 有玩家[0/1/2/3] 多个玩家[*] 大豆[o] 小豆[.]\n", turnID, aliveCount);
			for (int _ = 0; _ < MAX_PLAYER_COUNT; _++)
			{
				const Player &p = players[_];
				printf("[玩家%d(%d, %d)|力量%d|加成剩余回合%d|%s]\n",
					_, p.row, p.col, p.strength, p.powerUpLeft, p.dead ? "死亡" : "存活");
			}
			putchar(' ');
			putchar(' ');
			for (int c = 0; c < width; c++)
				printf("  %d ", c);
			putchar('\n');
			for (int r = 0; r < height; r++)
			{
				putchar(' ');
				putchar(' ');
				for (int c = 0; c < width; c++)
				{
					putchar(' ');
					printf((fieldStatic[r][c] & wallNorth) ? "---" : "   ");
				}
				printf("\n%d ", r);
				for (int c = 0; c < width; c++)
				{
					putchar((fieldStatic[r][c] & wallWest) ? '|' : ' ');
					putchar(' ');
					int hasPlayer = -1;
					for (int _ = 0; _ < MAX_PLAYER_COUNT; _++)
						if (fieldContent[r][c] & playerID2Mask[_])
							if (hasPlayer == -1)
								hasPlayer = _;
							else
								hasPlayer = 4;
					if (hasPlayer == 4)
						putchar('*');
					else if (hasPlayer != -1)
						putchar('0' + hasPlayer);
					else if (fieldStatic[r][c] & generator)
						putchar('G');
					else if (fieldContent[r][c] & playerMask)
						putchar('*');
					else if (fieldContent[r][c] & smallFruit)
						putchar('.');
					else if (fieldContent[r][c] & largeFruit)
						putchar('o');
					else
						putchar(' ');
					putchar(' ');
				}
				putchar((fieldStatic[r][width - 1] & wallEast) ? '|' : ' ');
				putchar('\n');
			}
			putchar(' ');
			putchar(' ');
			for (int c = 0; c < width; c++)
			{
				putchar(' ');
				printf((fieldStatic[height - 1][c] & wallSouth) ? "---" : "   ");
			}
			putchar('\n');
#endif
		}
 
		Json::Value SerializeCurrentTurnChange()
		{
			Json::Value result;
			TurnStateTransfer &bt = backtrack[turnID - 1];
			for (int _ = 0; _ < MAX_PLAYER_COUNT; _++)
			{
				result["actions"][_] = bt.actions[_];
				result["strengthDelta"][_] = bt.strengthDelta[_];
				result["change"][_] = bt.change[_];
			}
			return result;
		}
 
		// 初始化游戏管理器
		GameField()
		{
			if (constructed)
				throw runtime_error("请不要再创建 GameField 对象了,整个程序中只应该有一个对象");
			constructed = true;
 
			turnID = 0;
		}
 
		GameField(const GameField &b) : GameField() { }
	};
 
	bool GameField::constructed = false;
}
 
// 一些辅助程序
namespace Helpers
{
 
	double actionScore[9] = {};
 
	inline int RandBetween(int a, int b)
	{
		if (a > b)
			swap(a, b);
		return rand() % (b - a) + a;
	}
 
	void RandomPlay(Pacman::GameField &gameField, int myID)
	{
		int count = 0, myAct = -1;
		while (true)
		{
			// 对每个玩家生成随机的合法动作
			for (int i = 0; i < MAX_PLAYER_COUNT; i++)
			{
				if (gameField.players[i].dead)
					continue;
				Pacman::Direction valid[9];
				int vCount = 0;
				for (Pacman::Direction d = Pacman::stay; d < 8; ++d)
					if (gameField.ActionValid(i, d))
						valid[vCount++] = d;
				gameField.actions[i] = valid[RandBetween(0, vCount)];
			}
 
			if (count == 0)
				myAct = gameField.actions[myID];
 
			// 演算一步局面变化
			// NextTurn返回true表示游戏没有结束
			bool hasNext = gameField.NextTurn();
			count++;
 
			if (!hasNext)
				break;
		}
 
		// 计算分数
 
		int total = 0;
		for (int _ = 0; _ < MAX_PLAYER_COUNT; _++)
			total += gameField.players[_].strength;
 
		if (total != 0)
			actionScore[myAct + 1] += (10000 * gameField.players[myID].strength / total) / 100.0;
 
		// 恢复游戏状态到最初(就是本回合)
		while (count-- > 0)
			gameField.PopState();
	}
}
 
int main()
{
	Pacman::GameField gameField;
	string data, globalData; // 这是回合之间可以传递的信息
 
							 // 如果在本地调试,有input.txt则会读取文件内容作为输入
							 // 如果在平台上,则不会去检查有无input.txt
	int myID = gameField.ReadInput("input.txt", data, globalData); // 输入,并获得自己ID
	srand(Pacman::seed + myID);
 
	// 简单随机,看哪个动作随机赢得最多
	for (int i = 0; i < 1000; i++)
		Helpers::RandomPlay(gameField, myID);
 
	int maxD = 0, d;
	for (d = 0; d < 8; d++)
		if (Helpers::actionScore[d] > Helpers::actionScore[maxD])
			maxD = d;
 
	// 输出当前游戏局面状态以供本地调试。注意提交到平台上会自动优化掉,不必担心。
	gameField.DebugPrint();
 
	// 随机决定是否叫嚣
	// 注意这里输出(maxD - 1),是因为之前进行随机的时候数组下标(actionScore的下标)是0~4,而游戏要求的输出是-1~3
	// 如果不使用上述方式得出自己动作,请不要保留这个-1。
	if (rand() % 6)
		gameField.WriteOutput((Pacman::Direction)(maxD - 1), "", data, globalData);
	else
		gameField.WriteOutput((Pacman::Direction)(maxD - 1), "Hello, cruel world", data, globalData);
	return 0;
}