1/*
2 * Copyright 2007-2008 Thomas Gallinari <tg8187@yahoo.fr>
3 * Copyright 2007-2008 Pierre-Benoît Besse <besse.pb@gmail.com>
4 *
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License as
7 * published by the Free Software Foundation; either version 2 of
8 * the License, or (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program. If not, see <http://www.gnu.org/licenses/>.
17 */
18
19#include "maze.h"
20
21#include <KDebug>
22
23#include <math.h>
24
25Maze::Maze() : m_totalNbElem(0), m_nbElem(0) {
26
27}
28
29Maze::~Maze() {
30 for(int i = 0 ; i < m_nbRows; ++i) {
31 delete[] m_cells[i];
32 }
33 delete[] m_cells;
34}
35
36void Maze::init(const int p_nbRows, const int p_nbColumns) {
37 m_nbRows = p_nbRows;
38 m_nbColumns = p_nbColumns;
39 m_cells = new Cell*[m_nbRows];
40 for (int i = 0; i < m_nbRows; ++i) {
41 m_cells[i] = new Cell[m_nbColumns];
42 }
43}
44
45void Maze::setCellType(const int p_row, const int p_column, const Cell::Type p_type) {
46 if (p_row < 0 || p_row >= m_nbRows || p_column < 0 || p_column >= m_nbColumns) {
47 kError() << "Bad maze coordinates";
48 }
49 m_cells[p_row][p_column].setType(p_type);
50}
51
52void Maze::setCellElement(const int p_row, const int p_column, Element * p_element) {
53 if (p_row < 0 || p_row >= m_nbRows || p_column < 0 || p_column >= m_nbColumns) {
54 kError() << "Bad maze coordinates";
55 }
56 m_cells[p_row][p_column].setElement(p_element);
57 if (p_element != NULL) {
58 m_totalNbElem++;
59 m_nbElem++;
60 }
61}
62
63void Maze::setResurrectionCell(QPoint p_resurrectionCell) {
64 // TODO : COORDINATES INVERTED, NEED TO CORRECT IT in the findPAth algorithm
65 m_resurrectionCell.setX(p_resurrectionCell.y());
66 m_resurrectionCell.setY(p_resurrectionCell.x());
67}
68
69void Maze::decrementNbElem() {
70 m_nbElem--;
71 if (m_nbElem == 0) {
72 emit(allElementsEaten());
73 }
74}
75
76void Maze::resetNbElem() {
77 m_nbElem = m_totalNbElem;
78}
79
80QList<QPoint> Maze::getPathToGhostCamp(const int p_row, const int p_column) const {
81 QList<QPoint> path;
82 QList<QPoint> openList;
83 QList<QPoint> closedList;
84 QPoint currentCell;
85 QPoint tmpCell;
86 int lowestCost;
87 int icurrent = 0;
88 int oldSize = 0;
89
90 // Initialize the starting cell
91 m_cells[p_row][p_column].setCost(abs(m_resurrectionCell.y() - p_row) + abs(m_resurrectionCell.x() - p_column));
92 // Add the starting cell to the openList
93 openList.append(QPoint(p_column, p_row));
94 // While the closed list does not contain the target cell
95 while (!closedList.contains(QPoint(m_resurrectionCell.x(), m_resurrectionCell.y())) && openList.size() != oldSize) {
96 // Look for the lowest cost cell on the open list
97 lowestCost = 1000;
98 for (int i = 0; i < openList.size(); ++i) {
99 if (m_cells[openList[i].y()][openList[i].x()].getCost() < lowestCost) {
100 lowestCost = m_cells[openList[i].y()][openList[i].x()].getCost();
101 currentCell = openList[i];
102 icurrent = i;
103 }
104 }
105 // Switch this cell to the closed list
106 closedList.append(currentCell);
107 openList.removeAt(icurrent);
108 oldSize = openList.size();
109 // For each of the 4 cells adjacent to the current node
110 // Left
111 tmpCell.setX(currentCell.x() - 1);
112 tmpCell.setY(currentCell.y());
113 if (m_cells[tmpCell.y()][tmpCell.x()].getType() != Cell::WALL) {
114 // If the cell is not in the closed list or the open list
115 if (!closedList.contains(tmpCell) && !openList.contains(tmpCell)) {
116 // Initialize the cell
117 m_cells[tmpCell.y()][tmpCell.x()].setCost(
118 abs(m_resurrectionCell.y() - tmpCell.y()) + abs(m_resurrectionCell.x() - (tmpCell.x())));
119 m_cells[tmpCell.y()][tmpCell.x()].setParent(&m_cells[currentCell.y()][currentCell.x()]);
120 // Add it to the open list
121 openList.append(tmpCell);
122 }
123 }
124 // Right
125 tmpCell.setX(currentCell.x() + 1);
126 tmpCell.setY(currentCell.y());
127 if (m_cells[tmpCell.y()][tmpCell.x()].getType() != Cell::WALL) {
128 // If the cell is not in the closed list or the open list
129 if (!closedList.contains(tmpCell) && !openList.contains(tmpCell)) {
130 // Initialize the cell
131 m_cells[tmpCell.y()][tmpCell.x()].setCost(
132 abs(m_resurrectionCell.y() - tmpCell.y()) + abs(m_resurrectionCell.x() - (tmpCell.x())));
133 m_cells[tmpCell.y()][tmpCell.x()].setParent(&m_cells[currentCell.y()][currentCell.x()]);
134 // Add it to the open list
135 openList.append(tmpCell);
136 }
137 }
138 // Top
139 tmpCell.setX(currentCell.x());
140 tmpCell.setY(currentCell.y() - 1);
141 if (m_cells[tmpCell.y()][tmpCell.x()].getType() != Cell::WALL) {
142 // If the cell is not in the closed list or the open list
143 if (!closedList.contains(tmpCell) && !openList.contains(tmpCell)) {
144 // Initialize the cell
145 m_cells[tmpCell.y()][tmpCell.x()].setCost(
146 abs(m_resurrectionCell.y() - tmpCell.y()) + abs(m_resurrectionCell.x() - (tmpCell.x())));
147 m_cells[tmpCell.y()][tmpCell.x()].setParent(&m_cells[currentCell.y()][currentCell.x()]);
148 // Add it to the open list
149 openList.append(tmpCell);
150 }
151 }
152 // Bottom
153 tmpCell.setX(currentCell.x());
154 tmpCell.setY(currentCell.y() + 1);
155 if (m_cells[tmpCell.y()][tmpCell.x()].getType() != Cell::WALL) {
156 // If the cell is not in the closed list or the open list
157 if (!closedList.contains(tmpCell) && !openList.contains(tmpCell)) {
158 // Initialize the cell
159 m_cells[tmpCell.y()][tmpCell.x()].setCost(
160 abs(m_resurrectionCell.y() - tmpCell.y()) + abs(m_resurrectionCell.x() - (tmpCell.x())));
161 m_cells[tmpCell.y()][tmpCell.x()].setParent(&m_cells[currentCell.y()][currentCell.x()]);
162 // Add it to the open list
163 openList.append(tmpCell);
164 }
165 }
166 }
167 if (oldSize == openList.size()) {
168 kError() << "Path to ghost home not found";
169 return QList<QPoint>();
170 }
171 // Save the path : from the target cell, go from each cell to its parent cell until reaching the starting cell
172 for (Cell* cell = &m_cells[m_resurrectionCell.y()][m_resurrectionCell.x()];
173 cell->getParent() != &m_cells[p_row][p_column]; cell = cell->getParent()) {
174 path.prepend(getCoords(cell));
175 }
176
177 return path;
178}
179
180Cell Maze::getCell(const int p_row, const int p_column) const {
181 if (p_row < 0 || p_row >= m_nbRows ||
182 p_column < 0 || p_column >= m_nbColumns) {
183 kError() << "Bad maze coordinates";
184 }
185 return m_cells[p_row][p_column];
186}
187
188QPoint Maze::getCoords(Cell* p_cell) const {
189 for (int i = 0; i < m_nbRows; ++i) {
190 for (int j = 0; j < m_nbColumns; ++j) {
191 if (&m_cells[i][j] == p_cell) {
192 return QPoint(j, i);
193 }
194 }
195 }
196 return QPoint();
197}
198
199int Maze::getRowFromY(const qreal p_y) const {
200 return (int)(p_y / Cell::SIZE);
201}
202
203int Maze::getColFromX(const qreal p_x) const {
204 return (int)(p_x / Cell::SIZE);
205}
206
207int Maze::getNbColumns() const {
208 return m_nbColumns;
209}
210
211int Maze::getNbRows() const {
212 return m_nbRows;
213}
214
215int Maze::getNbElem() const {
216 return m_nbElem;
217}
218
219int Maze::getTotalNbElem() const {
220 return m_totalNbElem;
221}
222
223QPoint Maze::getResurrectionCell() const {
224 return m_resurrectionCell;
225}
226