SCI: AvoidPath: Add simpler visibility algorithm (still disabled).

svn-id: r45590

1 files changed, 139 insertions, 77 deletions

diff --git a/engines/sci/engine/kpathing.cpp b/engines/sci/engine/kpathing.cpp
index 103e4c8a98..3e46586914 100644
--- a/engines/sci/engine/kpathing.cpp
+++ b/engines/sci/engine/kpathing.cpp
@@ -38,6 +38,7 @@ namespace Sci {
 #define POLY_LAST_POINT 0x7777
 #define POLY_POINT_SIZE 4
 //#define DEBUG_AVOIDPATH	//enable for avoidpath debugging
+#define OLD_PATHFINDING
 
 static void POLY_GET_POINT(const byte *p, int i, Common::Point &pt) {
 	pt.x = (int16)READ_LE_UINT16((p) + (i) * POLY_POINT_SIZE);
@@ -282,32 +283,6 @@ static Common::Point read_point(SegManager *segMan, reg_t list, int offset) {
 	return point;
 }
 
-/**
- * Checks whether two polygons are equal
- */
-static bool polygons_equal(SegManager *segMan, reg_t p1, reg_t p2) {
-	// Check for same type
-	if (GET_SEL32(segMan, p1, type).toUint16() != GET_SEL32(segMan, p2, type).toUint16())
-		return false;
-
-	int size = GET_SEL32(segMan, p1, size).toUint16();
-
-	// Check for same number of points
-	if (size != GET_SEL32(segMan, p2, size).toUint16())
-		return false;
-
-	reg_t p1_points = GET_SEL32(segMan, p1, points);
-	reg_t p2_points = GET_SEL32(segMan, p2, points);
-
-	// Check for the same points
-	for (int i = 0; i < size; i++) {
-		if (read_point(segMan, p1_points, i) != read_point(segMan, p2_points, i))
-			return false;
-	}
-
-	return true;
-}
-
 #ifdef DEBUG_AVOIDPATH
 
 static void draw_line(EngineState *s, Common::Point p1, Common::Point p2, int type) {
@@ -460,16 +435,6 @@ static bool left(const Common::Point &a, const Common::Point &b, const Common::P
 	return area(a, b, c) > 0;
 }
 
-static bool left_on(const Common::Point &a, const Common::Point &b, const Common::Point &c) {
-	// Determines whether or not a point is to the left of or collinear with a
-	// directed line
-	// Parameters: (const Common::Point &) a, b: The directed line (a, b)
-	//             (const Common::Point &) c: The query point
-	// Returns   : (int) true if c is to the left of or collinear with (a, b), false
-	//                   otherwise
-	return area(a, b, c) >= 0;
-}
-
 static bool collinear(const Common::Point &a, const Common::Point &b, const Common::Point &c) {
 	// Determines whether or not three points are collinear
 	// Parameters: (const Common::Point &) a, b, c: The three points
@@ -503,17 +468,6 @@ static bool intersect_proper(const Common::Point &a, const Common::Point &b, con
 	return ab && cd;
 }
 
-static bool intersect(const Common::Point &a, const Common::Point &b, const Common::Point &c, const Common::Point &d) {
-	// Determines whether or not two line segments intersect
-	// Parameters: (const Common::Point &) a, b: The line segment (a, b)
-	//             (const Common::Point &) c, d: The line segment (c, d)
-	// Returns   : (int) true if (a, b) intersects (c, d), false otherwise
-	if (intersect_proper(a, b, c, d))
-		return true;
-
-	return between(a, b, c) || between(a, b, d) || between(c, d, a) || between(c, d, b);
-}
-
 static int contained(const Common::Point &p, Polygon *polygon) {
 	// Polygon containment test
 	// Parameters: (const Common::Point &) p: The point
@@ -614,6 +568,73 @@ static void fix_vertex_order(Polygon *polygon) {
 	}
 }
 
+static int inside(const Common::Point &p, Vertex *vertex) {
+	// Determines whether or not a line from a point to a vertex intersects the
+	// interior of the polygon, locally at that vertex
+	// Parameters: (Common::Point) p: The point
+	//             (Vertex *) vertex: The vertex
+	// Returns   : (int) 1 if the line (p, vertex->v) intersects the interior of
+	//                   the polygon, locally at the vertex. 0 otherwise
+	// Check that it's not a single-vertex polygon
+	if (VERTEX_HAS_EDGES(vertex)) {
+		const Common::Point &prev = CLIST_PREV(vertex)->v;
+		const Common::Point &next = CLIST_NEXT(vertex)->v;
+		const Common::Point &cur = vertex->v;
+
+		if (left(prev, cur, next)) {
+			// Convex vertex, line (p, cur) intersects the inside
+			// if p is located left of both edges
+			if (left(cur, next, p) && left(prev, cur, p))
+				return 1;
+		} else {
+			// Non-convex vertex, line (p, cur) intersects the
+			// inside if p is located left of either edge
+			if (left(cur, next, p) || left(prev, cur, p))
+				return 1;
+		}
+	}
+
+	return 0;
+}
+
+#ifdef OLD_PATHFINDING
+
+/**
+ * Checks whether two polygons are equal
+ */
+static bool polygons_equal(SegManager *segMan, reg_t p1, reg_t p2) {
+	// Check for same type
+	if (GET_SEL32(segMan, p1, type).toUint16() != GET_SEL32(segMan, p2, type).toUint16())
+		return false;
+
+	int size = GET_SEL32(segMan, p1, size).toUint16();
+
+	// Check for same number of points
+	if (size != GET_SEL32(segMan, p2, size).toUint16())
+		return false;
+
+	reg_t p1_points = GET_SEL32(segMan, p1, points);
+	reg_t p2_points = GET_SEL32(segMan, p2, points);
+
+	// Check for the same points
+	for (int i = 0; i < size; i++) {
+		if (read_point(segMan, p1_points, i) != read_point(segMan, p2_points, i))
+			return false;
+	}
+
+	return true;
+}
+
+static bool left_on(const Common::Point &a, const Common::Point &b, const Common::Point &c) {
+	// Determines whether or not a point is to the left of or collinear with a
+	// directed line
+	// Parameters: (const Common::Point &) a, b: The directed line (a, b)
+	//             (const Common::Point &) c: The query point
+	// Returns   : (int) true if c is to the left of or collinear with (a, b), false
+	//                   otherwise
+	return area(a, b, c) >= 0;
+}
+
 static Vertex *s_vertex_cur = 0;	// FIXME: Avoid non-const global vars
 
 static int vertex_compare(const void *a, const void *b) {
@@ -710,35 +731,6 @@ static bool edgeIsCloser(const Vertex *vertex_cur, const Vertex *a, const Vertex
 	return ((left_on(*v1, *v2, *w1) && left_on(*v1, *v2, *w2)) || (left_on(*w2, *w1, *v1) && left_on(*w2, *w1, *v2)));
 }
 
-static int inside(const Common::Point &p, Vertex *vertex) {
-	// Determines whether or not a line from a point to a vertex intersects the
-	// interior of the polygon, locally at that vertex
-	// Parameters: (Common::Point) p: The point
-	//             (Vertex *) vertex: The vertex
-	// Returns   : (int) 1 if the line (p, vertex->v) intersects the interior of
-	//                   the polygon, locally at the vertex. 0 otherwise
-	// Check that it's not a single-vertex polygon
-	if (VERTEX_HAS_EDGES(vertex)) {
-		const Common::Point &prev = CLIST_PREV(vertex)->v;
-		const Common::Point &next = CLIST_NEXT(vertex)->v;
-		const Common::Point &cur = vertex->v;
-
-		if (left(prev, cur, next)) {
-			// Convex vertex, line (p, cur) intersects the inside
-			// if p is located left of both edges
-			if (left(cur, next, p) && left(prev, cur, p))
-				return 1;
-		} else {
-			// Non-convex vertex, line (p, cur) intersects the
-			// inside if p is located left of either edge
-			if (left(cur, next, p) || left(prev, cur, p))
-				return 1;
-		}
-	}
-
-	return 0;
-}
-
 /**
  * Determines whether or not a vertex is visible from vertex_cur.
  * @param vertex_cur	the base vertex
@@ -864,6 +856,52 @@ static VertexList *visible_vertices(PathfindingState *s, Vertex *vertex_cur) {
 	return visVerts;
 }
 
+#else
+
+/**
+ * Returns a list of all vertices that are visible from a particular vertex.
+ * @param s				the pathfinding state
+ * @param vertex_cur	the vertex
+ * @return list of vertices that are visible from vert
+ */
+static VertexList *visible_vertices(PathfindingState *s, Vertex *vertex_cur) {
+	VertexList *visVerts = new VertexList();
+
+	for (int i = 0; i < s->vertices; i++) {
+		Vertex *vertex = s->vertex_index[i];
+
+		// Make sure we don't intersect a polygon locally at the vertices
+		if ((vertex == vertex_cur) || (inside(vertex->v, vertex_cur)) || (inside(vertex_cur->v, vertex)))
+			continue;
+
+		// Check for intersecting edges
+		int j;
+		for (j = 0; j < s->vertices; j++) {
+			Vertex *edge = s->vertex_index[j];
+			if (VERTEX_HAS_EDGES(edge)) {
+				if (between(vertex_cur->v, vertex->v, edge->v)) {
+					// If we hit a vertex, make sure we can pass through it without intersecting its polygon
+					if ((inside(vertex_cur->v, edge)) || (inside(vertex->v, edge)))
+						break;
+
+					// This edge won't properly intersect, so we continue
+					continue;
+				}
+
+				if (intersect_proper(vertex_cur->v, vertex->v, edge->v, CLIST_NEXT(edge)->v))
+					break;
+			}
+		}
+
+		if (j == s->vertices)
+			visVerts->push_front(vertex);
+	}
+
+	return visVerts;
+}
+
+#endif // OLD_PATHFINDING
+
 static bool point_on_screen_border(const Common::Point &p) {
 	// Determines if a point lies on the screen border
 	// Parameters: (const Common::Point &) p: The point
@@ -1267,6 +1305,7 @@ static Polygon *convert_polygon(EngineState *s, reg_t polygon) {
 		}
 	}
 
+#ifdef OLD_PATHFINDING
 	// WORKAROUND: self-intersecting polygons in ECO, rooms 221, 280 and 300
 	if ((size == 11) && (s->_gameName == "ecoquest")) {
 		if ((s->currentRoomNumber() == 300)
@@ -1292,8 +1331,10 @@ static Polygon *convert_polygon(EngineState *s, reg_t polygon) {
 			skip = 2;
 		}
 	}
+#endif
 
 	for (i = skip; i < size; i++) {
+#ifdef OLD_PATHFINDING
 		if (size == 35 && (i == 20 || i == 21) && s->_gameName == "sq1sci" &&
 			s->currentRoomNumber() == 66) {
 			if (i == 20 && read_point(segMan, points, 20) == Common::Point(0, 104)) {
@@ -1308,7 +1349,7 @@ static Polygon *convert_polygon(EngineState *s, reg_t polygon) {
 				continue;
 			}
 		}
-
+#endif
 		Vertex *vertex = new Vertex(read_point(segMan, points, i));
 		poly->vertices.insertHead(vertex);
 	}
@@ -1318,6 +1359,7 @@ static Polygon *convert_polygon(EngineState *s, reg_t polygon) {
 	return poly;
 }
 
+#ifdef OLD_PATHFINDING
 // WORKAROUND: intersecting polygons in Longbow, room 210.
 static void fixLongbowRoom210(PathfindingState *s, const Common::Point &start, const Common::Point &end) {
 	Polygon *barred = NULL;
@@ -1367,6 +1409,7 @@ static void fixLongbowRoom210(PathfindingState *s, const Common::Point &start, c
 		s->polygons.push_front(barred);
 	}
 }
+#endif
 
 static void change_polygons_opt_0(PathfindingState *s) {
 	// Changes the polygon list for optimization level 0 (used for keyboard
@@ -1415,10 +1458,12 @@ static PathfindingState *convert_polygon_set(EngineState *s, reg_t poly_list, Co
 
 			// Workaround for game bugs that put a polygon in the list more than once
 			while (dup != node) {
+#ifdef OLD_PATHFINDING
 				if (polygons_equal(s->_segMan, node->value, dup->value)) {
 					warning("[avoidpath] Ignoring duplicate polygon");
 					break;
 				}
+#endif
 				dup = s->_segMan->lookupNode(dup->succ);
 			}
 
@@ -1488,8 +1533,10 @@ static PathfindingState *convert_polygon_set(EngineState *s, reg_t poly_list, Co
 			new_start = new Common::Point(77, 107);
 		}
 
+#ifdef OLD_PATHFINDING
 		if (s->_gameName == "longbow" && s->currentRoomNumber() == 210)
 				fixLongbowRoom210(pf_s, *new_start, *new_end);
+#endif
 
 		// Merge start and end points into polygon set
 		pf_s->vertex_start = merge_point(pf_s, *new_start);
@@ -1518,6 +1565,18 @@ static PathfindingState *convert_polygon_set(EngineState *s, reg_t poly_list, Co
 	return pf_s;
 }
 
+#ifdef OLD_PATHFINDING
+static bool intersect(const Common::Point &a, const Common::Point &b, const Common::Point &c, const Common::Point &d) {
+	// Determines whether or not two line segments intersect
+	// Parameters: (const Common::Point &) a, b: The line segment (a, b)
+	//             (const Common::Point &) c, d: The line segment (c, d)
+	// Returns   : (int) true if (a, b) intersects (c, d), false otherwise
+	if (intersect_proper(a, b, c, d))
+		return true;
+
+	return between(a, b, c) || between(a, b, d) || between(c, d, a) || between(c, d, b);
+}
+
 static int intersecting_polygons(PathfindingState *s) {
 	// Detects (self-)intersecting polygons
 	// Parameters: (PathfindingState *) s: The pathfinding state
@@ -1545,6 +1604,7 @@ static int intersecting_polygons(PathfindingState *s) {
 
 	return 0;
 }
+#endif
 
 /**
  * Computes a shortest path from vertex_start to vertex_end. The caller can
@@ -1731,11 +1791,13 @@ reg_t kAvoidPath(EngineState *s, int argc, reg_t *argv) {
 
 		p = convert_polygon_set(s, poly_list, start, end, opt);
 
+#ifdef OLD_PATHFINDING
 		if (p && intersecting_polygons(p)) {
 			warning("[avoidpath] input set contains (self-)intersecting polygons");
 			delete p;
 			p = NULL;
 		}
+#endif
 
 		if (!p) {
 			byte *oref;