CGE: In progress work on pathfinder

6 files changed, 122 insertions, 66 deletions

diff --git a/engines/cge/cge.h b/engines/cge/cge.h
index 7dd218e258..dc757ec5a0 100644
--- a/engines/cge/cge.h
+++ b/engines/cge/cge.h
@@ -142,7 +142,6 @@ public:
 	void trouble(int seq, int txt);
 	void offUse();
 	void tooFar();
-	void noWay();
 	void loadHeroXY();
 	void keyClick();
 	void switchColorMode();
diff --git a/engines/cge/cge_main.cpp b/engines/cge/cge_main.cpp
index 0e2bcc451c..f532bd05e8 100644
--- a/engines/cge/cge_main.cpp
+++ b/engines/cge/cge_main.cpp
@@ -241,12 +241,6 @@ void CGEEngine::tooFar() {
 	trouble(TOO_FAR, TOO_FAR_TEXT);
 }
 
-// Used in stubbed function, do not remove!
-void CGEEngine::noWay() {
-	trouble(NO_WAY, NO_WAY_TEXT);
-}
-
-
 void CGEEngine::loadHeroXY() {
 	INI_FILE cf(progName(".HXY"));
 	memset(_heroXY, 0, sizeof(_heroXY));
diff --git a/engines/cge/cge_main.h b/engines/cge/cge_main.h
index bd57bd64bd..40e6d88668 100644
--- a/engines/cge/cge_main.h
+++ b/engines/cge/cge_main.h
@@ -92,7 +92,6 @@ namespace CGE {
 #define STD_DELAY      3
 #define LEV_MAX        5
 #define CAVE_MAX       (CAVE_NX * CAVE_NY)
-#define MAX_FIND_LEVEL 3
 #define MAX_DISTANCE   3
 #define INI_EXT        ".INI"
 #define IN0_EXT        ".IN0"
diff --git a/engines/cge/general.h b/engines/cge/general.h
index b4f73726ee..0639fe2a01 100644
--- a/engines/cge/general.h
+++ b/engines/cge/general.h
@@ -49,46 +49,6 @@ struct Dac {
 
 typedef uint16  CRYPT(void *buf, uint16 siz, uint16 seed);
 
-class Couple {
-protected:
-	signed char _a;
-	signed char _b;
-public:
-	Couple() { }
-	Couple(const signed char a, const signed char b) : _a(a), _b(b) { }
-	Couple operator + (Couple c) {
-		return Couple(_a + c._a, _b + c._b);
-	}
-
-	void operator += (Couple c) {
-		_a += c._a;
-		_b += c._b;
-	}
-
-	Couple operator - (Couple c) {
-		return Couple(_a - c._a, _b - c._b);
-	}
-
-	void operator -= (Couple c) {
-		_a -= c._a;
-		_b -= c._b;
-	}
-
-	bool operator == (Couple c) {
-		return ((_a - c._a) | (_b - c._b)) == 0;
-	}
-
-	bool operator != (Couple c) {
-		return !(operator == (c));
-	}
-
-	void split(signed char &a, signed char &b) {
-		a = _a;
-		b = _b;
-	}
-};
-
-
 class Engine_ {
 protected:
 	static void (* oldTimer)(...);
diff --git a/engines/cge/walk.cpp b/engines/cge/walk.cpp
index fc2ed277db..e33638b958 100644
--- a/engines/cge/walk.cpp
+++ b/engines/cge/walk.cpp
@@ -48,8 +48,10 @@
 namespace CGE {
 
 WALK *_hero;
-Cluster Trace[MAX_FIND_LEVEL];
-int FindLevel;
+
+struct TabDir {
+	int xd, yd;
+};
 
 uint8 Cluster::_map[MAP_ZCNT][MAP_XCNT];
 
@@ -58,6 +60,9 @@ uint8 &Cluster::cell() {
 	return _map[_b][_a];
 }
 
+bool Cluster::isValid() const {
+	return (_a >= 0) && (_a < MAP_XCNT) && (_b >= 0) && (_b < MAP_ZCNT);
+}
 
 bool Cluster::Protected() {
 /*
@@ -148,12 +153,12 @@ void WALK::tick() {
 	if (_flags._hold || _tracePtr < 0)
 		park();
 	else {
-		if (_here == Trace[_tracePtr]) {
+		if (_here == _trace[_tracePtr]) {
 			if (--_tracePtr < 0)
 				park();
 		} else {
 			signed char dx, dz;
-			(Trace[_tracePtr] - _here).split(dx, dz);
+			(_trace[_tracePtr] - _here).split(dx, dz);
 			DIR d = (dx) ? ((dx > 0) ? EE : WW) : ((dz > 0) ? SS : NN);
 			turn(d);
 		}
@@ -215,26 +220,23 @@ void WALK::park() {
 
 
 void WALK::findWay(Cluster c) {
-	/*
-	bool Find1Way();
-	extern uint16 Target;
-
 	if (c != _here) {
-		for (FindLevel = 1; FindLevel <= MAX_FIND_LEVEL; FindLevel++) {
+		_level = 0;
+
+		for (_findLevel = 1; _findLevel <= MAX_FIND_LEVEL; _findLevel++) {
 			signed char x, z;
 			_here.split(x, z);
-			Target = (z << 8) | x;
+			_target = (z << 8) | x;
 			c.split(x, z);
-			_CX = (z << 8) | x;
-			if (Find1Way())
+
+			if (find1Way(XZ(x, z)))
 				break;
 		}
-		_tracePtr = (FindLevel > MAX_FIND_LEVEL) ? -1 : (FindLevel - 1);
+		_tracePtr = (_findLevel > MAX_FIND_LEVEL) ? -1 : (_findLevel - 1);
 		if (_tracePtr < 0)
-			NoWay();
-		Time = 1;
+			noWay();
+		_time = 1;
 	}
-	*/
 }
 
 
@@ -278,4 +280,59 @@ void WALK::reach(Sprite *spr, int mode) {
 	// now it is just at sprite appear (disappear) point
 }
 
+void WALK::noWay() {
+	_vm->trouble(NO_WAY, NO_WAY_TEXT);
+}
+
+bool WALK::find1Way(Cluster c) {
+	Cluster start = c;
+	const Cluster tab[4] = { Cluster(-1, 0), Cluster(1, 0), Cluster(0, -1), Cluster(0, 1)};
+	const int tabLen = 4;
+
+	if (c == _here)
+		// Found destination
+		return true;
+
+	if (_level >= _findLevel)
+		// Nesting limit
+		return false;
+
+	// Look for barriers
+	if (c.Protected())
+		return false;
+
+	if (c.cell())
+		// Location is occupied
+		return false;
+
+
+	// Loop through each direction
+	for (int i = 0; i < tabLen; ++i) {
+		// Reset to starting position
+		c = start;
+
+		do {
+			c += tab[i];
+			if (!c.isValid())
+				// Break to check next direction
+				break;
+
+			// Recursively check for further paths
+			++_level;
+			++c.cell();
+			bool foundPath = find1Way(c);
+			--c.cell();
+			--_level;
+
+			if (foundPath) {
+				// Set route point
+				_trace[_level] = start;
+				return true;
+			}
+		} while (c.Protected() && !c.cell());
+	}
+
+	return false;
+}
+
 } // End of namespace CGE
diff --git a/engines/cge/walk.h b/engines/cge/walk.h
index 4573816bb4..30eb727e2c 100644
--- a/engines/cge/walk.h
+++ b/engines/cge/walk.h
@@ -40,7 +40,46 @@ namespace CGE {
 #define MAP_HIG        80
 #define MAP_XGRID      (SCR_WID / MAP_XCNT)
 #define MAP_ZGRID      (MAP_HIG / MAP_ZCNT)
+#define MAX_FIND_LEVEL 3
 
+class Couple {
+protected:
+	signed char _a;
+	signed char _b;
+public:
+	Couple() { }
+	Couple(const signed char a, const signed char b) : _a(a), _b(b) { }
+	Couple operator + (Couple c) {
+		return Couple(_a + c._a, _b + c._b);
+	}
+
+	void operator += (Couple c) {
+		_a += c._a;
+		_b += c._b;
+	}
+
+	Couple operator - (Couple c) {
+		return Couple(_a - c._a, _b - c._b);
+	}
+
+	void operator -= (Couple c) {
+		_a -= c._a;
+		_b -= c._b;
+	}
+
+	bool operator == (const Couple &c) {
+		return ((_a - c._a) | (_b - c._b)) == 0;
+	}
+
+	bool operator != (Couple c) {
+		return !(operator == (c));
+	}
+
+	void split(signed char &a, signed char &b) {
+		a = _a;
+		b = _b;
+	}
+};
 
 class Cluster : public Couple {
 public:
@@ -49,13 +88,21 @@ public:
 	Cluster() : Couple() { }
 	Cluster(int a, int b) : Couple(a, b) { }
 	bool Protected();
+	bool isValid() const;
+
 };
 
 
 class WALK : public Sprite {
+private:
+	CGEEngine *_vm;
 public:
 	Cluster _here;
 	int _tracePtr;
+	int _level;
+	int _findLevel;
+	int _target;
+	Cluster _trace[MAX_FIND_LEVEL];
 
 	enum DIR { NO_DIR = -1, NN, EE, SS, WW } Dir;
 	WALK(CGEEngine *vm, BMP_PTR *shpl);
@@ -67,9 +114,9 @@ public:
 	void park();
 	bool lower(Sprite *spr);
 	void reach(Sprite *spr, int mode = -1);
-private:
-	CGEEngine *_vm;
 
+	void noWay();
+	bool find1Way(Cluster c);
 };
 
 Cluster XZ(int x, int y);