← Back to branch summary

~ubuntu-branches/ubuntu/vivid/kapman/vivid-proposed

« back to all changes in this revision

Viewing changes to maze.cpp

  • Committer: Package Import Robot
  • Author(s): Jonathan Riddell
  • Date: 2012-12-07 17:37:19 UTC
  • Revision ID: package-import@ubuntu.com-20121207173719-5973b949kqub4zup
Tags: upstream-4.9.90
Import upstream version 4.9.90

Show diffs side-by-side

added added

removed removed

Lines of Context:
maze.cpp
 
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
 
 
25
Maze::Maze() : m_totalNbElem(0), m_nbElem(0) {
 
26
        
 
27
}
 
28
        
 
29
Maze::~Maze() {
 
30
        for(int i = 0 ; i < m_nbRows; ++i) {
 
31
                delete[] m_cells[i];
 
32
        }
 
33
        delete[] m_cells;
 
34
}
 
35
 
 
36
void 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
 
 
45
void 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
 
 
52
void 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
 
 
63
void 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
 
 
69
void Maze::decrementNbElem() {
 
70
        m_nbElem--;
 
71
        if (m_nbElem == 0) {
 
72
                emit(allElementsEaten());
 
73
        }
 
74
}
 
75
 
 
76
void Maze::resetNbElem() {
 
77
        m_nbElem = m_totalNbElem;
 
78
}
 
79
 
 
80
QList<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
 
 
180
Cell 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
 
 
188
QPoint 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
 
 
199
int Maze::getRowFromY(const qreal p_y) const {
 
200
        return (int)(p_y / Cell::SIZE);
 
201
}
 
202
 
 
203
int Maze::getColFromX(const qreal p_x) const {
 
204
        return (int)(p_x / Cell::SIZE);
 
205
}
 
206
 
 
207
int Maze::getNbColumns() const {
 
208
        return m_nbColumns;
 
209
}
 
210
 
 
211
int Maze::getNbRows() const {
 
212
        return m_nbRows;
 
213
}
 
214
 
 
215
int Maze::getNbElem() const {
 
216
        return m_nbElem;
 
217
}
 
218
 
 
219
int Maze::getTotalNbElem() const {
 
220
        return m_totalNbElem;
 
221
}
 
222
 
 
223
QPoint Maze::getResurrectionCell() const {
 
224
        return m_resurrectionCell;
 
225
}