6 files changed, 406 insertions, 9 deletions
diff --git a/engines/pink/objects/walk/walk_location.cpp b/engines/pink/objects/walk/walk_location.cpp
index e5f5ea7535..c4b56d95db 100644
--- a/engines/pink/objects/walk/walk_location.cpp
+++ b/engines/pink/objects/walk/walk_location.cpp
@@ -20,10 +20,23 @@
  *
  */
 
+#include <common/debug.h>
 #include "walk_location.h"
 #include "engines/pink/archive.h"
 
-void Pink::WalkLocation::deserialize(Pink::Archive &archive) {
+namespace Pink {
+
+void WalkLocation::deserialize(Pink::Archive &archive) {
     NamedObject::deserialize(archive);
     archive >> _neighbors;
 }
+
+void WalkLocation::toConsole() {
+    debug("\tWalkLocation: _name =%s", _name.c_str());
+    debug("\tNeighbors:");
+    for (int i = 0; i < _neighbors.size(); ++i) {
+        debug("\t\t%s", _neighbors[i].c_str());
+    }
+}
+
+} // End of namespace Pink;
+\ No newline at end of file
diff --git a/engines/pink/objects/walk/walk_location.h b/engines/pink/objects/walk/walk_location.h
index 82e6436b77..b9515cdc10 100644
--- a/engines/pink/objects/walk/walk_location.h
+++ b/engines/pink/objects/walk/walk_location.h
@@ -33,6 +33,8 @@ class WalkLocation : public NamedObject {
 public:
     virtual void deserialize(Archive &archive);
 
+    void toConsole() override;
+    Common::StringArray &getNeigbors() { return _neighbors;}
 private:
     Common::StringArray _neighbors;
 };
diff --git a/engines/pink/objects/walk/walk_mgr.cpp b/engines/pink/objects/walk/walk_mgr.cpp
index 1b5ceef210..0cacbd07f6 100644
--- a/engines/pink/objects/walk/walk_mgr.cpp
+++ b/engines/pink/objects/walk/walk_mgr.cpp
@@ -1,20 +1,153 @@
-//
-// Created by andrei on 3/17/18.
-//
+/* 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 "walk_mgr.h"
 #include "walk_location.h"
+#include "engines/pink/objects/actions/walk_action.h"
 #include "engines/pink/objects/actors/lead_actor.h"
 #include "engines/pink/archive.h"
+#include "pink/cel_decoder.h"
 
+namespace Pink {
 
-void Pink::WalkMgr::deserialize(Pink::Archive &archive) {
-    _leadActor = static_cast<LeadActor*>(archive.readObject());
+WalkMgr::WalkMgr()
+    : _isWalking(false), _leadActor(nullptr)
+{
+
+}
+
+void WalkMgr::deserialize(Pink::Archive &archive) {
+    _leadActor = static_cast<LeadActor *>(archive.readObject());
     archive >> _locations;
 }
 
-Pink::WalkLocation *Pink::WalkMgr::findLocation(Common::String &name) {
-    return *Common::find_if(_locations.begin(), _locations.end(), [&name] (WalkLocation *location) {
+WalkLocation *WalkMgr::findLocation(const Common::String &name) {
+    auto it = Common::find_if(_locations.begin(), _locations.end(), [&name](WalkLocation *location) {
         return location->getName() == name;
     });
+    if (it == _locations.end())
+        return nullptr;
+
+    return *it;
+}
+
+void WalkMgr::toConsole() {
+    debug("WalkMgr:");
+    for (int i = 0; i < _locations.size(); ++i) {
+        _locations[i]->toConsole();
+    }
+}
+
+void WalkMgr::start(WalkLocation *destination) {
+    if (_isWalking)
+        return;
+
+    if (_current.name.empty()) {
+        _current.name = _locations[0]->getName();
+        _current.coord = getLocationCoordinates(_locations[0]->getName());
+    }
+
+    _destination = destination;
+
+    if (_current.name == _destination->getName()) {
+        end();
+    }
+    else {
+        _isWalking = true;
+        WalkLocation *currentLocation = findLocation(_current.name);
+        WalkShortestPath path(this);
+        WalkLocation *nextLocation = path.next(currentLocation, _destination);
+        initNextWayPoint(nextLocation);
+        _leadActor->setAction(getWalkAction(), 0);
+    }
+}
+
+void WalkMgr::initNextWayPoint(WalkLocation *location) {
+    _next.name = location->getName();
+    _next.coord = getLocationCoordinates(location->getName());
+}
+
+WalkAction *WalkMgr::getWalkAction() {
+    Common::String walkActionName;
+    if (_current.coord.z == _next.coord.z){
+        if (_next.coord.x > _current.coord.x){
+            walkActionName = Common::String::format("%dRight", _current.coord.z);
+        }
+        else walkActionName = Common::String::format("%dLeft", _next.coord.z);
+    }
+    else walkActionName = Common::String::format("%dTo%d", _current.coord.z, _next.coord.z);
+
+    Action *action = _leadActor->findAction(walkActionName);
+
+
+    return static_cast<WalkAction*>(action);
 }
+
+double WalkMgr::getLengthBetweenLocations(WalkLocation *first, WalkLocation *second) {
+    Coordinates firstCoord = getLocationCoordinates(first->getName());
+    Coordinates secondCoord = getLocationCoordinates(second->getName());
+    return sqrt((secondCoord.x - firstCoord.x) * (secondCoord.x - firstCoord.x) +
+                (secondCoord.y - firstCoord.y) * (secondCoord.y - firstCoord.y));
+}
+
+WalkMgr::Coordinates WalkMgr::getLocationCoordinates(const Common::String &locationName) {
+    Coordinates coords;
+    ActionCEL *action  = static_cast<ActionCEL*>(_leadActor->findAction(locationName));
+
+    action->start(0);
+    CelDecoder *decoder = action->getDecoder();
+
+    coords.x = decoder->getX() + decoder->getWidth() / 2;
+    coords.y = decoder->getY() + decoder->getHeight() / 2;
+    coords.z = action->getZ();
+
+    action->end();
+
+    return coords;
+}
+
+void WalkMgr::setCurrentWayPoint(WalkLocation *location) {
+    _current.name = location->getName();
+    _current.coord = getLocationCoordinates(_current.name);
+}
+
+void WalkMgr::update() {
+    if (_leadActor->isPlaying())
+        return;
+
+    WalkShortestPath path(this);
+    _current = _next;
+    WalkLocation *next = path.next(findLocation(_current.name), _destination);
+    if (next){
+        initNextWayPoint(next);
+        _leadActor->setAction(getWalkAction(), 0);
+    }
+    else end();
+
+}
+
+void WalkMgr::end() {
+    _isWalking = false;
+     _leadActor->onWalkEnd();
+}
+
+} // End of namespace Pink
+\ No newline at end of file
diff --git a/engines/pink/objects/walk/walk_mgr.h b/engines/pink/objects/walk/walk_mgr.h
index 0ae7ef6194..403cc7ee2e 100644
--- a/engines/pink/objects/walk/walk_mgr.h
+++ b/engines/pink/objects/walk/walk_mgr.h
@@ -25,20 +25,49 @@
 
 #include <common/array.h>
 #include "engines/pink/objects/object.h"
+#include "walk_shortest_path.h"
 
 namespace Pink {
 
 class WalkLocation;
 class LeadActor;
+class WalkAction;
 
 class WalkMgr : public Object {
 public:
+    WalkMgr();
     virtual void deserialize(Archive &archive);
-    WalkLocation *findLocation(Common::String &name);
+    void toConsole() override;
+
+    WalkLocation *findLocation(const Common::String &name);
+    void start(WalkLocation *destination);
+    void update();
+
+    double getLengthBetweenLocations(WalkLocation *first, WalkLocation *second);
+    void setCurrentWayPoint(WalkLocation *location);
 
 private:
+    struct Coordinates {
+        int x;
+        int y;
+        int z;
+    };
+    struct WayPoint {
+        Common::String name;
+        Coordinates coord;
+    };
+
+    Coordinates getLocationCoordinates(const Common::String &locationName);
+    void end();
+    void initNextWayPoint(WalkLocation *location);
+    WalkAction *getWalkAction();
+
     LeadActor *_leadActor;
+    WalkLocation *_destination;
     Common::Array<WalkLocation*> _locations;
+    WayPoint _current;
+    WayPoint _next;
+    bool _isWalking;
 };
 
 } // End of namespace Pink
diff --git a/engines/pink/objects/walk/walk_shortest_path.cpp b/engines/pink/objects/walk/walk_shortest_path.cpp
new file mode 100644
index 0000000000..77562e81cb
--- /dev/null
+++ b/engines/pink/objects/walk/walk_shortest_path.cpp
@@ -0,0 +1,159 @@
+/* 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 "walk_shortest_path.h"
+#include "walk_mgr.h"
+#include "walk_location.h"
+
+namespace Pink {
+
+WalkShortestPath::WalkShortestPath(WalkMgr *manager)
+    : _manager(manager)
+{}
+
+WalkLocation *WalkShortestPath::next(WalkLocation *start, WalkLocation *destination) {
+    if (start == destination)
+        return nullptr;
+    add(start, 0.0, 0);
+    while (build() != destination);
+    return getNearestNeighbor(destination);
+}
+
+void WalkShortestPath::add(WalkLocation *wl, double val, WalkLocation *nearest) {
+    _locations.push_back(wl);
+    _visited.push_back(wl);
+    _weight.push_back(val);
+    _nearestNeigbor.push_back(nearest);
+}
+
+WalkLocation *WalkShortestPath::build() {
+    WalkLocation *nearest = nullptr;
+    WalkLocation *location = nullptr;
+    double len = -1.0;
+    addLocationsToVisit();
+    for (int i = 0; i < _toVisit.size(); ++i) {
+        double curLen = getLengthToNearestNeigbor(_toVisit[i]);
+        if (curLen < 0) {
+            remove(_toVisit[i]);
+            continue;
+        }
+        curLen += getWeight(_toVisit[i]);
+        if (len < 0.0 || len > curLen) {
+            len = curLen;
+            location = _toVisit[i];
+            nearest = getNearestNeighbor(_toVisit[i]);
+            if (!nearest)
+                nearest = findNearestNeighbor(_toVisit[i]);
+        }
+    }
+
+    WalkLocation *neighbor = findNearestNeighbor(location);
+    if (neighbor)
+        add(neighbor, len, nearest);
+
+    return neighbor;
+}
+
+WalkLocation *WalkShortestPath::getNearestNeighbor(WalkLocation *location) {
+    for(int i = 0; i < _visited.size(); ++i){
+        if (_visited[i] == location)
+            return _nearestNeigbor[i];
+    }
+
+    return nullptr;
+}
+
+void WalkShortestPath::addLocationsToVisit() {
+    _toVisit.resize(_locations.size());
+    for (int i = 0; i < _locations.size(); ++i) {
+        _toVisit[i] = _locations[i];
+    }
+}
+
+double WalkShortestPath::getLengthToNearestNeigbor(WalkLocation *location) {
+    double minLength = -1.0;
+    auto &neighbors = location->getNeigbors();
+    for (int i = 0; i < neighbors.size(); ++i) {
+        WalkLocation *neighbor = _manager->findLocation(neighbors[i]);
+        if (!isLocationVisited(neighbor)){
+            double length = _manager->getLengthBetweenLocations(location, neighbor);
+            if (minLength >= 0.0) {
+                if (length < minLength)
+                    minLength = length;
+            }
+            else minLength = length;
+        }
+    }
+
+    return minLength;
+}
+
+WalkLocation *WalkShortestPath::findNearestNeighbor(WalkLocation *location) {
+    double minLength = -1.0;
+    WalkLocation *nearest = nullptr;
+    auto neighbors = location->getNeigbors();
+    for (int i = 0; i < neighbors.size(); ++i) {
+        WalkLocation *neighbor = _manager->findLocation(neighbors[i]);
+        if (!isLocationVisited(neighbor)){
+            double length = _manager->getLengthBetweenLocations(location, neighbor);
+            if (minLength >= 0.0) {
+                if (length < minLength) {
+                    nearest = neighbor;
+                    minLength = length;
+                }
+            }
+            else {
+                nearest = neighbor;
+                minLength = length;
+            }
+        }
+    }
+
+    return nearest;
+}
+
+double WalkShortestPath::getWeight(WalkLocation *location) {
+    for (int i = 0; i < _locations.size(); ++i) {
+        if (_locations[i] == location)
+            return _weight[i];
+    }
+    return 0.0;
+}
+
+bool WalkShortestPath::isLocationVisited(WalkLocation *location) {
+    for (int i = 0; i < _visited.size(); ++i) {
+        if (_visited[i] == location)
+            return 1;
+    }
+    return 0;
+}
+
+void WalkShortestPath::remove(WalkLocation *location) {
+    for (int i = 0; i < _locations.size(); ++i) {
+        if (_locations[i] == location){
+            _locations.remove_at(i);
+            _weight.remove_at(i);
+        }
+    }
+}
+
+} // End of namespace Pink
+\ No newline at end of file
diff --git a/engines/pink/objects/walk/walk_shortest_path.h b/engines/pink/objects/walk/walk_shortest_path.h
new file mode 100644
index 0000000000..8b7dc803b4
--- /dev/null
+++ b/engines/pink/objects/walk/walk_shortest_path.h
@@ -0,0 +1,61 @@
+/* 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 PINK_WALK_SHORTEST_PATH_H
+#define PINK_WALK_SHORTEST_PATH_H
+
+#include <common/array.h>
+
+namespace Pink {
+
+class WalkLocation;
+class WalkMgr;
+
+class WalkShortestPath {
+public:
+    WalkShortestPath(WalkMgr *manager);
+    WalkLocation *next(WalkLocation *start, WalkLocation *destination);
+
+private:
+    void add(WalkLocation *wl, double val, WalkLocation *nearest);
+    void remove(WalkLocation *location);
+    WalkLocation *build();
+    WalkLocation *getNearestNeighbor(WalkLocation *location);
+    WalkLocation *findNearestNeighbor(WalkLocation *location);
+    double getLengthToNearestNeigbor(WalkLocation *location);
+    double getWeight(WalkLocation *location);
+    void addLocationsToVisit();
+    bool isLocationVisited(WalkLocation *location);
+
+
+    WalkMgr *_manager;
+    Common::Array<WalkLocation*> _locations;
+    Common::Array<WalkLocation*> _toVisit;
+    Common::Array<double> _weight;
+    Common::Array<WalkLocation*> _visited;
+    Common::Array<WalkLocation*> _nearestNeigbor;
+};
+
+} // End of namespace Pink
+
+
+#endif