[Scummvm-cvs-logs] SF.net SVN: scummvm:[38603] scummvm/trunk/engines/sci/engine/kpathing.cpp
aquadran at users.sourceforge.net
aquadran at users.sourceforge.net
Fri Feb 20 17:59:06 CET 2009
Revision: 38603
http://scummvm.svn.sourceforge.net/scummvm/?rev=38603&view=rev
Author: aquadran
Date: 2009-02-20 16:59:05 +0000 (Fri, 20 Feb 2009)
Log Message:
-----------
formating
Modified Paths:
--------------
scummvm/trunk/engines/sci/engine/kpathing.cpp
Modified: scummvm/trunk/engines/sci/engine/kpathing.cpp
===================================================================
--- scummvm/trunk/engines/sci/engine/kpathing.cpp 2009-02-20 16:34:21 UTC (rev 38602)
+++ scummvm/trunk/engines/sci/engine/kpathing.cpp 2009-02-20 16:59:05 UTC (rev 38603)
@@ -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 @@
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 @@
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 @@
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 @@
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_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 @@
}
}
-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 @@
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 @@
}
}
-
-/*** 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 @@
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 @@
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 @@
}
}
- /* 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 @@
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 @@
}
}
-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 @@
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 @@
}
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
}
}
- /* 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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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);
}
-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(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 @@
}
}
-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 @@
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 @@
}
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 @@
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 @@
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 @@
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 @@
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 @@
}
}
-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 @@
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 @@
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 @@
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 @@
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 @@
}
}
-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 @@
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 @@
}
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 @@
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 @@
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 @@
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 @@
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 @@
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;
}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
More information about the Scummvm-git-logs
mailing list