14 files changed, 580 insertions, 49 deletions

diff --git a/engines/illusions/actor.cpp b/engines/illusions/actor.cpp
index 030097bba9..31f3a28613 100644
--- a/engines/illusions/actor.cpp
+++ b/engines/illusions/actor.cpp
@@ -72,6 +72,8 @@ Actor::Actor(IllusionsEngine *vm)
 	_scaleLayer = 0;
 	_priorityLayer = 0;
 	_regionLayer = 0;
+	_pathWalkPoints = 0;
+	_pathWalkRects = 0;
 	_position.x = 0;
 	_position.y = 0;
 	_position2.x = 0;
@@ -115,13 +117,7 @@ Actor::Actor(IllusionsEngine *vm)
 
 #if 0 // TODO
 	_field2 = 0;
-	_namedPointsCount = 0;
-	_namedPoints = 0;
 	_field164 = 0;
-	_pathWalkRects = 0;
-	_pathWalkPoints = 0;
-	_regionLayer = 0;
-	_transitionRegionId = 0;
 	_field18C = 0;
 	_field190 = 0;
 	_field192 = 0;
@@ -768,9 +764,15 @@ void Control::startMoveActor(uint32 sequenceId, Common::Point destPt, uint32 cal
 
 PointArray *Control::createPath(Common::Point destPt) {
 	// TODO Implement actual pathfinding
-	PointArray *pathNode = new PointArray();
-	pathNode->push_back(destPt);
-	return pathNode;
+	PointArray *walkPoints = (_actor->_flags & 2) ? _actor->_pathWalkPoints->_points : 0;
+	PathLines *walkRects = (_actor->_flags & 0x10) ? _actor->_pathWalkRects->_rects : 0;
+	PathFinder pathFinder;
+	WidthHeight bgDimensions = _vm->_backgroundItems->getMasterBgDimensions();
+	PointArray *path = pathFinder.findPath(_actor->_position, destPt, walkPoints, walkRects, bgDimensions);
+	for (uint i = 0; i < path->size(); ++i) {
+		debug("Path(%d) (%d, %d)", i, (*path)[i].x, (*path)[i].y);
+	}
+	return path;
 }
 
 void Control::updateActorMovement(uint32 deltaTime) {
@@ -793,16 +795,6 @@ void Control::updateActorMovement(uint32 deltaTime) {
 	if (_vm->testMainActorCollision(this))
 		break;
 
-	/* TODO
-	if (controla->objectId == GameScript_getField0() && again == const0 && Input_pollButton__(0x10u)) {
-		again = 1;
-		Control_disappearActor__(controla);
-		HIBYTE(_actor->_flags) |= 0x80u;
-		_actor->_seqCodeIp = 0;
-		deltaTime = 2;
-	}
-	*/
-
 	Common::Point prevPt;
 	if (_actor->_pathPointIndex == 0) {
 		if (_actor->_pathInitialPosFlag) {
@@ -1051,7 +1043,7 @@ void Controls::placeActor(uint32 actorTypeId, Common::Point placePt, uint32 sequ
 	
 	BackgroundResource *bgRes = _vm->_backgroundItems->getActiveBgResource();
 	if (actorType->_pathWalkPointsIndex) {
-		// TODO actor->_pathWalkPoints = bgRes->getPathWalkPoints(actorType->_pathWalkPointsIndex - 1);
+		actor->_pathWalkPoints = bgRes->getPathWalkPoints(actorType->_pathWalkPointsIndex - 1);
 		actor->_flags |= 0x02;
 	}
 
@@ -1061,7 +1053,7 @@ void Controls::placeActor(uint32 actorTypeId, Common::Point placePt, uint32 sequ
 	}
 
 	if (actorType->_pathWalkRectIndex) {
-		// TODO actor->_pathWalkRects = bgRes->getPathWalkRects(actorType->_pathWalkRectIndex - 1);
+		actor->_pathWalkRects = bgRes->getPathWalkRects(actorType->_pathWalkRectIndex - 1);
 		actor->_flags |= 0x10;
 	}
 	
@@ -1080,12 +1072,12 @@ void Controls::placeActor(uint32 actorTypeId, Common::Point placePt, uint32 sequ
 	_controls.push_back(control);
 	_vm->_dict->setObjectControl(objectId, control);
 
-    if (_vm->getGameId() == kGameIdDuckman) {
+	if (_vm->getGameId() == kGameIdDuckman) {
 		control->appearActor();
-    } else if (_vm->getGameId() == kGameIdBBDOU) {
+	} else if (_vm->getGameId() == kGameIdBBDOU) {
 		control->_flags |= 0x01;
 		actor->_flags |= 0x1000;
-    }
+	}
 
 	if (_vm->isCursorObject(actorTypeId, objectId))
 		_vm->placeCursorControl(control, sequenceId);
@@ -1318,6 +1310,24 @@ bool Controls::getDialogItemAtPos(Control *control, Common::Point pt, Control **
 	return foundControl != 0;
 }
 
+bool Controls::getOverlappedWalkObject(Control *control, Common::Point pt, Control **outOverlappedControl) {
+	Control *foundControl = 0;
+	for (ItemsIterator it = _controls.begin(); it != _controls.end(); ++it) {
+		Control *testControl = *it;
+		if (testControl != control && testControl->_pauseCtr == 0 &&
+			(testControl->_flags & 1)) {
+			Common::Rect collisionRect;
+			testControl->getCollisionRect(collisionRect);
+			if (!collisionRect.isEmpty() && collisionRect.contains(pt) &&
+				(!foundControl || foundControl->_priority < testControl->_priority))
+				foundControl = testControl;
+		}
+	}
+	if (foundControl)
+		*outOverlappedControl = foundControl;
+	return foundControl != 0;
+}
+
 void Controls::destroyControl(Control *control) {
 	_controls.remove(control);
 	destroyControlInternal(control);
diff --git a/engines/illusions/actor.h b/engines/illusions/actor.h
index e71eebcdb1..7e69ee6cab 100644
--- a/engines/illusions/actor.h
+++ b/engines/illusions/actor.h
@@ -26,6 +26,7 @@
 #include "illusions/actorresource.h"
 #include "illusions/backgroundresource.h"
 #include "illusions/graphics.h"
+#include "illusions/pathfinder.h"
 #include "common/algorithm.h"
 #include "common/func.h"
 #include "common/list.h"
@@ -66,7 +67,6 @@ protected:
 };
 
 typedef Common::Functor2<Control*, uint32, void> ActorControlRoutine;
-typedef Common::Array<Common::Point> PointArray;
 
 class Actor {
 public:
@@ -102,6 +102,8 @@ public:
 	ScaleLayer *_scaleLayer;
 	PriorityLayer *_priorityLayer;
 	RegionLayer *_regionLayer;
+	PathWalkPoints *_pathWalkPoints;
+	PathWalkRects *_pathWalkRects;
 	
 	uint _seqStackCount;
 	int16 _seqStack[5];
@@ -238,6 +240,7 @@ public:
 	void unpauseControlsByTag(uint32 tag);
 	bool getOverlappedObject(Control *control, Common::Point pt, Control **outOverlappedControl, int minPriority);
 	bool getDialogItemAtPos(Control *control, Common::Point pt, Control **outOverlappedControl);
+	bool getOverlappedWalkObject(Control *control, Common::Point pt, Control **outOverlappedControl);
 	void destroyControl(Control *control);
 	bool findNamedPoint(uint32 namedPointId, Common::Point &pt);
 	void actorControlRoutine(Control *control, uint32 deltaTime);
diff --git a/engines/illusions/backgroundresource.cpp b/engines/illusions/backgroundresource.cpp
index f76000513a..07a07c2079 100644
--- a/engines/illusions/backgroundresource.cpp
+++ b/engines/illusions/backgroundresource.cpp
@@ -218,6 +218,41 @@ void BackgroundObject::load(byte *dataStart, Common::SeekableReadStream &stream)
 		_objectId, _flags, _priority, pointsConfigOffs);
 }
 
+// PathWalkPoints
+
+void PathWalkPoints::load(byte *dataStart, Common::SeekableReadStream &stream) {
+	_points = new PointArray();
+	uint count = stream.readUint32LE();
+	uint32 pointsOffs = stream.readUint32LE();
+	_points->reserve(count);
+	stream.seek(pointsOffs);
+	for (uint i = 0; i < count; ++i) {
+		Common::Point pt;
+		loadPoint(stream, pt);
+		_points->push_back(pt);
+	}
+	debug(0, "PathWalkPoints::load() count: %d; pointsOffs: %08X",
+		count, pointsOffs);
+}
+
+// PathWalkRects
+
+void PathWalkRects::load(byte *dataStart, Common::SeekableReadStream &stream) {
+	_rects = new PathLines();
+	uint count = stream.readUint32LE();
+	uint32 rectsOffs = stream.readUint32LE();
+	_rects->reserve(count);
+	stream.seek(rectsOffs);
+	for (uint i = 0; i < count; ++i) {
+		PathLine rect;
+		loadPoint(stream, rect.p0);
+		loadPoint(stream, rect.p1);
+		_rects->push_back(rect);
+	}
+	debug(0, "PathWalkRects::load() count: %d; rectsOffs: %08X",
+		count, rectsOffs);
+}
+
 // BackgroundResource
 
 BackgroundResource::BackgroundResource() {
@@ -303,6 +338,30 @@ void BackgroundResource::load(byte *data, uint32 dataSize) {
 		_backgroundObjects[i].load(data, stream);
 	}
 	
+	// Load path walk points
+	stream.seek(0x0E);
+	_pathWalkPointsCount = stream.readUint16LE();
+	debug("_pathWalkPointsCount: %d", _pathWalkPointsCount);
+	_pathWalkPoints = new PathWalkPoints[_pathWalkPointsCount];
+	stream.seek(0x28);
+	uint32 pathWalkPointsOffs = stream.readUint32LE();
+	for (uint i = 0; i < _pathWalkPointsCount; ++i) {
+		stream.seek(pathWalkPointsOffs + i * 8);
+		_pathWalkPoints[i].load(data, stream);
+	}
+
+	// Load path walk rects
+	stream.seek(0x12);
+	_pathWalkRectsCount = stream.readUint16LE();
+	debug("_pathWalkRectsCount: %d", _pathWalkRectsCount);
+	_pathWalkRects = new PathWalkRects[_pathWalkRectsCount];
+	stream.seek(0x30);
+	uint32 pathWalkRectsOffs = stream.readUint32LE();
+	for (uint i = 0; i < _pathWalkRectsCount; ++i) {
+		stream.seek(pathWalkRectsOffs + i * 8);
+		_pathWalkRects[i].load(data, stream);
+	}
+
 	// Load named points
 	stream.seek(0xC);
 	uint namedPointsCount = stream.readUint16LE();
@@ -344,6 +403,14 @@ RegionLayer *BackgroundResource::getRegionLayer(uint index) {
 	return &_regionLayers[index];
 }
 
+PathWalkPoints *BackgroundResource::getPathWalkPoints(uint index) {
+	return &_pathWalkPoints[index];
+}
+
+PathWalkRects *BackgroundResource::getPathWalkRects(uint index) {
+	return &_pathWalkRects[index];
+}
+
 bool BackgroundResource::findNamedPoint(uint32 namedPointId, Common::Point &pt) {
 	return _namedPoints.findNamedPoint(namedPointId, pt);
 }
diff --git a/engines/illusions/backgroundresource.h b/engines/illusions/backgroundresource.h
index 3a7e1ebcef..b09c2d5e6f 100644
--- a/engines/illusions/backgroundresource.h
+++ b/engines/illusions/backgroundresource.h
@@ -25,6 +25,7 @@
 
 #include "illusions/camera.h"
 #include "illusions/graphics.h"
+#include "illusions/pathfinder.h"
 #include "illusions/resourcesystem.h"
 #include "graphics/surface.h"
 
@@ -103,19 +104,6 @@ protected:
 	byte *_map, *_values;
 };
 
-
-#if 0
-BgResource_PathWalkRects struc ; (sizeof=0x8)
-count dd ?
-rects dd ?
-BgResource_PathWalkRects ends
-
-BgResource_PathWalkPoints struc ; (sizeof=0x8)
-count dd ?
-points dd ?
-BgResource_PathWalkPoints ends
-#endif
-
 struct Palette {
 	uint16 _count;
 	uint16 _unk;
@@ -131,6 +119,20 @@ struct BackgroundObject {
 	void load(byte *dataStart, Common::SeekableReadStream &stream);
 };
 
+struct PathWalkPoints {
+	PointArray *_points;
+	PathWalkPoints() : _points(0) {}
+	~PathWalkPoints() { delete _points; }
+	void load(byte *dataStart, Common::SeekableReadStream &stream);
+};
+
+struct PathWalkRects {
+	PathLines *_rects;
+	PathWalkRects() : _rects(0) {}
+	~PathWalkRects() { delete _rects; }
+	void load(byte *dataStart, Common::SeekableReadStream &stream);
+};
+
 class BackgroundResource {
 public:
 	BackgroundResource();
@@ -140,6 +142,8 @@ public:
 	PriorityLayer *getPriorityLayer(uint index);
 	ScaleLayer *getScaleLayer(uint index);
 	RegionLayer *getRegionLayer(uint index);
+	PathWalkPoints *getPathWalkPoints(uint index);
+	PathWalkRects *getPathWalkRects(uint index);
 	bool findNamedPoint(uint32 namedPointId, Common::Point &pt);
 public:
 
@@ -162,7 +166,13 @@ public:
 
 	uint _backgroundObjectsCount;
 	BackgroundObject *_backgroundObjects;
-	
+
+	uint _pathWalkPointsCount;
+	PathWalkPoints *_pathWalkPoints;
+
+	uint _pathWalkRectsCount;
+	PathWalkRects *_pathWalkRects;
+
 	NamedPoints _namedPoints;
 	
 	uint _palettesCount;
diff --git a/engines/illusions/graphics.cpp b/engines/illusions/graphics.cpp
index 37fe4d547e..a4fa0e6cfe 100644
--- a/engines/illusions/graphics.cpp
+++ b/engines/illusions/graphics.cpp
@@ -76,7 +76,7 @@ void loadPoint(Common::SeekableReadStream &stream, Common::Point &pt) {
 	pt.x = stream.readSint16LE();
 	pt.y = stream.readSint16LE();
 	
-	debug(5, "loadPoint() x: %d; y: %d",
+	debug(0, "loadPoint() x: %d; y: %d",
 		pt.x, pt.y);
 }
 
diff --git a/engines/illusions/illusions_duckman.cpp b/engines/illusions/illusions_duckman.cpp
index 48db89d26a..3f32ad48e6 100644
--- a/engines/illusions/illusions_duckman.cpp
+++ b/engines/illusions/illusions_duckman.cpp
@@ -118,6 +118,8 @@ Common::Error IllusionsEngine_Duckman::run() {
 	_unpauseControlActorFlag = false;
 	_lastUpdateTime = 0;
 
+	_currWalkOverlappedControl = 0;
+
 	_pauseCtr = 0;
 	_doScriptThreadInit = false;
 	_field8 = 1;
@@ -239,7 +241,7 @@ int IllusionsEngine_Duckman::updateScreenShaker(uint flags) {
 		}
 	}
 
-    if (_screenShaker->_finished) {
+	if (_screenShaker->_finished) {
 		notifyThreadId(_screenShaker->_notifyThreadId);
 		delete _screenShaker;
 		_screenShaker = 0;
@@ -296,8 +298,29 @@ bool IllusionsEngine_Duckman::testMainActorFastWalk(Control *control) {
 }
 
 bool IllusionsEngine_Duckman::testMainActorCollision(Control *control) {
-	// TODO
-	return false;
+	bool result = false;
+	Control *overlappedControl;
+	if (_controls->getOverlappedWalkObject(control, control->_actor->_position, &overlappedControl)) {
+		if (_currWalkOverlappedControl != overlappedControl) {
+			_currWalkOverlappedControl = overlappedControl;
+			if (runTriggerCause(9, 0, overlappedControl->_objectId)) {
+				delete control->_actor->_pathNode;
+				control->_actor->_flags &= ~0x0400;
+				control->_actor->_pathNode = 0;
+				control->_actor->_pathPoints = 0;
+				control->_actor->_pathPointsCount = 0;
+				_threads->terminateThreadChain(control->_actor->_walkCallerThreadId1);
+				if (control->_actor->_notifyId3C) {
+					notifyThreadId(control->_actor->_notifyId3C);
+					control->_actor->_walkCallerThreadId1 = 0;
+				}
+				result = true;
+			}
+		}
+	} else {
+		_currWalkOverlappedControl = 0;
+	}
+	return result;
 }
 
 Control *IllusionsEngine_Duckman::getObjectControl(uint32 objectId) {
diff --git a/engines/illusions/illusions_duckman.h b/engines/illusions/illusions_duckman.h
index da3036f348..305a531c98 100644
--- a/engines/illusions/illusions_duckman.h
+++ b/engines/illusions/illusions_duckman.h
@@ -115,6 +115,7 @@ public:
 	uint32 _activeScenes[6];
 
 	Cursor_Duckman _cursor;
+	Control *_currWalkOverlappedControl;
 
 	Common::Array<DialogItem> _dialogItems;
 
diff --git a/engines/illusions/module.mk b/engines/illusions/module.mk
index f0688d35ad..4f2b58af8e 100644
--- a/engines/illusions/module.mk
+++ b/engines/illusions/module.mk
@@ -22,6 +22,7 @@ MODULE_OBJS := \
 	illusions_duckman.o \
 	input.o \
 	midiresource.o \
+	pathfinder.o \
 	resourcesystem.o \
 	screen.o \
 	screentext.o \
diff --git a/engines/illusions/pathfinder.cpp b/engines/illusions/pathfinder.cpp
new file mode 100644
index 0000000000..a9a76e3a65
--- /dev/null
+++ b/engines/illusions/pathfinder.cpp
@@ -0,0 +1,338 @@
+/* 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.
+ *
+ */
+
+#include "illusions/illusions.h"
+#include "illusions/pathfinder.h"
+
+namespace Illusions {
+
+PointArray *PathFinder::findPath(Common::Point sourcePt, Common::Point destPt,
+	PointArray *walkPoints, PathLines *walkRects, WidthHeight bgDimensions) {
+	_walkPoints = walkPoints;
+	_walkRects = walkRects;
+	_bgDimensions = bgDimensions;
+	return findPathInternal(sourcePt, destPt);
+}
+
+PointArray *PathFinder::findPathInternal(Common::Point sourcePt, Common::Point destPt) {
+	PathLine line;
+	PointArray *foundPath = new PointArray();
+	line.p0 = sourcePt;
+	line.p1 = destPt;
+	
+	if (_walkRects && _walkPoints && isLineBlocked(line)) {
+		Common::Point nextStartPt = sourcePt, outPt;
+
+		if (!findValidDestLine(destPt)) {
+			findValidDestPt(destPt);
+			line.p1 = destPt;
+		}
+
+		_pathBytes = (byte*)calloc(1, _walkPoints->size());
+
+		bool done = false;
+		while (!done) {
+			line.p0 = nextStartPt;
+			if (!isLineBlocked(line)) {
+				foundPath->push_back(destPt);
+				done = true;
+			} else {
+				if (foundPath->size() < _walkPoints->size() + 2 && findClosestPt(nextStartPt, outPt, destPt)) {
+					foundPath->push_back(outPt);
+					nextStartPt = outPt;
+				} else {
+					if (foundPath->size() == 0)
+						foundPath->push_back(sourcePt);
+					done = true;
+				}
+			}
+		}
+
+		free(_pathBytes);
+		// TODO postProcess(sourcePt, foundPath);
+
+	} else {
+		foundPath->push_back(destPt);
+	}
+	return foundPath;
+}
+
+bool PathFinder::isLineBlocked(PathLine &line) {
+	for (uint i = 0; i < _walkRects->size(); ++i)
+		if (calcLineStatus(line, (*_walkRects)[i], 0) != 3)
+			return true;
+	return false;
+}
+
+int PathFinder::calcLineDistance(PathLine &line) {
+	int16 deltaX = line.p0.x - line.p1.x;
+	int16 deltaY = line.p0.y - line.p1.y;
+	if (deltaX != 0 || deltaY != 0)
+		return sqrt(deltaX * deltaX + deltaY * deltaY);
+	return 0;
+}
+
+bool PathFinder::findClosestPt(Common::Point &sourcePt, Common::Point &closestPt, Common::Point &destPt) {
+	PathLine sourceLine, destLine;
+	uint minIndex = 0;
+	int minDistance = 0xFFFF;
+	sourceLine.p0 = sourcePt;
+	destLine.p1 = destPt;
+	for (uint i = 0; i < _walkPoints->size(); ++i) {
+		sourceLine.p1 = (*_walkPoints)[i];
+		destLine.p0 = (*_walkPoints)[i];
+		if (!_pathBytes[i] && !isLineBlocked(sourceLine)) {
+			int currDistance = calcLineDistance(destLine);
+			if (currDistance <= minDistance) {
+				minDistance = currDistance;
+				minIndex = i + 1;
+			}
+		}
+	}
+	if (minIndex) {
+		closestPt = (*_walkPoints)[minIndex - 1];
+		_pathBytes[minIndex - 1] = 1;
+		return true;
+	}
+	return false;
+}
+
+bool PathFinder::findValidDestLine(Common::Point &destPt) {
+	PathLine destLine;
+	destLine.p0 = destPt;
+	for (uint i = 0; i < _walkPoints->size(); ++i) {
+		destLine.p1 = (*_walkPoints)[i];
+		if (!isLineBlocked(destLine))
+			return true;
+	}
+	return false;
+}
+
+void PathFinder::findValidDestPt(Common::Point &destPt) {
+	Common::Point minPt, outPt, deltaPt;
+	int minDistance = 0xFFFF, currDistance;
+	PathLine destLine;
+	for (uint i = 0; i < _walkRects->size(); ++i) {
+		PathLine &currRect = (*_walkRects)[i];
+		WidthHeight rectDimensions = calcRectDimensions(currRect);
+		adjustRectDimensions(rectDimensions);
+		clipLineToBg(destPt, rectDimensions, destLine);
+		if (calcLineStatus(destLine, currRect, &outPt) == 3) {
+			destLine.p0 = destPt;
+			destLine.p1 = currRect.p0;
+			currDistance = calcLineDistance(destLine);
+			if (currDistance < minDistance) {
+				minDistance = currDistance;
+				minPt = currRect.p0;
+			}
+			destLine.p0 = destPt;
+			destLine.p1 = currRect.p1;
+			currDistance = calcLineDistance(destLine);
+			if (currDistance < minDistance) {
+				minDistance = currDistance;
+				minPt = currRect.p1;
+			}
+		} else {
+			destLine.p0 = destPt;
+			destLine.p1 = outPt;
+			currDistance = calcLineDistance(destLine);
+			if (currDistance < minDistance) {
+				minDistance = currDistance;
+				minPt = outPt;
+			}
+		}
+	}
+	findDeltaPt(minPt, deltaPt);
+	destPt.x = deltaPt.x + minPt.x;
+	destPt.y = deltaPt.y + minPt.y;
+}
+
+WidthHeight PathFinder::calcRectDimensions(PathLine &rect) {
+	WidthHeight dimensions;
+	dimensions._width = rect.p1.x - rect.p0.x;
+	dimensions._height = rect.p1.y - rect.p0.y;
+	swapDimensions(dimensions);
+	return dimensions;
+}
+
+void PathFinder::adjustRectDimensions(WidthHeight &dimensions) {
+	dimensions._width = ABS(dimensions._height) * (dimensions._width < 0 ? -1 : 1);
+	dimensions._height = ABS(dimensions._width) * (dimensions._height < 0 ? -1 : 1);
+	if (dimensions._width)
+		dimensions._width = -dimensions._width;
+	else
+		dimensions._height = -dimensions._height;
+	swapDimensions(dimensions);
+}
+
+void PathFinder::swapDimensions(WidthHeight &dimensions) {
+	if (dimensions._width < 0) {
+		dimensions._width = -dimensions._width;
+		dimensions._height = -dimensions._height;
+	} else if (dimensions._width == 0)
+		dimensions._height = abs(dimensions._height);
+	else if (dimensions._height == 0)
+		dimensions._width = abs(dimensions._width);
+}
+
+void PathFinder::clipLineToBg(Common::Point &destPt, WidthHeight &rectDimensions, PathLine &outDestLine) {
+	if (rectDimensions._height == 0) {
+		outDestLine.p0.x = 0;
+		outDestLine.p0.y = destPt.y;
+		outDestLine.p1.x = _bgDimensions._width;
+		outDestLine.p1.y = destPt.y;
+	} else if (rectDimensions._width == 0) {
+		outDestLine.p0.y = 0;
+		outDestLine.p0.x = destPt.x;
+		outDestLine.p1.x = destPt.x;
+		outDestLine.p1.y = _bgDimensions._height;
+	} else {
+		outDestLine.p0 = destPt;
+		outDestLine.p1.x = destPt.x + rectDimensions._width;
+		outDestLine.p1.y = destPt.y + rectDimensions._height;
+		int16 y1 = destPt.y + (rectDimensions._height * -destPt.x / rectDimensions._width);
+		int16 y2 = destPt.y + (rectDimensions._height * (_bgDimensions._width - destPt.x) / rectDimensions._width);
+		int16 x1 = destPt.x + (rectDimensions._width * -destPt.y / rectDimensions._height);
+		int16 x2 = destPt.x + (rectDimensions._width * (_bgDimensions._height - destPt.y) / rectDimensions._height);
+		if (ABS(rectDimensions._height) <= ABS(rectDimensions._width)) {
+			outDestLine.p0.y = 0;
+			outDestLine.p0.x = _bgDimensions._width;
+			if (x1 < 0 || _bgDimensions._width < x1)
+				outDestLine.p0.y = y2;
+			else
+				outDestLine.p0.x = x1;
+			outDestLine.p1.x = 0;
+			outDestLine.p1.y = _bgDimensions._height;
+			if (x2 < 0 || _bgDimensions._width < x2)
+				outDestLine.p1.y = y1;
+			else
+				outDestLine.p1.x = x2;
+		} else {
+			outDestLine.p0.y = 0;
+			outDestLine.p0.x = 0;
+			if (x1 < 0 || _bgDimensions._width < x1)
+				outDestLine.p0.y = y1;
+			else
+				outDestLine.p0.x = x1;
+			outDestLine.p1.x = _bgDimensions._width;
+			outDestLine.p1.y = _bgDimensions._height;
+			if (x2 < 0 || _bgDimensions._width < x2)
+				outDestLine.p1.y = y2;
+			else
+				outDestLine.p1.x = x2;
+		}
+	}
+}
+
+void PathFinder::findDeltaPt(Common::Point pt, Common::Point &outDeltaPt) {
+	static const struct { int16 x, y; } kDeltaPoints[] = {
+		{ 0, -4}, {0, 4}, {-4, 0}, { 4,  0}, {-3, -3}, {3, 3}, {-3, 3}, { 3, -3},
+		{-2, -4}, {2, 4}, {-2, 4}, { 2, -4}, {-4, -2}, {4, 2}, {-4, 2}, { 4, -2},
+		{-1, -4}, {1, 4}, {-1, 4}, { 1, -4}, {-4, -1}, {4, 1}, {-4, 1}, { 4, -1},
+		{-2, -3}, {2, 3}, {-2, 3}, { 2, -3}, {-3, -2}, {3, 2}, {-3, 2}, { 3, -2}
+	};
+	Common::Point testPt;
+	for (uint i = 0; i < 32; ++i) {
+		testPt.x = pt.x + kDeltaPoints[i].x;
+		testPt.y = pt.y + kDeltaPoints[i].y;
+		if (findValidDestLine(testPt)) {
+			outDeltaPt.x = kDeltaPoints[i].x;
+			outDeltaPt.y = kDeltaPoints[i].y;
+			break;
+		}
+	}
+}
+
+bool PathFinder::testRect(PathLine &line, PathLine &rect) {
+	return line.p0.x <= rect.p1.x && line.p1.x >= rect.p0.x &&
+		line.p0.y <= rect.p1.y && line.p1.y >= rect.p0.y;
+}
+
+void PathFinder::swapLine(PathLine &line, PathLine &outLine) {
+	if (line.p1.x <= line.p0.x) {
+		outLine.p1.x = line.p0.x;
+		outLine.p0.x = line.p1.x;
+	} else {
+		outLine.p0.x = line.p0.x;
+		outLine.p1.x = line.p1.x;
+	}
+	if (line.p1.y <= line.p0.y) {
+		outLine.p1.y = line.p0.y;
+		outLine.p0.y = line.p1.y;
+	} else {
+		outLine.p0.y = line.p0.y;
+		outLine.p1.y = line.p1.y;
+	}
+}
+
+int PathFinder::calcLineStatus(PathLine &sourceLine, PathLine &destRect, Common::Point *outPoint) {
+	PathLine sourceLine1, destRect1;
+	swapLine(sourceLine, sourceLine1);
+	swapLine(destRect, destRect1);
+
+	if (!testRect(sourceLine1, destRect1))
+		return 3;
+
+	int sourceDeltaX = sourceLine.p1.x - sourceLine.p0.x;
+	int sourceDeltaY = sourceLine.p1.y - sourceLine.p0.y;
+	int destDeltaX = destRect.p0.x - destRect.p1.x;
+	int destDeltaY = destRect.p0.y - destRect.p1.y;
+	int sdDeltaX = sourceLine.p0.x - destRect.p0.x;
+	int sdDeltaY = sourceLine.p0.y - destRect.p0.y;
+	int delta1 = destDeltaY * sdDeltaX - destDeltaX * sdDeltaY;
+	int delta2 = sourceDeltaY * destDeltaX - sourceDeltaX * destDeltaY;
+	int delta3 = sourceDeltaX * sdDeltaY - sourceDeltaY * sdDeltaX;
+
+	if ((delta2 <= 0 && (delta1 > 0 || delta2 > delta1)) ||
+		(delta2 > 0 && (delta1 < 0 || delta2 < delta1)) ||
+		(delta2 <= 0 && (delta3 > 0 || delta2 > delta3)) ||
+		(delta2 > 0 && (delta3 < 0 || delta2 < delta3)))
+		return 3;
+	
+	if (!outPoint)
+		return 1;
+
+	if (delta2 == 0)
+		return 2;
+
+	int v15 = sourceDeltaX * delta1, v18 = sourceDeltaY * delta1;
+	int v16, v17;
+	
+	if ((v15 >= 0 && delta2 >= 0) || (v15 < 0 && delta2 < 0)) {
+		v16 = delta2 / 2;
+		v17 = delta2 / 2;
+	} else if ((v15 < 0 && delta2 >= 0) || (v15 >= 0 && delta2 < 0)) {
+		v17 = delta2 / 2;
+		v16 = delta2 / -2;
+	}
+
+	outPoint->x = sourceLine.p0.x + (v15 + v16) / delta2;
+	
+	if ((v18 >= 0 && delta2 < 0) || (v18 < 0 && delta2 >= 0))
+		v17 = -v17;
+
+	outPoint->y = sourceLine.p0.y + (v18 + v17) / delta2;
+	
+	return 1;
+}
+
+} // End of namespace Illusions
diff --git a/engines/illusions/pathfinder.h b/engines/illusions/pathfinder.h
new file mode 100644
index 0000000000..ca402bb95d
--- /dev/null
+++ b/engines/illusions/pathfinder.h
@@ -0,0 +1,67 @@
+/* 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.
+ *
+ */
+
+#ifndef ILLUSIONS_PATHFINDER_H
+#define ILLUSIONS_PATHFINDER_H
+
+#include "illusions/graphics.h"
+#include "common/array.h"
+#include "common/list.h"
+#include "common/rect.h"
+
+namespace Illusions {
+
+struct PathLine {
+	Common::Point p0, p1;
+};
+
+typedef Common::Array<PathLine> PathLines;
+typedef Common::Array<Common::Point> PointArray;
+
+class PathFinder {
+public:
+	PointArray *findPath(Common::Point sourcePt, Common::Point destPt,
+		PointArray *walkPoints, PathLines *walkRects, WidthHeight bgDimensions);
+protected:
+	PointArray *_walkPoints;
+	PathLines *_walkRects;
+	WidthHeight _bgDimensions;
+	byte *_pathBytes;
+	PointArray *findPathInternal(Common::Point sourcePt, Common::Point destPt);
+	bool isLineBlocked(PathLine &line);
+	int calcLineDistance(PathLine &line);
+	bool findClosestPt(Common::Point &sourcePt, Common::Point &closestPt, Common::Point &destPt);
+	bool findValidDestLine(Common::Point &destPt);
+	void findValidDestPt(Common::Point &destPt);
+	WidthHeight calcRectDimensions(PathLine &rect);
+	void adjustRectDimensions(WidthHeight &dimensions);	
+	void swapDimensions(WidthHeight &dimensions);
+	void clipLineToBg(Common::Point &destPt, WidthHeight &rectDimensions, PathLine &outDestLine);
+	void findDeltaPt(Common::Point pt, Common::Point &outDeltaPt);
+	bool testRect(PathLine &line, PathLine &rect);
+	void swapLine(PathLine &line, PathLine &outLine);
+	int calcLineStatus(PathLine &sourceLine, PathLine &destRect, Common::Point *outPoint);
+};
+
+} // End of namespace Illusions
+
+#endif // ILLUSIONS_PATHFINDER_H
diff --git a/engines/illusions/scriptopcodes_duckman.cpp b/engines/illusions/scriptopcodes_duckman.cpp
index 1caf3b8bca..971a8eeb7e 100644
--- a/engines/illusions/scriptopcodes_duckman.cpp
+++ b/engines/illusions/scriptopcodes_duckman.cpp
@@ -200,7 +200,7 @@ void ScriptOpcodes_Duckman::opStartTimerThread(ScriptThread *scriptThread, OpCal
 		duration += _vm->getRandom(maxDuration);
 		
 //duration = 1;//DEBUG Speeds up things
-duration = 5;		
+duration = 5;
 		
 	if (isAbortable)
 		_vm->startAbortableTimerThread(duration, opCall._threadId);
@@ -244,7 +244,7 @@ void ScriptOpcodes_Duckman::opEnterScene18(ScriptThread *scriptThread, OpCall &o
 
 //static uint dsceneId = 0, dthreadId = 0;
 //static uint dsceneId = 0x00010008, dthreadId = 0x00020029;//Beginning in Jac
-static uint dsceneId = 0x00010012, dthreadId = 0x0002009D;//Paramount
+//static uint dsceneId = 0x00010012, dthreadId = 0x0002009D;//Paramount
 //static uint dsceneId = 0x00010039, dthreadId = 0x00020089;//Map
 //static uint dsceneId = 0x00010033, dthreadId = 0x000201A4;//Chinese
 //static uint dsceneId = 0x00010020, dthreadId = 0x00020112;//Xmas
@@ -252,8 +252,10 @@ static uint dsceneId = 0x00010012, dthreadId = 0x0002009D;//Paramount
 //static uint dsceneId = 0x0001002D, dthreadId = 0x00020141;
 //static uint dsceneId = 0x0001004B, dthreadId = 0x0002029B;
 //static uint dsceneId = 0x00010021, dthreadId = 0x00020113;
-//static uint dsceneId = 0x0001000A, dthreadId = 0x00020043;//Home front
+static uint dsceneId = 0x0001000A, dthreadId = 0x00020043;//Home front
 //static uint dsceneId = 0x0001000E, dthreadId = 0x0002007C;
+//static uint dsceneId = 0x00010022, dthreadId = 0x00020114;
+//static uint dsceneId = 0x0001003D, dthreadId = 0x000201E0;
 
 void ScriptOpcodes_Duckman::opChangeScene(ScriptThread *scriptThread, OpCall &opCall) {
 	ARG_SKIP(2);
@@ -645,7 +647,7 @@ void ScriptOpcodes_Duckman::opJumpIf(ScriptThread *scriptThread, OpCall &opCall)
 void ScriptOpcodes_Duckman::opIsPrevSceneId(ScriptThread *scriptThread, OpCall &opCall) {
 	ARG_SKIP(2);
 	ARG_UINT32(sceneId);
-	_vm->_stack->push(_vm->_prevSceneId == sceneId ? 1 : 0);
+	_vm->_stack->push(_vm->getPrevScene() == sceneId ? 1 : 0);
 }
 
 void ScriptOpcodes_Duckman::opNot(ScriptThread *scriptThread, OpCall &opCall) {
diff --git a/engines/illusions/sequenceopcodes.cpp b/engines/illusions/sequenceopcodes.cpp
index d508eeac20..7783972f4d 100644
--- a/engines/illusions/sequenceopcodes.cpp
+++ b/engines/illusions/sequenceopcodes.cpp
@@ -284,7 +284,7 @@ void SequenceOpcodes::opSetPathWalkPoints(Control *control, OpCall &opCall) {
 	ARG_INT16(pathWalkPointsIndex);
 	BackgroundResource *bgRes = _vm->_backgroundItems->getActiveBgResource();
 	control->_actor->_flags |= 2;
-	// TODO control->_actor->_pathWalkPoints = bgRes->getPathWalkPoints(pathWalkPointsIndex - 1);
+	control->_actor->_pathWalkPoints = bgRes->getPathWalkPoints(pathWalkPointsIndex - 1);
 }
 
 void SequenceOpcodes::opDisableAutoScale(Control *control, OpCall &opCall) {
@@ -315,7 +315,7 @@ void SequenceOpcodes::opSetPathWalkRects(Control *control, OpCall &opCall) {
 	ARG_INT16(pathWalkRectsIndex);
 	BackgroundResource *bgRes = _vm->_backgroundItems->getActiveBgResource();
 	control->_actor->_flags |= 0x0010;
-	// TODO control->_actor->_pathWalkRects = bgRes->getPathWalkRects(pathWalkRectsIndex - 1);
+	control->_actor->_pathWalkRects = bgRes->getPathWalkRects(pathWalkRectsIndex - 1);
 }
 
 void SequenceOpcodes::opSetPriority(Control *control, OpCall &opCall) {
diff --git a/engines/illusions/thread.cpp b/engines/illusions/thread.cpp
index 7ecc3d8606..6c6a7d6fa2 100644
--- a/engines/illusions/thread.cpp
+++ b/engines/illusions/thread.cpp
@@ -277,6 +277,14 @@ void ThreadList::endTalkThreadsNoNotify() {
 	}
 }
 
+void ThreadList::terminateThreadChain(uint32 threadId) {
+	while (threadId) {
+		Thread *thread = findThread(threadId);
+		thread->terminate();
+		threadId = thread->_callingThreadId;
+	}
+}
+
 void ThreadList::killThread(uint32 threadId) {
 
 	if (!threadId)
diff --git a/engines/illusions/thread.h b/engines/illusions/thread.h
index 3a335a27bf..996226dcf7 100644
--- a/engines/illusions/thread.h
+++ b/engines/illusions/thread.h
@@ -97,6 +97,7 @@ public:
 	void resumeThreads(uint32 threadId);
 	void endTalkThreads();
 	void endTalkThreadsNoNotify();
+	void terminateThreadChain(uint32 threadId);
 	void killThread(uint32 threadId);
 	void setThreadSceneId(uint32 threadId, uint32 sceneId);
 	uint32 getThreadSceneId(uint32 threadId);