Completed an AI implementation

[GoMoku3D.git] / src / core / GameMatrix.cpp

/********************************************************************
 *
 * Copyright (C) 2008  Daniele Battaglia
 *
 * This file is part of GoMoku3D.
 *
 * GoMoku3D is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * GoMoku3D is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with GoMoku3D. If not, see <http://www.gnu.org/licenses/>.
 *
 *******************************************************************/

#include <QtGlobal>
#include "GameMatrix.h"

const int GameMatrix::EmptyPoint = -1;

GameMatrix *GameMatrix::_instance = 0;

GameMatrix::GameMatrix(int d1, int d2, int numPlayers)
{
    _d1 = d1;
    _d2 = d2;

    for (int i = 0; i < numPlayers; i++) {
        _lastRound.append(Point());
    }

    int matrixSize = (d1 * d2) * (d1 * d2) * (d1 * d2);
    _matrix = new int[matrixSize];
    for (int i = 0; i < matrixSize; i++) {
        _matrix[i] = EmptyPoint;
    }

    _freeCounter = matrixSize;
}

GameMatrix::~GameMatrix()
{
    _instance = 0;
    delete _matrix;
}

GameMatrix *GameMatrix::create(int d1, int d2, int numPlayers)
{
    if (_instance == 0) {
        _instance = new GameMatrix(d1, d2, numPlayers);
    }
    return _instance;
}

void GameMatrix::destroy()
{
    if (_instance != 0) {
        delete _instance;
        _instance = 0;
    }
    return;
}

GameMatrix *GameMatrix::instance()
{
    return _instance;
}

bool GameMatrix::check(Point point)
{
    return point.isValid() && instance()->elementAt(point) == EmptyPoint;
}

bool GameMatrix::add(Move move)
{
    int pos = move.point().x() * (_d1 * _d2) * (_d1 * _d2) + move.point().y() * (_d1 * _d2) + move.point().z();
    _matrix[pos] = move.playerId();

    int start = qMax(0, move.point().x());
    int i = 0;
    bool valid = true;

    while (valid && start <= move.point().x()) {
        while (valid && i < _d1) {
            int id = elementAt(start + i, move.point().y(), move.point().z());
            if (id == move.playerId()) {
                i++;
            }
            else {
                if (id == -2) {
                    valid = false;
                }
                else {
                    start++;
                    i = 0;
                }
            }
        }
        if (i == _d1) {
            return true;
        }
    }

    start = qMax(0, move.point().y());
    i = 0;
    valid = true;

    while (valid && start <= move.point().y()) {
        while (valid && i < _d1) {
            int id = elementAt(move.point().x(), start + i, move.point().z());
            if (id == move.playerId()) {
                i++;
            }
            else {
                if (id == -2) {
                    valid = false;
                }
                else {
                    start++;
                    i = 0;
                }
            }
        }
        if (i == _d1) {
            return true;
        }
    }

    start = qMax(0, move.point().z());
    i = 0;
    valid = true;

    while (valid && start <= move.point().z()) {
        while (valid && i < _d1) {
            int id = elementAt(move.point().x(), move.point().y(), start + i);
            if (id == move.playerId()) {
                i++;
            }
            else {
                if (id == -2) {
                    valid = false;
                }
                else {
                    start++;
                    i = 0;
                }
            }
        }
        if (i == _d1) {
            return true;
        }
    }

    if (_d2 != 3) {
        return false;
    }

    QSet<Point> set;
    extractCC(move.point(), move.playerId(), set);

    Point e;
    int minX = _d1 * _d2;
    int maxX = -1;
    int minY = minX;
    int maxY = maxX;
    int minZ = minX;
    int maxZ = maxX;

    foreach (e, set) {
         minX = qMin(minX, e.x());
         minY = qMin(minY, e.y());
         minZ = qMin(minZ, e.z());
         maxX = qMax(maxX, e.x());
         maxY = qMax(maxY, e.y());
         maxZ = qMax(maxZ, e.z());
     }
     return (minX == 0 && maxX == _d1 * _d2 -1) || (minY == 0 && maxY == _d1 * _d2 -1) || (minZ == 0 && maxZ == _d1 * _d2 -1);
}

void GameMatrix::clear(Point point)
{
    if (elementAt(point) != EmptyPoint) {
        _freeCounter++;
        int pos = point.x() * (_d1 * _d2) * (_d1 * _d2) + point.y() * (_d1 * _d2) + point.z();
        _matrix[pos] = EmptyPoint;
    }
    return;
}

int GameMatrix::elementAt(int x, int y, int z) const
{
    if (Point(x, y, z).isValid()) {
        int pos = x * (_d1 * _d2) * (_d1 * _d2) + y * (_d1 * _d2) + z;
        return _matrix[pos];
    }
    return -2;
}

int GameMatrix::elementAt(Point point) const
{
    return elementAt(point.x(), point.y(), point.z());
}

bool GameMatrix::isFull() const
{
    return _freeCounter == 0;
}

int GameMatrix::numberOfPlayers() const
{
    return _lastRound.size();
}

void GameMatrix::setLastRound(QList<Point> round)
{
    _lastRound = round;
    return;
}

void GameMatrix::extractCC(Point p, int id, QSet<Point> &set)
{
    set.insert(p);

    QList<Point> adjacent;
    adjacent.append(Point(p.x() - 1, p.y(), p.z()));
    adjacent.append(Point(p.x() + 1, p.y(), p.z()));
    adjacent.append(Point(p.x(), p.y() - 1, p.z()));
    adjacent.append(Point(p.x(), p.y() + 1, p.z()));
    adjacent.append(Point(p.x(), p.y(), p.z() - 1));
    adjacent.append(Point(p.x(), p.y(), p.z() + 1));

    Point e;

    foreach (e, adjacent) {
        if (id == elementAt(e) && set.find(e) == set.end()) {
            extractCC(e, id, set);
        }
    }
    return;
}

int GameMatrix::d1() const
{
    return _d1;
}

int GameMatrix::d2() const
{
    return _d2;
}