From f0d10b62b37b7d3e35ebcd989745a2d0a9570a21 Mon Sep 17 00:00:00 2001 From: Paul Gilbert Date: Thu, 14 Jul 2011 22:36:18 +1000 Subject: CGE: In progress work on pathfinder --- engines/cge/cge.h | 1 - engines/cge/cge_main.cpp | 6 ---- engines/cge/cge_main.h | 1 - engines/cge/general.h | 40 ---------------------- engines/cge/walk.cpp | 89 +++++++++++++++++++++++++++++++++++++++--------- engines/cge/walk.h | 51 +++++++++++++++++++++++++-- 6 files changed, 122 insertions(+), 66 deletions(-) (limited to 'engines') 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); -- cgit v1.2.3