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 "ags/lib/std/queue.h"
24 #include "ags/lib/std/vector.h"
25 #include "ags/lib/std/algorithm.h"
26 #include "ags/lib/std/functional.h"
27 #include "ags/lib/std/xutility.h"
28
29 // Not all platforms define INFINITY
30 #ifndef INFINITY
31 #define INFINITY ((float)(1e+300 * 1e+300)) // This must overflow
32 #endif
33
34 namespace AGS3 {
35
36 // TODO: this could be cleaned up/simplified ...
37
38 // further optimizations possible:
39 // - forward refinement should use binary search
40
41 class Navigation {
42 public:
43 Navigation();
44
45 void Resize(int width, int height);
46
47 enum NavResult {
48 // unreachable
49 NAV_UNREACHABLE,
50 // straight line exists
51 NAV_STRAIGHT,
52 // path used
53 NAV_PATH
54 };
55
56 // ncpath = navpoint-compressed path
57 // opath = path composed of individual grid elements
58 NavResult NavigateRefined(int sx, int sy, int ex, int ey, std::vector<int> &opath,
59 std::vector<int> &ncpath);
60
61 NavResult Navigate(int sx, int sy, int ex, int ey, std::vector<int> &opath);
62
63 bool TraceLine(int srcx, int srcy, int targx, int targy, int &lastValidX, int &lastValidY) const;
64 bool TraceLine(int srcx, int srcy, int targx, int targy, std::vector<int> *rpath = nullptr) const;
65
SetMapRow(int y,const unsigned char * row)66 inline void SetMapRow(int y, const unsigned char *row) {
67 map[y] = row;
68 }
69
70 static int PackSquare(int x, int y);
71 static void UnpackSquare(int sq, int &x, int &y);
72
73 private:
74 // priority queue entry
75 struct Entry {
76 float cost;
77 int index;
78
EntryEntry79 inline Entry() {}
80
EntryEntry81 inline Entry(float ncost, int nindex)
82 : cost(ncost)
83 , index(nindex) {
84 }
85
86 inline bool operator <(const Entry &b) const {
87 return cost < b.cost;
88 }
89
90 inline bool operator >(const Entry &b) const {
91 return cost > b.cost;
92 }
93 };
94
95 int mapWidth;
96 int mapHeight;
97 std::vector<const unsigned char *> map;
98
99 typedef unsigned short tFrameId;
100 typedef int tPrev;
101
102 struct NodeInfo {
103 // quantized min distance from origin
104 unsigned short dist;
105 // frame id (counter to detect new search)
106 tFrameId frameId;
107 // previous node index (packed, relative to current node)
108 tPrev prev;
109
NodeInfoNodeInfo110 inline NodeInfo()
111 : dist(0)
112 , frameId(0)
113 , prev(-1) {
114 }
115 };
116
117 static const float DIST_SCALE_PACK;
118 static const float DIST_SCALE_UNPACK;
119
120 std::vector<NodeInfo> mapNodes;
121 tFrameId frameId;
122
123 std::priority_queue<Entry, std::vector<Entry>, Common::Greater<Entry> > pq;
124
125 // temporary buffers:
126 mutable std::vector<int> fpath;
127 std::vector<int> ncpathIndex;
128 std::vector<int> rayPath, orayPath;
129
130 // temps for routing towards unreachable areas
131 int cnode;
132 int closest;
133
134 // orthogonal only (this should correspond to what AGS is doing)
135 bool nodiag;
136
137 bool navLock;
138
139 void IncFrameId();
140
141 // outside map test
142 inline bool Outside(int x, int y) const;
143 // stronger inside test
144 bool Passable(int x, int y) const;
145 // plain access, unchecked
146 inline bool Walkable(int x, int y) const;
147
148 void AddPruned(int *buf, int &bcount, int x, int y) const;
149 bool HasForcedNeighbor(int x, int y, int dx, int dy) const;
150 int FindJump(int x, int y, int dx, int dy, int ex, int ey);
151 int FindOrthoJump(int x, int y, int dx, int dy, int ex, int ey);
152
153 // neighbor reachable (nodiag only)
154 bool Reachable(int x0, int y0, int x1, int y1) const;
155
sign(int n)156 static inline int sign(int n) {
157 return n < 0 ? -1 : (n > 0 ? 1 : 0);
158 }
159
iabs(int n)160 static inline int iabs(int n) {
161 return n < 0 ? -n : n;
162 }
163
iclamp(int v,int min,int max)164 static inline int iclamp(int v, int min, int max) {
165 return v < min ? min : (v > max ? max : v);
166 }
167
ClosestDist(int dx,int dy)168 static inline int ClosestDist(int dx, int dy) {
169 return dx * dx + dy * dy;
170 // Manhattan?
171 //return iabs(dx) + iabs(dy);
172 }
173 };
174
PackSquare(int x,int y)175 inline int Navigation::PackSquare(int x, int y) {
176 return (y << 16) + x;
177 }
178
UnpackSquare(int sq,int & x,int & y)179 inline void Navigation::UnpackSquare(int sq, int &x, int &y) {
180 y = sq >> 16;
181 x = sq & ((1 << 16) - 1);
182 }
183
Outside(int x,int y)184 inline bool Navigation::Outside(int x, int y) const {
185 return
186 (unsigned)x >= (unsigned)mapWidth ||
187 (unsigned)y >= (unsigned)mapHeight;
188 }
189
Walkable(int x,int y)190 inline bool Navigation::Walkable(int x, int y) const {
191 // invert condition because of AGS
192 return map[y][x] != 0;
193 }
194
195 } // namespace AGS3
196