File: route_finder_impl.cpp

package info (click to toggle)
scummvm 2.7.0%2Bdfsg-1
  • links: PTS, VCS
  • area: main
  • in suites: bookworm
  • size: 363,784 kB
  • sloc: cpp: 3,622,060; asm: 27,410; python: 10,528; sh: 10,241; xml: 6,752; java: 5,579; perl: 2,570; yacc: 1,635; javascript: 1,016; lex: 539; makefile: 398; ansic: 378; awk: 275; objc: 82; sed: 11; php: 1
file content (256 lines) | stat: -rw-r--r-- 7,026 bytes parent folder | download
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