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
24 #include "common/endian.h"
25 #include "common/textconsole.h"
26 #include "common/util.h"
27
28 #include "sky/autoroute.h"
29 #include "sky/compact.h"
30 #include "sky/grid.h"
31 #include "sky/skydefs.h"
32 #include "sky/struc.h"
33
34 namespace Sky {
35
36 #define ROUTE_GRID_WIDTH ((GAME_SCREEN_WIDTH/8)+2)
37 #define ROUTE_GRID_HEIGHT ((GAME_SCREEN_HEIGHT/8)+2)
38 #define ROUTE_GRID_SIZE (ROUTE_GRID_WIDTH*ROUTE_GRID_HEIGHT*2)
39 #define WALK_JUMP 8 // walk in blocks of 8
40
41 const int16 AutoRoute::_routeDirections[4] = { -1, 1, -ROUTE_GRID_WIDTH, ROUTE_GRID_WIDTH };
42 const uint16 AutoRoute::_logicCommands[4] = { RIGHTY, LEFTY, DOWNY, UPY };
43
AutoRoute(Grid * pGrid,SkyCompact * compact)44 AutoRoute::AutoRoute(Grid *pGrid, SkyCompact *compact) {
45 _grid = pGrid;
46 _skyCompact = compact;
47 _routeGrid = (uint16 *)malloc(ROUTE_GRID_SIZE);
48 _routeBuf = (uint16 *)malloc(ROUTE_SPACE);
49 }
50
~AutoRoute()51 AutoRoute::~AutoRoute() {
52 free(_routeGrid);
53 free(_routeBuf);
54 }
55
checkBlock(uint16 * blockPos)56 uint16 AutoRoute::checkBlock(uint16 *blockPos) {
57 uint16 retVal = 0xFFFF;
58
59 for (uint8 cnt = 0; cnt < 4; cnt++) {
60 uint16 fieldVal = *(blockPos + _routeDirections[cnt]);
61 if (fieldVal && (fieldVal < retVal))
62 retVal = fieldVal;
63 }
64 return retVal;
65 }
66
clipCoordX(uint16 x,uint8 & blkX,int16 & initX)67 void AutoRoute::clipCoordX(uint16 x, uint8 &blkX, int16 &initX) {
68 if (x < TOP_LEFT_X) {
69 blkX = 0;
70 initX = x - TOP_LEFT_X;
71 } else if (x >= TOP_LEFT_X + GAME_SCREEN_WIDTH) {
72 blkX = (GAME_SCREEN_WIDTH - 1) >> 3;
73 initX = x - (TOP_LEFT_X + GAME_SCREEN_WIDTH - 1);
74 } else {
75 blkX = (x - TOP_LEFT_X) >> 3;
76 initX = 0;
77 }
78 }
79
clipCoordY(uint16 y,uint8 & blkY,int16 & initY)80 void AutoRoute::clipCoordY(uint16 y, uint8 &blkY, int16 &initY) {
81 if (y < TOP_LEFT_Y) {
82 blkY = 0;
83 initY = y - TOP_LEFT_Y;
84 } else if (y >= TOP_LEFT_Y + GAME_SCREEN_HEIGHT) {
85 blkY = (GAME_SCREEN_HEIGHT - 1) >> 3;
86 initY = y - (TOP_LEFT_Y + GAME_SCREEN_HEIGHT);
87 } else {
88 blkY = (y - TOP_LEFT_Y) >> 3;
89 initY = 0;
90 }
91 }
92
initWalkGrid(uint8 screen,uint8 width)93 void AutoRoute::initWalkGrid(uint8 screen, uint8 width) {
94 uint16 *wGridPos;
95 uint8 stretch = 0;
96 uint8 *screenGrid = _grid->giveGrid(screen);
97 screenGrid += GRID_SIZE;
98 wGridPos = _routeGrid + (ROUTE_GRID_SIZE >> 1) - ROUTE_GRID_WIDTH - 2;
99
100 memset(_routeGrid, 0, ROUTE_GRID_SIZE);
101 uint8 bitsLeft = 0; uint32 gridData = 0;
102 for (uint8 gridCntY = 0; gridCntY < ROUTE_GRID_HEIGHT - 2; gridCntY++) {
103 for (uint8 gridCntX = 0; gridCntX < ROUTE_GRID_WIDTH - 2; gridCntX++) {
104 if (!bitsLeft) {
105 screenGrid -= 4;
106 gridData = READ_LE_UINT32(screenGrid);
107 bitsLeft = 32;
108 }
109 if (gridData & 1) {
110 *wGridPos = 0xFFFF; // block is not accessible
111 stretch = width;
112 } else if (stretch) {
113 *wGridPos = 0xFFFF;
114 stretch--;
115 }
116 wGridPos--;
117 bitsLeft--;
118 gridData >>= 1;
119 }
120 wGridPos -= 2;
121 stretch = 0;
122 }
123 }
124
calcWalkGrid(uint8 startX,uint8 startY,uint8 destX,uint8 destY)125 bool AutoRoute::calcWalkGrid(uint8 startX, uint8 startY, uint8 destX, uint8 destY) {
126 int16 directionX, directionY;
127 uint8 roiX, roiY; // Rectangle Of Interest in the walk grid
128 if (startY > destY) {
129 directionY = -ROUTE_GRID_WIDTH;
130 roiY = startY;
131 } else {
132 directionY = ROUTE_GRID_WIDTH;
133 roiY = (ROUTE_GRID_HEIGHT-1) - startY;
134 }
135 if (startX > destX) {
136 directionX = -1;
137 roiX = startX + 2;
138 } else {
139 directionX = 1;
140 roiX = (ROUTE_GRID_WIDTH - 1) - startX;
141 }
142
143 uint16 *walkDest = _routeGrid + (destY + 1) * ROUTE_GRID_WIDTH + destX + 1;
144 uint16 *walkStart = _routeGrid + (startY + 1) * ROUTE_GRID_WIDTH + startX + 1;
145 *walkStart = 1;
146
147 // if we are on the edge, move diagonally from start
148 if (roiY < ROUTE_GRID_HEIGHT-3)
149 walkStart -= directionY;
150
151 if (roiX < ROUTE_GRID_WIDTH-2)
152 walkStart -= directionX;
153
154 bool gridChanged = true;
155 bool foundRoute = false;
156
157 while ((!foundRoute) && gridChanged) {
158 gridChanged = false;
159 uint16 *yWalkCalc = walkStart;
160 for (uint8 cnty = 0; cnty < roiY; cnty++) {
161 uint16 *xWalkCalc = yWalkCalc;
162 for (uint8 cntx = 0; cntx < roiX; cntx++) {
163 if (!*xWalkCalc) { // block wasn't done, yet
164 uint16 blockRet = checkBlock(xWalkCalc);
165 if (blockRet < 0xFFFF) {
166 *xWalkCalc = blockRet + 1;
167 gridChanged = true;
168 }
169 }
170 xWalkCalc += directionX;
171 }
172 yWalkCalc += directionY;
173 }
174 if (*walkDest) { // okay, finished
175 foundRoute = true;
176 } else { // we couldn't find the route, let's extend the ROI
177 if (roiY < ROUTE_GRID_HEIGHT - 4) {
178 walkStart -= directionY;
179 roiY++;
180 }
181 if (roiX < ROUTE_GRID_WIDTH - 4) {
182 walkStart -= directionX;
183 roiX++;
184 }
185 }
186 }
187 return foundRoute;
188 }
189
makeRouteData(uint8 startX,uint8 startY,uint8 destX,uint8 destY)190 uint16 *AutoRoute::makeRouteData(uint8 startX, uint8 startY, uint8 destX, uint8 destY) {
191 memset(_routeBuf, 0, ROUTE_SPACE);
192
193 uint16 *routePos = _routeGrid + (destY + 1) * ROUTE_GRID_WIDTH + destX + 1;
194 uint16 *dataTrg = _routeBuf + (ROUTE_SPACE >> 1) - 2;
195
196 uint16 lastVal = (*routePos) - 1;
197 while (lastVal) { // lastVal == 0 means route is done.
198 dataTrg -= 2;
199
200 int16 walkDirection = 0;
201 for (uint8 cnt = 0; cnt < 4; cnt++)
202 if (lastVal == *(routePos + _routeDirections[cnt])) {
203 *(dataTrg + 1) = _logicCommands[cnt];
204 walkDirection = _routeDirections[cnt];
205 break;
206 }
207
208 if (!walkDirection)
209 error("makeRouteData:: can't find way through walkGrid (pos %d)", lastVal);
210 while (lastVal && (lastVal == *(routePos + walkDirection))) {
211 *dataTrg += WALK_JUMP;
212 lastVal--;
213 routePos += walkDirection;
214 }
215 }
216 return dataTrg;
217 }
218
checkInitMove(uint16 * data,int16 initStaX)219 uint16 *AutoRoute::checkInitMove(uint16 *data, int16 initStaX) {
220 if (initStaX < 0) {
221 data -= 2;
222 *(data + 1) = RIGHTY;
223 *data = ((-initStaX) + 7) & 0xFFF8;
224 } else if (initStaX > 0) {
225 data -= 2;
226 *(data + 1) = LEFTY;
227 *data = (initStaX + 7) & 0xFFF8;
228 }
229 return data;
230 }
231
autoRoute(Compact * cpt)232 uint16 AutoRoute::autoRoute(Compact *cpt) {
233 uint8 cptScreen = (uint8)cpt->screen;
234 uint8 cptWidth = (uint8)SkyCompact::getMegaSet(cpt)->gridWidth;
235 initWalkGrid(cptScreen, cptWidth);
236
237 uint8 startX, startY, destX, destY;
238 int16 initStaX, initStaY, initDestX, initDestY;
239
240 clipCoordX(cpt->xcood, startX, initStaX);
241 clipCoordY(cpt->ycood, startY, initStaY);
242 clipCoordX(cpt->arTargetX, destX, initDestX);
243 clipCoordY(cpt->arTargetY, destY, initDestY);
244
245 uint16 *routeDest = (uint16 *)_skyCompact->fetchCpt(cpt->animScratchId);
246 memset(routeDest, 0, 64);
247 if ((startX == destX) && (startY == destY))
248 return 2;
249
250 if (_routeGrid[(destY + 1) * ROUTE_GRID_WIDTH + destX + 1]) {
251 //if ((cpt == &Sky::SkyCompact::foster) && (cptScreen == 12) && (destX == 2) && (destY == 14)) {
252 if (_skyCompact->cptIsId(cpt, CPT_FOSTER) && (cptScreen == 12) && (destX == 2) && (destY == 14)) {
253 /* workaround for Scriptbug #1043047
254 In screen 12 (the pipe factory) Joey can block Foster's target
255 coordinates (2/14). This is normally not too tragic, but in the
256 scene when foster gets thrown out by Lamb (first time you enter
257 the pipe factory), the game would enter an infinite loop. */
258 _routeGrid[(destY + 1) * ROUTE_GRID_WIDTH + destX + 1] = 0;
259 // hide this part joey from the grid
260 } else
261 return 1; // AR destination is an unaccessible block
262 }
263
264 if (!calcWalkGrid(startX, startY, destX, destY))
265 return 1; // can't find route to block
266
267 uint16 *routeData = makeRouteData(startX, startY, destX, destY);
268 // the route is done.
269 // if there was an initial x movement (due to clipping) tag it onto the start
270 routeData = checkInitMove(routeData, initStaX);
271
272 uint8 cnt = 0;
273 do {
274 routeDest[cnt] = routeData[cnt];
275 routeDest[cnt + 1] = routeData[cnt + 1];
276 cnt += 2;
277 } while (routeData[cnt - 2]);
278 return 0;
279 }
280
281 } // End of namespace Sky
282