1 /* ScummVM - Graphic Adventure Engine
2 *
3 * ScummVM is the legal property of its developers, whose names
4 * are too numerous to list here. Please refer to the COPYRIGHT
5 * file distributed with this source distribution.
6 *
7 * This program is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License
9 * as published by the Free Software Foundation; either version 2
10 * of the License, or (at your option) any later version.
11 *
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
20 *
21 */
22
23 #include "ultima/nuvie/core/map.h"
24 #include "ultima/nuvie/pathfinder/dir_finder.h"
25 #include "ultima/nuvie/pathfinder/seek_path.h"
26
27 namespace Ultima {
28 namespace Nuvie {
29
30 using Std::vector;
31
SeekPath()32 SeekPath::SeekPath() {
33
34 }
35
~SeekPath()36 SeekPath::~SeekPath() {
37
38 }
39
40 /* Get two relative directions that a line can travel to trace around an
41 obstacle towards `xdir',`ydir'. */
get_obstacle_tracer(MapCoord & start,sint32 xdir,sint32 ydir,sint32 & Axdir,sint32 & Aydir,sint32 & Bxdir,sint32 & Bydir)42 bool SeekPath::get_obstacle_tracer(MapCoord &start, sint32 xdir, sint32 ydir,
43 sint32 &Axdir, sint32 &Aydir,
44 sint32 &Bxdir, sint32 &Bydir) {
45 if (xdir && ydir) { // original direction is diagonal
46 MapCoord checkA(start.x + xdir, start.y, start.z);
47 MapCoord checkB(start.x, start.y + ydir, start.z);
48 if (check_loc(checkA)) { // can go in X
49 Axdir = xdir;
50 Aydir = 0; // Horizontal; in X direction
51 } else { // X is blocked, must go in Y
52 Axdir = 0;
53 Aydir = -ydir; // Vertical; opposite Y direction
54 }
55 if (check_loc(checkB)) { // can go in Y
56 Bxdir = 0;
57 Bydir = ydir; // Vertical; in Y direction
58 } else { // Y is blocked, must go in X
59 Bxdir = -xdir;
60 Bydir = 0; // Horizontal; opposite X direction
61 }
62 } else { // orthagonal
63 // scan in perpendicular straight line
64 Axdir = ydir;
65 Aydir = xdir;
66 Bxdir = -Axdir;
67 Bydir = -Aydir;
68 }
69 return false;
70 }
71
72 /* Returns true if an opening is found along the original line. */
trace_check_obstacle(bool & turned,MapCoord & line,sint32 & deltax,sint32 & deltay,sint32 & xdir,sint32 & ydir,Std::vector<MapCoord> * scan)73 bool SeekPath::trace_check_obstacle(bool &turned, MapCoord &line, sint32 &deltax, sint32 &deltay, sint32 &xdir, sint32 &ydir, Std::vector<MapCoord> *scan) {
74 MapCoord obstacle(line.x + xdir, line.y + ydir, line.z);
75 if (check_loc(obstacle)) { // no obstacle here; able to move closer
76 if (scan->empty() || scan->back() != line)
77 scan->push_back(line); // *ADD TRACE NODE*
78 if (!turned) {
79 scan->push_back(obstacle); // *ADD TRACE NODE*
80 return true;
81 }
82 // bend line TOWARDS obstacle
83 line.x += xdir;
84 line.y += ydir; // step forward
85 sint32 old_deltax = deltax, old_deltay = deltay;
86 deltax = xdir;
87 deltay = ydir; // now moving in that direction
88 xdir = -old_deltax;
89 ydir = -old_deltay; // and looking away from old delta
90 turned = false;
91 }
92 return false;
93 }
94
trace_around_corner(MapCoord & line,sint32 & deltax,sint32 & deltay,sint32 & xdir,sint32 & ydir,Std::vector<MapCoord> * scan)95 void SeekPath::trace_around_corner(MapCoord &line, sint32 &deltax, sint32 &deltay, sint32 &xdir, sint32 &ydir, Std::vector<MapCoord> *scan) {
96 line.x -= deltax;
97 line.y -= deltay; // step back
98 if (scan->empty() || scan->back() != line)
99 scan->push_back(line); // *ADD TRACE NODE*
100 sint8 old_xdir = xdir, old_ydir = ydir;
101 xdir = deltax;
102 ydir = deltay; // now looking in that direction
103 deltax = -old_xdir;
104 deltay = -old_ydir; // and moving scan away from old obstacle
105 }
106
107 /* Trace an obstacle from 'start' towards the direction 'deltax' and 'deltay',
108 looking for openings towards 'xdir' and 'ydir'. The scan can bend 90 degrees
109 to get around walls. Returns true if something that looks like an opening
110 has been found. Trace nodes are placed at turns and where the scan ends. */
trace_obstacle(MapCoord line,sint32 deltax,sint32 deltay,sint32 xdir,sint32 ydir,Std::vector<MapCoord> * scan)111 bool SeekPath::trace_obstacle(MapCoord line, sint32 deltax, sint32 deltay, sint32 xdir, sint32 ydir, Std::vector<MapCoord> *scan) {
112 const uint32 scan_max = 8; // number of squares to check before giving up
113 bool bend = false; // true if the scanning line is rotated 90 degrees
114 uint32 s = 0;
115 do {
116 line.x += deltax;
117 line.y += deltay;
118 if (!check_loc(line)) {
119 if (!bend) { // bend line AWAY from obstacle
120 trace_around_corner(line, deltax, deltay, xdir, ydir, scan);
121 bend = true;
122 } else // blocked (we only allow one turn)
123 break;
124 } else if (trace_check_obstacle(bend, line, deltax, deltay, xdir, ydir, scan))
125 return true;
126 } while (++s < scan_max);
127 scan->resize(0);
128 return false;
129 }
130
131 // choose which set of nodes traced around an obstacle should be used for a path
get_best_scan(MapCoord & start,MapCoord & goal)132 Std::vector<MapCoord> *SeekPath::get_best_scan(MapCoord &start, MapCoord &goal) {
133 if (A_scan.empty() && B_scan.empty())
134 return 0;
135 if (A_scan.empty())
136 return &B_scan;
137 if (B_scan.empty())
138 return &A_scan;
139 if (B_scan.back().distance(goal) < A_scan.back().distance(goal))
140 return &B_scan;
141 return &A_scan;
142 }
143
144 // copy A or B nodes to the path
create_path(MapCoord & start,MapCoord & goal)145 void SeekPath::create_path(MapCoord &start, MapCoord &goal) {
146 vector<MapCoord> *nodes = get_best_scan(start, goal); // points to line A or B
147 MapCoord prev_node(start);
148
149 // these nodes are only at certain locations in the path, so all steps in
150 // between have to be added
151 while (nodes && !nodes->empty()) {
152 // create steps from prev_node to this_node
153 MapCoord this_node = nodes->front();
154 nodes->erase(nodes->begin());
155 if (this_node == start) // start is the first prev_node, which results in duplicate steps
156 continue;
157 sint16 dx = clamp(this_node.x - prev_node.x, -1, 1), dy = clamp(this_node.y - prev_node.y, -1, 1);
158 do {
159 prev_node = prev_node.abs_coords(dx, dy); // add dx & dy
160 add_step(prev_node);
161 } while (prev_node != this_node);
162
163 prev_node = this_node;
164 }
165 }
166
167 /* Returns true if a path is found around the obstacle between locations. */
path_search(MapCoord & start,MapCoord & goal)168 bool SeekPath::path_search(MapCoord &start, MapCoord &goal) {
169 sint8 xdir = 0, ydir = 0; // direction start->goal
170 DirFinder::get_normalized_dir(start, goal, xdir, ydir); // init xdir & ydir
171
172 // confirm that goal is more than one square away
173 if ((start.x + xdir) == goal.x && (start.y + ydir) == goal.y)
174 return false;
175
176 // determine if each line (A and B) will be vertical or horizontal
177 sint32 Ax = 0, Ay = 0, Bx = 0, By = 0; // vector of line segments to scan
178 get_obstacle_tracer(start, xdir, ydir, Ax, Ay, Bx, By);
179
180 // direction from line to scan is perpendicular to line, towards obstacle
181 delete_nodes();
182 bool successA = trace_obstacle(start, Ax, Ay, (Ay) ? xdir : 0, (Ax) ? ydir : 0, &A_scan);
183 bool successB = trace_obstacle(start, Bx, By, (By) ? xdir : 0, (Bx) ? ydir : 0, &B_scan);
184 if (successA || successB)
185 create_path(start, goal); // create path from available nodes
186 delete_nodes();
187 return (successA || successB);
188 }
189
delete_nodes()190 void SeekPath::delete_nodes() {
191 A_scan.clear();
192 B_scan.clear();
193 }
194
195 } // End of namespace Nuvie
196 } // End of namespace Ultima
197