1 /*
2 Copyright (C) 2007, 2010 - Bit-Blot
3
4 This file is part of Aquaria.
5
6 Aquaria is free software; you can redistribute it and/or
7 modify it under the terms of the GNU General Public License
8 as published by the Free Software Foundation; either version 2
9 of the License, or (at your option) any later version.
10
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
14
15 See the 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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
20 */
21
22 #include <JPS.h>
23 #include "PathFinding.h"
24 #include "DSQ.h"
25 #include "Game.h"
26
27
28 class SearchGridRaw
29 {
30 public:
SearchGridRaw(ObsType blocking)31 SearchGridRaw(ObsType blocking) : game(dsq->game), blockingObsBits(blocking) {}
operator ()(unsigned x,unsigned y) const32 inline bool operator()(unsigned x, unsigned y) const
33 {
34 return (game->getGridRaw(TileVector(x, y)) & blockingObsBits) == OT_EMPTY;
35 }
36
37 ObsType blockingObsBits;
38 const Game *game;
39 };
40
41 class PathFinding::State : public ScriptObject
42 {
43 public:
State(ObsType obs)44 State(ObsType obs) : grid(obs), searcher(grid), result(JPS::NO_PATH) {}
45 SearchGridRaw grid;
46 JPS::Searcher<SearchGridRaw> searcher;
47 JPS::Result result;
48 };
49
generateVectorPath(const JPS::PathVector & rawpath,VectorPath & vp,int offx,int offy)50 static void generateVectorPath(const JPS::PathVector& rawpath, VectorPath& vp, int offx, int offy)
51 {
52 for(JPS::PathVector::const_iterator it = rawpath.begin(); it != rawpath.end(); ++it)
53 vp.addPathNode(Vector((it->x*TILE_SIZE)+TILE_SIZE/2+offx, (it->y*TILE_SIZE)+TILE_SIZE/2)+offy, 0);
54 }
55
56
forceMinimumPath(VectorPath & path,const Vector & start,const Vector & dest)57 void PathFinding::forceMinimumPath(VectorPath &path, const Vector &start, const Vector &dest)
58 {
59 if (path.getNumPathNodes() <= 2)
60 {
61 //debugLog(" Path is <= 2 nodes... setting up simple path");
62 path.clear();
63 path.addPathNode(start, 0);
64 path.addPathNode(dest, 1);
65 }
66 }
67
molestPath(VectorPath & path)68 void PathFinding::molestPath(VectorPath &path)
69 {
70 int sz=path.getNumPathNodes();
71 if(!sz)
72 return;
73
74 int i = 0;
75 // make normals
76 std::vector<Vector> normals;
77 normals.resize(sz);
78 for (i = 0; i < sz; i++)
79 {
80 Vector node = path.getPathNode(i)->value;
81 float dist;
82 int sample = 20;
83 float maxDist = sample * TILE_SIZE;
84 {
85 Vector n = dsq->game->getWallNormal(node, sample, &dist);
86 if (dist != -1 && (n.x != 0 || n.y != 0))
87 {
88 n.setLength2D(200);
89 TileVector test(node + n);
90 if (dsq->game->isObstructed(test))
91 {
92 n.setLength2D(100);
93 test = TileVector(node+n);
94 if (dsq->game->isObstructed(test))
95 {
96 n.setLength2D(50);
97 test = TileVector(node+n);
98 if (dsq->game->isObstructed(test))
99 {
100 n = Vector(0,0,0);
101 }
102 }
103 }
104 normals[i] = n;
105 }
106 }
107 }
108
109 // use wall normal to push out node a bit
110 std::vector<Vector> newNormals;
111 newNormals.resize(normals.size());
112 for (i = 1; i < normals.size()-1; i++)
113 newNormals[i] = (normals[i] + normals[i-1] + normals[i+1])/3.0f;
114 for (i = 1; i < sz-1; i++)
115 path.getPathNode(i)->value += newNormals[i];
116
117 // kill bowls
118 int start = 0;
119 int runs=0;
120 bool hadSuccess = false;
121 int lastSuccessNode = 0;
122 int adjust = 2;
123 sz=path.getNumPathNodes();
124
125 for (i = start; i < sz-1; i++)
126 {
127 runs++;
128 if (runs > 8000)
129 {
130 debugLog("kill bowls ran too much");
131 start = sz*100;
132 }
133 lastSuccessNode = 0;
134 hadSuccess = false;
135 Vector node = path.getPathNode(i)->value;
136 for (int j = sz-1; j >= i+adjust; j--)
137 {
138 Vector target = path.getPathNode(j)->value;
139 if (dsq->game->trace(node, target))
140 {
141 hadSuccess = true;
142 lastSuccessNode = j;
143 break;
144 }
145 }
146 if (hadSuccess)
147 {
148 // this code will only delete things that are bowl-ish
149 // (things that take you on detours)
150 ++i;
151 path.removeNodes(i, lastSuccessNode-1);
152 hadSuccess = false;
153 }
154 sz = path.getNumPathNodes();
155 }
156 sz=path.getNumPathNodes();
157
158 // remove last node
159 //path.removeNodes(path.getNumPathNodes()-2, path.getNumPathNodes()-2);
160
161 path.realPercentageCalc();
162 }
163
generatePath(RenderObject * ro,TileVector start,TileVector goal,int offx,int offy)164 void PathFinding::generatePath(RenderObject *ro, TileVector start, TileVector goal, int offx, int offy)
165 {
166 ro->position.ensureData();
167 VectorPath& vp = ro->position.data->path;
168 vp.clear();
169
170 SearchGridRaw grid(OT_BLOCKING);
171 JPS::PathVector path;
172 if(JPS::findPath(path, grid, start.x, start.y, goal.x, goal.y, 1))
173 {
174 vp.addPathNode(ro->position, 0);
175 generateVectorPath(path, vp, offx, offy);
176 }
177 }
178
generatePathSimple(VectorPath & path,const Vector & start,const Vector & end,unsigned int step,unsigned int obs)179 bool PathFinding::generatePathSimple(VectorPath& path, const Vector& start, const Vector& end, unsigned int step /* = 0 */, unsigned int obs /* = 0 */)
180 {
181 if(obs == OT_EMPTY)
182 obs = OT_BLOCKING;
183
184 SearchGridRaw grid((ObsType)obs);
185 JPS::PathVector p;
186 TileVector tstart(start);
187 TileVector tend(end);
188 if(!JPS::findPath(p, grid, tstart.x, tstart.y, tend.x, tend.y, step))
189 return false;
190
191 generateVectorPath(p, path, 0, 0);
192 molestPath(path);
193 return true;
194 }
195
initFindPath()196 PathFinding::State *PathFinding::initFindPath()
197 {
198 State *state = new PathFinding::State(OT_BLOCKING);
199 return state;
200 }
201
deleteFindPath(State * state)202 void PathFinding::deleteFindPath(State *state)
203 {
204 delete state;
205 }
206
beginFindPath(PathFinding::State * state,const Vector & start,const Vector & end,unsigned int obs)207 void PathFinding::beginFindPath(PathFinding::State *state, const Vector& start, const Vector& end, unsigned int obs /* = 0 */)
208 {
209 if(obs == OT_EMPTY)
210 obs = OT_BLOCKING;
211
212 state->grid.blockingObsBits = (ObsType)obs;
213 JPS::Position istart = JPS::Pos(start.x, start.y);
214 JPS::Position iend = JPS::Pos(end.x, end.y);
215 state->result = state->searcher.findPathInit(istart, iend);
216 }
217
updateFindPath(PathFinding::State * state,int limit)218 bool PathFinding::updateFindPath(PathFinding::State *state, int limit)
219 {
220 int oldres = state->result;
221 if(oldres == JPS::NEED_MORE_STEPS)
222 {
223 state->result = state->searcher.findPathStep(limit);
224 return oldres != state->result;
225 }
226 return true; // done
227 }
228
finishFindPath(PathFinding::State * state,VectorPath & path,unsigned step)229 bool PathFinding::finishFindPath(PathFinding::State *state, VectorPath& path, unsigned step /* = 0 */)
230 {
231 if(state->result != JPS::FOUND_PATH)
232 return false;
233
234 JPS::PathVector rawpath;
235 state->searcher.findPathFinish(rawpath, step);
236 generateVectorPath(rawpath, path, 0, 0);
237 molestPath(path);
238 return true;
239 }
240
getStats(PathFinding::State * state,unsigned & stepsDone,unsigned & nodesExpanded)241 void PathFinding::getStats(PathFinding::State *state, unsigned& stepsDone, unsigned& nodesExpanded)
242 {
243 stepsDone = (unsigned)state->searcher.getStepsDone();
244 nodesExpanded = (unsigned)state->searcher.getNodesExpanded();
245 }
246
247