乐趣区

关于前端:教你做小游戏-五子棋怎么判断输赢你能5分钟交出代码吗

我是 HullQin,公众号 线下团聚游戏 的作者(欢送关注公众号,发送加微信,交个敌人),转发本文前需取得作者 HullQin 受权。我独立开发了《联机桌游合集》,是个网页,能够很不便的跟敌人联机玩斗地主、五子棋等游戏,不免费没广告。还开发了《Dice Crush》加入 Game Jam 2022。喜爱能够关注我 HullQin 噢~我有空了会分享做游戏的相干技术。

1. 问题形容

《五子棋》游戏,如何判断输赢呢?

这个问题是不是很简略?适宜给代码初学者练手。

然而如果你真的只想疾速开发一个五子棋,长年混迹开发业务、多年没摸算法的你,确实可能会在这个问题上头疼。

因为指标不一样:代码初学者违心花好几个小时在这下面优化算法,但业务开发者只想 5 分钟内解决掉这个问题。

明天,咱们作为 业务开发者,5 分钟实现它。

输出

以后棋盘上的棋子散布信息,散布信息通常有 2 种存储形式,见上篇文章《《五子棋》怎么存棋局信息?》。本文采纳的是 文中 2.6 节的计划一

  • 用一个列表存储已落的棋子,列表程序表明棋子程序,列表每一项的值代表棋子的地位,值为 0 -224(刚好 15*15=225 个值),奇数地位是黑棋,偶数地位是白棋。

以这局为例:https://game.hullqin.cn/wzq/?…

留神:网址参数中,是用 15 进制示意棋子的。每 2 位是一个棋子。

// 网址参数对应这样的输出数据:const input = [0, 1, 15, 16, 30, 31, 45, 46, 60];
// 别离是 00 01 10 11 20 21 30 31 40 奇数地位是黑棋,偶数地位是白棋

输入

有 3 种可能:

  1. 黑棋赢
  2. 白棋赢
  3. 没人赢(游戏应该持续)

(当然也有诉求判断是否平局,但场景不多,本文不思考这种判断是否平局的诉求。另外也因为我游戏中有认输性能,不会呈现棋盘下满导致单方无奈做任何操作的状况)

根本假如

有且仅有最初一手棋,导致某方五联珠胜利。

也就是说:

  • 如果最初一手是黑棋,那么以后白棋肯定没赢,只须要判断黑棋是否赢,就晓得输入是 1 还是 3。
  • 如果最初一手是白棋,那么以后黑棋肯定没赢,只须要判断白棋是否赢,就晓得输入是 2 还是 3。

这个根本假如,合乎实在的五子棋场景。

2. 解决方案

2.1 五分钟计划

如果你感觉这个问题 又简略又恶心,只想疾速做完,能够这样做:

先找到最初一手棋的色彩,拿到该色彩棋子的汇合:

const input = [0, 1, 15, 16, 30, 31, 45, 46, 60];
const pieces = input.filter((piece, index) => input.length % 2 !== index % 2);
console.log(pieces);

比方 input.length 是奇数,表明最初一手是黑棋,筛选出 input 的所有第偶数项(从 0 开始)都是黑棋。

而后遍历这个汇合,看看它上下左右斜共 8 个方向,有没有 5 连珠,若有,则他赢;否则他没赢。

const input = [0, 1, 15, 16, 30, 31, 45, 46, 60];
const pieces = input.filter((piece, index) => input.length % 2 !== index % 2);
console.log(pieces);

const judge = (pieces) => {const pieceSet = new Set(pieces);
  for (let i = 0; i < pieces.length; i++) {const piece = pieces[i];
    if (piece % 15 >= 4 && pieceSet.has(piece - 1) && pieceSet.has(piece - 2) && pieceSet.has(piece - 3) && pieceSet.has(piece - 4)) return true;
    if (piece % 15 <= 10 && pieceSet.has(piece + 1) && pieceSet.has(piece + 2) && pieceSet.has(piece + 3) && pieceSet.has(piece + 4)) return true;
    if (Math.floor(piece / 15) >= 4 && pieceSet.has(piece - 15) && pieceSet.has(piece - 30) && pieceSet.has(piece - 45) && pieceSet.has(piece - 60)) return true;
    if (Math.floor(piece / 15) <= 10 && pieceSet.has(piece + 15) && pieceSet.has(piece + 30) && pieceSet.has(piece + 45) && pieceSet.has(piece + 60)) return true;
    if (piece % 15 >= 4 && Math.floor(piece / 15) >= 4 && pieceSet.has(piece - 1 - 15) && pieceSet.has(piece - 2 - 30) && pieceSet.has(piece - 3 - 45) && pieceSet.has(piece - 4 - 60)) return true;
    if (piece % 15 <= 10 && Math.floor(piece / 15) <= 10 && pieceSet.has(piece + 1 + 15) && pieceSet.has(piece + 2 + 30) && pieceSet.has(piece + 3 + 45) && pieceSet.has(piece + 4+ 60)) return true;
    if (piece % 15 >= 4 && Math.floor(piece / 15) <= 10 && pieceSet.has(piece - 1 + 15) && pieceSet.has(piece - 2 + 30) && pieceSet.has(piece - 3 + 45) && pieceSet.has(piece - 4 + 60)) return true;
    if (piece % 15 <= 10 && Math.floor(piece / 15) >= 4 && pieceSet.has(piece + 1 - 15) && pieceSet.has(piece + 2 - 30) && pieceSet.has(piece + 3 - 45) && pieceSet.has(piece + 4 - 60)) return true;
  }
  return false;
};

console.log(judge(pieces));

算法形容

如果最初一手为黑棋,则遍历所有黑棋:以该黑棋为五联珠的顶点,看看它的上、下、左、右、左上、右下、左下、右上是否有间断的 4 个黑棋,只有找到任意一项成立,则黑棋赢。若遍历了所有棋子的所有方向后,没找到能使任意 if 成立的,则表明黑棋没赢。

外面有 1 个 for 循环,用于遍历黑棋。8 个 if 判断,散布判断 8 个方向是否有 4 连珠。

注意事项

8 个 if 判断的前缀表达式:

piece % 15是棋子在第几行。Math.floor(piece / 15)是第几列。

这个前缀表达式判断不可省略。想想为什么?

答案:

如果你省略,会出错,比方在这种状况,算法会误判:

const input = [11, 224, 12, 223, 13, 222, 14, 221, 15];

算法点评

我置信这是大多数人,看到这道题最快能想到的暴力解法。该算法尽管比拟蠢,有很多中央能够 剪枝优化 ,然而因为pieces 最长长度为Math.ceil(225/2)=113 的列表,所以该算法理论状况下不会慢多少。齐全能够投入生产环境应用。

我五子棋第一个版本就采纳了该算法,过后只是为了疾速加上胜利判断性能。

2.2 十五分钟计划

如果你把产品需要赶完了,有工夫做技术优化了,能够对 2.1 计划做个剪枝优化。

(当然产品需要是一辈子也做不完的,你可能没工夫做优化了)

算法形容

看该计划前,须要强调一下根本假如:有且仅有最初一手棋,导致某方五联珠胜利。

而最初一手棋胜利,有 4 个可能的方向:高低 5 连珠、左右 5 连珠、左上右下五联珠、右上左下五联珠。

所以,咱们判断最初一手棋的 4 个方向的连珠,只有任意方向有 5 连珠,就赢了。否则没赢。

残缺代码

这也是我的五子棋游戏采纳的计划,我间接贴源码:

export function judgeWin(pieces: number[]) {
  // 先选出与最初一手同色的棋子汇合
  const samePieces = new Set<number>();
  const color = pieces.length % 2;
  pieces.forEach((v, i) => {if (i % 2 !== color) {samePieces.add(v);
    }
  });
  // 拿到最初一手棋子的坐标
  const p = pieces[pieces.length - 1];
  // 判断该棋子【高低、左右、左上右下、左下右上】四条直线方向,最大有多少连珠。若找到 5 连珠,则胜利
  let count = 0;
  // 右上
  for (let i = 1; i <= Math.min(4, p % 15, 14 - Math.floor(p / 15)); i++) {if (samePieces.has(p - i + 15 * i)) {count += 1;} else {break;}
  }
  // 左下
  for (let i = 1; i <= Math.min(4, 14 - (p % 15), Math.floor(p / 15)); i++) {if (samePieces.has(p + i - 15 * i)) {count += 1;} else {break;}
  }
  // 右上和左下,累计 4 个连珠,就赢了
  if (count >= 4) return true;
  // 若上述方向没赢,再看其它方向
  count = 0;
  // 左上
  for (let i = 1; i <= Math.min(4, p % 15, Math.floor(p / 15)); i++) {if (samePieces.has(p - i - 15 * i)) {count += 1;} else {break;}
  }
  // 右下
  for (let i = 1; i <= Math.min(4, 14 - (p % 15), 14 - Math.floor(p / 15)); i++) {if (samePieces.has(p + i + 15 * i)) {count += 1;} else {break;}
  }
  // 左上和右下,累计 4 个连珠,就赢了
  if (count >= 4) return true;
  // 若上述方向没赢,再看其它方向
  count = 0;
  // 上
  for (let i = 1; i <= Math.min(4, p % 15); i++) {if (samePieces.has(p - i)) {count += 1;} else {break;}
  }
  // 下
  for (let i = 1; i <= Math.min(4, 14 - (p % 15)); i++) {if (samePieces.has(p + i)) {count += 1;} else {break;}
  }
  // 上和下,累计 4 个连珠,就赢了
  if (count >= 4) return true;
  // 若上述方向没赢,再看其它方向
  count = 0;
  // 左
  for (let i = 1; i <= Math.min(4, Math.floor(p / 15)); i++) {if (samePieces.has(p - i * 15)) {count += 1;} else {break;}
  }
  // 右
  for (let i = 1; i <= Math.min(4, 14 - Math.floor(p / 15)); i++) {if (samePieces.has(p + i * 15)) {count += 1;} else {break;}
  }
  // 左和右,累计 4 个连珠,就赢了。否则,方向曾经遍历完了,阐明没赢
  return count >= 4;
}

算法剖析

相比 5 分钟计划,真的是翻倍的快了。尽管两个算法复杂度都是 O(n),然而 15 分钟计划少了很屡次遍历过程。

当然,计划二的算法复杂度次要来源于开始遍历棋子,生成同色棋子汇合。如果抛开这个过程,只谈 判断同色棋子是否存在 5 连珠,计划二的算法复杂度是 O(1),但计划一的算法复杂度是 O(n)。

注意事项

该代码写法不是最精简的,你能通过方向数组,把 8 个 for 循环简化成嵌套的 2 或 3 个 for 循环。这不会扭转代码复杂度,然而会缩短代码长度。

什么是方向数组?

const dx = [0, 0, 1, -1, 1, -1, 1, -1];
const dy = [1, -1, 0, 0, 1, -1, -1, 1];

这样找相邻棋子的写法,就能够对立了。通过加一层循环,把 j 从 0 遍历到 7 即可:p - i - 15 * i变成p + i * dx[j] + 15 * i * dy[j]

感兴趣的敌人能够尝试精简一下。我只是个业务开发者,就不花过多工夫了,哈哈。

3. 写在最初

这种算法,你不去本人开发《五子棋》,可能不会去思考。然而当你做的时候,会发现,十分好玩儿,实现计划很多,你要选出最适宜你的那一个。

以上,也是我开发我的联

开发五子棋时,我始终谋求极致用户体验,参考文章:《我做的《联机五子棋》是如何谋求极致用户体验的?(上)》

我是 HullQin,公众号 线下团聚游戏 的作者(欢送关注公众号,发送加微信,交个敌人),转发本文前需取得作者 HullQin 受权。我独立开发了《联机桌游合集》,是个网页,能够很不便的跟敌人联机玩斗地主、五子棋等游戏,不免费没广告。还开发了《Dice Crush》加入 Game Jam 2022。喜爱能够关注我 HullQin 噢~我有空了会分享做游戏的相干技术。

退出移动版