1 /***********************************************************************
2 *
3 * Copyright (C) 2009, 2014, 2017 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 "solver.h"
21
22 #include "maze.h"
23 #include "path.h"
24
25 #include <algorithm>
26
27 // ============================================================================
28
29 namespace
30 {
31 QPoint compare_start;
32
pathShorter(const Path * path1,const Path * path2)33 bool pathShorter(const Path* path1, const Path* path2)
34 {
35 return path1->length(compare_start) < path2->length(compare_start);
36 }
37 }
38
39 // ============================================================================
40
Solver(Maze * maze,const QPoint & start,const QList<QPoint> & targets)41 Solver::Solver(Maze* maze, const QPoint& start, const QList<QPoint>& targets)
42 : m_maze(maze)
43 {
44 for (const QPoint& target : targets) {
45 m_paths.append(new Path(m_maze, start, target));
46 }
47 compare_start = start;
48 std::sort(m_paths.begin(), m_paths.end(), pathShorter);
49 }
50
51 // ============================================================================
52
hint(const QPoint & current)53 QPoint Solver::hint(const QPoint& current)
54 {
55 forever {
56 QPoint result = m_paths.first()->hint(current);
57 if (result.x() != -1) {
58 return result;
59 } else {
60 QPoint target = m_paths.first()->end();
61 delete m_paths.takeFirst();
62 m_paths.append(new Path(m_maze, current, target));
63 compare_start = current;
64 std::sort(m_paths.begin(), m_paths.end(), pathShorter);
65 }
66 }
67 }
68
69 // ============================================================================
70
removeTarget(const QPoint & target)71 void Solver::removeTarget(const QPoint& target)
72 {
73 for (int i = 0; i < m_paths.count(); ++i) {
74 if (m_paths.at(i)->end() == target) {
75 delete m_paths.takeAt(i);
76 break;
77 }
78 }
79 }
80
81 // ============================================================================
82