From 22a6923e4cdaa07f0d644e75ee91b1fc5d90c30f Mon Sep 17 00:00:00 2001
From: =?utf8?q?Rafa=C5=82=20Rzepecki?= <divided.mind@gmail.com>
Date: Wed, 17 Sep 2008 07:38:42 +0200
Subject: [PATCH] Pathfinding (doesn't work, though.)

---
 engines/innocent/actor.cpp           | 71 +++++++++++++++++++++++++++++++++++-
 engines/innocent/actor.h             | 21 ++++++++++-
 engines/innocent/opcode_handlers.cpp |  4 +-
 3 files changed, 91 insertions(+), 5 deletions(-)

diff --git a/engines/innocent/actor.cpp b/engines/innocent/actor.cpp
index e65467d2d..72c50721b 100644
--- a/engines/innocent/actor.cpp
+++ b/engines/innocent/actor.cpp
@@ -1,5 +1,7 @@
 #include "innocent/actor.h"
 
+#include <sstream>
+
 #include "common/rect.h"
 
 #include "innocent/innocent.h"
@@ -92,6 +94,74 @@ void Actor::setFrame(uint16 frame) {
 	_position = f.position();
 }
 
+Common::List<Actor::Frame> Actor::findPath(Actor::Frame from, uint16 to) {
+	Common::List<Common::List<Frame> > reachable;
+
+	Common::List<Frame> zero;
+	zero.push_back(from);
+	reachable.push_back(zero);
+
+	bool found = false;
+	while (!found) {
+		Common::List<Common::List<Frame> >::iterator back = reachable.end();
+		back--;
+		Common::List<Frame>::iterator current = back->begin();
+		Common::List<Frame> next;
+		while (!found && current != back->end()) {
+			std::vector<byte> nexts = current->nexts();
+			for (int i = 0; i < 8; i++)
+				if (nexts[i]) {
+					next.push_back(Log.room()->getFrame(nexts[i]));
+					if (nexts[i] == to) {
+						found = true;
+						break;
+					}
+				}
+			current++;
+		}
+		reachable.push_back(next);
+	}
+
+	Common::List<Frame> path;
+
+	Common::List<Common::List<Frame> >::iterator level = reachable.end();
+	level--;
+	Common::List<Frame>::iterator current = level->end();
+	current--;
+	uint16 index = level->size() - 1;
+
+	forever {
+		path.push_front(*current);
+		if (*current == from)
+			break;
+		level--;
+		current = level->begin();
+		uint16 new_index = 0;
+		while (index >= current->nextCount()) {
+			index -= current->nextCount();
+			new_index++;
+			current++;
+		}
+		index = new_index;
+	}
+
+	return path;
+}
+
+void Actor::moveTo(uint16 frame) {
+	Frame cur = Log.room()->getFrame(_frame);
+	Common::List<Frame> path = findPath(cur, frame);
+
+	std::string pathspec;
+	std::ostringstream s(pathspec);
+	foreach(Frame, path) {
+		_framequeue.push(*it);
+		s << " " << it->index();
+	}
+
+	debugC(3, kDebugLevelActor, "found path: %s", pathspec.c_str());
+}
+
 void Actor::setRoom(uint16 r, uint16 frame, uint16 next_frame) {
 	_room = r;
 	unless (next_frame)
@@ -172,7 +242,6 @@ void Actor::animate() {
 
 Animation::Status Actor::tick() {
 	animate();
-
 	callBacks();
 
 	if (isFine()) {
diff --git a/engines/innocent/actor.h b/engines/innocent/actor.h
index 501912d39..5d7e4db2a 100644
--- a/engines/innocent/actor.h
+++ b/engines/innocent/actor.h
@@ -63,19 +63,34 @@ class Actor : public Animation {
 public:
 	class Frame {
 	public:
-		Frame() : _position(999, 999), _nexts(8) {}
-		Frame(Common::Point pos, std::vector<byte> n, uint16 i) : _position(pos), _nexts(n), _index(i) {}
+		Frame() : _position(999, 999), _nexts(8), _nextCount(0xff) {}
+		Frame(Common::Point pos, std::vector<byte> n, uint16 i) : _position(pos), _nexts(n), _index(i), _nextCount(0xff) {}
 
 		Common::Point position() const { return _position; }
 		const std::vector<byte> &nexts() const { return _nexts; }
 		const uint16 index() const { return _index; }
 
 		Direction operator-(const Frame &other) const;
+		bool operator==(const Frame &other) const {
+			return _index == other._index;
+		}
+		byte nextCount() const {
+			if (_nextCount == 0xff) {
+				byte ct = 0;
+				for (int i = 0; i < 8; i++)
+					if (_nexts[i])
+						ct++;
+				_nextCount = ct;
+			}
+
+			return _nextCount;
+		}
 
 	private:
 		uint16 _index;
 		Common::Point _position;
 		std::vector<byte> _nexts;
+		mutable byte _nextCount;
 	};
 
 	class Speech {
@@ -109,6 +124,8 @@ public:
 	};
 
 	void setFrame(uint16 f);
+	void moveTo(uint16 f);
+	static Common::List<Frame> findPath(Frame from, uint16 to);
 
 	uint16 room() const { return _room; }
 	void setRoom(uint16, uint16 frame = 0, uint16 nextFrame = 0);
diff --git a/engines/innocent/opcode_handlers.cpp b/engines/innocent/opcode_handlers.cpp
index 6c38e79f2..4892b7839 100644
--- a/engines/innocent/opcode_handlers.cpp
+++ b/engines/innocent/opcode_handlers.cpp
@@ -412,7 +412,7 @@ OPCODE(0xab) {
 		return kReturn;
 	}
 
-	ac->setFrame(a[0]);
+	ac->moveTo(a[0]);
 	return kThxBye;
 }
 
@@ -457,7 +457,7 @@ OPCODE(0xbd) {
 OPCODE(0xc2) {
 	// add animation at cursor
 	debugC(3, kDebugLevelScript, "opcode 0xc2: add animation %s at cursor partial STUB", +a[0]);
-	_logic->addAnimation(new Animation(static_cast<CodePointer &>(a[0]), _graphics->cursorPosition()));
+//	_logic->addAnimation(new Animation(static_cast<CodePointer &>(a[0]), _graphics->cursorPosition()));
 	return kThxBye;
 }
 
-- 
2.11.4.GIT