1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256
|
/* ScummVM - Graphic Adventure Engine
*
* ScummVM is the legal property of its developers, whose names
* are too numerous to list here. Please refer to the COPYRIGHT
* file distributed with this source distribution.
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*
*/
//=============================================================================
//
// New jump point search (JPS) A* pathfinder by Martin Sedlak.
//
//=============================================================================
#include "ags/engine/ac/route_finder_impl.h"
#include "ags/lib/std/math.h"
#include "ags/shared/ac/common.h" // quit()
#include "ags/engine/ac/move_list.h" // MoveList
#include "ags/shared/ac/common_defines.h"
#include "ags/shared/gfx/bitmap.h"
#include "ags/shared/debugging/out.h"
#include "ags/engine/ac/route_finder_jps.h"
#include "ags/globals.h"
namespace AGS3 {
using AGS::Shared::Bitmap;
namespace AGS {
namespace Engine {
namespace RouteFinder {
#define MAKE_INTCOORD(x,y) (((unsigned short)x << 16) | ((unsigned short)y))
static const int MAXNAVPOINTS = MAXNEEDSTAGES;
void init_pathfinder() {
}
void shutdown_pathfinder() {
}
void set_wallscreen(Bitmap *wallscreen_) {
_G(wallscreen) = wallscreen_;
}
static void sync_nav_wallscreen() {
// FIXME: this is dumb, but...
_GP(nav).Resize(_G(wallscreen)->GetWidth(), _G(wallscreen)->GetHeight());
for (int y = 0; y < _G(wallscreen)->GetHeight(); y++)
_GP(nav).SetMapRow(y, _G(wallscreen)->GetScanLine(y));
}
int can_see_from(int x1, int y1, int x2, int y2) {
_G(lastcx) = x1;
_G(lastcy) = y1;
if ((x1 == x2) && (y1 == y2))
return 1;
sync_nav_wallscreen();
return !_GP(nav).TraceLine(x1, y1, x2, y2, _G(lastcx), _G(lastcy));
}
void get_lastcpos(int &lastcx_, int &lastcy_) {
lastcx_ = _G(lastcx);
lastcy_ = _G(lastcy);
}
// new routing using JPS
static int find_route_jps(int fromx, int fromy, int destx, int desty) {
sync_nav_wallscreen();
std::vector<int> path, cpath;
path.clear();
cpath.clear();
if (_GP(nav).NavigateRefined(fromx, fromy, destx, desty, path, cpath) == Navigation::NAV_UNREACHABLE)
return 0;
_G(num_navpoints) = 0;
// new behavior: cut path if too complex rather than abort with error message
int count = MIN<int>((int)cpath.size(), MAXNAVPOINTS);
for (int i = 0; i < count; i++) {
int x, y;
_GP(nav).UnpackSquare(cpath[i], x, y);
_G(navpoints)[_G(num_navpoints)++] = MAKE_INTCOORD(x, y);
}
return 1;
}
void set_route_move_speed(int speed_x, int speed_y) {
// negative move speeds like -2 get converted to 1/2
if (speed_x < 0) {
_G(move_speed_x) = itofix(1) / (-speed_x);
} else {
_G(move_speed_x) = itofix(speed_x);
}
if (speed_y < 0) {
_G(move_speed_y) = itofix(1) / (-speed_y);
} else {
_G(move_speed_y) = itofix(speed_y);
}
}
// Calculates the X and Y per game loop, for this stage of the
// movelist
void calculate_move_stage(MoveList *mlsp, int aaa) {
// work out the x & y per move. First, opp/adj=tan, so work out the angle
if (mlsp->pos[aaa] == mlsp->pos[aaa + 1]) {
mlsp->xpermove[aaa] = 0;
mlsp->ypermove[aaa] = 0;
return;
}
short ourx = (mlsp->pos[aaa] >> 16) & 0x000ffff;
short oury = (mlsp->pos[aaa] & 0x000ffff);
short destx = ((mlsp->pos[aaa + 1] >> 16) & 0x000ffff);
short desty = (mlsp->pos[aaa + 1] & 0x000ffff);
// Special case for vertical and horizontal movements
if (ourx == destx) {
mlsp->xpermove[aaa] = 0;
mlsp->ypermove[aaa] = _G(move_speed_y);
if (desty < oury)
mlsp->ypermove[aaa] = -mlsp->ypermove[aaa];
return;
}
if (oury == desty) {
mlsp->xpermove[aaa] = _G(move_speed_x);
mlsp->ypermove[aaa] = 0;
if (destx < ourx)
mlsp->xpermove[aaa] = -mlsp->xpermove[aaa];
return;
}
fixed xdist = itofix(abs(ourx - destx));
fixed ydist = itofix(abs(oury - desty));
fixed useMoveSpeed;
if (_G(move_speed_x) == _G(move_speed_y)) {
useMoveSpeed = _G(move_speed_x);
} else {
// different X and Y move speeds
// the X proportion of the movement is (x / (x + y))
fixed xproportion = fixdiv(xdist, (xdist + ydist));
if (_G(move_speed_x) > _G(move_speed_y)) {
// speed = y + ((1 - xproportion) * (x - y))
useMoveSpeed = _G(move_speed_y) + fixmul(xproportion, _G(move_speed_x) - _G(move_speed_y));
} else {
// speed = x + (xproportion * (y - x))
useMoveSpeed = _G(move_speed_x) + fixmul(itofix(1) - xproportion, _G(move_speed_y) - _G(move_speed_x));
}
}
fixed angl = fixatan(fixdiv(ydist, xdist));
// now, since new opp=hyp*sin, work out the Y step size
//fixed newymove = useMoveSpeed * fsin(angl);
fixed newymove = fixmul(useMoveSpeed, fixsin(angl));
// since adj=hyp*cos, work out X step size
//fixed newxmove = useMoveSpeed * fcos(angl);
fixed newxmove = fixmul(useMoveSpeed, fixcos(angl));
if (destx < ourx)
newxmove = -newxmove;
if (desty < oury)
newymove = -newymove;
mlsp->xpermove[aaa] = newxmove;
mlsp->ypermove[aaa] = newymove;
}
int find_route(short srcx, short srcy, short xx, short yy, Bitmap *onscreen, int movlst, int nocross, int ignore_walls) {
int i;
_G(wallscreen) = onscreen;
_G(num_navpoints) = 0;
if (ignore_walls || can_see_from(srcx, srcy, xx, yy)) {
_G(num_navpoints) = 2;
_G(navpoints)[0] = MAKE_INTCOORD(srcx, srcy);
_G(navpoints)[1] = MAKE_INTCOORD(xx, yy);
} else {
if ((nocross == 0) && (_G(wallscreen)->GetPixel(xx, yy) == 0))
return 0; // clicked on a wall
find_route_jps(srcx, srcy, xx, yy);
}
if (!_G(num_navpoints))
return 0;
// FIXME: really necessary?
if (_G(num_navpoints) == 1)
_G(navpoints)[_G(num_navpoints)++] = _G(navpoints)[0];
assert(_G(num_navpoints) <= MAXNAVPOINTS);
#ifdef DEBUG_PATHFINDER
AGS::Shared::Debug::Printf("Route from %d,%d to %d,%d - %d stages", srcx, srcy, xx, yy, _G(num_navpoints));
#endif
int mlist = movlst;
_GP(mls)[mlist].numstage = _G(num_navpoints);
memcpy(&_GP(mls)[mlist].pos[0], &_G(navpoints)[0], sizeof(int) * _G(num_navpoints));
#ifdef DEBUG_PATHFINDER
AGS::Shared::Debug::Printf("stages: %d\n", _G(num_navpoints));
#endif
for (i = 0; i < _G(num_navpoints) - 1; i++)
calculate_move_stage(&_GP(mls)[mlist], i);
_GP(mls)[mlist].fromx = srcx;
_GP(mls)[mlist].fromy = srcy;
_GP(mls)[mlist].onstage = 0;
_GP(mls)[mlist].onpart = 0;
_GP(mls)[mlist].doneflag = 0;
_GP(mls)[mlist].lastx = -1;
_GP(mls)[mlist].lasty = -1;
return mlist;
}
} // namespace RouteFinder
} // namespace Engine
} // namespace AGS
} // namespace AGS3
|