新一年校赛，奖金越来越多了（想起第一届只有几百块奖金……），不过即使如此每年也只能选出个位数的新人，CTF相比OI毕竟还是太硬核了只能沦为小众（半斤八两吧）。
由于上课磕盐比较忙，原本想着出几道web几道misc结果都鸽了直接摆烂，只能弄个传统艺能KoH算了……

darkforest

a.png

花了周末一天的时间写了个游戏，服务端大概1k行golang，加上几百行的web前端显示结果。由于平台年久失修都是大几年前slipper等前辈写的根本不支持KoH，想了一会还是催更tkmk加了个token验证的接口，然后比赛结束后手动更新数据库分数23333

题目背景是三体的黑暗森林，配合PUBG的吃鸡玩法，加上了csgo武器、水滴、智子、二向箔之类乱七八糟的东西，玩家可以在地图上拾取flag并攻击其他玩家捡取掉落的包，每秒1个tick总共1000tick一轮，活到最后的玩家可以获得背包里flag数量的分数。因为服务端每秒结算1个tick，并且提供了源码，所以一开始可以通过手操的方式和观察代码了解操作opcode，然后写程序自动化挂机（类似screeps）。原本预估20-30人玩结果最后只有5、6个活人……哎不说了。

完整代码在这里：https://github.com/MXWXZ/my-ctf-challenges/tree/main/sjtuctf-2021/darkforest

游戏系统设计

每个玩家100滴血，可以通过捡血包增加血量，捡甲增加减伤，简单期间伤害计算直接是伤害-护甲。玩家有背包，捡了武器之后可以通过使用背包里的不同武器进行攻击，被非地形击杀（地图边界和水面）会掉落背包里的所有物品。为了增加难度且更加符合“黑暗森林”特性，玩家有一个初始视野范围，无法看到更远的东西并且有阻挡物的时候视线会被阻挡。

为了增加对抗激烈度，还添加了一个二向箔降维打击的机制，当有人走到二向箔的地块时会启动降维打击，每过167轮以启动的位置为正方形中心向外侧扩展一圈地图边界（0）并击杀所有被覆盖的玩家（类似缩圈，不过这里是扩圈），理论上来说25*25的地图最多会被毁灭一大半的地方，还是留有余地的。

游戏目标是拾取最多的flag并存活到最后，可以通过到处杀人舔包，也可以捡完东西找个地方苟住，游戏收益在设计上就是不均衡的，大部分flag会集中在一个人身上，因此算法更加优秀的程序能获得更高奖励。当然游戏也提供了翻盘点，比如存在地雷的设定，跑的多了运气不好也会直接挂，还有不平衡的武器供欧皇翻盘，或者直接启动二向箔同归于尽。

地图物品设计

简单起见采用了古老但好玩的tile map模式，有这么几种地块：

  • 0：地图边界，取自“归零者”，走上去就挂。
  • G：普通地面
  • T：树，阻挡视线，不允许穿过
  • W：水，不阻挡视线，走上去就挂。

地块上可能有物品，类似吃鸡的物资：

  • F：flag，每个会在结算时提供1分
  • U：USP，伤害20，射程6，只会伤害首个目标
  • K：AK47，伤害40，射程8，只会伤害首个目标
  • A：AWP，伤害80，射程12，只会伤害首个目标
  • R：+10护甲
  • B：+20血
  • M：地雷，不可见，走上去就挂并掉落背包所有物资
  • S：智子，提高视野至999（单方向全图），并可穿透树，可以看到地雷
  • D：水滴，伤害999（秒杀），射程999（一条线全图），秒杀攻击路径上所有目标，只能使用一次
  • V：二向箔，走上去就启动降维打击

地图由地图文件指定，为了简单起见只有一张地图，物品则是按指定数量随机分布。

攻击系统设计

玩家如果没有武器的话可以用拳头，射程只有1格，伤害10点，使用USP、AK、AWP的话就根据伤害-护甲的计算公式对射程内目标方向上的第一个目标造成伤害，而水滴则可以消灭某个方向上一条线的所有玩家。

需要注意的是设计上玩家的默认视野是6，和射程最低的USP一样，也就是说存在超视距打击的情况，而USP一般5-6枪致命，AK3枪，AWP2枪，水滴秒杀。因此在游戏中武器的优先级非常高，因为没有最低伤害，USP甚至无法破吃了两个甲的玩家的防。正如某同学wp里说的，这是一个杀人游戏，你掉血了却不知到被谁打，那你的生存几率就会急剧下降，而高价值武器所带来的优势也非常明显。

还有需要注意的一点是除了水滴目前所有武器都没有子弹限制，而树木和水面都不会阻挡子弹的穿透，这一点在武器配置里是没有的，而是在战斗代码里：

1
2
3
4
5
6
7
8
9
10
if p.Turn == TRight {
	for i := p.Y + 1; i < Min(p.Y+vision+1, e.Size); i++ {
		if e.Forest[p.X][i].GetType() == CPlayer {
			target = append(target, e.Forest[p.X][i].Contain.(*Player).ID)
			if !penetrate {
				break
			}
		}
	}
}

大概意思是寻找当前方向上射程内遇到的第一个玩家加入打击列表，而武器穿透属性只是决定了是否只会打击第一个遇到的人（目前只有水滴有穿透属性），而并没有对地形进行判断！因此即使看不到人也能直接向面前开枪，进行超视距打击，从而增加生存率。不过很可惜的是貌似没有人发现这一点……

控制系统设计

服务端监听了一个端口，玩家连接后加入连接列表，每轮游戏开始加入游戏列表，游戏引擎会每秒加锁读取动作列表执行相应动作，而玩家可以通过发送动作对角色进行操作。这里存在几个问题：

一是每个tick服务端会向每个玩家发送对应的视野、状态信息，而玩家接收消息的先后顺序可能对处理时长、发送后续动作的先后顺序造成影响，方便起见每个tick服务端会shuffle发送信息的玩家顺序，并开启一个goroutine异步发送（防止阻塞，利用多线程等），一定程度上保证公平。

二是玩家动作消息的到达时间不一致，而每个动作涉及了攻击、移动等不同操作，会对后续其他玩家动作造成影响。例如在某个tick，玩家A的动作消息在B之前处理，而A对面前的B进行了攻击并杀死了他，那B的消息该如何处理？或者B的消息先到达，进行了移动从而改变位置，如何判断A的攻击动作？这里我进行了简化处理，统一按动作消息的顺序进行处理，如果在处理前死亡就忽略此消息，处理时也按当前的游戏状态进行操作。因此对于上面两个例子，B先被杀死那么B的消息将不会被处理，而如果B先移动，A的攻击则会落空。

三是为了支持每个tick进行多个动作，同时限制玩家消息数量（每个tick只允许发送一条动作消息），这里采用了链式动作的处理方式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func (o *OP) NextTurn(t TurnType) *OP {
	o.Next = &OP{
		Oper: OPTurn,
		Turn: t,
	}
	return o.Next
}

func (o *OP) NextWalk() *OP {
	o.Next = &OP{
		Oper: OPWalk,
	}
	return o.Next
}

func (o *OP) NextShoot(i int) *OP {
	o.Next = &OP{
		Oper: OPShoot,
		Item: i,
	}
	return o.Next
}

分别为转身、向前走和攻击，而执行时根据链表即可按顺序执行多个动作。而这又带来了一个问题，玩家可能“转起来”比如一个tick内向上下左右四个方向攻击很多次从而导致射程内无活物的情况，或者一回合走好多步瞬移，为了进行限制每一个动作链只允许存在一个walk和shoot，而每一个tick只允许一个动作链存在，这样就能愉快地游戏了:)

动作链以分号分割，可以做到比如开枪然后向旁边闪避从而进行一些高级的骚操作，不过貌似也没有人发现这一点……每一个tick只进行了一个动作。

总结

可能是竞争对手比较少大家都没有卷的动力……预期由于地图固定不说根据视野确定位置，至少记忆化搜索还是可以做的吧？开个足够大的数组在中间根据视野里的东西还原地图避免乱走应该不难做到，然而大家基本还是随机游走（或者优化后的随机游走）……不过还行，几个高分玩家还是挖掘出了一些策略（虽然留的几个增强实力的小漏洞没被发现），也不负我花一天时间写游戏的辛苦了hhh。

（或许这游戏以后还能用到^_^）