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
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
|
/* 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 2
* 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, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
*
* $URL$
* $Id$
*
*/
/*
* This code is based on original Hugo Trilogy source code
*
* Copyright (c) 1989-1995 David P. Gray
*
*/
// Find shortest route from hero to destination
#include "common/system.h"
#include "hugo/hugo.h"
#include "hugo/game.h"
#include "hugo/route.h"
#include "hugo/global.h"
namespace Hugo {
Route::Route(HugoEngine &vm) : _vm(vm) {
}
// Face hero in new direction, based on cursor key input by user.
void Route::setDirection(uint16 keyCode) {
debugC(1, kDebugRoute, "setDirection(%d)", keyCode);
object_t *obj = _vm._hero; // Pointer to hero object
// Set first image in sequence
switch (keyCode) {
case Common::KEYCODE_UP:
obj->currImagePtr = obj->seqList[_UP].seqPtr;
break;
case Common::KEYCODE_DOWN:
obj->currImagePtr = obj->seqList[DOWN].seqPtr;
break;
case Common::KEYCODE_LEFT:
obj->currImagePtr = obj->seqList[LEFT].seqPtr;
break;
case Common::KEYCODE_RIGHT:
obj->currImagePtr = obj->seqList[RIGHT].seqPtr;
break;
case Common::KEYCODE_HOME:
obj->currImagePtr = obj->seqList[LEFT].seqPtr;
break;
case Common::KEYCODE_END:
obj->currImagePtr = obj->seqList[LEFT].seqPtr;
break;
// case Common::KEYCODE_PRIOR:
// obj->currImagePtr = obj->seqList[RIGHT].seqPtr;
// break;
// case Common::KEYCODE_NEXT:
// obj->currImagePtr = obj->seqList[RIGHT].seqPtr;
// break;
}
}
// Set hero walking, based on cursor key input by user.
// Hitting same key twice will stop hero.
void Route::setWalk(uint16 direction) {
debugC(1, kDebugRoute, "setWalk(%d)", direction);
static uint16 oldDirection = 0; // Last direction char
object_t *obj = _vm._hero; // Pointer to hero object
if (_vm.getGameStatus().storyModeFl || obj->pathType != USER) // Make sure user has control
return;
if (!obj->vx && !obj->vy)
oldDirection = 0; // Fix for consistant restarts
if (direction != oldDirection) {
// Direction has changed
setDirection(direction); // Face new direction
obj->vx = obj->vy = 0;
switch (direction) { // And set correct velocity
case Common::KEYCODE_UP:
obj->vy = -DY;
break;
case Common::KEYCODE_DOWN:
obj->vy = DY;
break;
case Common::KEYCODE_LEFT:
obj->vx = -DX;
break;
case Common::KEYCODE_RIGHT:
obj->vx = DX;
break;
case Common::KEYCODE_HOME:
obj->vx = -DX;
obj->vy = -DY / 2;
break;
case Common::KEYCODE_END:
obj->vx = -DX;
obj->vy = DY / 2;
break;
// case Common::KEYCODE_PRIOR:
// obj->vx = DX;
// obj->vy = -DY / 2;
// break;
// case Common::KEYCODE_NEXT:
// obj->vx = DX;
// obj->vy = DY / 2;
// break;
}
oldDirection = direction;
obj->cycling = CYCLE_FORWARD;
} else {
// Same key twice - halt hero
obj->vy = 0;
obj->vx = 0;
oldDirection = 0;
obj->cycling = NOT_CYCLING;
}
}
// Recursive algorithm! Searches from hero to dest_x, dest_y
// Find horizontal line segment about supplied point and recursively
// find line segments for each point above and below that segment.
// When destination point found in segment, start surfacing and leave
// a trail in segment[] from destination back to hero.
//
// Note: there is a bug which allows a route through a 1-pixel high
// narrow gap if between 2 segments wide enough for hero. To work
// around this, make sure any narrow gaps are 2 or more pixels high.
// An example of this was the blocking guard in Hugo1/Dead-End.
void Route::segment(int16 x, int16 y) {
debugC(1, kDebugRoute, "segment(%d, %d)", x, y);
// Note use of static - can't waste stack
static image_pt p; // Ptr to _boundaryMap[y]
static segment_t *seg_p; // Ptr to segment
// Bomb out if stack exhausted
// Vinterstum: Is this just a safeguard, or actually used?
//_fullStackFl = _stackavail () < 256;
_fullStackFl = false;
// Find and fill on either side of point
p = _boundaryMap[y];
int16 x1, x2; // Range of segment
for (x1 = x; x1 > 0; x1--) {
if (p[x1] == 0) {
p[x1] = kMapFill;
} else {
break;
}
}
for (x2 = x + 1; x2 < XPIX; x2++) {
if (p[x2] == 0) {
p[x2] = kMapFill;
} else {
break;
}
}
x1++;
x2--;
// Discard path if not wide enough for hero - dead end
if (_heroWidth > x2 - x1 + 1)
return;
// Have we found the destination yet?
if (y == _destY && x1 <= _destX && x2 >= _destX)
_routeFoundFl = true;
// Bounds check y in case no boundary around screen
if (y <= 0 || y >= YPIX - 1)
return;
if (_vm._hero->x < x1) {
// Hero x not in segment, search x1..x2
// Find all segments above current
for (x = x1; !(_routeFoundFl | _fullStackFl | _fullSegmentFl) && x <= x2; x++) {
if (_boundaryMap[y - 1][x] == 0)
segment(x, y - 1);
}
// Find all segments below current
for (x = x1; !(_routeFoundFl | _fullStackFl | _fullSegmentFl) && x <= x2; x++) {
if (_boundaryMap[y + 1][x] == 0)
segment(x, y + 1);
}
} else if (_vm._hero->x + HERO_MAX_WIDTH > x2) {
// Hero x not in segment, search x1..x2
// Find all segments above current
for (x = x2; !(_routeFoundFl | _fullStackFl | _fullSegmentFl) && x >= x1; x--) {
if (_boundaryMap[y - 1][x] == 0)
segment(x, y - 1);
}
// Find all segments below current
for (x = x2; !(_routeFoundFl | _fullStackFl | _fullSegmentFl) && x >= x1; x--) {
if (_boundaryMap[y + 1][x] == 0)
segment(x, y + 1);
}
} else {
// Organize search around hero x position - this gives
// better chance for more direct route.
for (x = _vm._hero->x; !(_routeFoundFl | _fullStackFl | _fullSegmentFl) && x <= x2; x++) {
if (_boundaryMap[y - 1][x] == 0)
segment(x, y - 1);
}
for (x = x1; !(_routeFoundFl | _fullStackFl | _fullSegmentFl) && x < _vm._hero->x; x++) {
if (_boundaryMap[y - 1][x] == 0)
segment(x, y - 1);
}
for (x = _vm._hero->x; !(_routeFoundFl | _fullStackFl | _fullSegmentFl) && x <= x2; x++) {
if (_boundaryMap[y + 1][x] == 0)
segment(x, y + 1);
}
for (x = x1; !(_routeFoundFl | _fullStackFl | _fullSegmentFl) && x < _vm._hero->x; x++) {
if (_boundaryMap[y + 1][x] == 0)
segment(x, y + 1);
}
}
// If found, surface, leaving trail back to hero
if (_routeFoundFl) {
// Bomb out if too many segments (leave one spare)
if (_segmentNumb >= kMaxSeg - 1) {
_fullSegmentFl = true;
} else {
// Create segment
seg_p = &_segment[_segmentNumb];
seg_p->y = y;
seg_p->x1 = x1;
seg_p->x2 = x2;
_segmentNumb++;
}
}
}
// Create and return ptr to new node. Initialize with previous node.
// Returns 0 if MAX_NODES exceeded
Point *Route::newNode() {
debugC(1, kDebugRoute, "newNode");
if (_routeListIndex >= kMaxNodes) // Too many nodes
return 0; // Incomplete route - failure
_routeListIndex++;
_route[_routeListIndex] = _route[_routeListIndex - 1]; // Initialize with previous node
return &_route[_routeListIndex];
}
// Construct route to cx, cy. Return TRUE if successful.
// 1. Copy boundary bitmap to local byte map (include object bases)
// 2. Construct list of segments segment[] from hero to destination
// 3. Compress to shortest route in route[]
bool Route::findRoute(int16 cx, int16 cy) {
debugC(1, kDebugRoute, "findRoute(%d, %d)", cx, cy);
// Initialize for search
_routeFoundFl = false; // Path not found yet
_fullStackFl = false; // Stack not exhausted
_fullSegmentFl = false; // Segments not exhausted
_segmentNumb = 0; // Segment index
_heroWidth = HERO_MIN_WIDTH; // Minimum width of hero
_destY = cy; // Destination coords
_destX = cx; // Destination coords
int16 herox1 = _vm._hero->x + _vm._hero->currImagePtr->x1; // Hero baseline
int16 herox2 = _vm._hero->x + _vm._hero->currImagePtr->x2; // Hero baseline
int16 heroy = _vm._hero->y + _vm._hero->currImagePtr->y2; // Hero baseline
// Store all object baselines into objbound (except hero's = [0])
object_t *obj; // Ptr to object
int i;
for (i = 1, obj = &_vm._objects[i]; i < _vm._numObj; i++, obj++) {
if ((obj->screenIndex == *_vm._screen_p) && (obj->cycling != INVISIBLE) && (obj->priority == FLOATING))
_vm.storeBoundary(obj->oldx + obj->currImagePtr->x1, obj->oldx + obj->currImagePtr->x2, obj->oldy + obj->currImagePtr->y2);
}
// Combine objbound and boundary bitmaps to local byte map
for (int16 y = 0; y < YPIX; y++) {
for (int16 x = 0; x < XBYTES; x++) {
for (i = 0; i < 8; i++)
_boundaryMap[y][x * 8 + i] = ((_vm.getObjectBoundaryOverlay()[y * XBYTES + x] | _vm.getBoundaryOverlay()[y * XBYTES + x]) & (0x80 >> i)) ? kMapBound : 0;
}
}
// Clear all object baselines from objbound
for (i = 0, obj = _vm._objects; i < _vm._numObj; i++, obj++) {
if ((obj->screenIndex == *_vm._screen_p) && (obj->cycling != INVISIBLE) && (obj->priority == FLOATING))
_vm.clearBoundary(obj->oldx + obj->currImagePtr->x1, obj->oldx + obj->currImagePtr->x2, obj->oldy + obj->currImagePtr->y2);
}
// Search from hero to destination
segment(herox1, heroy);
// Not found or not enough stack or MAX_SEG exceeded
if (!_routeFoundFl || _fullStackFl || _fullSegmentFl) {
return false;
}
// Now find the route of nodes from destination back to hero
// Assign first node as destination
_route[0].x = _destX;
_route[0].y = _destY;
// Make a final segment for hero's base (we left a spare)
_segment[_segmentNumb].y = heroy;
_segment[_segmentNumb].x1 = herox1;
_segment[_segmentNumb].x2 = herox2;
_segmentNumb++;
Point *routeNode; // Ptr to route node
// Look in segments[] for straight lines from destination to hero
for (i = 0, _routeListIndex = 0; i < _segmentNumb - 1; i++) {
if ((routeNode = newNode()) == 0) // New node for new segment
return false; // Too many nodes
routeNode->y = _segment[i].y;
// Look ahead for furthest straight line
for (int16 j = i + 1; j < _segmentNumb; j++) {
segment_t *seg_p = &_segment[j];
// Can we get to this segment from previous node?
if (seg_p->x1 <= routeNode->x && seg_p->x2 >= routeNode->x + _heroWidth - 1) {
routeNode->y = seg_p->y; // Yes, keep updating node
} else {
// No, create another node on previous segment to reach it
if ((routeNode = newNode()) == 0) // Add new route node
return false; // Too many nodes
// Find overlap between old and new segments
int16 x1 = MAX(_segment[j - 1].x1, seg_p->x1);
int16 x2 = MIN(_segment[j - 1].x2, seg_p->x2);
// If room, add a little offset to reduce staircase effect
int16 dx = HERO_MAX_WIDTH >> 1;
if (x2 - x1 < _heroWidth + dx)
dx = 0;
// Bear toward final hero position
if (j == _segmentNumb - 1)
routeNode->x = herox1;
else if (herox1 < x1)
routeNode->x = x1 + dx;
else if (herox1 > x2 - _heroWidth + 1)
routeNode->x = x2 - _heroWidth - dx;
else
routeNode->x = herox1;
i = j - 2; // Restart segment (-1 to offset auto increment)
break;
}
}
// Terminate loop if we've reached hero
if (routeNode->x == herox1 && routeNode->y == heroy)
break;
}
return true;
}
// Process hero in route mode - called from Move_objects()
void Route::processRoute() {
debugC(1, kDebugRoute, "processRoute");
static bool turnedFl = false; // Used to get extra cylce for turning
// Current hero position
int16 herox = _vm._hero->x + _vm._hero->currImagePtr->x1;
int16 heroy = _vm._hero->y + _vm._hero->currImagePtr->y2;
status_t &gameStatus = _vm.getGameStatus();
Point *routeNode = &_route[gameStatus.routeIndex];
// Arrived at node?
if (abs(herox - routeNode->x) < DX + 1 && abs(heroy - routeNode->y) < DY) {
// DX too low
// Close enough - position hero exactly
_vm._hero->x = _vm._hero->oldx = routeNode->x - _vm._hero->currImagePtr->x1;
_vm._hero->y = _vm._hero->oldy = routeNode->y - _vm._hero->currImagePtr->y2;
_vm._hero->vx = _vm._hero->vy = 0;
_vm._hero->cycling = NOT_CYCLING;
// Arrived at final node?
if (--gameStatus.routeIndex < 0) {
// See why we walked here
switch (gameStatus.go_for) {
case GO_EXIT: // Walked to an exit, proceed into it
setWalk(_vm._hotspots[gameStatus.go_id].direction);
break;
case GO_LOOK: // Look at an object
if (turnedFl) {
_vm.lookObject(&_vm._objects[gameStatus.go_id]);
turnedFl = false;
} else {
setDirection(_vm._objects[gameStatus.go_id].direction);
gameStatus.routeIndex++; // Come round again
turnedFl = true;
}
break;
case GO_GET: // Get (or use) an object
if (turnedFl) {
_vm.useObject(gameStatus.go_id);
turnedFl = false;
} else {
setDirection(_vm._objects[gameStatus.go_id].direction);
gameStatus.routeIndex++; // Come round again
turnedFl = true;
}
break;
case GO_SPACE:
warning("Unhandled gameStatus.go_for GO_STATUS");
break;
}
}
} else if (_vm._hero->vx == 0 && _vm._hero->vy == 0) {
// Set direction of travel if at a node
// Note realignment when changing to (thinner) up/down sprite,
// otherwise hero could bump into boundaries along route.
if (herox < routeNode->x) {
setWalk(Common::KEYCODE_RIGHT);
} else if (herox > routeNode->x) {
setWalk(Common::KEYCODE_LEFT);
} else if (heroy < routeNode->y) {
setWalk(Common::KEYCODE_DOWN);
_vm._hero->x = _vm._hero->oldx = routeNode->x - _vm._hero->currImagePtr->x1;
} else if (heroy > routeNode->y) {
setWalk(Common::KEYCODE_UP);
_vm._hero->x = _vm._hero->oldx = routeNode->x - _vm._hero->currImagePtr->x1;
}
}
}
// Start a new route from hero to cx, cy
// go_for is the purpose, id indexes the exit or object to walk to
// Returns FALSE if route not found
bool Route::startRoute(go_t go_for, int16 id, int16 cx, int16 cy) {
debugC(1, kDebugRoute, "startRoute(%d, %d, %d, %d)", go_for, id, cx, cy);
// Don't attempt to walk if user does not have control
if (_vm._hero->pathType != USER)
return false;
status_t &gameStatus = _vm.getGameStatus();
// if inventory showing, make it go away
if (gameStatus.inventoryState != I_OFF)
gameStatus.inventoryState = I_UP;
gameStatus.go_for = go_for; // Purpose of trip
gameStatus.go_id = id; // Index of exit/object
// Adjust destination to center hero if walking to cursor
if (gameStatus.go_for == GO_SPACE)
cx -= HERO_MIN_WIDTH / 2;
bool foundFl = false; // TRUE if route found ok
if ((foundFl = findRoute(cx, cy))) { // Found a route?
gameStatus.routeIndex = _routeListIndex; // Node index
_vm._hero->vx = _vm._hero->vy = 0; // Stop manual motion
}
return foundFl;
}
} // End of namespace Hugo
|