/* ScummVM - Scumm Interpreter
 * Copyright (C) 2003 The ScummVM project
 *
 * 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., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 *
 * $Header: /cvsroot/scummvm/scummvm/sky/autoroute.cpp,v 1.18 2003/08/20 12:12:11 lavosspawn Exp $
 *
 */

#include "autoroute.h"

#define ROUTE_GRID_WIDTH ((GAME_SCREEN_WIDTH/8)+2)
#define ROUTE_GRID_HEIGHT ((GAME_SCREEN_HEIGHT/8)+2)
#define ROUTE_GRID_SIZE (ROUTE_GRID_WIDTH*ROUTE_GRID_HEIGHT*2)
#define WALK_JUMP 8      // walk in blocks of 8

const int16 SkyAutoRoute::_routeDirections[4] = {    -1,     1, -ROUTE_GRID_WIDTH, ROUTE_GRID_WIDTH };
const uint16 SkyAutoRoute::_logicCommands[4] = { RIGHTY, LEFTY,             DOWNY,              UPY };

SkyAutoRoute::SkyAutoRoute(SkyGrid *pGrid) {

	_grid = pGrid;
	_routeGrid = (uint16 *)malloc(ROUTE_GRID_SIZE);
	_routeBuf = (uint16 *)malloc(ROUTE_SPACE);
}

SkyAutoRoute::~SkyAutoRoute(void) {

	free(_routeGrid);
	free(_routeBuf);
}

uint16 SkyAutoRoute::checkBlock(uint16 *blockPos) {

	uint16 retVal = 0xFFFF;

	for (uint8 cnt = 0; cnt < 4; cnt++) {
		uint16 fieldVal = *(blockPos + _routeDirections[cnt]);
		if (fieldVal && (fieldVal < retVal))
			retVal = fieldVal;
	}
	return retVal;
}

void SkyAutoRoute::clipCoordX(uint16 x, uint8 &blkX, int16 &initX) {
	if (x < TOP_LEFT_X) {
		blkX = 0;
		initX = x - TOP_LEFT_X;
	} else if (x >= TOP_LEFT_X + GAME_SCREEN_WIDTH) {
		blkX = (GAME_SCREEN_WIDTH - 1) >> 3;
		initX = x - (TOP_LEFT_X + GAME_SCREEN_WIDTH);
	} else {
		blkX = (x - TOP_LEFT_X) >> 3;
		initX = 0;
	}
}

void SkyAutoRoute::clipCoordY(uint16 y, uint8 &blkY, int16 &initY) {
	if (y < TOP_LEFT_Y) {
		blkY = 0;
		initY = y - TOP_LEFT_Y;
	} else if (y >= TOP_LEFT_Y + GAME_SCREEN_HEIGHT) {
		blkY = (GAME_SCREEN_HEIGHT - 1) >> 3;
		initY = y - (TOP_LEFT_Y + GAME_SCREEN_WIDTH);
	} else {
		blkY = (y - TOP_LEFT_Y) >> 3;
		initY = 0;
	}
}

void SkyAutoRoute::initWalkGrid(uint8 screen, uint8 width) {

	uint16 *wGridPos;
	uint8 stretch = 0;
	uint8 *screenGrid = _grid->giveGrid(screen);
	screenGrid += GRID_SIZE;
	wGridPos = _routeGrid + (ROUTE_GRID_SIZE >> 1) - ROUTE_GRID_WIDTH - 2;

    memset(_routeGrid, 0, ROUTE_GRID_SIZE);
	uint8 bitsLeft = 0; uint32 gridData = 0;
	for (uint8 gridCntY = 0; gridCntY < ROUTE_GRID_HEIGHT - 2; gridCntY++) {
		for (uint8 gridCntX = 0; gridCntX < ROUTE_GRID_WIDTH - 2; gridCntX++) {
			if (!bitsLeft) {
				screenGrid -= 4;
				gridData = READ_LE_UINT32(screenGrid);
				bitsLeft = 32;
			}
			if (gridData & 1) {
				*wGridPos = 0xFFFF; // block is not accessible
				stretch = width;
			} else if (stretch) {
				*wGridPos = 0xFFFF;
				stretch--;
			}
			wGridPos--;
			bitsLeft--;
			gridData >>= 1;
		}
		wGridPos -= 2;
		stretch = 0;
	}
}

bool SkyAutoRoute::calcWalkGrid(uint8 startX, uint8 startY, uint8 destX, uint8 destY) {

	int16 directionX, directionY;
	uint8 roiX, roiY; // Rectangle Of Interest in the walk grid
	if (startY > destY) {
		directionY = -ROUTE_GRID_WIDTH;
		roiY = startY;
	} else {
		directionY = ROUTE_GRID_WIDTH;
		roiY = (ROUTE_GRID_HEIGHT-1) - startY;
	}
	if (startX > destX) {
		directionX = -1;
		roiX = startX + 2;
	} else {
		directionX = 1;
		roiX = (ROUTE_GRID_WIDTH - 1) - startX;
	}

	uint16 *walkDest  = _routeGrid + (destY + 1) * ROUTE_GRID_WIDTH + destX + 1;
	uint16 *walkStart = _routeGrid + (startY + 1) * ROUTE_GRID_WIDTH + startX + 1;
	*walkStart = 1;

	// if we are on the edge, move diagonally from start
	if (roiY < ROUTE_GRID_HEIGHT-3)
		walkStart -= directionY;

	if (roiX < ROUTE_GRID_WIDTH-2)
		walkStart -= directionX;
    
	bool gridChanged = true;
	bool foundRoute = false;

	while ((!foundRoute) && gridChanged) {
		gridChanged = false;
		uint16 *yWalkCalc = walkStart;
		for (uint8 cnty = 0; cnty < roiY; cnty++) {
			uint16 *xWalkCalc = yWalkCalc;
			for (uint8 cntx = 0; cntx < roiX; cntx++) {
				if (!*xWalkCalc) { // block wasn't done, yet
					uint16 blockRet = checkBlock(xWalkCalc);
					if (blockRet < 0xFFFF) {
						*xWalkCalc = blockRet + 1;
						gridChanged = true;
					}
				}
                xWalkCalc += directionX;
			}
			yWalkCalc += directionY;
		}
		if (*walkDest) { // okay, finished
			foundRoute = true;
		} else { // we couldn't find the route, let's extend the ROI
			if (roiY < ROUTE_GRID_HEIGHT - 4) {
				walkStart -= directionY;
				roiY++;
			}
			if (roiX < ROUTE_GRID_WIDTH - 4) {
				walkStart -= directionX;
				roiX++;
			}
		}
	}
	return foundRoute;
}

uint16 *SkyAutoRoute::makeRouteData(uint8 startX, uint8 startY, uint8 destX, uint8 destY) {

	memset(_routeBuf, 0, ROUTE_SPACE);

	uint16 *routePos = _routeGrid + (destY + 1) * ROUTE_GRID_WIDTH + destX + 1;
	uint16 *dataTrg = _routeBuf + (ROUTE_SPACE >> 1) - 2;

	uint16 lastVal = (*routePos) - 1;
	while (lastVal) { // lastVal == 0 means route is done.
		dataTrg -= 2;
		
		int16 walkDirection = 0;
		for (uint8 cnt = 0; cnt < 4; cnt++)
			if (lastVal == *(routePos + _routeDirections[cnt])) {
				*(dataTrg + 1) = _logicCommands[cnt];
				walkDirection = _routeDirections[cnt];
				break;
			}

		if (!walkDirection)
			error("makeRouteData:: can't find way through walkGrid (pos %d)", lastVal);
		while (lastVal && (lastVal == *(routePos + walkDirection))) {
            *dataTrg += WALK_JUMP;
			lastVal--;
			routePos += walkDirection;
		}
	}
    return dataTrg;
}

uint16 *SkyAutoRoute::checkInitMove(uint16 *data, int16 initStaX) {
	if (initStaX < 0) {
		data -= 2;
		*(data + 1) = RIGHTY;
		*data = ((-initStaX) + 7) & 0xFFF8;
	} else if (initStaX > 0) {
		data -= 2;
		*(data + 1) = LEFTY;
		*data = (initStaX + 7) & 0xFFF8;
	}
	return data;
}

uint16 SkyAutoRoute::autoRoute(Compact *cpt) {

	uint8 cptScreen = (uint8)cpt->screen;
	uint8 cptWidth = (uint8)SkyCompact::getMegaSet(cpt, cpt->extCompact->megaSet)->gridWidth;
	initWalkGrid(cptScreen, cptWidth);

	uint8 startX, startY, destX, destY;
	int16 initStaX, initStaY, initDestX, initDestY;

	clipCoordX(cpt->xcood, startX, initStaX);
	clipCoordY(cpt->ycood, startY, initStaY);
	clipCoordX(cpt->extCompact->arTargetX, destX, initDestX);
	clipCoordY(cpt->extCompact->arTargetY, destY, initDestY);

	memset(cpt->extCompact->animScratch, 0, 64);
	if ((startX == destX) && (startY == destY))
		return 2;

	if (_routeGrid[(destY + 1) * ROUTE_GRID_WIDTH + destX + 1])
		return 1; // AR destination is an unaccessible block

	if (!calcWalkGrid(startX, startY, destX, destY))
		return 1; // can't find route to block

	uint16 *routeData = makeRouteData(startX, startY, destX, destY);
	// the route is done.
	// if there was an initial x movement (due to clipping) tag it onto the start
	routeData = checkInitMove(routeData, initStaX);

    uint8 cnt = 0;
	do {
		((uint16*)cpt->extCompact->animScratch)[cnt]     = routeData[cnt];
		((uint16*)cpt->extCompact->animScratch)[cnt + 1] = routeData[cnt + 1];
		cnt += 2;
	} while (routeData[cnt - 2]);
	return 0;
}

