src/ai/Threat.cpp

   1 /********************************************************************
   2  *
   3  * Copyright (C) 2008  Daniele Battaglia
   4  *
   5  * This file is part of GoMoku3D.
   6  *
   7  * GoMoku3D is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU General Public License
   9  * as published by the Free Software Foundation; either version 2
  10  * of the License, or (at your option) any later version.
  11  *
  12  * GoMoku3D is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  * GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with GoMoku3D. If not, see <http://www.gnu.org/licenses/>.
  19  *
  20  *******************************************************************/
  21
  22 #include <QVector>
  23 #include "Threat.h"
  24
  25 Threat::Threat(ThreatSearchAI *ai)
  26 {
  27     _ai = ai;
  28     _mat = GameMatrix::instance();
  29     _d1 = _mat->d1();
  30     _d2 = _mat->d2();
  31     _priority = new Node*[_d1 - 1];
  32     for (int i = 0; i < _d1 - 1; i++) {
  33         _priority[i] = 0;
  34     }
  35 }
  36
  37 Threat::~Threat()
  38 {
  39     for (int i = 0; i < _d1 - 1; i++) {
  40         delete _priority[i];
  41     }
  42     delete _priority;
  43 }
  44
  45 void Threat::insert(Point point)
  46 {
  47     for (int i = 0; i < _d1; i++) {
  48         evalInsert(point, i, DIR_X);
  49         evalInsert(point, i, DIR_Y);
  50         evalInsert(point, i, DIR_Z);
  51     }
  52 }
  53
  54 void Threat::scanFromMatrix()
  55 {
  56     int dim = _d1 * _d2;
  57     for (int x = 0; x < dim; x++) {
  58         for (int y = 0; y < dim; y++) {
  59             for (int z = 0; z < dim; z++) {
  60                 Point key = Point(x, y, z);
  61
  62                 int pri = evalPriority(key, DIR_X);
  63                 if (pri >= 0) {
  64                     QMap<Point, Node*>::iterator it = _x.insert(key, new Node(pri, key, DIR_X));
  65                     insertInPriority(*it);
  66                 }
  67
  68                 pri = evalPriority(key, DIR_Y);
  69                 if (pri >= 0) {
  70                     QMap<Point, Node*>::iterator it = _y.insert(key, new Node(pri, key, DIR_Y));
  71                     insertInPriority(*it);
  72                 }
  73
  74                 pri = evalPriority(key, DIR_Z);
  75                 if (pri >= 0) {
  76                     QMap<Point, Node*>::iterator it = _z.insert(key, new Node(pri, key, DIR_Z));
  77                     insertInPriority(*it);
  78                 }
  79             }
  80         }
  81     }
  82
  83     scanFromMatrixHook();
  84 }
  85
  86 void Threat::insertHook(Point p)
  87 {
  88 }
  89
  90 void Threat::scanFromMatrixHook()
  91 {
  92 }
  93
  94 void Threat::evalInsert(Point p, int index, Direction dir)
  95 {
  96     QMap<Point, Node*> *map = 0;
  97     QVector<int> coeff(3,0);
  98
  99     switch (dir) {
 100         case DIR_X :
 101             map = &_x;
 102             coeff[0] = 1;
 103             break;
 104         case DIR_Y :
 105             map = &_y;
 106             coeff[1] = 1;
 107             break;
 108         case DIR_Z :
 109             map = &_z;
 110             coeff[2] = 1;
 111             break;
 112     }
 113
 114     int start = coeff[0] * p.x() + coeff[1] * p.y() + coeff[2] * p.z() - index; //calcolo dove inizia il pattern
 115     if (start < 0) {
 116         return;
 117     }
 118     Point key(p.x() - coeff[0] * index, p.y() - coeff[0] * index, p.z() - coeff[0] * index);
 119     QMap<Point, Node*>::iterator it = map->find(key);
 120     int pri = evalPriority(key, dir);
 121
 122     if (it == map->end()) {
 123         if (pri >= 0) {
 124             //inserisco nella struttura
 125             it = map->insert(key, new Node(pri, key, dir));
 126             //aggiungo alla list priority corretta
 127             insertInPriority(*it);
 128         }
 129     }
 130     else {
 131         //tolgo dalla lista priority
 132         removeFromPriority(*it);
 133         if (pri < 0) {
 134         //tolgo dalla struttura
 135             delete *it;
 136             map->erase(it);
 137         }
 138         else {
 139         //aggiorno la priorità nel nodo
 140             (*it)->value = pri;
 141         //e lo inserisco nuovamente nella lista
 142             insertInPriority(*it);
 143         }
 144     }
 145 }
 146
 147 int Threat::evalPriority(Point p, Direction dir) const
 148 {
 149     QVector<int> coeff(3,0);
 150
 151     switch (dir) {
 152         case DIR_X :
 153             coeff[0] = 1;
 154             break;
 155         case DIR_Y :
 156             coeff[1] = 1;
 157             break;
 158         case DIR_Z :
 159             coeff[2] = 1;
 160             break;
 161     }
 162
 163     //controllo che il pattern sia nei limiti della matrice
 164     int start = p.x() * coeff[0] + p.y() * coeff[1] + p.z() * coeff[2];
 165     if (start < 0 || start + _d1 > _d1*_d2) {
 166         return -1;
 167     }
 168
 169     int pri = 0;
 170     bool valid = true;
 171
 172     for (int j = 0; j < _d1 && valid; j++) {
 173         int piece = _mat->elementAt(p.x() + coeff[0] * j, p.y() + coeff[0] * j, p.z() + coeff[0] * j);
 174         if (piece == _ai->playerId()) {
 175             pri++;
 176         }
 177         else {
 178             if (piece != GameMatrix::EmptyPoint) {
 179                 valid = false;
 180             }
 181         }
 182     }
 183
 184     if (!valid) {
 185         pri=0;
 186     }
 187     return pri-1;
 188 }
 189
 190 void Threat::insertInPriority(Node *it)
 191 {
 192     int pri = it->value;
 193     if (pri >= 0 && pri < _d1 - 1) {
 194         it->next = _priority[pri];
 195         it->par = &(_priority[pri]);
 196         if (_priority[pri]) {
 197             _priority[pri]->par = &(it->next);
 198         }
 199         _priority[pri] = it;
 200     }
 201 }
 202
 203 void Threat::removeFromPriority(Node *it)
 204 {
 205     *(it->par) = it->next;
 206     if (it->next) {
 207         it->next->par = it->par;
 208     }
 209     it->par = 0;
 210     it->next = 0;
 211 }
 212
 213 QList<Point> Threat::findEmptyPoints(Node *node)
 214 {
 215     QList<Point> result;
 216
 217     QVector<int> coeff(3,0);
 218
 219     switch (node->dir) {
 220         case DIR_X :
 221             coeff[0] = 1;
 222             break;
 223         case DIR_Y :
 224             coeff[1] = 1;
 225             break;
 226         case DIR_Z :
 227             coeff[2] = 1;
 228             break;
 229     }
 230
 231     for (int i = 0; i < _d1; i++) {
 232         Point key(node->point.x() + i * coeff[0], node->point.y() + i * coeff[1], node->point.z() + i * coeff[2]);
 233         if (_mat->elementAt(key) == GameMatrix::EmptyPoint) {
 234             result.append(key);
 235         }
 236     }
 237     return result;
 238 }
 239
 240 Threat::Node::Node(int val, Point p, Direction dir)
 241 {
 242     value = val;
 243     point = p;
 244     this->dir = dir;
 245     par = 0;
 246     next = 0;
 247 }
 248
 249 Threat::Node::~Node()
 250 {
 251     if (next != 0) {
 252         delete next;
 253     }
 254 }