1 /***********************************************************************
2 *
3 * Copyright (C) 2009 Graeme Gott <graeme@gottcode.org>
4 *
5 * This program is free software: you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation, either version 3 of the License, or
8 * (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
20 #include "path.h"
21
22 #include "maze.h"
23
24 // ============================================================================
25
Path(Maze * maze,const QPoint & start,const QPoint & end)26 Path::Path(Maze* maze, const QPoint& start, const QPoint& end)
27 : m_maze(maze),
28 m_start(start),
29 m_end(end),
30 m_cells(maze->columns(), QVector<bool>(maze->rows(), false))
31 {
32 // Fill in dead ends
33 for (int r = 0; r < m_maze->rows(); ++r) {
34 for (int c = 0; c < m_maze->columns(); ++c) {
35 QPoint pos(c, r);
36 while (cellWalls(pos) == 3 && pos != m_start && pos != m_end) {
37 m_cells[pos.x()][pos.y()] = true;
38 findNextCell(pos);
39 }
40 }
41 }
42
43 // Follow path and record cells
44 QPoint pos = start;
45 pos = start;
46 do {
47 m_cells[pos.x()][pos.y()] = true;
48 m_solution.append(pos);
49 findNextCell(pos);
50 } while (pos != end);
51 m_solution.append(pos);
52 }
53
54 // ============================================================================
55
hint(const QPoint & cell) const56 QPoint Path::hint(const QPoint& cell) const
57 {
58 int pos = m_solution.indexOf(cell);
59 if (pos != -1 && pos < m_solution.count() - 1) {
60 return m_solution.at(pos + 1);
61 } else {
62 return QPoint(-1,-1);
63 }
64 }
65
66 // ============================================================================
67
length(const QPoint & start) const68 int Path::length(const QPoint& start) const
69 {
70 int pos = m_solution.indexOf(start);
71 if (pos != -1) {
72 return m_solution.count() - pos - 1;
73 } else {
74 return -1;
75 }
76 }
77
78 // ============================================================================
79
findNextCell(QPoint & pos)80 void Path::findNextCell(QPoint& pos)
81 {
82 if (!leftWall(pos)) {
83 pos.rx()--;
84 } else if (!rightWall(pos)) {
85 pos.rx()++;
86 } else if (!topWall(pos)) {
87 pos.ry()--;
88 } else if (!bottomWall(pos)) {
89 pos.ry()++;
90 }
91 }
92
93 // ============================================================================
94
leftWall(const QPoint & pos) const95 bool Path::leftWall(const QPoint& pos) const
96 {
97 return (m_maze->cell(pos.x(), pos.y()).leftWall() || (pos.x() > 0 && m_cells[pos.x() - 1][pos.y()] == true));
98 }
99
100 // ============================================================================
101
rightWall(const QPoint & pos) const102 bool Path::rightWall(const QPoint& pos) const
103 {
104 return (m_maze->cell(pos.x(), pos.y()).rightWall() || (pos.x() < m_maze->columns() - 1 && m_cells[pos.x() + 1][pos.y()] == true));
105 }
106
107 // ============================================================================
108
topWall(const QPoint & pos) const109 bool Path::topWall(const QPoint& pos) const
110 {
111 return (m_maze->cell(pos.x(), pos.y()).topWall() || (pos.y() > 0 && m_cells[pos.x()][pos.y() - 1] == true));
112 }
113
114 // ============================================================================
115
bottomWall(const QPoint & pos) const116 bool Path::bottomWall(const QPoint& pos) const
117 {
118 return (m_maze->cell(pos.x(), pos.y()).bottomWall() || (pos.y() < m_maze->rows() - 1 && m_cells[pos.x()][pos.y() + 1] == true));
119 }
120
121 // ============================================================================
122