From 8b5a57c683d9892360881e739eb085a3d467c428 Mon Sep 17 00:00:00 2001 From: Daniele Battaglia Date: Fri, 7 Mar 2008 19:37:10 +0100 Subject: [PATCH] Completed an AI implementation --- ai_diagram/128044.diagram | 2 +- ai_diagram/128058.diagram | 12 +-- ai_diagram/ai_diagram.prj | 16 ++-- doc/DP/DP_Core.tex | 7 ++ src/ai/Threat.cpp | 205 +++++++++++++++++++++++++++++++++++++++++++++- src/core/GameMatrix.cpp | 2 + 6 files changed, 228 insertions(+), 16 deletions(-) diff --git a/ai_diagram/128044.diagram b/ai_diagram/128044.diagram index 52bad04..2c884fd 100644 --- a/ai_diagram/128044.diagram +++ b/ai_diagram/128044.diagram @@ -49,7 +49,7 @@ flowcanvas 128940 flow_ref 128300 // end flowcanvas 129196 flow_ref 128428 // - from ref 128556 z 2004 label "[0 <= pri < _d1]" xyz 227 181 2004 to ref 129068 + from ref 128556 z 2004 label "[0 <= pri < _d1 - 1]" xyz 223 181 2004 to ref 129068 show_infonote default drawing_language default write_horizontally default end flowcanvas 129964 flow_ref 128684 // diff --git a/ai_diagram/128058.diagram b/ai_diagram/128058.diagram index cd19fa5..8c10a6f 100644 --- a/ai_diagram/128058.diagram +++ b/ai_diagram/128058.diagram @@ -86,7 +86,7 @@ activityactioncanvas 134842 activityaction_ref 128698 // activity action difesa end end end -activityactioncanvas 135354 activityaction_ref 128826 // activity action cerca l'unica casella libera nello spazio indicato da un elemento di _priority[_d1-1] +activityactioncanvas 135354 activityaction_ref 128826 // activity action cerca l'unica casella libera nello spazio indicato da un elemento di _priority[_d1-2] show_infonote default drawing_language default show_opaque_action_definition default xyzwh 631 421 2005 178 74 @@ -175,18 +175,18 @@ flowcanvas 128163 flow_ref 128035 // end flowcanvas 128272 flow_ref 128016 // - from ref 139706 z 2004 label "[difesa.isNull()]" xyz 338 554 3000 to ref 128144 + from ref 139706 z 2004 label "[difesa.isNull()]" xyz 338 554 2004 to ref 128144 show_infonote default drawing_language default write_horizontally default end flowcanvas 128291 flow_ref 128163 // - from ref 128035 z 2004 label "[_priority[_d1 - 1] non vuota]" xyz 444 386 2004 to point 717 380 + from ref 128035 z 2004 label "[_priority[_d1 - 2] non vuota]" xyz 452 383 2004 to point 717 380 line 128419 z 2004 to ref 135354 show_infonote default drawing_language default write_horizontally default end flowcanvas 128400 flow_ref 128144 // - from ref 128144 z 2004 label "[level >= 3]" xyz 356 579 3000 to ref 134842 + from ref 128144 z 2004 label "[else]" xyz 373 582 2004 to ref 134842 show_infonote default drawing_language default write_horizontally default end flowcanvas 128547 flow_ref 128291 // @@ -207,7 +207,7 @@ flowcanvas 128826 flow_ref 128186 // end flowcanvas 128912 flow_ref 128400 // - from ref 128144 z 2009 label "[else]" xyz 341 636 3000 to ref 128528 + from ref 128144 z 2009 label "[level < 3]" xyz 339 627 2009 to ref 128528 show_infonote default drawing_language default write_horizontally default end flowcanvas 129040 flow_ref 128528 // @@ -224,7 +224,7 @@ flowcanvas 129082 flow_ref 128314 // end flowcanvas 129168 flow_ref 128656 // - from ref 140218 z 2004 label "[difesa.isNull()]" xyz 379 680 3000 to ref 128528 + from ref 140218 z 2004 label "[difesa.isNull()]" xyz 379 680 2004 to ref 128528 show_infonote default drawing_language default write_horizontally default end flowcanvas 129424 flow_ref 128784 // diff --git a/ai_diagram/ai_diagram.prj b/ai_diagram/ai_diagram.prj index dd4c6d0..6a93bcb 100644 --- a/ai_diagram/ai_diagram.prj +++ b/ai_diagram/ai_diagram.prj @@ -1,7 +1,7 @@ format 49 "ai_diagram" - revision 36 - modified_by 121 "daniele" + revision 37 + modified_by 89 "daniele" @@ -1149,7 +1149,7 @@ se nn lo trova return -1;" flow 128428 "" on activityaction_ref 128300 // activity action push del Node puntato da it in testa alla lista _priority[pri] - uml_guard "0 <= pri < _d1" + uml_guard "0 <= pri < _d1 - 1" end end @@ -2112,7 +2112,7 @@ ${inlines} out end - activityaction 128826 "cerca l'unica casella libera nello spazio indicato da un elemento di _priority[_d1-1]" + activityaction 128826 "cerca l'unica casella libera nello spazio indicato da un elemento di _priority[_d1-2]" opaque_action pin 128186 "mossa" explicit_type "" unordered @@ -2251,8 +2251,8 @@ ${inlines} activitynode 128035 decision "" flow 128163 "" - on activityaction_ref 128826 // activity action cerca l'unica casella libera nello spazio indicato da un elemento di _priority[_d1-1] - uml_guard "_priority[_d1 - 1] non vuota" + on activityaction_ref 128826 // activity action cerca l'unica casella libera nello spazio indicato da un elemento di _priority[_d1-2] + uml_guard "_priority[_d1 - 2] non vuota" end flow 128291 "" @@ -2264,12 +2264,12 @@ ${inlines} activitynode 128016 decision "" flow 128144 "" on activityaction_ref 128698 // activity action difesa = defenseHook() - uml_guard "level >= 3" + uml_guard "else" end flow 128400 "" on activitynode_ref 128144 // merge - uml_guard "else" + uml_guard "level < 3" end end diff --git a/doc/DP/DP_Core.tex b/doc/DP/DP_Core.tex index fd7ca31..3debc83 100644 --- a/doc/DP/DP_Core.tex +++ b/doc/DP/DP_Core.tex @@ -87,6 +87,13 @@ Le istanze di questa classe rappresentano una posizione all'interno della \uline \end{itemize} \smallskip +\subsubsection{toString} +\texttt{public QString toString() [const]} +\begin{itemize} + \item Comportamento: ritorna la rappresentazione nella forma \verb!(x, y, z)! del \texttt{Point} su cui viene invocato. +\end{itemize} +\smallskip + \subsubsection{operator==} \texttt{public bool operator==(const Point \&p) [const]} \begin{itemize} diff --git a/src/ai/Threat.cpp b/src/ai/Threat.cpp index 2acdbb3..c92711c 100644 --- a/src/ai/Threat.cpp +++ b/src/ai/Threat.cpp @@ -19,6 +19,7 @@ * *******************************************************************/ +#include #include "Threat.h" Threat::Threat(ThreatSearchAI *ai) @@ -48,4 +49,206 @@ void Threat::insert(Point point) evalInsert(point, i, DIR_Y); evalInsert(point, i, DIR_Z); } -} \ No newline at end of file +} + +void Threat::scanFromMatrix() +{ + int dim = _d1 * _d2; + for (int x = 0; x < dim; x++) { + for (int y = 0; y < dim; y++) { + for (int z = 0; z < dim; z++) { + Point key = Point(x, y, z); + + int pri = evalPriority(key, DIR_X); + if (pri >= 0) { + QMap::iterator it = _x.insert(key, new Node(pri, key, DIR_X)); + insertInPriority(*it); + } + + pri = evalPriority(key, DIR_Y); + if (pri >= 0) { + QMap::iterator it = _y.insert(key, new Node(pri, key, DIR_Y)); + insertInPriority(*it); + } + + pri = evalPriority(key, DIR_Z); + if (pri >= 0) { + QMap::iterator it = _z.insert(key, new Node(pri, key, DIR_Z)); + insertInPriority(*it); + } + } + } + } + + scanFromMatrixHook(); +} + +void Threat::insertHook(Point p) +{ +} + +void Threat::scanFromMatrixHook() +{ +} + +void Threat::evalInsert(Point p, int index, Direction dir) +{ + QMap *map = 0; + QVector coeff(3,0); + + switch (dir) { + case DIR_X : + map = &_x; + coeff[0] = 1; + break; + case DIR_Y : + map = &_y; + coeff[1] = 1; + break; + case DIR_Z : + map = &_z; + coeff[2] = 1; + break; + } + + int start = coeff[0] * p.x() + coeff[1] * p.y() + coeff[2] * p.z() - index; //calcolo dove inizia il pattern + if (start < 0) { + return; + } + Point key(p.x() - coeff[0] * index, p.y() - coeff[0] * index, p.z() - coeff[0] * index); + QMap::iterator it = map->find(key); + int pri = evalPriority(key, dir); + + if (it == map->end()) { + if (pri >= 0) { + //inserisco nella struttura + it = map->insert(key, new Node(pri, key, dir)); + //aggiungo alla list priority corretta + insertInPriority(*it); + } + } + else { + //tolgo dalla lista priority + removeFromPriority(*it); + if (pri < 0) { + //tolgo dalla struttura + delete *it; + map->erase(it); + } + else { + //aggiorno la priorità nel nodo + (*it)->value = pri; + //e lo inserisco nuovamente nella lista + insertInPriority(*it); + } + } +} + +int Threat::evalPriority(Point p, Direction dir) const +{ + QVector coeff(3,0); + + switch (dir) { + case DIR_X : + coeff[0] = 1; + break; + case DIR_Y : + coeff[1] = 1; + break; + case DIR_Z : + coeff[2] = 1; + break; + } + + //controllo che il pattern sia nei limiti della matrice + int start = p.x() * coeff[0] + p.y() * coeff[1] + p.z() * coeff[2]; + if (start < 0 || start + _d1 > _d1*_d2) { + return -1; + } + + int pri = 0; + bool valid = true; + + for (int j = 0; j < _d1 && valid; j++) { + int piece = _mat->elementAt(p.x() + coeff[0] * j, p.y() + coeff[0] * j, p.z() + coeff[0] * j); + if (piece == _ai->playerId()) { + pri++; + } + else { + if (piece != GameMatrix::EmptyPoint) { + valid = false; + } + } + } + + if (!valid) { + pri=0; + } + return pri-1; +} + +void Threat::insertInPriority(Node *it) +{ + int pri = it->value; + if (pri >= 0 && pri < _d1 - 1) { + it->next = _priority[pri]; + it->par = &(_priority[pri]); + if (_priority[pri]) { + _priority[pri]->par = &(it->next); + } + _priority[pri] = it; + } +} + +void Threat::removeFromPriority(Node *it) +{ + *(it->par) = it->next; + if (it->next) { + it->next->par = it->par; + } + it->par = 0; + it->next = 0; +} + +QList Threat::findEmptyPoints(Node *node) +{ + QList result; + + QVector coeff(3,0); + + switch (node->dir) { + case DIR_X : + coeff[0] = 1; + break; + case DIR_Y : + coeff[1] = 1; + break; + case DIR_Z : + coeff[2] = 1; + break; + } + + for (int i = 0; i < _d1; i++) { + Point key(node->point.x() + i * coeff[0], node->point.y() + i * coeff[1], node->point.z() + i * coeff[2]); + if (_mat->elementAt(key) == GameMatrix::EmptyPoint) { + result.append(key); + } + } + return result; +} + +Threat::Node::Node(int val, Point p, Direction dir) +{ + value = val; + point = p; + this->dir = dir; + par = 0; + next = 0; +} + +Threat::Node::~Node() +{ + if (next != 0) { + delete next; + } +} diff --git a/src/core/GameMatrix.cpp b/src/core/GameMatrix.cpp index 8ff27ea..50bee2d 100644 --- a/src/core/GameMatrix.cpp +++ b/src/core/GameMatrix.cpp @@ -24,6 +24,8 @@ const int GameMatrix::EmptyPoint = -1; +GameMatrix *GameMatrix::_instance = 0; + GameMatrix::GameMatrix(int d1, int d2, int numPlayers) { _d1 = d1; -- 2.11.4.GIT