added original-like pathfinding.

svn-id: r46244

4 files changed, 156 insertions, 182 deletions

diff --git a/engines/teenagent/actor.cpp b/engines/teenagent/actor.cpp
index 49f283f48c..77bec914c5 100644
--- a/engines/teenagent/actor.cpp
+++ b/engines/teenagent/actor.cpp
@@ -69,8 +69,8 @@ Common::Rect Actor::render(Graphics::Surface *surface, const Common::Point &posi
 	}
 	int dx, dy;
 	switch (orientation) {
-	case Object::kActorLeft:
-	case Object::kActorRight:
+	case kActorLeft:
+	case kActorRight:
 		if (render_head) {
 			if (head_index >= sizeof(frames_head_left_right))
 				head_index = 0;
@@ -84,7 +84,7 @@ Common::Rect Actor::render(Graphics::Surface *surface, const Common::Point &posi
 		dx = 11;
 		dy = 62;
 		break;
-	case Object::kActorUp:
+	case kActorUp:
 		if (render_head) {
 			if (head_index >= sizeof(frames_head_up))
 				head_index = 0;
@@ -98,7 +98,7 @@ Common::Rect Actor::render(Graphics::Surface *surface, const Common::Point &posi
 		dx = 11;
 		dy = 62;
 		break;
-	case Object::kActorDown:
+	case kActorDown:
 		if (render_head) {
 			if (head_index >= sizeof(frames_head_down))
 				head_index = 0;
@@ -137,10 +137,10 @@ Common::Rect Actor::render(Graphics::Surface *surface, const Common::Point &posi
 	if (yp + clip.top + clip.height() > 200)
 		yp = 200 - clip.top - clip.height();
 	
-	dirty = s->render(surface, xp, yp + clip.top, orientation == Object::kActorLeft, clip, zoom);
+	dirty = s->render(surface, xp, yp + clip.top, orientation == kActorLeft, clip, zoom);
 
 	if (head != NULL)
-		dirty.extend(head->render(surface, xp, yp, orientation == Object::kActorLeft, Common::Rect(), zoom));
+		dirty.extend(head->render(surface, xp, yp, orientation == kActorLeft, Common::Rect(), zoom));
 
 	return dirty;
 }
diff --git a/engines/teenagent/objects.cpp b/engines/teenagent/objects.cpp
index 81d1c96293..e7f3c78666 100644
--- a/engines/teenagent/objects.cpp
+++ b/engines/teenagent/objects.cpp
@@ -150,8 +150,8 @@ void UseHotspot::dump() const {
 void Walkbox::dump() const {
 	debug(0, "walkbox %02x %02x [%d, %d, %d, %d] top: %u, right: %u, bottom: %u, left: %u",
 		type, orientation,
-		rect.left, rect.right, rect.top, rect.bottom,
-		top_side_hint, right_side_hint, bottom_side_hint, left_side_hint);
+		rect.left, rect.top, rect.right, rect.bottom,
+		side_hint[0], side_hint[1], side_hint[2], side_hint[3]);
 }
 
 void Walkbox::load(byte *src) {
@@ -161,10 +161,8 @@ void Walkbox::load(byte *src) {
 	orientation = *src++;
 	rect.load(src);
 	src += 8;
-	top_side_hint = *src++;
-	right_side_hint = *src++;
-	bottom_side_hint = *src++;
-	left_side_hint = *src++;
+	for(byte i = 0; i < 4; ++i)
+		side_hint[i] = *src++;
 }
 
 void Walkbox::save() const {
diff --git a/engines/teenagent/objects.h b/engines/teenagent/objects.h
index 7a74cbddad..19978a01cf 100644
--- a/engines/teenagent/objects.h
+++ b/engines/teenagent/objects.h
@@ -31,6 +31,8 @@
 
 namespace TeenAgent {
 
+enum {kActorUp = 1, kActorRight = 2, kActorDown = 3, kActorLeft = 4 };
+
 struct Rect {
 	int16 left, top, right, bottom;
 
@@ -79,18 +81,75 @@ struct Rect {
 		return rect.left >= left && rect.right <= right && rect.top >= top && rect.bottom <= bottom;
 	}
 	
-	inline Common::Point closest_to(const Common::Point & src) const {
-		Common::Point p(src);
-		if (p.x < left)
-			p.x = left;
-		if (p.x > right)
-			p.x = right;
-
-		if (p.y < top)
-			p.y = top;
-		if (p.y > bottom)
-			p.y = bottom;
-		return p;
+	static inline bool inside(int x, int a, int b) {
+		if (a > b)
+			SWAP(a, b);
+		return x >= a && x <= b;
+	}
+	
+	int intersects_line(const Common::Point &a, const Common::Point &b) const {
+		int dy = b.y - a.y, dx = b.x - a.x;
+
+		int mask = 0; //orientation bitmask: 1 - top, 2 - right, 3 - bottom, 4 - left
+		
+		if (dx != 0) {
+			int yl = (left - a.x) * dy / dx + a.y;
+			if (yl > top && yl < bottom && inside(yl, a.y, b.y)) {
+				//c[idx++] = Common::Point(left, yl);
+				mask |= 8;
+			}
+			int yr = (right - a.x) * dy / dx + a.y;
+			if (yr > top && yr < bottom && inside(yr, a.y, b.y)) {
+				//c[idx++] = Common::Point(right, yr);
+				mask |= 2;
+			}
+		} 
+		
+		if (dy != 0) {
+			int xt = (top - a.y) * dx / dy + a.x;
+			if (xt > left && xt < right && inside(xt, a.x, b.x)) {
+				//assert(idx < 2);
+				//c[idx++] = Common::Point(xt, top);
+				mask |= 1;
+			}
+			int xb = (bottom - a.y) * dx / dy + a.x;
+			if (xb > left && xb < right && inside(xb, a.x, b.x)) {
+				//assert(idx < 2);
+				//c[idx++] = Common::Point(xb, bottom);
+				mask |= 4;
+			}
+		}
+		return mask;
+	}
+	
+	void side(Common::Point &p1, Common::Point &p2, int o, const Common::Point &nearest) const {
+		switch(o) {
+		case kActorLeft:
+			p1 = Common::Point(left, top);
+			p2 = Common::Point(left, bottom);
+			break;
+
+		case kActorRight:
+			p1 = Common::Point(right, top);
+			p2 = Common::Point(right, bottom);
+			break;
+
+		case kActorUp:
+			p1 = Common::Point(left, top);
+			p2 = Common::Point(right, top);
+			break;
+
+		case kActorDown:
+			p1 = Common::Point(left, bottom);
+			p2 = Common::Point(right, bottom);
+			break;
+		
+		default:
+			p1 = Common::Point();
+			p2 = Common::Point();
+		}
+		if (p1.sqrDist(nearest) >= p2.sqrDist(nearest)) 
+			SWAP(p1, p2);
 	}
 
 protected:
@@ -98,7 +157,6 @@ protected:
 };
 
 struct Object {
-	enum {kActorUp = 1, kActorRight = 2, kActorDown = 3, kActorLeft = 4 };
 
 	byte id; //0
 	Rect rect; //1
@@ -146,10 +204,7 @@ struct Walkbox {
 	byte type;
 	byte orientation;
 	Rect rect;
-	byte top_side_hint;
-	byte right_side_hint;
-	byte bottom_side_hint;
-	byte left_side_hint;
+	byte side_hint[4];
 
 	Walkbox() : _base(NULL) {}
 	void dump() const;
diff --git a/engines/teenagent/scene.cpp b/engines/teenagent/scene.cpp
index 551566facc..56df743e14 100644
--- a/engines/teenagent/scene.cpp
+++ b/engines/teenagent/scene.cpp
@@ -36,7 +36,7 @@ namespace TeenAgent {
 Scene::Scene() : intro(false), _engine(NULL),
 		_system(NULL),
 		_id(0), ons(0),
-		orientation(Object::kActorRight), actor_talking(false), 
+		orientation(kActorRight), actor_talking(false), 
 		message_timer(0), message_first_frame(0), message_last_frame(0), message_animation(NULL), 
 		current_event(SceneEvent::kNone), hide_actor(false), callback(0), callback_timer(0) {}
 
@@ -48,159 +48,88 @@ void Scene::warp(const Common::Point &_point, byte o) {
 		orientation = o;
 }
 
-struct Splitter {
-	typedef Common::List<int> ListType;
-	ListType values;
-	uint _size;
-	
-	Splitter(): values(), _size(0) {}
-	
-	void insert(int v) {
-		ListType::iterator i;
-		for(i = values.begin(); i != values.end(); ++i) {
-			if (v == *i)
-				return;
-			
-			if (v < *i)
-				break;
-		}
-		values.insert(i, v);
-		++_size;
-	}
-	uint size() const { return _size; }
-};
-
-struct Node {
-	Rect rect;
-	int step;
-	int prev;
-
-	Node(): step(0), prev(0) {}
-};
-
-
-static void search(Node *nodes, int n, int m, int i, int j, int prev_idx, int end, int level) {
-	if (i < 0 || i >= n || j < 0 || j >= m)
-		return;
-	int idx = j + i * m;
-	int v = nodes[idx].step;
-	//debug(1, "search (%d, %d) %d, value = %d", i, j, level, v);
-	if (v != 0 && (v == -1 || v <= level))
-		return;
-
-	
-	nodes[idx].step = level; //mark as visited
-	nodes[idx].prev = prev_idx;
-
-	++level;
-	
-	search(nodes, n, m, i - 1, j, idx, end, level);
-	search(nodes, n, m, i + 1, j, idx, end, level);
-	search(nodes, n, m, i, j - 1, idx, end, level);
-	search(nodes, n, m, i, j + 1, idx, end, level);
-}
-
-
 bool Scene::findPath(Scene::Path &p, const Common::Point &src, const Common::Point &dst) const {
 	const Common::Array<Walkbox> &scene_walkboxes = walkboxes[_id - 1];
 	if (dst.x < 0 || dst.x > 319 || dst.y < 0 || dst.y > 199)
 		return false;
 	
 	debug(1, "findPath %d,%d -> %d,%d", src.x, src.y, dst.x, dst.y);
-
-	Splitter hsplit, vsplit;
-	for(byte i = 0; i < scene_walkboxes.size(); ++i) {
-		const Walkbox &w = scene_walkboxes[i];
-		if (w.rect.valid()) {
-			hsplit.insert(w.rect.left);
-			hsplit.insert(w.rect.right);
-			vsplit.insert(w.rect.top);
-			vsplit.insert(w.rect.bottom);
-		}
-	}
-	
-	int n = (int)vsplit.size() - 1, m = (int)hsplit.size() - 1;
-	debug(1, "split: %ux%u", n, m);
-	if (n <= 0 || m <= 0) {
-		p.push_back(Common::Point(src.x, dst.y));
-		p.push_back(dst);
-		return true;
-	}
+	p.clear();
+	p.push_back(src);
+	p.push_back(dst);
 	
-	Node *nodes = new Node[n * m];
-	int start = -1, end = -1;
-	{
-		int idx = 0;
-		for(Splitter::ListType::const_iterator i = vsplit.values.begin(); i != vsplit.values.end(); ++i) {
-			Splitter::ListType::const_iterator in = i; ++in;
-			if (in == vsplit.values.end())
-				break;
+	for(Path::iterator i = p.begin(); i != p.end(); ) {
+		Path::iterator next = i;
+		++next;
+		if (next == p.end())
+			break;
+			
+		const Common::Point &p1 = *i, &p2 = *next;
+		debug(1, "%d,%d -> %d,%d", p1.x, p1.y, p2.x, p2.y);
 		
-			for(Splitter::ListType::const_iterator j = hsplit.values.begin(); j != hsplit.values.end(); ++j) {
-				Splitter::ListType::const_iterator jn = j; ++jn;
-				if (jn == hsplit.values.end())
+		byte wi;
+		for(wi = 0; wi < scene_walkboxes.size(); ++wi) {
+			const Walkbox & w = scene_walkboxes[wi];
+			int mask = w.rect.intersects_line(p1, p2);
+			if (mask == 0) {
+				continue;
+			}
+			
+			w.dump();
+			debug(1, "%u: intersection mask 0x%04x, searching hints", wi, mask);
+			int dx = p2.x - p1.x, dy = p2.y - p1.y;
+			if (dx >= 0) {
+				if ((mask & 8) != 0 && w.side_hint[3] != 0) {
+					debug(1, "hint left: %u", w.side_hint[3]);
+					Common::Point w1, w2;
+					w.rect.side(w1, w2, w.side_hint[3], p1);
+					if (w1 == p2)
+						continue;
+					debug(1, "hint: %d,%d-%d,%d", w1.x, w1.y, w2.x, w2.y);
+					p.insert(next, w1);
+					break;
+				}
+			} else {
+				if ((mask & 2) != 0 && w.side_hint[1] != 0) {
+					debug(1, "hint right: %u", w.side_hint[1]);
+					Common::Point w1, w2;
+					w.rect.side(w1, w2, w.side_hint[1], p1);
+					if (w1 == p2)
+						continue;
+					debug(1, "hint: %d,%d-%d,%d", w1.x, w1.y, w2.x, w2.y);
+					p.insert(next, w1);
 					break;
-
-				Rect &r = nodes[idx].rect;
-				r = Rect(*j, *i, *jn, *in);
-				if (r.in(src))
-					start = idx;
-				if (r.in(dst))
-					end = idx;
-
-				byte k = 0;
-				for(k = 0; k < scene_walkboxes.size(); ++k) {
-					const Walkbox &w = scene_walkboxes[k];
-					if (w.rect.contains(r))
-						break;
 				}
-				nodes[idx].step = k >= scene_walkboxes.size()? 0: -1;
-				nodes[idx].prev = -1;
-				++idx;
 			}
-		}
-	}
 
-	debug(1, "%d -> %d", start, end);
-	
-	if (start == -1 || end == -1)
-		return false;
-
-	search(nodes, n, m, start / m, start % m, -1, end, 1);
-	int v = end;
-	Common::Point prev(dst);
-	do {
-		debug(1, "backtrace %d", v);
-		Common::Point c = nodes[v].rect.closest_to(prev);
-		prev = c;
-		p.push_front(c);
-		if (v == start)
-			break;
-		
-		v = nodes[v].prev;
-	} while(v >= 0);
-	
-	debug(1, "end vertex = %d", v);
-
-#if 0
-	{
-		int idx = 0;
-		for(int i = 0; i < n; ++i) {
-			Common::String line;
-			for(int j = 0; j < m; ++j) {
-				line += Common::String::printf("%2d.%2d  ", nodes[idx].step, nodes[idx].prev);
-				++idx;
+			if (dy >= 0) {
+				if ((mask & 1) != 0 && w.side_hint[0] != 0) {
+					debug(1, "hint top: %u", w.side_hint[0]);
+					Common::Point w1, w2;
+					w.rect.side(w1, w2, w.side_hint[0], p1);
+					if (w1 == p2)
+						continue;
+					debug(1, "hint: %d,%d-%d,%d", w1.x, w1.y, w2.x, w2.y);
+					p.insert(next, w1);
+					break;
+				}
+			} else {
+				if ((mask & 4) != 0 && w.side_hint[2] != 0) {
+					debug(1, "hint bottom: %u", w.side_hint[2]);
+					Common::Point w1, w2;
+					w.rect.side(w1, w2, w.side_hint[2], p1);
+					if (w1 == p2)
+						continue;
+					debug(1, "hint: %d,%d-%d,%d", w1.x, w1.y, w2.x, w2.y);
+					p.insert(next, w1);
+					break;
+				}
 			}
-			debug(1, "map: %s", line.c_str());
 		}
+		if (wi >= scene_walkboxes.size())
+			++i;
 	}
-#endif
 
-	if (v != start)
-		return false;
-	
-	
-	delete[] nodes;
 	return true;
 }
 
@@ -679,25 +608,17 @@ bool Scene::render(OSystem *system) {
 					const int speed_x = 10, speed_y = 5;
 					const Common::Point &destination = path.front();
 					Common::Point dp(destination.x - position.x, destination.y - position.y);
-					switch(orientation) {
-					case 2: //left or right
-					case 4: 
-						if (dp.y != 0)
-							dp.x = 0; //first, walking up-down
-						break;
-					default:
-						if (dp.x != 0)
-							dp.y = 0; //first, walking left-right
-					}
-					
+
 					int o;
-					if (ABS(dp.x) > ABS(dp.y))
-						o = dp.x > 0 ? Object::kActorRight : Object::kActorLeft;
+					if (ABS(dp.x) > 3 * ABS(dp.y))
+						o = dp.x > 0 ? kActorRight : kActorLeft;
 					else
-						o = dp.y > 0 ? Object::kActorDown : Object::kActorUp;
+						o = dp.y > 0 ? kActorDown : kActorUp;
 
-					position.x += (ABS(dp.x) < speed_x? dp.x: SIGN(dp.x) * speed_x);
 					position.y += (ABS(dp.y) < speed_y? dp.y: SIGN(dp.y) * speed_y);
+					position.x += (o == kActorDown || o == kActorUp)? 
+						(ABS(dp.x) < speed_y? dp.x: SIGN(dp.x) * speed_y):
+						(ABS(dp.x) < speed_x? dp.x: SIGN(dp.x) * speed_x);
 					
 					actor_animation_position = teenagent.render(surface, position, o, 1, false, zoom);
 					if (position == destination) {