Крестики-нолики проверка по диагонали

448

14 ноября 2018, 15:10

class Board
{
    const MARK_0 = 0;
    const MARK_X = 1;
    /** @var int */
    private $sizeX;
    /** @var int */
    private $sizeY;
    /** @var int */
    private $requiredMarks;
    /** @var array */
    private $map = [];
    /**
     * @param int $sizeX
     * @param int $sizeY
     */
    public function __construct (int $sizeX = 3, int $sizeY = 3)
    {
        $this->sizeX = $sizeX;
        $this->sizeY = $sizeY;
        $this->requiredMarks = $sizeX;
    }
    /**
     * @return int
     */
    public function getSizeX() : int
    {
        return $this->sizeX;
    }
    /**
     * @return int
     */
    public function getSizeY() : int
    {
        return $this->sizeY;
    }
    /**
     * @return int
     */
    public function getRequiredMarks() : int
    {
        return $this->requiredMarks;
    }
    /**
     * @param int $count
     */
    public function setRequiredMarks (int $count) : void
    {
        $this->requiredMarks = $count;
    }
    /**
     * @param int $x
     * @param int $y
     * @param int $mark
     */
    public function setMark (int $x, int $y, int $mark) : void
    {
        $this->map[$x][$y] = $mark;
    }
    /**
     * @param int $x
     * @param int $y
     *
     * @return int|null
     */
    public function getMark (int $x, int $y) : ?int
    {
        return $this->map[$x][$y] ?? null;
    }
    /**
     * @return int|null
     */
    public function checkWin() : ?int
    {
        foreach([self::MARK_0, self::MARK_X] as $mark)
        {
            if(/* $this->checkLanes($mark) ||  */ $this->checkDiagonals($mark))
            {
                return $mark;
            }
        }
        return null;
    }
    /**
     * @param int $mark
     *
     * @return bool
     */
    private function checkDiagonals (int $mark) : bool
    {
        $sizeX = $this->getSizeX();
        $sizeY = $this->getSizeY();
        $required = $this->getRequiredMarks();
        $size = max($sizeX, $sizeY);
        for($k = $required - $size; $k <= ($size - $required); $k++)
        {
            $score1 = 0;
            $score2 = 0;
            $startI = max(0, $k);
            $endI = min($size, $size + $k);
            for($i = $startI; $i < $endI; $i++)
            {
                if($this->getMark($i, $k + $i) === $mark)
                {
                    if(++$score1 >= $required)
                    {
                        return true;
                    }
                }
                else
                {
                    $score1 = 0;
                }
                if($this->getMark($i, $size - 1 + $k - $i) === $mark)
                {
                    if(++$score2 >= $required)
                    {
                        return true;
                    }
                }
                else
                {
                    $score2 = 0;
                }
            }
        }
        return false;
    }
}

$b = new Board (4, 4);
$b->setRequiredMarks(3);
$b->setMark(0, 1, Board::MARK_X);
$b->setMark(1, 2, Board::MARK_X);
$b->setMark(2, 3, Board::MARK_X);
$winner = $b->checkWin();
if($winner === null)
{
    $winner = "nobody";
}
elseif($winner === Board::MARK_X)
{
    $winner = "X";
}
else
{
    $winner = "0";
}
var_dump($winner);

Как пофиксить функцию "checkDiagonals", чтобы она обрабатывала диагонали как на фото корректно и возвращала корректный результат?

Если делать проверку на диагоналях как на фото, то это работает корректно.

Я не могу придумать этот алгоритм, поэтому я взял его с этого ответа https://stackoverflow.com/a/34257658/10261980

Закомментированная функция "checkLanes" работает корректно, поэтому она удалена из кода.

Answer 1

private function checkDiagonals ($mark)
{
    $sizeX = $this->getSizeX();
    $sizeY = $this->getSizeY();
    $required = $this->getRequiredMarks();
    $lastPosition = 0;
    $newPosition = 0;
    $match = 0;
    for ($i = 0; $i < $sizeX; $i++) {
        for ($j = 0; $j < $sizeY; $j++) {
            $tmp[] = $_mark = $this->getMark($i, $j);
            if ( $_mark !== $mark ) {
                continue;
            }
            if ( $newPosition === 0 ) {
                $match++;
            }
            $newPosition = count($tmp) - 1;
            $delta = $newPosition - $lastPosition;
            if ( ($delta === $sizeX - 1 || $delta ===  $sizeX + 1) && $lastPosition !== 0 ) {
                    $match++;
            }
            $lastPosition = $newPosition;
            if ( $match === $required ) {
                return true;
            }
        }
    }
    return false;
}

Выполнить код

UPD

Функция для проверки всех направлений:

private function check ($mark)
{
    $sizeX = $this->getSizeX();
    $sizeY = $this->getSizeY();
    $required = $this->getRequiredMarks();
    $lastPosition = 0;
    $match = 0;
    $lastCheck = '';
    for ($i = 0; $i < $sizeX; $i++) {
        for ($j = 0; $j < $sizeY; $j++) {
            $tmp[] = $_mark = $this->getMark($i, $j);
            if ($_mark !== $mark) {
                continue;
            }
            $newPosition = count($tmp) - 1;
            $rules = [
                'upDiagonal' => $newPosition - $lastPosition === $sizeX - 1,
                'downDiagonal' => $newPosition - $lastPosition ===  $sizeX + 1,
                'cols' => $newPosition - $lastPosition ===  $sizeX,
                'rows' => $newPosition - $lastPosition ===  1,
            ];
            $newCheck = array_search(true, $rules);
            if ( $newCheck === $lastCheck || $lastCheck == '' ) {
                $match++;
            } else if ($newCheck !== $lastCheck) {
                $match = 2;
            }
            $lastPosition = $newPosition;
            if ( $match > 1 ) {
                $lastCheck = $newCheck;
            }
            if ( $match === $required ) {
                return true;
            }
        }
    }
    return false;
}

Код не протестирован!

Answer 2

Если передать последний ход в метод checkWin, проверить условие выигрыша будет гораздо проще.

Продемонстрирую:

  private function checkWin($i, $j)
  {
    $player = $this->map[$j][$i];
    // Для каждого направления считаем количество совпадающих знаков в обе стороны:
    //  '—' direction
    $count = 1; 
    for ($ci = $i - 1; $this->map[$j][$ci] === $player; $ci--) $count++;
    for ($ci = $i + 1; $this->map[$j][$ci] === $player; $ci++) $count++;
    if ($count >= $this->win) return true;
    //  '|' direction
    $count = 1;
    for ($cj = $j - 1; $this->map[$cj][$i] === $player; $cj--) $count++;
    for ($cj = $j + 1; $this->map[$cj][$i] === $player; $cj++) $count++;
    if ($count >= $this->win) return true;
    //  '\' direction
    $count = 1;
    for ($ci = $i - 1, $cj = $j - 1; $this->map[$cj][$ci] === $player; $ci--, $cj--) $count++;
    for ($ci = $i + 1, $cj = $j + 1; $this->map[$cj][$ci] === $player; $ci++, $cj++) $count++;
    if ($count >= $this->win) return true;
    //  '/' direction
    $count = 1;
    for ($ci = $i - 1, $cj = $j + 1; $this->map[$cj][$ci] === $player; $ci--, $cj++) $count++;
    for ($ci = $i + 1, $cj = $j - 1; $this->map[$cj][$ci] === $player; $ci++, $cj--) $count++;
    if ($count >= $this->win) return true;
    return false;
  }

Ради наглядности убрал из циклов проверки на достижение краёв карты. В принципе это можно решить даже добавлением кольца из null-ов вокруг карты в массиве.