快速验证游戏板 [英] Validate A Game Board, And Fast

问题描述

我正在使用Apache/PHP服务器创建一个多人对战舰游戏(是的，我知道Node对此会更好，但是稍后我将继续学习它).无论如何，我正处于两个玩家都上载游戏板以开始游戏的时刻.虽然我的客户端JavaScript在将板发送到服务器之前显然可以正确编译和验证板，但这仍然容易受到欺骗，因此服务器也必须仔细检查.但是，在服务器上，速度和效率至关重要.

I am creating a multiplayer Battleship game using an Apache/PHP server (yes, I know Node would be much better for this, but I'll get around to learning it later). Anyways, I am at the point in which both players are uploading their game boards to start the game. While my client side JavaScript would obviously properly compile and validate boards before sending them off to the server, that is still vulnerable to cheating, so the server must also double check. However, on the server, speed and efficiency is everything.

到目前为止，这是我的服务器遵循的过程:

As of now, this is the process my server follows:

1. 服务器通过AJAX请求将板作为JSON编码的多维数组接收.

1. Server receives the board as a JSON encoded multidimensional array via an AJAX request.

$board = json_decode($_REQUEST["board"]);

服务器验证传递的输入的结构.

Server validates the structure of the passed input.

$validate = array(gettype($board) == "array", count($board) == 10);
for($i = 0; $i < count($board); $i++) {
   array_push($validate, count($board[$i]) == 10);
   for($ii = 0; $ii < count($board[$i]); $ii++) {
       array_push($validate, gettype($board[$i][$ii]) == "integer");
   }
}
if(in_array(0, $validate)) throwError();

在数组中，数字0到5分别代表空白，航空母舰，战舰，巡洋舰，潜艇和驱逐舰瓦片.我算出每种的适当数量.

In the array, numbers zero through five represent blank, aircraft carrier, battleship, cruiser, submarine, and destroyer tiles respectively. I count the proper quantity of each.

 $valueCount = array_count_values(array_merge($board[0], $board[1], $board[2], $board[3], $board[4], $board[5], $board[6], $board[7], $board[8], $board[9]));
 $template = array("0"=>83,"1"=>5, "2"=>4, "3"=>3, "4"=>3, "5"=>2);
 if($template != $valueCount) throwError();

我需要确保船用瓷砖仅是垂直或水平线.

I need to ensure that ship tiles are only vertical or horizontal lines.

 $shipsValid = array(false, false, false, false, false);
 $transpose = array_map(null, $board[0], $board[1], $board[2], $board[3], $board[4], $board[5], $board[6], $board[7], $board[8], $board[9]);
 for($i = 0; $i < 9; $i++) {
     $temp1 = array_count_values($board[$i]);
     $temp2 = array_count_values($transpose[$i]);
     if($temp1["1"] == 5 || $temp2["1"] == 5) shipsValid[0] = true;
     if($temp1["2"] == 4 || $temp2["2"] == 4) shipsValid[1] = true;
     if($temp1["3"] == 3 || $temp2["3"] == 3) shipsValid[2] = true;
     if($temp1["4"] == 3 || $temp2["4"] == 3) shipsValid[3] = true;
     if($temp1["5"] == 2 || $temp2["5"] == 2) shipsValid[4] = true;
 }
 if(in_array(0, $shipsValid)) throwError();

我需要确保船只连续无间隙.

I need to ensure ships are continuous with no gaps.

??????????????????????????

只要有足够的工作，我就可以完成第五步，但是这样做会非常低效，需要反复遍历所有内容.因此，总而言之，我如何才能使设计的效率更高，以及如何完成验证上传的木板的最后一步(5)?

With enough work, I could have completed step five, but it would have been grossly inefficient, looping through everything repeatedly. So, in conclusion, how can I make what I have designed more efficient, and how I complete the final step (5) to validating the uploaded board?

示例板(有效):

    "[[0,1,1,1,1,1,0,0,0,0],
    [0,0,0,0,0,0,0,2,0,0],
    [0,0,0,0,0,0,0,2,0,0],
    [0,0,0,0,0,0,0,2,0,0],
    [0,3,3,3,0,0,0,2,0,0],
    [0,0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0],
    [0,0,5,0,0,0,4,4,4,0],
    [0,0,5,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0]]"

示例面板(由于许多原因无效):

Example Board (Invalid, for many reasons):

    "[[0,1,1,0,1,1,0,0,0,1],
    [0,0,0,0,0,0,0,2,0,0],
    [0,0,0,0,0,0,0,2,0,0],
    [0,0,0,0,0,0,0,2,0,0],
    [0,6,6,6,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,4,4,4,4,4],
    [0,0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0]]"

推荐答案

版本2:现在，验证速度具有最高优先级.

(无需调用json_decode())

以下是我的两个有效测试$board字符串.在这两艘船之间，所有舰船都朝着两个方向航行.

The following are my two valid test $board strings. Between the two of them, all ships occur in both orientations.

测试#1:

[[0,1,1,1,1,1,0,0,0,0],[0,0,0,0,0,0,0,2,0,0],[0,0,0,0,0,0,0,2,0,0],[0,0,0,0,0,0,0,2,0,0],[0,3,3,3,0,0,0,2,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,5,0,0,0,4,4,4,0],[0,0,5,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0]]

测试2:

[[0,1,0,0,0,0,0,0,0,0],[0,1,0,0,2,2,2,2,0,0],[0,1,0,0,0,0,0,0,0,0],[0,1,0,0,0,0,0,0,0,0],[0,1,3,0,0,0,0,0,0,0],[0,0,3,0,0,0,0,0,0,0],[0,0,3,0,0,0,0,0,0,0],[0,0,5,5,0,0,4,0,0,0],[0,0,0,0,0,0,4,0,0,0],[0,0,0,0,0,0,4,0,0,0]]

要遵循的方法是在php中进行简单的preg_match()调用.该技术使用先行验证来验证每艘战舰，然后使用全字符串匹配来验证json结构.

The method to follow is a simple preg_match() call in php. The technique uses lookaheads to validate each ship, followed by a fullstring match that validates the json structure.

此技术是验证密码时最常用的技术，其中通常必须对字符串的长度和/或有效字符进行验证，而且还必须检查字符的最小出现次数或字符范围(例如，密码必须至少为8个字符)并包括小写字母，大写字母，数字和符号).

This technique is most commonly used when validating passwords, where a string must be generally validated for length and/or valid characters, but also checked for minimum occurrences of characters or ranges of characters (e.g. password must be a minimum of 8 characters and include a lowercase, uppercase, number, and a symbol).

我的方法的出色之处不仅在于它是单个调用，而且还可以无缝地调用它以验证javascript中的数据.

The brilliance in my method is not just that it is a single call, but that it can also be seamlessly called to validate the data in javascript as well.

现在开始使用模式(请系好安全带):

Now for the patterns (seatbelts on, please):

(1590个字符)(测试#1:371个步骤;

(1590 characters) (Test#1: 371 steps; Test#2 446 steps)

/(?=^[^1]*(?:1,1,1,1,1|1\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+1\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+1\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+1\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+1)[^1]*$)(?=^[^2]*(?:2,2,2,2|2\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+2\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+2\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+2)[^2]*$)(?=^[^3]*(?:3,3,3|3\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+3\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+3)[^3]*$)(?=^[^4]*(?:4,4,4|4\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+4\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+4)[^4]*$)(?=^[^5]*(?:5,5|5\D+[^5]\D+[^5]\D+[^5]\D+[^5]\D+[^5]\D+[^5]\D+[^5]\D+[^5]\D+[^5]\D+5)[^5]*$)^\[\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\],\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\],\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\],\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\],\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\],\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\],\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\],\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\],\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\],\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\]\]$/

(306个字符)(测试#1:576个步骤;

(306 characters) (Test#1: 576 steps; Test#2 698 steps)

/(?=^[^1]*(?:1,1,1,1,1|1(?:(?:\D+[^1]){9}\D+1){4})[^1]*$)(?=^[^2]*(?:2,2,2,2|2(?:(?:\D+[^2]){9}\D+2){3})[^2]*$)(?=^[^3]*(?:3,3,3|3(?:(?:\D+[^3]){9}\D+3){2})[^3]*$)(?=^[^4]*(?:4,4,4|4(?:(?:\D+[^4]){9}\D+4){2})[^4]*$)(?=^[^5]*(?:5,5|5(?:\D+[^5]){9}\D+5)[^5]*$)(?:(?:^\[|)\[[0-5](?:,[0-5]){9}\](?:,|\]$)){10}/

第一个模式更快的原因是因为我删除了所有无关紧要的非捕获组.就简洁"而言，成本是巨大的.两种模式的可读性"都非常差.两种模式都保持相同的准确性"，但是第一种模式在效率"上有一定优势.

The reason the first pattern is faster is because I have removed all inessential non-capture groups. The cost, in terms of "Brevity", is drastic. "Readability" is extremely poor in both of patterns. Both patterns maintain the same "Accuracy", but the first pattern wins on "Efficiency" by some margin.

所有先行者具有相同的基本结构，并遵守游戏规则/要求:

All lookaheads have the same basic structure and obey the game rules/requirements:

(?=           #lookahead, but don't "consume" any characters in the process
^             #from the start of the string
[^5]*         #quickly, greedily match all characters that are not a 5
(?:           #non-capture group to isolate the "alternatives"
    5,5       #literally match a 2-peg row
    |         # or
    5\D+[^5]\D+[^5]\D+[^5]\D+[^5]\D+[^5]\D+[^5]\D+[^5]\D+[^5]\D+[^5]\D+5  #match two 5 pegs that have nine non-5 pegs between them
)             #end non-capture group
[^5]*         #quickly, greedily match all characters that are not a 5 (ensure there are no more 5's in the string) 
$             #all the way to the end of the string
)             #end the lookahead

一般的板结构钉匹配:

^                       #from the start of the string
\[                      #match the opening outer bracket
\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\],  #match a row of 0, 1, 2, 3, 4, or 5's 
\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\],  #match a row of 0, 1, 2, 3, 4, or 5's
\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\],  #match a row of 0, 1, 2, 3, 4, or 5's
\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\],  #match a row of 0, 1, 2, 3, 4, or 5's
\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\],  #match a row of 0, 1, 2, 3, 4, or 5's
\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\],  #match a row of 0, 1, 2, 3, 4, or 5's
\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\],  #match a row of 0, 1, 2, 3, 4, or 5's
\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\],  #match a row of 0, 1, 2, 3, 4, or 5's
\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\],  #match a row of 0, 1, 2, 3, 4, or 5's
\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\]  #match a row of 0, 1, 2, 3, 4, or 5's
\]                      #match the closing outer bracket
$                       #to the end of the string

PHP代码:(演示)

$pattern='/(?=^[^1]*(?:1,1,1,1,1|1\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+1\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+1\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+1\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+1)[^1]*$)(?=^[^2]*(?:2,2,2,2|2\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+2\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+2\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+2)[^2]*$)(?=^[^3]*(?:3,3,3|3\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+3\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+3)[^3]*$)(?=^[^4]*(?:4,4,4|4\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+4\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+4)[^4]*$)(?=^[^5]*(?:5,5|5\D+[^5]\D+[^5]\D+[^5]\D+[^5]\D+[^5]\D+[^5]\D+[^5]\D+[^5]\D+[^5]\D+5)[^5]*$)^\[\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\],\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\],\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\],\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\],\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\],\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\],\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\],\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\],\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\],\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\]\]$/';
echo preg_match($pattern,$_REQUEST["board"]) ? 'success' : 'invalid';

这篇关于快速验证游戏板的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！