implemented iso pathfinding

glitches: some tiles draws above figures

svn-id: r16935

7 files changed, 366 insertions, 23 deletions

diff --git a/saga/actor.cpp b/saga/actor.cpp
index f3627b7f5d..2253f4fb04 100644
--- a/saga/actor.cpp
+++ b/saga/actor.cpp
@@ -768,6 +768,7 @@ void Actor::handleActions(int msec, bool setup) {
 	int hitZoneIndex;
 	const HitZone *hitZone;
 	Point hitPoint;
+	Location pickLocation;
 
 	for (i = 0; i < _actorsCount; i++) {
 		actor = _actors[i];
@@ -823,7 +824,66 @@ void Actor::handleActions(int msec, bool setup) {
 			case kActionWalkToLink:
 				// tiled stuff
 				if (_vm->_scene->getFlags() & kSceneFlagISO) {
-					//todo: it
+					actor->partialTarget.delta(actor->location, delta);
+					
+					while ((delta.u() == 0) && (delta.v() == 0)) {
+
+						if ((actor == _protagonist) && (_vm->_interface->_playfieldClicked)) {
+							_vm->_isoMap->screenPointToTileCoords(_vm->getMousePos(), pickLocation);
+
+							if(!actorWalkTo(_protagonist->id, pickLocation)) {
+								break;
+							}
+						} else {
+								if (!_vm->_isoMap->nextTileTarget(actor)) {
+									if (!actorEndWalk(actor->id, true)) {
+										break;
+									}
+								}
+						}
+
+						actor->partialTarget.delta(actor->location, delta);						
+						actor->partialTarget.z = 0;						
+					}
+
+					speed = 4;
+					if (actor->flags & kFastest) {
+						speed = 8;
+					} else {
+						if (actor->flags & kFaster) {
+							speed = 6;
+						}
+					}
+
+					if (_vm->_scene->currentSceneNumber() == RID_ITE_OVERMAP_SCENE) {
+						speed = 2;
+					}
+
+					if ((actor->actionDirection == 2) || (actor->actionDirection == 6)) {
+						speed = speed / 2;
+					}
+
+					if (ABS(delta.v()) > ABS(delta.u())) {
+						addDelta.v() = clamp( -speed, delta.v(), speed );
+						if (addDelta.v() == delta.v()) {
+							addDelta.u() = delta.u();
+						} else {
+							addDelta.u() = delta.u() * addDelta.v();
+							addDelta.u() += (addDelta.u() > 0) ? (delta.v() / 2) : (-delta.v() / 2);
+							addDelta.u() /= delta.v();
+						}
+					} else {  
+						addDelta.u() = clamp( -speed, delta.u(), speed );
+						if (addDelta.u() == delta.u()) {
+							addDelta.v() = delta.v();
+						} else {
+							addDelta.v() = delta.v() * addDelta.u();
+							addDelta.v() += (addDelta.v() > 0) ? (delta.u() / 2) : (-delta.u() / 2);
+							addDelta.v() /= delta.u();
+						}
+					}
+
+					actor->location.add(addDelta);
 				} else {
 					actor->partialTarget.delta(actor->location, delta);
 
@@ -902,7 +962,14 @@ void Actor::handleActions(int msec, bool setup) {
 			case kActionWalkDir:
 				// tiled stuff
 				if (_vm->_scene->getFlags() & kSceneFlagISO) {
-					//todo: it
+					actor->location.u() += tileDirectionLUT[actor->actionDirection][0];
+					actor->location.v() += tileDirectionLUT[actor->actionDirection][1];
+
+					frameRange = getActorFrameRange(actor->id, actor->walkFrameSequence);
+
+					actor->actionCycle++;
+					actor->cycleWrap(frameRange->frameCount);
+					actor->frameNumber = frameRange->frameIndex + actor->actionCycle;
 				} else {
 					actor->location.x += directionLUT[actor->actionDirection][0] * 2;
 					actor->location.y += directionLUT[actor->actionDirection][1] * 2;
@@ -1008,13 +1075,14 @@ void Actor::handleActions(int msec, bool setup) {
 			hitZone = NULL;
 			// tiled stuff
 			if (_vm->_scene->getFlags() & kSceneFlagISO) {
-				//todo: it
+				hitPoint.x = actor->location.u();
+				hitPoint.y = actor->location.v();
 			} else {
 				actor->location.toScreenPointXY(hitPoint);
-				hitZoneIndex = _vm->_scene->_actionMap->hitTest(hitPoint);
-				if (hitZoneIndex != -1) {
-					hitZone = _vm->_scene->_actionMap->getHitZone(hitZoneIndex);
-				}
+			}
+			hitZoneIndex = _vm->_scene->_actionMap->hitTest(hitPoint);
+			if (hitZoneIndex != -1) {
+				hitZone = _vm->_scene->_actionMap->getHitZone(hitZoneIndex);
 			}
 
 			if (hitZone != actor->lastZone) {
@@ -1215,6 +1283,10 @@ bool Actor::followProtagonist(ActorData *actor) {
 	Point prefer1;
 	Point prefer2;
 	Point prefer3;
+	int16 prefU;
+	int16 prefV;
+	int16 newU;
+	int16 newV;
 	
 	assert(_protagonist);
 
@@ -1223,7 +1295,39 @@ bool Actor::followProtagonist(ActorData *actor) {
 	calcScreenPosition(_protagonist);
 
 	if (_vm->_scene->getFlags() & kSceneFlagISO) {
-		//todo: it
+		prefU = 60;
+		prefV = 60;
+
+
+		actor->location.delta(protagonistLocation, delta);
+
+		if (actor->id == actorIndexToId(2)) {
+			prefU = prefV = 48;
+		}
+
+		if ((delta.u() > prefU) || (delta.u() < -prefU) || (delta.v() > prefV) || (delta.v() < -prefV)) {
+
+			if ((delta.u() > prefU * 2) || (delta.u() < -prefU * 2) || (delta.v() > prefV * 2) || (delta.v() < -prefV * 2)) {
+				actor->flags |= kFaster;
+
+				if ((delta.u() > prefU * 3) || (delta.u() < -prefU*3) || (delta.v() > prefV * 3) || (delta.v() < -prefV * 3)) {
+					actor->flags |= kFastest;
+				}
+			}
+
+			prefU /= 2;
+			prefV /= 2;
+
+			newU = clamp( -prefU, delta.u(), prefU ) + protagonistLocation.u();
+			newV = clamp( -prefV, delta.v(), prefV ) + protagonistLocation.v();
+
+			newLocation.u() = newU + (rand() % prefU) - prefU / 2;
+			newLocation.v() = newV + (rand() % prefV) - prefV / 2;
+			newLocation.z = 0;
+
+			return actorWalkTo(actor->id, newLocation);
+		}
+
 	} else {		
 		prefer1.x = (100 * _protagonist->screenScale) >> 8;
 		prefer1.y = (50 * _protagonist->screenScale) >> 8;
@@ -1254,8 +1358,6 @@ bool Actor::followProtagonist(ActorData *actor) {
 			}
 		}
 
-		
-
 		if ((rand() & 0x7) == 0)
 			actor->actorFlags &= ~kActorNoFollow;
 
@@ -1371,7 +1473,27 @@ bool Actor::actorWalkTo(uint16 actorId, const Location &toLocation) {
 	}
 
 	if (_vm->_scene->getFlags() & kSceneFlagISO) {
-		//todo: it
+
+		//todo: dragon stuff
+
+		actor->finalTarget = toLocation;
+		actor->walkStepsCount = 0;
+		_vm->_isoMap->findTilePath(actor, actor->location, toLocation);
+
+
+		if ((actor->walkStepsCount == 0) && (actor->flags & kProtagonist)) {
+			actor->actorFlags |= kActorNoCollide;
+			_vm->_isoMap->findTilePath(actor, actor->location, toLocation);
+		}
+
+		actor->walkStepIndex = 0;
+		if (_vm->_isoMap->nextTileTarget(actor)) {
+			actor->currentAction = kActionWalkToPoint;
+			actor->walkFrameSequence = kFrameWalk;
+		} else {
+			actorEndWalk( actorId, false);
+			return false;
+		}
 	} else {
 		
 		actor->location.toScreenPointXY(pointFrom);
diff --git a/saga/actor.h b/saga/actor.h
index f7939c7c0b..babc847ef8 100644
--- a/saga/actor.h
+++ b/saga/actor.h
@@ -234,12 +234,17 @@ public:
 	int framesCount;			// Actor's frames count
 	int frameListResourceId;	// Actor's frame list resource id
 	
-//	int walkPath[ACTOR_STEPS_MAX]; //todo: will gone
-	int walkStepsCount;
+	//int walkPath[ACTOR_STEPS_MAX]; //todo: will gone
+
+	int tileDirectionsAlloced;
+	byte *tileDirections;
+
 	int walkStepsAlloced;
-	int walkStepIndex;
 	Point *walkStepsPoints;
 
+	int walkStepsCount;
+	int walkStepIndex;
+
 	Location finalTarget;
 	Location partialTarget;
 	int walkFrameSequence;
@@ -260,11 +265,13 @@ public:
 	ActorData() {
 		memset(this, 0xFE, sizeof(*this)); 
 		walkStepsPoints = NULL;
-		walkStepsAlloced = walkStepsCount = walkStepIndex = 0;
+		tileDirectionsAlloced = walkStepsAlloced = walkStepsCount = walkStepIndex = 0;
+		tileDirections = NULL;
 		memset(&spriteList, 0, sizeof(spriteList));
 	}
 	~ActorData() {
 		free(frames);
+		free(tileDirections);
 		free(walkStepsPoints);
 		spriteList.freeMem();
 	}
diff --git a/saga/interface.cpp b/saga/interface.cpp
index c873830416..59913ad018 100644
--- a/saga/interface.cpp
+++ b/saga/interface.cpp
@@ -66,6 +66,8 @@ Interface::Interface(SagaEngine *vm) : _vm(vm), _initialized(false) {
 	if (_initialized) {
 		return;
 	}
+	
+	_playfieldClicked = false;
 
 	// Load interface module resource file context
 	_interfaceContext = _vm->getFileContext(GAME_RESOURCEFILE, 0);
@@ -370,7 +372,7 @@ int Interface::draw() {
 
 int Interface::update(const Point& mousePoint, int updateFlag) {
 	SURFACE *backBuffer;
-
+	
 	if (_vm->_scene->isInDemo() || _panelMode == kPanelFade)
 		return SUCCESS;
 
@@ -382,7 +384,6 @@ int Interface::update(const Point& mousePoint, int updateFlag) {
 		if (updateFlag & UPDATE_MOUSEMOVE) {
 	
 			if (mousePoint.y < _vm->getSceneHeight()) {
-				//handlePlayfieldUpdate(backBuffer, imousePointer);
 				_vm->_script->whichObject(mousePoint);
 			} else {
 				if (_lastMousePoint.y < _vm->getSceneHeight()) {
@@ -395,9 +396,9 @@ int Interface::update(const Point& mousePoint, int updateFlag) {
 
 			if (updateFlag & UPDATE_MOUSECLICK) {
 				if (mousePoint.y < _vm->getSceneHeight()) {
-					//handlePlayfieldClick(backBuffer, mousePoint);
-					_vm->_script->playfieldClick(mousePoint, (updateFlag & UPDATE_LEFTBUTTONCLICK) != 0);
-										
+					_playfieldClicked = true;
+					_vm->_script->playfieldClick(mousePoint, (updateFlag & UPDATE_LEFTBUTTONCLICK) != 0);										
+					_playfieldClicked = false;
 				} else {
 					handleCommandClick(backBuffer, mousePoint);
 				}
diff --git a/saga/interface.h b/saga/interface.h
index d213284312..4311c0f690 100644
--- a/saga/interface.h
+++ b/saga/interface.h
@@ -106,6 +106,8 @@ enum ITEColors {
 
 class Interface {
 public:
+	bool _playfieldClicked;
+
 	Interface(SagaEngine *vm);
 	~Interface(void);
 
diff --git a/saga/isomap.cpp b/saga/isomap.cpp
index 6bf742c579..9c6d527020 100644
--- a/saga/isomap.cpp
+++ b/saga/isomap.cpp
@@ -99,6 +99,7 @@ IsoMap::IsoMap(SagaEngine *vm) : _vm(vm) {
 	_viewScroll.x = (128 - 8) * 16;
 	_viewScroll.x = (128 - 8) * 16 - 64;
 	_viewDiff = 1;
+
 }
 
 void IsoMap::loadImages(const byte *resourcePointer, size_t resourceLength) {
@@ -1195,5 +1196,203 @@ void IsoMap::placeOnTileMap(const Location &start, Location &result, int16 dista
 	result.v() = ((vBase + bestV) << 4) + 8;
 }
 
+void IsoMap::findTilePath(ActorData* actor, const Location &start, const Location &end) {
+	ActorData *other;
+	int i;
+	int16 u;
+	int16 v;
+	int16 bestDistance;
+	int16 bestU;
+	int16 bestV;
+
+	int16 uBase;
+	int16 vBase;
+	int16 uFinish;
+	int16 vFinish;
+
+	TilePoint tilePoint;
+	uint16 dir;
+	int16 dist;
+	uint16 terraComp[8];
+	const TilePoint *tdir;
+	uint16 terrainMask;
+	const PathCell *pcell;
+	byte *res;
+
+
+	bestDistance = SAGA_SEARCH_DIAMETER;
+	bestU = SAGA_SEARCH_CENTER,
+	bestV = SAGA_SEARCH_CENTER;
+
+	uBase = (start.u() >> 4) - SAGA_SEARCH_CENTER;
+	vBase = (start.v() >> 4) - SAGA_SEARCH_CENTER;
+	uFinish = (end.u() >> 4) - uBase;
+	vFinish = (end.v() >> 4) - vBase;
+
+	_platformHeight = _vm->_actor->_protagonist->location.z / 8;
+
+
+
+	memset( &_searchArray, 0, sizeof(_searchArray));
+
+	if (!(actor->actorFlags & kActorNoCollide) && 
+		(_vm->_scene->currentSceneNumber() != RID_ITE_OVERMAP_SCENE)) {
+			for (i = 0; i < _vm->_actor->_actorsCount; i++) {
+				other = _vm->_actor->_actors[i];
+				if (other->disabled) continue;
+				if (other->sceneNumber != _vm->_scene->currentSceneNumber()) continue;
+				if (other==actor) continue;
+
+				u = (other->location.u() >> 4) - uBase;
+				v = (other->location.v() >> 4) - vBase;
+				if ((u >= 1) && (u < SAGA_SEARCH_DIAMETER) &&
+					(v >= 1) && (v < SAGA_SEARCH_DIAMETER) && 
+					((u != SAGA_SEARCH_CENTER) || (v != SAGA_SEARCH_CENTER))) {
+						_searchArray.getPathCell(u, v)->visited = 1;
+					}
+			}
+		}
+
+	_queueCount = 0;
+	pushPoint(SAGA_SEARCH_CENTER, SAGA_SEARCH_CENTER, 0, 0);
+
+
+	while (_queueCount > 0) {	
+
+		_queueCount--;
+		tilePoint = *_searchArray.getQueue(_queueCount);
+
+		if (tilePoint.cost > 100 && actor == _vm->_actor->_protagonist) continue;
+
+		dist = ABS(tilePoint.u - uFinish) + ABS(tilePoint.v - vFinish);
+
+		if (dist < bestDistance) {
+			bestU = tilePoint.u;
+			bestV = tilePoint.v;
+			bestDistance = dist;
+
+			if (dist == 0) {
+				break;
+			}
+		}
+
+		testPossibleDirections(uBase + tilePoint.u, vBase + tilePoint.v, terraComp, 
+			(tilePoint.u == SAGA_SEARCH_CENTER && tilePoint.v == SAGA_SEARCH_CENTER));
+
+		for (dir = 0; dir < 8; dir++) {
+			terrainMask = terraComp[dir];
+
+			if (terrainMask & SAGA_IMPASSABLE) {
+				continue;
+			} else {
+				if(terrainMask & (1 << kTerrRough)) {
+					tdir = &hardDirTable[ dir ];
+				} else {
+					if(terrainMask & (1 << kTerrNone)) {
+						tdir = &normalDirTable[ dir ];
+					} else {
+						tdir = &easyDirTable[ dir ];
+					}
+				}
+			}
+
+
+			pushPoint(tilePoint.u + tdir->u, tilePoint.v + tdir->v, tilePoint.cost + tdir->cost, dir);
+		}
+	}
+
+	res = &_pathDirections[SAGA_MAX_PATH_DIRECTIONS];
+	i = 0;
+	while ((bestU != SAGA_SEARCH_CENTER) || (bestV != SAGA_SEARCH_CENTER)) {
+		pcell = _searchArray.getPathCell(bestU, bestV);
+
+		*--res = pcell->direction;
+		i++;
+		if (i >= SAGA_MAX_PATH_DIRECTIONS) {
+			break;
+		}
+
+		dir = (pcell->direction + 4) & 0x07;
+
+		bestU += normalDirTable[dir].u;
+		bestV += normalDirTable[dir].v;
+	}
+
+	if (i > 64) {
+		i = 64;
+	}
+	actor->walkStepsCount = i;
+	if (i) {	
+		if (actor->tileDirectionsAlloced < i) {
+			actor->tileDirectionsAlloced = i;
+			actor->tileDirections = (byte*)realloc(actor->tileDirections, actor->tileDirectionsAlloced * sizeof(*actor->tileDirections));
+		}
+		memcpy(actor->tileDirections, res, i );
+	}
+}
+
+static const int16 directions[8][2] = {
+	{	16,		16},
+	{	16,		0},
+	{	16,		-16},
+	{	0,		-16},
+	{	-16,	-16},
+	{	-16,	0},
+	{	-16,	16},
+	{	0,		16}
+};
+
+
+bool IsoMap::nextTileTarget(ActorData* actor) {
+	uint16 dir;
+
+	if (actor->walkStepIndex >= actor->walkStepsCount) {
+		return false;
+	}
+
+
+	actor->actionDirection = dir = actor->tileDirections[actor->walkStepIndex++];
+
+	actor->partialTarget.u() =
+		(actor->location.u() & ~0x0f) + 8 + directions[dir][0];
+
+	actor->partialTarget.v() =
+		(actor->location.v() & ~0x0f) + 8 + directions[dir][1];
+
+
+	if (dir == 0) {
+		actor->facingDirection = kDirUp;
+	} else {
+		if (dir == 4) {
+			actor->facingDirection = kDirDown;
+		} else {
+			if (dir < 4) {
+				actor->facingDirection = kDirRight;
+			} else {
+				actor->facingDirection = kDirLeft;
+			}
+		}
+	}
+
+	return true;
+}
+
+void IsoMap::screenPointToTileCoords(const Point &position, Location &location) {
+	Point mPos(position);
+	int x,y;
+
+	if (_vm->_scene->currentSceneNumber() == RID_ITE_OVERMAP_SCENE){
+		if (mPos.y < 16) {
+			mPos.y = 16;
+		}
+	}
+
+	x = mPos.x + _viewScroll.x - (128 * SAGA_TILEMAP_W) - 16;
+	y = mPos.y + _viewScroll.y - (128 * SAGA_TILEMAP_W) + _vm->_actor->_protagonist->location.z;
+
+	location.u() = (x - y * 2) >> 1;
+	location.v() = - (x + y * 2) >> 1;
+	location.z = _vm->_actor->_protagonist->location.z;
+}
 
 } // End of namespace Saga
diff --git a/saga/isomap.h b/saga/isomap.h
index 21e3306d41..185155d3fb 100644
--- a/saga/isomap.h
+++ b/saga/isomap.h
@@ -66,6 +66,7 @@ namespace Saga {
 
 #define SAGA_STRAIGHT_HARD_COST				9
 #define SAGA_DIAG_HARD_COST					10
+#define SAGA_MAX_PATH_DIRECTIONS			256
 
 enum TerrainTypes {
 	kTerrNone	= 0,
@@ -161,7 +162,10 @@ public:
 		position.x = location.u() - location.v() + (128 * SAGA_TILEMAP_W) - _viewScroll.x + 16;
 		position.y = -((location.u() + location.v()) >> 1) + (128 * SAGA_TILEMAP_W) - _viewScroll.y - location.z;
 	}
+	void screenPointToTileCoords(const Point &position, Location &location);
 	void placeOnTileMap(const Location &start, Location &result, int16 distance, uint16 direction);
+	void findTilePath(ActorData* actor, const Location &start, const Location &end);
+	bool nextTileTarget(ActorData* actor);
 	
 private:
 	void drawTiles(SURFACE *ds, const Location *location);
@@ -242,6 +246,8 @@ private:
 	
 	int16 _queueCount;
 	SearchArray _searchArray;
+	byte _pathDirections[SAGA_MAX_PATH_DIRECTIONS];
+
 
 	int _viewDiff;
 	Point _viewScroll;
diff --git a/saga/script.cpp b/saga/script.cpp
index 5e0f044be1..34f454aa7c 100644
--- a/saga/script.cpp
+++ b/saga/script.cpp
@@ -36,6 +36,7 @@
 #include "saga/events.h"
 #include "saga/actor.h"
 #include "saga/objectmap.h"
+#include "saga/isomap.h"
 
 namespace Saga {
 
@@ -607,7 +608,7 @@ void Script::playfieldClick(const Point& mousePoint, bool leftButton) {
 
 	// tiled stuff
 	if (_vm->_scene->getFlags() & kSceneFlagISO) {
-		//todo: it
+		_vm->_isoMap->screenPointToTileCoords(mousePoint, pickLocation);
 	} else {
 		pickLocation.fromScreenPoint(mousePoint);
 	}
@@ -637,7 +638,9 @@ void Script::playfieldClick(const Point& mousePoint, bool leftButton) {
 			
 			// tiled stuff
 			if (_vm->_scene->getFlags() & kSceneFlagISO) {
-				//todo: it
+				pickLocation.u() = specialPoint.x;
+				pickLocation.v() = specialPoint.y;
+				pickLocation.z = _vm->_actor->_protagonist->location.z;
 			} else {
 				pickLocation.fromScreenPoint(specialPoint);
 			}
@@ -679,6 +682,7 @@ void Script::whichObject(const Point& mousePoint) {
 	Location pickLocation;
 	int hitZoneIndex;
 	const HitZone * hitZone;
+	Point tempPoint;
 
 	objectId = ID_NOTHING;
 	objectFlags = 0;
@@ -718,7 +722,9 @@ void Script::whichObject(const Point& mousePoint) {
 
 		if (newObjectId == ID_NOTHING) {		
 			if (_vm->_scene->getFlags() & kSceneFlagISO) {
-				//todo: it
+				tempPoint = mousePoint;
+				tempPoint.y -= _vm->_actor->_protagonist->location.z;
+				_vm->_isoMap->screenPointToTileCoords(tempPoint, pickLocation);
 			} else {
 				pickLocation.x = mousePoint.x;
 				pickLocation.y = mousePoint.y;