diff options
Diffstat (limited to 'engines')
| -rw-r--r-- | engines/sci/engine/kpathing.cpp | 937 |
1 files changed, 382 insertions, 555 deletions
diff --git a/engines/sci/engine/kpathing.cpp b/engines/sci/engine/kpathing.cpp index 12687bf8a3..6a9cf8f80c 100644 --- a/engines/sci/engine/kpathing.cpp +++ b/engines/sci/engine/kpathing.cpp @@ -44,13 +44,13 @@ y = KP_SINT((p)[(i) * 2 + 1]); \ } while (0) -/* SCI-defined polygon types */ +// SCI-defined polygon types #define POLY_TOTAL_ACCESS 0 #define POLY_NEAREST_ACCESS 1 #define POLY_BARRED_ACCESS 2 #define POLY_CONTAINED_ACCESS 3 -/* Polygon containment types */ +// Polygon containment types #define CONT_OUTSIDE 0 #define CONT_ON_EDGE 1 #define CONT_INSIDE 2 @@ -59,7 +59,7 @@ #define HUGE_DISTANCE 1e10 -/* Visibility matrix */ +// Visibility matrix #define VIS_MATRIX_ROW_SIZE(N) (((N) / 8) + ((N) % 8 ? 1 : 0)) #define SET_VISIBLE(S, P, Q) ((S)->vis_matrix)[(P) * VIS_MATRIX_ROW_SIZE((S)->vertices) \ + (Q) / 8] |= (1 << ((Q) % 8)) @@ -68,12 +68,12 @@ #define VERTEX_HAS_EDGES(V) ((V) != CLIST_NEXT(V, entries)) -/* Error codes */ +// Error codes #define PF_OK 0 #define PF_ERROR -1 #define PF_FATAL -2 -/* Floating point struct */ +// Floating point struct typedef struct pointf { pointf() : x(0), y(0) {} pointf(float x_, float y_) : x(x_), y(y_) {} @@ -81,87 +81,84 @@ typedef struct pointf { float x, y; } pointf_t; -pointf_t -to_pointf(Common::Point p) { +pointf_t to_pointf(Common::Point p) { return pointf(p.x, p.y); } typedef struct vertex { - /* Location */ + // Location Common::Point v; - /* Index */ + // Index int idx; - /* Vertex list entry */ + // Vertex list entry CLIST_ENTRY(vertex) entries; - /* Dijkstra list entry */ + // Dijkstra list entry LIST_ENTRY(vertex) dijkstra; - /* Distance from starting vertex */ + // Distance from starting vertex float dist; - /* Previous vertex in shortest path */ + // Previous vertex in shortest path struct vertex *path_prev; } vertex_t; typedef CLIST_HEAD(vertices_head, vertex) vertices_head_t; typedef struct polygon { - /* Circular list of vertices */ + // Circular list of vertices vertices_head_t vertices; - /* Polygon list entry */ + // Polygon list entry LIST_ENTRY(polygon) entries; - /* SCI polygon type */ + // SCI polygon type int type; } polygon_t; -/* Pathfinding state */ +// Pathfinding state typedef struct pf_state { - /* List of all polygons */ + // List of all polygons LIST_HEAD(polygons_head, polygon) polygons; - /* Original start and end points */ + // Original start and end points Common::Point start, end; - /* Flags for adding original points to final path */ + // Flags for adding original points to final path char keep_start, keep_end; - /* Start and end points for pathfinding */ + // Start and end points for pathfinding vertex_t *vertex_start, *vertex_end; - /* Array to quickly find vertices by idx */ + // Array to quickly find vertices by idx vertex_t **vertex_index; - /* Visibility matrix */ + // Visibility matrix char *vis_matrix; - /* Total number of vertices */ + // Total number of vertices int vertices; } pf_state_t; static vertex_t *vertex_cur; -/* Temporary hack to deal with points in reg_ts */ -static int -polygon_is_reg_t(unsigned char *list, int size) { +// Temporary hack to deal with points in reg_ts +static int polygon_is_reg_t(unsigned char *list, int size) { int i; - /* Check the first three reg_ts */ + // Check the first three reg_ts for (i = 0; i < (size < 3 ? size : 3); i++) if ((((reg_t *) list) + i)->segment) - /* Non-zero segment, cannot be reg_ts */ + // Non-zero segment, cannot be reg_ts return 0; - /* First three segments were zero, assume reg_ts */ + // First three segments were zero, assume reg_ts return 1; } -static Common::Point -read_point(unsigned char *list, int is_reg_t, int offset) { +static Common::Point read_point(unsigned char *list, int is_reg_t, int offset) { Common::Point point; if (!is_reg_t) { @@ -173,17 +170,12 @@ read_point(unsigned char *list, int is_reg_t, int offset) { return point; } - -/*** Debug functions ***/ - -static void -draw_line(state_t *s, Common::Point p1, Common::Point p2, int type) { - /* Colors for polygon debugging. - ** Green: Total access - ** Red : Barred access - ** Blue: Near-point access - ** Yellow: Contained access - */ +static void draw_line(state_t *s, Common::Point p1, Common::Point p2, int type) { + // Colors for polygon debugging. + // Green: Total access + // Red : Barred access + // Blue: Near-point access + // Yellow: Contained access int poly_colors[][3] = {{0, 255, 0}, {0, 0, 255}, {255, 0, 0}, {255, 255, 0}}; gfx_color_t col; gfxw_list_t *decorations = s->picture_port->decorations; @@ -202,15 +194,13 @@ draw_line(state_t *s, Common::Point p1, Common::Point p2, int type) { p2.y += 10; line = gfxw_new_line(p1, p2, col, GFX_LINE_MODE_CORRECT, GFX_LINE_STYLE_NORMAL); - decorations->add((gfxw_container_t *) decorations, (gfxw_widget_t *) line); + decorations->add((gfxw_container_t *)decorations, (gfxw_widget_t *)line); } -static void -draw_point(state_t *s, Common::Point p, int start) { - /* Colors for starting and end point - ** Green: End point - ** Blue: Starting point - */ +static void draw_point(state_t *s, Common::Point p, int start) { + // Colors for starting and end point + // Green: End point + // Blue: Starting point int point_colors[][3] = {{0, 255, 0}, {0, 0, 255}}; gfx_color_t col; gfxw_list_t *decorations = s->picture_port->decorations; @@ -229,8 +219,7 @@ draw_point(state_t *s, Common::Point p, int start) { decorations->add((gfxw_container_t *) decorations, (gfxw_widget_t *) box); } -static void -draw_polygon(state_t *s, reg_t polygon) { +static void draw_polygon(state_t *s, reg_t polygon) { reg_t points = GET_SEL32(polygon, points); int size = KP_UINT(GET_SEL32(polygon, size)); int type = KP_UINT(GET_SEL32(polygon, type)); @@ -250,8 +239,7 @@ draw_polygon(state_t *s, reg_t polygon) { draw_line(s, prev, first, type % 3); } -static void -draw_input(state_t *s, reg_t poly_list, Common::Point start, Common::Point end, int opt) { +static void draw_input(state_t *s, reg_t poly_list, Common::Point start, Common::Point end, int opt) { list_t *list; node_t *node; @@ -276,8 +264,7 @@ draw_input(state_t *s, reg_t poly_list, Common::Point start, Common::Point end, } } -static void -print_polygon(state_t *s, reg_t polygon) { +static void print_polygon(state_t *s, reg_t polygon) { reg_t points = GET_SEL32(polygon, points); int size = KP_UINT(GET_SEL32(polygon, size)); int type = KP_UINT(GET_SEL32(polygon, type)); @@ -297,8 +284,7 @@ print_polygon(state_t *s, reg_t polygon) { sciprintf(" (%i, %i);\n", point.x, point.y); } -static void -print_input(state_t *s, reg_t poly_list, Common::Point start, Common::Point end, int opt) { +static void print_input(state_t *s, reg_t poly_list, Common::Point start, Common::Point end, int opt) { list_t *list; node_t *node; @@ -325,112 +311,79 @@ print_input(state_t *s, reg_t poly_list, Common::Point start, Common::Point end, } } - -/*** Basic geometry functions ***/ - -static int -area(Common::Point a, Common::Point b, Common::Point c) -/* Computes the area of a triangle -** Parameters: (Common::Point) a, b, c: The points of the triangle -** Returns : (int) The area multiplied by two -*/ -{ +static int area(Common::Point a, Common::Point b, Common::Point c) { + // Computes the area of a triangle + // Parameters: (Common::Point) a, b, c: The points of the triangle + // Returns : (int) The area multiplied by two return (b.x - a.x) * (a.y - c.y) - (c.x - a.x) * (a.y - b.y); } -static int -left(Common::Point a, Common::Point b, Common::Point c) -/* Determines whether or not a point is to the left of a directed line -** Parameters: (Common::Point) a, b: The directed line (a, b) -** (Common::Point) c: The query point -** Returns : (int) 1 if c is to the left of (a, b), 0 otherwise -*/ -{ +static int left(Common::Point a, Common::Point b, Common::Point c) { + // Determines whether or not a point is to the left of a directed line + // Parameters: (Common::Point) a, b: The directed line (a, b) + // (Common::Point) c: The query point + // Returns : (int) 1 if c is to the left of (a, b), 0 otherwise return area(a, b, c) > 0; } -static int -left_on(Common::Point a, Common::Point b, Common::Point c) -/* Determines whether or not a point is to the left of or collinear with a -** directed line -** Parameters: (Common::Point) a, b: The directed line (a, b) -** (Common::Point) c: The query point -** Returns : (int) 1 if c is to the left of or collinear with (a, b), 0 -** otherwise -*/ -{ +static int left_on(Common::Point a, Common::Point b, Common::Point c) { + // Determines whether or not a point is to the left of or collinear with a + // directed line + // Parameters: (Common::Point) a, b: The directed line (a, b) + // (Common::Point) c: The query point + // Returns : (int) 1 if c is to the left of or collinear with (a, b), 0 + // otherwise return area(a, b, c) >= 0; } -static int -collinear(Common::Point a, Common::Point b, Common::Point c) -/* Determines whether or not three points are collinear -** Parameters: (Common::Point) a, b, c: The three points -** Returns : (int) 1 if a, b, and c are collinear, 0 otherwise -*/ -{ +static int collinear(Common::Point a, Common::Point b, Common::Point c) { + // Determines whether or not three points are collinear + // Parameters: (Common::Point) a, b, c: The three points + // Returns : (int) 1 if a, b, and c are collinear, 0 otherwise return area(a, b, c) == 0; } -static int -between(Common::Point a, Common::Point b, Common::Point c) -/* Determines whether or not a point lies on a line segment -** Parameters: (Common::Point) a, b: The line segment (a, b) -** (Common::Point) c: The query point -** Returns : (int) 1 if c lies on (a, b), 0 otherwise -*/ -{ +static int between(Common::Point a, Common::Point b, Common::Point c) { + // Determines whether or not a point lies on a line segment + // Parameters: (Common::Point) a, b: The line segment (a, b) + // (Common::Point) c: The query point + // Returns : (int) 1 if c lies on (a, b), 0 otherwise if (!collinear(a, b, c)) return 0; - /* Assumes a != b. */ + // Assumes a != b. if (a.x != b.x) return ((a.x <= c.x) && (c.x <= b.x)) || ((a.x >= c.x) && (c.x >= b.x)); else return ((a.y <= c.y) && (c.y <= b.y)) || ((a.y >= c.y) && (c.y >= b.y)); } -static int -intersect_proper(Common::Point a, Common::Point b, Common::Point c, Common::Point d) -/* Determines whether or not two line segments properly intersect -** Parameters: (Common::Point) a, b: The line segment (a, b) -** (Common::Point) c, d: The line segment (c, d) -** Returns : (int) 1 if (a, b) properly intersects (c, d), 0 otherwise -*/ -{ - int ab = (left(a, b, c) && left(b, a, d)) - || (left(a, b, d) && left(b, a, c)); - int cd = (left(c, d, a) && left(d, c, b)) - || (left(c, d, b) && left(d, c, a)); +static int intersect_proper(Common::Point a, Common::Point b, Common::Point c, Common::Point d) { + // Determines whether or not two line segments properly intersect + // Parameters: (Common::Point) a, b: The line segment (a, b) + // (Common::Point) c, d: The line segment (c, d) + // Returns : (int) 1 if (a, b) properly intersects (c, d), 0 otherwise + int ab = (left(a, b, c) && left(b, a, d)) || (left(a, b, d) && left(b, a, c)); + int cd = (left(c, d, a) && left(d, c, b)) || (left(c, d, b) && left(d, c, a)); return ab && cd; } -static int -intersect(Common::Point a, Common::Point b, Common::Point c, Common::Point d) -/* Determines whether or not two line segments intersect -** Parameters: (Common::Point) a, b: The line segment (a, b) -** (Common::Point) c, d: The line segment (c, d) -** Returns : (int) 1 if (a, b) intersects (c, d), 0 otherwise -*/ -{ +static int intersect(Common::Point a, Common::Point b, Common::Point c, Common::Point d) { + // Determines whether or not two line segments intersect + // Parameters: (Common::Point) a, b: The line segment (a, b) + // (Common::Point) c, d: The line segment (c, d) + // Returns : (int) 1 if (a, b) intersects (c, d), 0 otherwise if (intersect_proper(a, b, c, d)) return 1; - return between(a, b, c) || between(a, b, d) - || between(c, d, a) || between(c, d, b); + return between(a, b, c) || between(a, b, d) || between(c, d, a) || between(c, d, b); } - -/*** Pathfinding ***/ - -static vertex_t * -vertex_new(Common::Point p) -/* Allocates and initialises a new vertex -** Parameters: (Common::Point) p: The position of the vertex -** Returns : (vertex_t *) A newly allocated vertex -*/ -{ +static vertex_t *vertex_new(Common::Point p) { + // Allocates and initialises a new vertex + // Parameters: (Common::Point) p: The position of the vertex + // Returns : (vertex_t *) A newly allocated vertex vertex_t *vertex = (vertex_t*)sci_malloc(sizeof(vertex_t)); vertex->v = p; @@ -440,13 +393,10 @@ vertex_new(Common::Point p) return vertex; } -static polygon_t * -polygon_new(int type) -/* Allocates and initialises a new polygon -** Parameters: (int) type: The SCI polygon type -** Returns : (polygon_t *) A newly allocated polygon -*/ -{ +static polygon_t *polygon_new(int type) { + // Allocates and initialises a new polygon + // Parameters: (int) type: The SCI polygon type + // Returns : (polygon_t *) A newly allocated polygon polygon_t *polygon = (polygon_t*)sci_malloc(sizeof(polygon_t)); CLIST_INIT(&polygon->vertices); @@ -455,50 +405,45 @@ polygon_new(int type) return polygon; } -static int -contained(Common::Point p, polygon_t *polygon) -/* Polygon containment test -** Parameters: (Common::Point) p: The point -** (polygon_t *) polygon: The polygon -** Returns : (int) CONT_INSIDE if p is strictly contained in polygon, -** CONT_ON_EDGE if p lies on an edge of polygon, -** CONT_OUTSIDE otherwise -*/ -{ - /* Number of ray crossing left and right */ +static int contained(Common::Point p, polygon_t *polygon) { + // Polygon containment test + // Parameters: (Common::Point) p: The point + // (polygon_t *) polygon: The polygon + // Returns : (int) CONT_INSIDE if p is strictly contained in polygon, + // CONT_ON_EDGE if p lies on an edge of polygon, + // CONT_OUTSIDE otherwise + // Number of ray crossing left and right int lcross = 0, rcross = 0; vertex_t *vertex; - /* Iterate over edges */ + // Iterate over edges CLIST_FOREACH(vertex, &polygon->vertices, entries) { Common::Point v1 = vertex->v; Common::Point v2 = CLIST_NEXT(vertex, entries)->v; - /* Flags for ray straddling left and right */ + // Flags for ray straddling left and right int rstrad, lstrad; - /* Check if p is a vertex */ + // Check if p is a vertex if (POINT_EQUAL(p, v1)) return CONT_ON_EDGE; - /* Check if edge straddles the ray */ + // Check if edge straddles the ray rstrad = (v1.y < p.y) != (v2.y < p.y); lstrad = (v1.y > p.y) != (v2.y > p.y); if (lstrad || rstrad) { - /* Compute intersection point x / xq */ + // Compute intersection point x / xq int x = v2.x * v1.y - v1.x * v2.y + (v1.x - v2.x) * p.y; int xq = v1.y - v2.y; - /* Multiply by -1 if xq is negative (for comparison - ** that follows) - */ + // Multiply by -1 if xq is negative (for comparison that follows) if (xq < 0) { x = -x; xq = -xq; } - /* Avoid floats by multiplying instead of dividing */ + // Avoid floats by multiplying instead of dividing if (rstrad && (x > xq * p.x)) rcross++; else if (lstrad && (x < xq * p.x)) @@ -506,38 +451,29 @@ contained(Common::Point p, polygon_t *polygon) } } - /* If we counted an odd number of total crossings the point is on an - ** edge - */ + // If we counted an odd number of total crossings the point is on an edge if ((lcross + rcross) % 2 == 1) return CONT_ON_EDGE; - /* If there are an odd number of crossings to one side the point is - ** contained in the polygon - */ + // If there are an odd number of crossings to one side the point is contained in the polygon if (rcross % 2 == 1) { - /* Invert result for contained access polygons. */ + // Invert result for contained access polygons. if (polygon->type == POLY_CONTAINED_ACCESS) return CONT_OUTSIDE; return CONT_INSIDE; } - /* Point is outside polygon. Invert result for contained access - ** polygons - */ + // Point is outside polygon. Invert result for contained access polygons if (polygon->type == POLY_CONTAINED_ACCESS) return CONT_INSIDE; return CONT_OUTSIDE; } -static int -polygon_area(polygon_t *polygon) -/* Computes polygon area -** Parameters: (polygon_t *) polygon: The polygon -** Returns : (int) The area multiplied by two -*/ -{ +static int polygon_area(polygon_t *polygon) { + // Computes polygon area + // Parameters: (polygon_t *) polygon: The polygon + // Returns : (int) The area multiplied by two vertex_t *first = CLIST_FIRST(&polygon->vertices); vertex_t *v; int size = 0; @@ -552,30 +488,26 @@ polygon_area(polygon_t *polygon) return size; } -static void -fix_vertex_order(polygon_t *polygon) -/* Fixes the vertex order of a polygon if incorrect. Contained access -** polygons should have their vertices ordered clockwise, all other types -** anti-clockwise -** Parameters: (polygon_t *) polygon: The polygon -** Returns : (void) -*/ -{ +static void fix_vertex_order(polygon_t *polygon) { + // Fixes the vertex order of a polygon if incorrect. Contained access + // polygons should have their vertices ordered clockwise, all other types + // anti-clockwise + // Parameters: (polygon_t *) polygon: The polygon + // Returns : (void) int area = polygon_area(polygon); - /* When the polygon area is positive the vertices are ordered - ** anti-clockwise. When the area is negative the vertices are ordered - ** clockwise - */ + // When the polygon area is positive the vertices are ordered + // anti-clockwise. When the area is negative the vertices are ordered + // clockwise if (((area > 0) && (polygon->type == POLY_CONTAINED_ACCESS)) || ((area < 0) && (polygon->type != POLY_CONTAINED_ACCESS))) { vertices_head_t vertices; - /* Create a new circular list */ + // Create a new circular list CLIST_INIT(&vertices); while (!CLIST_EMPTY(&polygon->vertices)) { - /* Put first vertex in new list */ + // Put first vertex in new list vertex_t *vertex = CLIST_FIRST(&polygon->vertices); CLIST_REMOVE(&polygon->vertices, vertex, entries); CLIST_INSERT_HEAD(&vertices, vertex, entries); @@ -585,16 +517,13 @@ fix_vertex_order(polygon_t *polygon) } } -static int -vertex_compare(const void *a, const void *b) -/* Compares two vertices by angle (first) and distance (second) in relation -** to vertex_cur. The angle is relative to the horizontal line extending -** right from vertex_cur, and increases clockwise -** Parameters: (const void *) a, b: The vertices -** Returns : (int) -1 if a is smaller than b, 1 if a is larger than b, and -** 0 if a and b are equal -*/ -{ +static int vertex_compare(const void *a, const void *b) { + // Compares two vertices by angle (first) and distance (second) in relation + // to vertex_cur. The angle is relative to the horizontal line extending + // right from vertex_cur, and increases clockwise + // Parameters: (const void *) a, b: The vertices + // Returns : (int) -1 if a is smaller than b, 1 if a is larger than b, and + // 0 if a and b are equal Common::Point p0 = vertex_cur->v; Common::Point p1 = (*(vertex_t **) a)->v; Common::Point p2 = (*(vertex_t **) b)->v; @@ -602,18 +531,16 @@ vertex_compare(const void *a, const void *b) if (POINT_EQUAL(p1, p2)) return 0; - /* Points above p0 have larger angle than points below p0 */ + // Points above p0 have larger angle than points below p0 if ((p1.y < p0.y) && (p2.y >= p0.y)) return 1; if ((p2.y < p0.y) && (p1.y >= p0.y)) return -1; - /* Handle case where all points have the same y coordinate */ + // Handle case where all points have the same y coordinate if ((p0.y == p1.y) && (p0.y == p2.y)) { - /* Points left of p0 have larger angle than points right of - ** p0 - */ + // Points left of p0 have larger angle than points right of p0 if ((p1.x < p0.x) && (p2.x >= p0.x)) return 1; if ((p1.x >= p0.x) && (p2.x < p0.x)) @@ -621,9 +548,8 @@ vertex_compare(const void *a, const void *b) } if (collinear(p0, p1, p2)) { - /* At this point collinear points must have the same angle, - ** so compare distance to p0 - */ + // At this point collinear points must have the same angle, + // so compare distance to p0 if (abs(p1.x - p0.x) < abs(p2.x - p0.x)) return -1; if (abs(p1.y - p0.y) < abs(p2.y - p0.y)) @@ -632,25 +558,20 @@ vertex_compare(const void *a, const void *b) return 1; } - /* If p2 is left of the directed line (p0, p1) then p1 has greater - ** angle - */ + // If p2 is left of the directed line (p0, p1) then p1 has greater angle if (left(p0, p1, p2)) return 1; return -1; } -static void -clockwise(vertex_t *v, Common::Point *p1, Common::Point *p2) -/* Orders the points of an edge clockwise around vertex_cur. If all three -** points are collinear the original order is used -** Parameters: (vertex_t *) v: The first vertex of the edge -** Returns : (void) -** (Common::Point) *p1: The first point in clockwise order -** (Common::Point) *p2: The second point in clockwise order -*/ -{ +static void clockwise(vertex_t *v, Common::Point *p1, Common::Point *p2) { + // Orders the points of an edge clockwise around vertex_cur. If all three + // points are collinear the original order is used + // Parameters: (vertex_t *) v: The first vertex of the edge + // Returns : (void) + // (Common::Point) *p1: The first point in clockwise order + // (Common::Point) *p2: The second point in clockwise order vertex_t *w = CLIST_NEXT(v, entries); if (left_on(vertex_cur->v, w->v, v->v)) { @@ -664,78 +585,67 @@ clockwise(vertex_t *v, Common::Point *p1, Common::Point *p2) return; } -static int -edge_compare(const void *a, const void *b) -/* Compares two edges that are intersected by the sweeping line by distance -** from vertex_cur -** Parameters: (const void *) a, b: The first vertices of the edges -** Returns : (int) -1 if a is closer than b, 1 if b is closer than a, and -** 0 if a and b are equal -*/ -{ +static int edge_compare(const void *a, const void *b) { + // Compares two edges that are intersected by the sweeping line by distance + // from vertex_cur + // Parameters: (const void *) a, b: The first vertices of the edges + // Returns : (int) -1 if a is closer than b, 1 if b is closer than a, and + // 0 if a and b are equal Common::Point v1, v2, w1, w2; - /* We can assume that the sweeping line intersects both edges and - ** that the edges do not properly intersect - */ + // We can assume that the sweeping line intersects both edges and + // that the edges do not properly intersect if (a == b) return 0; - /* Order vertices clockwise so we know vertex_cur is to the right of - ** directed edges (v1, v2) and (w1, w2) - */ + // Order vertices clockwise so we know vertex_cur is to the right of + // directed edges (v1, v2) and (w1, w2) clockwise((vertex_t *) a, &v1, &v2); clockwise((vertex_t *) b, &w1, &w2); - /* As the edges do not properly intersect one edge must lie entirely - ** to one side of another. Note that the special case where edges are - ** collinear does not need to be handled as those edges will never be - ** in the tree simultaneously - */ + // As the edges do not properly intersect one edge must lie entirely + // to one side of another. Note that the special case where edges are + // collinear does not need to be handled as those edges will never be + // in the tree simultaneously - /* b is left of a */ + // b is left of a if (left_on(v1, v2, w1) && left_on(v1, v2, w2)) return -1; - /* b is right of a */ + // b is right of a if (left_on(v2, v1, w1) && left_on(v2, v1, w2)) return 1; - /* a is left of b */ + // a is left of b if (left_on(w1, w2, v1) && left_on(w1, w2, v2)) return 1; - /* a is right of b */ + // a is right of b return -1; } -static int -inside(Common::Point p, vertex_t *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_t *) 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 */ +static int inside(Common::Point p, vertex_t *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_t *) 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)) { Common::Point prev = CLIST_PREV(vertex, entries)->v; Common::Point next = CLIST_NEXT(vertex, entries)->v; 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 - */ + // 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 - */ + // 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; } @@ -744,44 +654,40 @@ inside(Common::Point p, vertex_t *vertex) return 0; } -static int -visible(vertex_t *vertex, vertex_t *vertex_prev, int visible, aatree_t *tree) -/* Determines whether or not a vertex is visible from vertex_cur -** Parameters: (vertex_t *) vertex: The vertex -** (vertex_t *) vertex_prev: The previous vertex in the sort -** order, or NULL -** (int) visible: 1 if vertex_prev is visible, 0 otherwise -** (aatree_t *) tree: The tree of edges intersected by the -** sweeping line -** Returns : (int) 1 if vertex is visible from vertex_cur, 0 otherwise -*/ -{ +static int visible(vertex_t *vertex, vertex_t *vertex_prev, int visible, aatree_t *tree) { + // Determines whether or not a vertex is visible from vertex_cur + // Parameters: (vertex_t *) vertex: The vertex + // (vertex_t *) vertex_prev: The previous vertex in the sort + // order, or NULL + // (int) visible: 1 if vertex_prev is visible, 0 otherwise + // (aatree_t *) tree: The tree of edges intersected by the + // sweeping line + // Returns : (int) 1 if vertex is visible from vertex_cur, 0 otherwise vertex_t *edge; Common::Point p = vertex_cur->v; Common::Point w = vertex->v; aatree_t *tree_n = tree; - /* Check if sweeping line intersects the interior of the polygon - ** locally at vertex - */ + // Check if sweeping line intersects the interior of the polygon + // locally at vertex if (inside(p, vertex)) return 0; - /* If vertex_prev is on the sweeping line, then vertex is invisible - ** if vertex_prev is invisible - */ + // If vertex_prev is on the sweeping line, then vertex is invisible + // if vertex_prev is invisible if (vertex_prev && !visible && between(p, w, vertex_prev->v)) return 0; - /* Find leftmost node of tree */ + // Find leftmost node of tree */ while ((tree_n = aatree_walk(tree_n, AATREE_WALK_LEFT))) tree = tree_n; + edge = (vertex_t*)aatree_get_data(tree); if (edge) { Common::Point p1, p2; - /* Check for intersection with sweeping line before vertex */ + // Check for intersection with sweeping line before vertex clockwise(edge, &p1, &p2); if (left(p2, p1, p) && left(p1, p2, w)) return 0; @@ -790,15 +696,12 @@ visible(vertex_t *vertex, vertex_t *vertex_prev, int visible, aatree_t *tree) return 1; } -static void -visible_vertices(pf_state_t *s, vertex_t *vert) -/* Determines all vertices that are visible from a particular vertex and -** updates the visibility matrix -** Parameters: (pf_state_t *) s: The pathfinding state -** (vertex_t *) vert: The vertex -** Returns : (void) -*/ -{ +static void visible_vertices(pf_state_t *s, vertex_t *vert) { + // Determines all vertices that are visible from a particular vertex and + // updates the visibility matrix + // Parameters: (pf_state_t *) s: The pathfinding state + // (vertex_t *) vert: The vertex + // Returns : (void) aatree_t *tree = aatree_new(); Common::Point p = vert->v; polygon_t *polygon; @@ -806,22 +709,21 @@ visible_vertices(pf_state_t *s, vertex_t *vert) int is_visible; vertex_t **vert_sorted = (vertex_t**)sci_malloc(sizeof(vertex_t *) * s->vertices); - /* Sort vertices by angle (first) and distance (second) */ + // Sort vertices by angle (first) and distance (second) memcpy(vert_sorted, s->vertex_index, sizeof(vertex_t *) * s->vertices); vertex_cur = vert; qsort(vert_sorted, s->vertices, sizeof(vertex_t *), vertex_compare); LIST_FOREACH(polygon, &s->polygons, entries) { vertex_t *vertex; - vertex = CLIST_FIRST(&polygon->vertices); - /* Check that there is more than one vertex. */ + // Check that there is more than one vertex. if (VERTEX_HAS_EDGES(vertex)) CLIST_FOREACH(vertex, &polygon->vertices, entries) { Common::Point high, low; - /* Add edges that intersect the initial position of the sweeping line */ + // Add edges that intersect the initial position of the sweeping line clockwise(vertex, &high, &low); if ((high.y < p.y) && (low.y >= p.y) && !POINT_EQUAL(low, p)) @@ -831,18 +733,18 @@ visible_vertices(pf_state_t *s, vertex_t *vert) is_visible = 1; - /* The first vertex will be vertex_cur, so we skip it */ + // The first vertex will be vertex_cur, so we skip it for (i = 1; i < s->vertices; i++) { vertex_t *v1; - /* Compute visibility of vertex_index[i] */ + // Compute visibility of vertex_index[i] is_visible = visible(vert_sorted[i], vert_sorted[i - 1], is_visible, tree); - /* Update visibility matrix */ + // Update visibility matrix if (is_visible) SET_VISIBLE(s, vert->idx, vert_sorted[i]->idx); - /* Delete anti-clockwise edges from tree */ + // Delete anti-clockwise edges from tree v1 = CLIST_PREV(vert_sorted[i], entries); if (left(p, vert_sorted[i]->v, v1->v)) { if (aatree_delete(v1, &tree, edge_compare)) @@ -855,7 +757,7 @@ visible_vertices(pf_state_t *s, vertex_t *vert) sciprintf("[avoidpath] Error: failed to remove edge from tree\n"); } - /* Add clockwise edges of collinear vertices when sweeping line moves */ + // Add clockwise edges of collinear vertices when sweeping line moves if ((i < s->vertices - 1) && !collinear(p, vert_sorted[i]->v, vert_sorted[i + 1]->v)) { int j; for (j = i; (j >= 1) && collinear(p, vert_sorted[i]->v, vert_sorted[j]->v); j--) { @@ -872,72 +774,55 @@ visible_vertices(pf_state_t *s, vertex_t *vert) free(vert_sorted); - /* Free tree */ + // Free tree aatree_free(tree); } -static float -distance(pointf_t a, pointf_t b) -/* Computes the distance between two pointfs -** Parameters: (Common::Point) a, b: The two pointfs -** Returns : (int) The distance between a and b, rounded to int -*/ -{ +static float distance(pointf_t a, pointf_t b) { + // Computes the distance between two pointfs + // Parameters: (Common::Point) a, b: The two pointfs + // Returns : (int) The distance between a and b, rounded to int float w = a.x - b.x; float h = a.y - b.y; return sqrt(w * w + h * h); } -static int -point_on_screen_border(Common::Point p) -/* Determines if a point lies on the screen border -** Parameters: (Common::Point) p: The point -** Returns : (int) 1 if p lies on the screen border, 0 otherwise -*/ -{ - /* FIXME get dimensions from somewhere? */ +static int point_on_screen_border(Common::Point p) { + // Determines if a point lies on the screen border + // Parameters: (Common::Point) p: The point + // Returns : (int) 1 if p lies on the screen border, 0 otherwise + // FIXME get dimensions from somewhere? return (p.x == 0) || (p.x == 319) || (p.y == 0) || (p.y == 189); } -static int -edge_on_screen_border(Common::Point p, Common::Point q) -/* Determines if an edge lies on the screen border -** Parameters: (Common::Point) p, q: The edge (p, q) -** Returns : (int) 1 if (p, q) lies on the screen border, 0 otherwise -*/ -{ - /* FIXME get dimensions from somewhere? */ - return ((p.x == 0 && q.x == 0) - || (p.x == 319 && q.x == 319) - || (p.y == 0 && q.y == 0) - || (p.y == 189 && q.y == 189)); +static int edge_on_screen_border(Common::Point p, Common::Point q) { + // Determines if an edge lies on the screen border + // Parameters: (Common::Point) p, q: The edge (p, q) + // Returns : (int) 1 if (p, q) lies on the screen border, 0 otherwise + // FIXME get dimensions from somewhere? + return ((p.x == 0 && q.x == 0) || (p.x == 319 && q.x == 319) || (p.y == 0 && q.y == 0) || (p.y == 189 && q.y == 189)); } -static int -find_free_point(pointf_t f, polygon_t *polygon, Common::Point *ret) -/* Searches for a nearby point that is not contained in a polygon -** Parameters: (pointf_t) f: The pointf to search nearby -** (polygon_t *) polygon: The polygon -** Returns : (int) PF_OK on success, PF_FATAL otherwise -** (Common::Point) *ret: The non-contained point on success -*/ -{ +static int find_free_point(pointf_t f, polygon_t *polygon, Common::Point *ret) { + // Searches for a nearby point that is not contained in a polygon + // Parameters: (pointf_t) f: The pointf to search nearby + // (polygon_t *) polygon: The polygon + // Returns : (int) PF_OK on success, PF_FATAL otherwise + // (Common::Point) *ret: The non-contained point on success Common::Point p; - /* Try nearest point first */ - p = Common::Point((int) floor(f.x + 0.5), - (int) floor(f.y + 0.5)); + // Try nearest point first + p = Common::Point((int)floor(f.x + 0.5), (int)floor(f.y + 0.5)); if (contained(p, polygon) != CONT_INSIDE) { *ret = p; return PF_OK; } - p = Common::Point((int) floor(f.x), - (int) floor(f.y)); + p = Common::Point((int)floor(f.x), (int)floor(f.y)); - /* Try (x, y), (x + 1, y), (x , y + 1) and (x + 1, y + 1) */ + // Try (x, y), (x + 1, y), (x , y + 1) and (x + 1, y + 1) if (contained(p, polygon) == CONT_INSIDE) { p.x++; if (contained(p, polygon) == CONT_INSIDE) { @@ -954,15 +839,12 @@ find_free_point(pointf_t f, polygon_t *polygon, Common::Point *ret) return PF_OK; } -static int -near_point(Common::Point p, polygon_t *polygon, Common::Point *ret) -/* Computes the near point of a point contained in a polygon -** Parameters: (Common::Point) p: The point -** (polygon_t *) polygon: The polygon -** Returns : (int) PF_OK on success, PF_FATAL otherwise -** (Common::Point) *ret: The near point of p in polygon on success -*/ -{ +static int near_point(Common::Point p, polygon_t *polygon, Common::Point *ret) { + // Computes the near point of a point contained in a polygon + // Parameters: (Common::Point) p: The point + // (polygon_t *) polygon: The polygon + // Returns : (int) PF_OK on success, PF_FATAL otherwise + // (Common::Point) *ret: The near point of p in polygon on success vertex_t *vertex; pointf_t near_p; float dist = HUGE_DISTANCE; @@ -974,17 +856,17 @@ near_point(Common::Point p, polygon_t *polygon, Common::Point *ret) pointf_t new_point; float new_dist; - /* Ignore edges on the screen border */ + // Ignore edges on the screen border if (edge_on_screen_border(p1, p2)) continue; - /* Compute near point */ + // Compute near point w = p2.x - p1.x; h = p2.y - p1.y; l = sqrt(w * w + h * h); u = ((p.x - p1.x) * (p2.x - p1.x) + (p.y - p1.y) * (p2.y - p1.y)) / (l * l); - /* Clip to edge */ + // Clip to edge if (u < 0.0f) u = 0.0f; if (u > 1.0f) @@ -1001,50 +883,41 @@ near_point(Common::Point p, polygon_t *polygon, Common::Point *ret) } } - /* Find point not contained in polygon */ + // Find point not contained in polygon return find_free_point(near_p, polygon, ret); } -static int -intersection(Common::Point a, Common::Point b, vertex_t *vertex, pointf_t *ret) -/* Computes the intersection point of a line segment and an edge (not -** including the vertices themselves) -** Parameters: (Common::Point) a, b: The line segment (a, b) -** (vertex_t *) vertex: The first vertex of the edge -** Returns : (int) FP_OK on success, PF_ERROR otherwise -** (pointf_t) *ret: The intersection point -*/ -{ - /* Parameters of parametric equations */ +static int intersection(Common::Point a, Common::Point b, vertex_t *vertex, pointf_t *ret) { + // Computes the intersection point of a line segment and an edge (not + // including the vertices themselves) + // Parameters: (Common::Point) a, b: The line segment (a, b) + // (vertex_t *) vertex: The first vertex of the edge + // Returns : (int) FP_OK on success, PF_ERROR otherwise + // (pointf_t) *ret: The intersection point + // Parameters of parametric equations float s, t; - /* Numerator and denominator of equations */ + // Numerator and denominator of equations float num, denom; Common::Point c = vertex->v; Common::Point d = CLIST_NEXT(vertex, entries)->v; - denom = a.x * (float)(d.y - c.y) + - b.x * (float)(c.y - d.y) + - d.x * (float)(b.y - a.y) + - c.x * (float)(a.y - b.y); + denom = a.x * (float)(d.y - c.y) + b.x * (float)(c.y - d.y) + + d.x * (float)(b.y - a.y) + c.x * (float)(a.y - b.y); if (denom == 0.0) - /* Segments are parallel, no intersection */ + // Segments are parallel, no intersection return PF_ERROR; - num = a.x * (float)(d.y - c.y) + - c.x * (float)(a.y - d.y) + - d.x * (float)(c.y - a.y); + num = a.x * (float)(d.y - c.y) + c.x * (float)(a.y - d.y) + d.x * (float)(c.y - a.y); s = num / denom; - num = -(a.x * (float)(c.y - b.y) + - b.x * (float)(a.y - c.y) + - c.x * (float)(b.y - a.y)); + num = -(a.x * (float)(c.y - b.y) + b.x * (float)(a.y - c.y) + c.x * (float)(b.y - a.y)); t = num / denom; if ((0.0 <= s) && (s <= 1.0) && (0.0 < t) && (t < 1.0)) { - /* Intersection found */ + // Intersection found ret->x = a.x + s * (b.x - a.x); ret->y = a.y + s * (b.y - a.y); return PF_OK; @@ -1053,19 +926,16 @@ intersection(Common::Point a, Common::Point b, vertex_t *vertex, pointf_t *ret) return PF_ERROR; } -static int -nearest_intersection(pf_state_t *s, Common::Point p, Common::Point q, Common::Point *ret) -/* Computes the nearest intersection point of a line segment and the polygon -** set. Intersection points that are reached from the inside of a polygon -** are ignored as are improper intersections which do not obstruct -** visibility -** Parameters: (pf_state_t *) s: The pathfinding state -** (Common::Point) p, q: The line segment (p, q) -** Returns : (int) PF_OK on success, PF_ERROR when no intersections were -** found, PF_FATAL otherwise -** (Common::Point) *ret: On success, the closest intersection point -*/ -{ +static int nearest_intersection(pf_state_t *s, Common::Point p, Common::Point q, Common::Point *ret) { + // Computes the nearest intersection point of a line segment and the polygon + // set. Intersection points that are reached from the inside of a polygon + // are ignored as are improper intersections which do not obstruct + // visibility + // Parameters: (pf_state_t *) s: The pathfinding state + // (Common::Point) p, q: The line segment (p, q) + // Returns : (int) PF_OK on success, PF_ERROR when no intersections were + // found, PF_FATAL otherwise + // (Common::Point) *ret: On success, the closest intersection point polygon_t *polygon = 0; pointf_t isec; polygon_t *ipolygon = 0; @@ -1078,22 +948,20 @@ nearest_intersection(pf_state_t *s, Common::Point p, Common::Point q, Common::Po float new_dist; pointf_t new_isec; - /* Check for intersection with vertex */ + // Check for intersection with vertex if (between(p, q, vertex->v)) { - /* Skip this vertex if we hit it from the - ** inside of the polygon - */ + // Skip this vertex if we hit it from the + // inside of the polygon if (inside(q, vertex)) { new_isec.x = vertex->v.x; new_isec.y = vertex->v.y; } else continue; } else { - /* Check for intersection with edges */ + // Check for intersection with edges - /* Skip this edge if we hit it from the - ** inside of the polygon - */ + // Skip this edge if we hit it from the + // inside of the polygon if (!left(vertex->v, CLIST_NEXT(vertex, entries)->v, q)) continue; @@ -1113,27 +981,24 @@ nearest_intersection(pf_state_t *s, Common::Point p, Common::Point q, Common::Po if (dist == HUGE_DISTANCE) return PF_ERROR; - /* Find point not contained in polygon */ + // Find point not contained in polygon return find_free_point(isec, ipolygon, ret); } -static int -fix_point(pf_state_t *s, Common::Point p, Common::Point *ret, polygon_t **ret_pol) -/* Checks a point for containment in any of the polygons in the polygon set. -** If the point is contained in a totally accessible polygon that polygon -** is removed from the set. If the point is contained in a polygon of another -** type the near point is returned. Otherwise the original point is returned -** Parameters: (Common::Point) p: The point -** Returns : (int) PF_OK on success, PF_FATAL otherwise -** (Common::Point) *ret: A valid input point for pathfinding -** (polygon_t *) *ret_pol: The polygon p was contained in if p -** != *ret, NULL otherwise -*/ -{ +static int fix_point(pf_state_t *s, Common::Point p, Common::Point *ret, polygon_t **ret_pol) { + // Checks a point for containment in any of the polygons in the polygon set. + // If the point is contained in a totally accessible polygon that polygon + // is removed from the set. If the point is contained in a polygon of another + // type the near point is returned. Otherwise the original point is returned + // Parameters: (Common::Point) p: The point + // Returns : (int) PF_OK on success, PF_FATAL otherwise + // (Common::Point) *ret: A valid input point for pathfinding + // (polygon_t *) *ret_pol: The polygon p was contained in if p + // != *ret, NULL otherwise polygon_t *polygon; *ret_pol = NULL; - /* Check for polygon containment */ + // Check for polygon containment LIST_FOREACH(polygon, &s->polygons, entries) { if (contained(p, polygon) != CONT_OUTSIDE) break; @@ -1143,15 +1008,13 @@ fix_point(pf_state_t *s, Common::Point p, Common::Point *ret, polygon_t **ret_po Common::Point near_p; if (polygon->type == POLY_TOTAL_ACCESS) { - /* Remove totally accessible polygon if it contains - ** p - */ + // Remove totally accessible polygon if it contains p LIST_REMOVE(polygon, entries); *ret = p; return PF_OK; } - /* Otherwise, compute near point */ + // Otherwise, compute near point if (near_point(p, polygon, &near_p) == PF_OK) { *ret = near_p; @@ -1164,27 +1027,24 @@ fix_point(pf_state_t *s, Common::Point p, Common::Point *ret, polygon_t **ret_po return PF_FATAL; } - /* p is not contained in any polygon */ + // p is not contained in any polygon *ret = p; return PF_OK; } -static vertex_t * -merge_point(pf_state_t *s, Common::Point v) -/* Merges a point into the polygon set. A new vertex is allocated for this -** point, unless a matching vertex already exists. If the point is on an -** already existing edge that edge is split up into two edges connected by -** the new vertex -** Parameters: (pf_state_t *) s: The pathfinding state -** (Common::Point) v: The point to merge -** Returns : (vertex_t *) The vertex corresponding to v -*/ -{ +static vertex_t *merge_point(pf_state_t *s, Common::Point v) { + // Merges a point into the polygon set. A new vertex is allocated for this + // point, unless a matching vertex already exists. If the point is on an + // already existing edge that edge is split up into two edges connected by + // the new vertex + // Parameters: (pf_state_t *) s: The pathfinding state + // (Common::Point) v: The point to merge + // Returns : (vertex_t *) The vertex corresponding to v vertex_t *vertex; vertex_t *v_new; polygon_t *polygon; - /* Check for already existing vertex */ + // Check for already existing vertex LIST_FOREACH(polygon, &s->polygons, entries) { CLIST_FOREACH(vertex, &polygon->vertices, entries) if (POINT_EQUAL(vertex->v, v)) @@ -1193,21 +1053,21 @@ merge_point(pf_state_t *s, Common::Point v) v_new = vertex_new(v); - /* Check for point being on an edge */ + // Check for point being on an edge LIST_FOREACH(polygon, &s->polygons, entries) - /* Skip single-vertex polygons */ + // Skip single-vertex polygons if (VERTEX_HAS_EDGES(CLIST_FIRST(&polygon->vertices))) CLIST_FOREACH(vertex, &polygon->vertices, entries) { vertex_t *next = CLIST_NEXT(vertex, entries); if (between(vertex->v, next->v, v)) { - /* Split edge by adding vertex */ + // Split edge by adding vertex CLIST_INSERT_AFTER(vertex, v_new, entries); return v_new; } } - /* Add point as single-vertex polygon */ + // Add point as single-vertex polygon polygon = polygon_new(POLY_BARRED_ACCESS); CLIST_INSERT_HEAD(&polygon->vertices, v_new, entries); LIST_INSERT_HEAD(&s->polygons, polygon, entries); @@ -1215,14 +1075,11 @@ merge_point(pf_state_t *s, Common::Point v) return v_new; } -static polygon_t * -convert_polygon(state_t *s, reg_t polygon) -/* Converts an SCI polygon into a polygon_t -** Parameters: (state_t *) s: The game state -** (reg_t) polygon: The SCI polygon to convert -** Returns : (polygon_t *) The converted polygon -*/ -{ +static polygon_t *convert_polygon(state_t *s, reg_t polygon) { + // Converts an SCI polygon into a polygon_t + // Parameters: (state_t *) s: The game state + // (reg_t) polygon: The SCI polygon to convert + // Returns : (polygon_t *) The converted polygon int i; reg_t points = GET_SEL32(polygon, points); int size = KP_UINT(GET_SEL32(polygon, size)); @@ -1240,13 +1097,10 @@ convert_polygon(state_t *s, reg_t polygon) return poly; } -static void -free_polygon(polygon_t *polygon) -/* Frees a polygon and its vertices -** Parameters: (polygon_t *) polygons: The polygon -** Returns : (void) -*/ -{ +static void free_polygon(polygon_t *polygon) { + // Frees a polygon and its vertices + // Parameters: (polygon_t *) polygons: The polygon + // Returns : (void) while (!CLIST_EMPTY(&polygon->vertices)) { vertex_t *vertex = CLIST_FIRST(&polygon->vertices); CLIST_REMOVE(&polygon->vertices, vertex, entries); @@ -1256,13 +1110,10 @@ free_polygon(polygon_t *polygon) free(polygon); } -static void -free_pf_state(pf_state_t *p) -/* Frees a pathfinding state -** Parameters: (pf_state_t *) p: The pathfinding state -** Returns : (void) -*/ -{ +static void free_pf_state(pf_state_t *p) { + // Frees a pathfinding state + // Parameters: (pf_state_t *) p: The pathfinding state + // Returns : (void) if (p->vertex_index) free(p->vertex_index); @@ -1278,15 +1129,12 @@ free_pf_state(pf_state_t *p) free(p); } -static void -change_polygons_opt_0(pf_state_t *s) -/* Changes the polygon list for optimization level 0 (used for keyboard -** support). Totally accessible polygons are removed and near-point -** accessible polygons are changed into totally accessible polygons. -** Parameters: (pf_state_t *) s: The pathfinding state -** Returns : (void) -*/ -{ +static void change_polygons_opt_0(pf_state_t *s) { + // Changes the polygon list for optimization level 0 (used for keyboard + // support). Totally accessible polygons are removed and near-point + // accessible polygons are changed into totally accessible polygons. + // Parameters: (pf_state_t *) s: The pathfinding state + // Returns : (void) polygon_t *polygon = LIST_FIRST(&s->polygons); while (polygon) { @@ -1303,18 +1151,15 @@ change_polygons_opt_0(pf_state_t *s) } } -static pf_state_t * -convert_polygon_set(state_t *s, reg_t poly_list, Common::Point start, Common::Point end, int opt) -/* Converts the SCI input data for pathfinding -** Parameters: (state_t *) s: The game state -** (reg_t) poly_list: Polygon list -** (Common::Point) start: The start point -** (Common::Point) end: The end point -** (int) opt: Optimization level (0, 1 or 2) -** Returns : (pf_state_t *) On success a newly allocated pathfinding state, -** NULL otherwise -*/ -{ +static pf_state_t *convert_polygon_set(state_t *s, reg_t poly_list, Common::Point start, Common::Point end, int opt) { + // Converts the SCI input data for pathfinding + // Parameters: (state_t *) s: The game state + // (reg_t) poly_list: Polygon list + // (Common::Point) start: The start point + // (Common::Point) end: The end point + // (int) opt: Optimization level (0, 1 or 2) + // Returns : (pf_state_t *) On success a newly allocated pathfinding state, + // NULL otherwise polygon_t *polygon; int err; int count = 0; @@ -1327,7 +1172,7 @@ convert_polygon_set(state_t *s, reg_t poly_list, Common::Point start, Common::Po pf_s->keep_end = 0; pf_s->vertex_index = NULL; - /* Convert all polygons */ + // Convert all polygons if (poly_list.segment) { list_t *list = LOOKUP_LIST(poly_list); node_t *node = LOOKUP_NODE(list->first); @@ -1341,10 +1186,10 @@ convert_polygon_set(state_t *s, reg_t poly_list, Common::Point start, Common::Po } if (opt == 0) { - /* Keyboard support */ + // Keyboard support change_polygons_opt_0(pf_s); - /* Find nearest intersection */ + // Find nearest intersection err = nearest_intersection(pf_s, start, end, &start); if (err == PF_FATAL) { @@ -1352,9 +1197,7 @@ convert_polygon_set(state_t *s, reg_t poly_list, Common::Point start, Common::Po free_pf_state(pf_s); return NULL; } else if (err == PF_OK) - /* Keep original start position if intersection - ** was found - */ + // Keep original start position if intersection was found pf_s->keep_start = 1; } else { if (fix_point(pf_s, start, &start, &polygon) != PF_OK) { @@ -1362,7 +1205,7 @@ convert_polygon_set(state_t *s, reg_t poly_list, Common::Point start, Common::Po free_pf_state(pf_s); return NULL; } else if (polygon) { - /* Start position has moved */ + // Start position has moved pf_s->keep_start = 1; if ((polygon->type != POLY_NEAREST_ACCESS)) sciprintf("[avoidpath] Warning: start position at unreachable location\n"); @@ -1374,18 +1217,17 @@ convert_polygon_set(state_t *s, reg_t poly_list, Common::Point start, Common::Po free_pf_state(pf_s); return NULL; } else { - /* Keep original end position if it is contained in a - ** near-point accessible polygon - */ + // Keep original end position if it is contained in a + // near-point accessible polygon if (polygon && (polygon->type == POLY_NEAREST_ACCESS)) pf_s->keep_end = 1; } - /* Merge start and end points into polygon set */ + // Merge start and end points into polygon set pf_s->vertex_start = merge_point(pf_s, start); pf_s->vertex_end = merge_point(pf_s, end); - /* Allocate and build vertex index */ + // Allocate and build vertex index pf_s->vertex_index = (vertex_t**)sci_malloc(sizeof(vertex_t *) * (count + 2)); count = 0; @@ -1401,19 +1243,16 @@ convert_polygon_set(state_t *s, reg_t poly_list, Common::Point start, Common::Po pf_s->vertices = count; - /* Allocate and clear visibility matrix */ - pf_s->vis_matrix = (char*)sci_calloc(pf_s->vertices * VIS_MATRIX_ROW_SIZE(pf_s->vertices), 1); + // Allocate and clear visibility matrix + pf_s->vis_matrix = (char *)sci_calloc(pf_s->vertices * VIS_MATRIX_ROW_SIZE(pf_s->vertices), 1); return pf_s; } -static void -visibility_graph(pf_state_t *s) -/* Computes the visibility graph -** Parameters: (pf_state_t *) s: The pathfinding state -** Returns : (void) -*/ -{ +static void visibility_graph(pf_state_t *s) { + // Computes the visibility graph + // Parameters: (pf_state_t *) s: The pathfinding state + // Returns : (void) polygon_t *polygon; LIST_FOREACH(polygon, &s->polygons, entries) { @@ -1424,13 +1263,10 @@ visibility_graph(pf_state_t *s) } } -static int -intersecting_polygons(pf_state_t *s) -/* Detects (self-)intersecting polygons -** Parameters: (pf_state_t *) s: The pathfinding state -** Returns : (int) 1 if s contains (self-)intersecting polygons, 0 otherwise -*/ -{ +static int intersecting_polygons(pf_state_t *s) { + // Detects (self-)intersecting polygons + // Parameters: (pf_state_t *) s: The pathfinding state + // Returns : (int) 1 if s contains (self-)intersecting polygons, 0 otherwise int i, j; for (i = 0; i < s->vertices; i++) { @@ -1442,7 +1278,7 @@ intersecting_polygons(pf_state_t *s) if (!VERTEX_HAS_EDGES(v2)) continue; - /* Skip neighbouring edges */ + // Skip neighbouring edges if ((CLIST_NEXT(v1, entries) == v2) || CLIST_PREV(v1, entries) == v2) continue; @@ -1456,26 +1292,23 @@ intersecting_polygons(pf_state_t *s) return 0; } -static void -dijkstra(pf_state_t *s) -/* Computes a shortest path from vertex_start to vertex_end. The caller can -** construct the resulting path by following the path_prev links from -** vertex_end back to vertex_start. If no path exists vertex_end->path_prev -** will be NULL -** Parameters: (pf_state_t *) s: The pathfinding state -** Returns : (void) -*/ -{ +static void dijkstra(pf_state_t *s) { + // Computes a shortest path from vertex_start to vertex_end. The caller can + // construct the resulting path by following the path_prev links from + // vertex_end back to vertex_start. If no path exists vertex_end->path_prev + // will be NULL + // Parameters: (pf_state_t *) s: The pathfinding state + // Returns : (void) polygon_t *polygon; - /* Vertices of which the shortest path is known */ + // Vertices of which the shortest path is known LIST_HEAD(done_head, vertex) done; - /* The remaining vertices */ + // The remaining vertices LIST_HEAD(remain_head, vertex) remain; LIST_INIT(&remain); LIST_INIT(&done); - /* Start out with all vertices in set remain */ + // Start out with all vertices in set remain LIST_FOREACH(polygon, &s->polygons, entries) { vertex_t *vertex; @@ -1485,13 +1318,13 @@ dijkstra(pf_state_t *s) s->vertex_start->dist = 0.0f; - /* Loop until we find vertex_end */ + // Loop until we find vertex_end while (1) { int i; vertex_t *vertex, *vertex_min = 0; float min = HUGE_DISTANCE; - /* Find vertex at shortest distance from set done */ + // Find vertex at shortest distance from set done LIST_FOREACH(vertex, &remain, dijkstra) { if (vertex->dist < min) { vertex_min = vertex; @@ -1504,25 +1337,24 @@ dijkstra(pf_state_t *s) return; } - /* If vertex_end is at shortest distance we can stop */ + // If vertex_end is at shortest distance we can stop if (vertex_min == s->vertex_end) return; - /* Move vertex from set remain to set done */ + // Move vertex from set remain to set done LIST_REMOVE(vertex_min, dijkstra); LIST_INSERT_HEAD(&done, vertex_min, dijkstra); for (i = 0; i < s->vertices; i++) { - /* Adjust upper bound for all vertices that are visible from vertex_min */ + // Adjust upper bound for all vertices that are visible from vertex_min if (IS_VISIBLE(s, vertex_min->idx, i)) { float new_dist; - /* Avoid plotting path along screen edge */ + // Avoid plotting path along screen edge if ((s->vertex_index[i] != s->vertex_end) && point_on_screen_border(s->vertex_index[i]->v)) continue; - new_dist = vertex_min->dist + distance(to_pointf(vertex_min->v), - to_pointf(s->vertex_index[i]->v)); + new_dist = vertex_min->dist + distance(to_pointf(vertex_min->v), to_pointf(s->vertex_index[i]->v)); if (new_dist < s->vertex_index[i]->dist) { s->vertex_index[i]->dist = new_dist; s->vertex_index[i]->path_prev = vertex_min; @@ -1532,14 +1364,11 @@ dijkstra(pf_state_t *s) } } -static reg_t -output_path(pf_state_t *p, state_t *s) -/* Stores the final path in newly allocated dynmem -** Parameters: (pf_state_t *) p: The pathfinding state -** (state_t *) s: The game state -** Returns : (reg_t) Pointer to dynmem containing path -*/ -{ +static reg_t output_path(pf_state_t *p, state_t *s) { + // Stores the final path in newly allocated dynmem + // Parameters: (pf_state_t *) p: The pathfinding state + // (state_t *) s: The game state + // Returns : (reg_t) Pointer to dynmem containing path int path_len = 0; byte *oref; reg_t output; @@ -1548,14 +1377,14 @@ output_path(pf_state_t *p, state_t *s) int unreachable = vertex->path_prev == NULL; if (unreachable) { - /* If pathfinding failed we only return the path up to vertex_start */ - oref = sm_alloc_dynmem(&s->seg_manager, POLY_POINT_SIZE * 3, - AVOIDPATH_DYNMEM_STRING, &output); + // If pathfinding failed we only return the path up to vertex_start + oref = sm_alloc_dynmem(&s->seg_manager, POLY_POINT_SIZE * 3, AVOIDPATH_DYNMEM_STRING, &output); if (p->keep_start) POLY_SET_POINT(oref, 0, p->start.x, p->start.y); else POLY_SET_POINT(oref, 0, p->vertex_start->v.x, p->vertex_start->v.y); + POLY_SET_POINT(oref, 1, p->vertex_start->v.x, p->vertex_start->v.y); POLY_SET_POINT(oref, 2, POLY_LAST_POINT, POLY_LAST_POINT); @@ -1563,18 +1392,17 @@ output_path(pf_state_t *p, state_t *s) } while (vertex) { - /* Compute path length */ + // Compute path length path_len++; vertex = vertex->path_prev; } - oref = sm_alloc_dynmem(&s->seg_manager, POLY_POINT_SIZE * (path_len + 1 + p->keep_start + p->keep_end), - AVOIDPATH_DYNMEM_STRING, &output); + oref = sm_alloc_dynmem(&s->seg_manager, POLY_POINT_SIZE * (path_len + 1 + p->keep_start + p->keep_end), AVOIDPATH_DYNMEM_STRING, &output); - /* Sentinel */ + // Sentinel POLY_SET_POINT(oref, path_len + p->keep_start + p->keep_end, POLY_LAST_POINT, POLY_LAST_POINT); - /* Add original start and end points if needed */ + // Add original start and end points if needed if (p->keep_end) POLY_SET_POINT(oref, path_len + p->keep_start, p->end.x, p->end.y); if (p->keep_start) @@ -1583,7 +1411,7 @@ output_path(pf_state_t *p, state_t *s) i = path_len + p->keep_start - 1; if (unreachable) { - /* Return straight trajectory from start to end */ + // Return straight trajectory from start to end POLY_SET_POINT(oref, i - 1, p->vertex_start->v.x, p->vertex_start->v.y); POLY_SET_POINT(oref, i, p->vertex_end->v.x, p->vertex_end->v.y); return output; @@ -1609,8 +1437,7 @@ output_path(pf_state_t *p, state_t *s) return output; } -reg_t -kAvoidPath(state_t *s, int funct_nr, int argc, reg_t *argv) { +reg_t kAvoidPath(state_t *s, int funct_nr, int argc, reg_t *argv) { Common::Point start = Common::Point(SKPV(0), SKPV(1)); if (s->debug_mode & (1 << SCIkAVOIDPATH_NR)) { @@ -1633,7 +1460,7 @@ kAvoidPath(state_t *s, int funct_nr, int argc, reg_t *argv) { if (polygon->type == POLY_CONTAINED_ACCESS) { sciprintf("[avoidpath] Warning: containment test performed on contained access polygon\n"); - /* Semantics unknown, assume barred access semantics */ + // Semantics unknown, assume barred access semantics polygon->type = POLY_BARRED_ACCESS; } @@ -1645,7 +1472,7 @@ kAvoidPath(state_t *s, int funct_nr, int argc, reg_t *argv) { case 7 : { Common::Point end = Common::Point(SKPV(2), SKPV(3)); reg_t poly_list = argv[4]; - /* int poly_list_size = UKPV(5); */ + //int poly_list_size = UKPV(5); int opt = UKPV_OR_ALT(6, 1); reg_t output; pf_state_t *p; @@ -1690,7 +1517,7 @@ kAvoidPath(state_t *s, int funct_nr, int argc, reg_t *argv) { output = output_path(p, s); free_pf_state(p); - /* Memory is freed by explicit calls to Memory */ + // Memory is freed by explicit calls to Memory return output; } |