[Scummvm-cvs-logs] SF.net SVN: scummvm:[50013] scummvm/trunk/engines/sci/engine/kpathing.cpp
fingolfin at users.sourceforge.net
fingolfin at users.sourceforge.net
Fri Jun 18 11:37:25 CEST 2010
Revision: 50013
http://scummvm.svn.sourceforge.net/scummvm/?rev=50013&view=rev
Author: fingolfin
Date: 2010-06-18 09:37:25 +0000 (Fri, 18 Jun 2010)
Log Message:
-----------
SCI: Doxygenify some comments
Modified Paths:
--------------
scummvm/trunk/engines/sci/engine/kpathing.cpp
Modified: scummvm/trunk/engines/sci/engine/kpathing.cpp
===================================================================
--- scummvm/trunk/engines/sci/engine/kpathing.cpp 2010-06-18 09:37:06 UTC (rev 50012)
+++ scummvm/trunk/engines/sci/engine/kpathing.cpp 2010-06-18 09:37:25 UTC (rev 50013)
@@ -436,33 +436,41 @@
}
}
+/**
+ * Computes the area of a triangle
+ * Parameters: (const Common::Point &) a, b, c: The points of the triangle
+ * Returns : (int) The area multiplied by two
+ */
static int area(const Common::Point &a, const Common::Point &b, const Common::Point &c) {
- // Computes the area of a triangle
- // Parameters: (const 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);
}
+/**
+ * Determines whether or not a point is to the left of a directed line
+ * Parameters: (const Common::Point &) a, b: The directed line (a, b)
+ * (const Common::Point &) c: The query point
+ * Returns : (int) true if c is to the left of (a, b), false otherwise
+ */
static bool left(const Common::Point &a, const Common::Point &b, const Common::Point &c) {
- // Determines whether or not a point is to the left of a directed line
- // Parameters: (const Common::Point &) a, b: The directed line (a, b)
- // (const Common::Point &) c: The query point
- // Returns : (int) true if c is to the left of (a, b), false otherwise
return area(a, b, c) > 0;
}
+/**
+ * Determines whether or not three points are collinear
+ * Parameters: (const Common::Point &) a, b, c: The three points
+ * Returns : (int) true if a, b, and c are collinear, false otherwise
+ */
static bool collinear(const Common::Point &a, const Common::Point &b, const Common::Point &c) {
- // Determines whether or not three points are collinear
- // Parameters: (const Common::Point &) a, b, c: The three points
- // Returns : (int) true if a, b, and c are collinear, false otherwise
return area(a, b, c) == 0;
}
+/**
+ * Determines whether or not a point lies on a line segment
+ * Parameters: (const Common::Point &) a, b: The line segment (a, b)
+ * (const Common::Point &) c: The query point
+ * Returns : (int) true if c lies on (a, b), false otherwise
+ */
static bool between(const Common::Point &a, const Common::Point &b, const Common::Point &c) {
- // Determines whether or not a point lies on a line segment
- // Parameters: (const Common::Point &) a, b: The line segment (a, b)
- // (const Common::Point &) c: The query point
- // Returns : (int) true if c lies on (a, b), false otherwise
if (!collinear(a, b, c))
return false;
@@ -473,25 +481,29 @@
return ((a.y <= c.y) && (c.y <= b.y)) || ((a.y >= c.y) && (c.y >= b.y));
}
+/**
+ * Determines whether or not two line segments properly intersect
+ * Parameters: (const Common::Point &) a, b: The line segment (a, b)
+ * (const Common::Point &) c, d: The line segment (c, d)
+ * Returns : (int) true if (a, b) properly intersects (c, d), false otherwise
+ */
static bool intersect_proper(const Common::Point &a, const Common::Point &b, const Common::Point &c, const Common::Point &d) {
- // Determines whether or not two line segments properly intersect
- // Parameters: (const Common::Point &) a, b: The line segment (a, b)
- // (const Common::Point &) c, d: The line segment (c, d)
- // Returns : (int) true if (a, b) properly intersects (c, d), false 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;
}
+/**
+ * Polygon containment test
+ * Parameters: (const Common::Point &) p: The point
+ * (Polygon *) 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(const Common::Point &p, Polygon *polygon) {
- // Polygon containment test
- // Parameters: (const Common::Point &) p: The point
- // (Polygon *) 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 *vertex;
@@ -549,10 +561,12 @@
return CONT_OUTSIDE;
}
+/**
+ * Computes polygon area
+ * Parameters: (Polygon *) polygon: The polygon
+ * Returns : (int) The area multiplied by two
+ */
static int polygon_area(Polygon *polygon) {
- // Computes polygon area
- // Parameters: (Polygon *) polygon: The polygon
- // Returns : (int) The area multiplied by two
Vertex *first = polygon->vertices.first();
Vertex *v;
int size = 0;
@@ -567,11 +581,13 @@
return size;
}
+/**
+ * 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 *) polygon: The polygon
+ */
static void fix_vertex_order(Polygon *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 *) polygon: The polygon
int area = polygon_area(polygon);
// When the polygon area is positive the vertices are ordered
@@ -584,13 +600,15 @@
}
}
+/**
+ * Determines whether or not a line from a point to a vertex intersects the
+ * interior of the polygon, locally at that vertex
+ * Parameters: (Common::Point) p: The point
+ * (Vertex *) vertex: The vertex
+ * Returns : (int) 1 if the line (p, vertex->v) intersects the interior of
+ * the polygon, locally at the vertex. 0 otherwise
+ */
static int inside(const Common::Point &p, Vertex *vertex) {
- // Determines whether or not a line from a point to a vertex intersects the
- // interior of the polygon, locally at that vertex
- // Parameters: (Common::Point) p: The point
- // (Vertex *) vertex: The vertex
- // Returns : (int) 1 if the line (p, vertex->v) intersects the interior of
- // the polygon, locally at the vertex. 0 otherwise
// Check that it's not a single-vertex polygon
if (VERTEX_HAS_EDGES(vertex)) {
const Common::Point &prev = CLIST_PREV(vertex)->v;
@@ -655,28 +673,34 @@
return visVerts;
}
+/**
+ * Determines if a point lies on the screen border
+ * Parameters: (const Common::Point &) p: The point
+ * Returns : (int) true if p lies on the screen border, false otherwise
+ */
bool PathfindingState::pointOnScreenBorder(const Common::Point &p) {
- // Determines if a point lies on the screen border
- // Parameters: (const Common::Point &) p: The point
- // Returns : (int) true if p lies on the screen border, false otherwise
return (p.x == 0) || (p.x == _width - 1) || (p.y == 0) || (p.y == _height - 1);
}
+/**
+ * Determines if an edge lies on the screen border
+ * Parameters: (const Common::Point &) p, q: The edge (p, q)
+ * Returns : (int) true if (p, q) lies on the screen border, false otherwise
+ */
bool PathfindingState::edgeOnScreenBorder(const Common::Point &p, const Common::Point &q) {
- // Determines if an edge lies on the screen border
- // Parameters: (const Common::Point &) p, q: The edge (p, q)
- // Returns : (int) true if (p, q) lies on the screen border, false otherwise
return ((p.x == 0 && q.x == 0) || (p.y == 0 && q.y == 0)
|| ((p.x == _width - 1) && (q.x == _width - 1))
|| ((p.y == _height - 1) && (q.y == _height - 1)));
}
+/**
+ * Searches for a nearby point that is not contained in a polygon
+ * Parameters: (FloatPoint) f: The pointf to search nearby
+ * (Polygon *) 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(FloatPoint f, Polygon *polygon, Common::Point *ret) {
- // Searches for a nearby point that is not contained in a polygon
- // Parameters: (FloatPoint) f: The pointf to search nearby
- // (Polygon *) 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
@@ -706,12 +730,14 @@
return PF_OK;
}
+/**
+ * Computes the near point of a point contained in a polygon
+ * Parameters: (const Common::Point &) p: The point
+ * (Polygon *) polygon: The polygon
+ * Returns : (int) PF_OK on success, PF_FATAL otherwise
+ * (Common::Point) *ret: The near point of p in polygon on success
+ */
int PathfindingState::findNearPoint(const Common::Point &p, Polygon *polygon, Common::Point *ret) {
- // Computes the near point of a point contained in a polygon
- // Parameters: (const Common::Point &) p: The point
- // (Polygon *) 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 *vertex;
FloatPoint near_p;
uint32 dist = HUGE_DISTANCE;
@@ -751,13 +777,15 @@
return find_free_point(near_p, polygon, ret);
}
+/**
+ * Computes the intersection point of a line segment and an edge (not
+ * including the vertices themselves)
+ * Parameters: (const Common::Point &) a, b: The line segment (a, b)
+ * (Vertex *) vertex: The first vertex of the edge
+ * Returns : (int) FP_OK on success, PF_ERROR otherwise
+ * (FloatPoint) *ret: The intersection point
+ */
static int intersection(const Common::Point &a, const Common::Point &b, Vertex *vertex, FloatPoint *ret) {
- // Computes the intersection point of a line segment and an edge (not
- // including the vertices themselves)
- // Parameters: (const Common::Point &) a, b: The line segment (a, b)
- // (Vertex *) vertex: The first vertex of the edge
- // Returns : (int) FP_OK on success, PF_ERROR otherwise
- // (FloatPoint) *ret: The intersection point
// Parameters of parametric equations
float s, t;
// Numerator and denominator of equations
@@ -790,16 +818,18 @@
return PF_ERROR;
}
+/**
+ * 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: (PathfindingState *) s: The pathfinding state
+ * (const 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(PathfindingState *s, const Common::Point &p, const 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: (PathfindingState *) s: The pathfinding state
- // (const 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 *polygon = 0;
FloatPoint isec;
Polygon *ipolygon = 0;
@@ -981,14 +1011,16 @@
return new_end;
}
+/**
+ * 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: (PathfindingState *) s: The pathfinding state
+ * (const Common::Point &) v: The point to merge
+ * Returns : (Vertex *) The vertex corresponding to v
+ */
static Vertex *merge_point(PathfindingState *s, const 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: (PathfindingState *) s: The pathfinding state
- // (const Common::Point &) v: The point to merge
- // Returns : (Vertex *) The vertex corresponding to v
Vertex *vertex;
Vertex *v_new;
Polygon *polygon;
@@ -1029,11 +1061,13 @@
return v_new;
}
+/**
+ * Converts an SCI polygon into a Polygon
+ * Parameters: (EngineState *) s: The game state
+ * (reg_t) polygon: The SCI polygon to convert
+ * Returns : (Polygon *) The converted polygon, or NULL on error
+ */
static Polygon *convert_polygon(EngineState *s, reg_t polygon) {
- // Converts an SCI polygon into a Polygon
- // Parameters: (EngineState *) s: The game state
- // (reg_t) polygon: The SCI polygon to convert
- // Returns : (Polygon *) The converted polygon, or NULL on error
SegManager *segMan = s->_segMan;
int i;
reg_t points = readSelector(segMan, polygon, SELECTOR(points));
@@ -1074,11 +1108,13 @@
return poly;
}
+/**
+ * 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: (PathfindingState *) s: The pathfinding state
+ */
static void change_polygons_opt_0(PathfindingState *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: (PathfindingState *) s: The pathfinding state
PolygonList::iterator it = s->polygons.begin();
while (it != s->polygons.end()) {
@@ -1096,15 +1132,17 @@
}
}
+/**
+ * Converts the SCI input data for pathfinding
+ * Parameters: (EngineState *) 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 : (PathfindingState *) On success a newly allocated pathfinding state,
+ * NULL otherwise
+ */
static PathfindingState *convert_polygon_set(EngineState *s, reg_t poly_list, Common::Point start, Common::Point end, int width, int height, int opt) {
- // Converts the SCI input data for pathfinding
- // Parameters: (EngineState *) 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 : (PathfindingState *) On success a newly allocated pathfinding state,
- // NULL otherwise
SegManager *segMan = s->_segMan;
Polygon *polygon;
int err;
@@ -1297,11 +1335,13 @@
return addr;
}
+/**
+ * Stores the final path in newly allocated dynmem
+ * Parameters: (PathfindingState *) p: The pathfinding state
+ * (EngineState *) s: The game state
+ * Returns : (reg_t) Pointer to dynmem containing path
+ */
static reg_t output_path(PathfindingState *p, EngineState *s) {
- // Stores the final path in newly allocated dynmem
- // Parameters: (PathfindingState *) p: The pathfinding state
- // (EngineState *) s: The game state
- // Returns : (reg_t) Pointer to dynmem containing path
int path_len = 0;
reg_t output;
Vertex *vertex = p->vertex_end;
@@ -1694,8 +1734,10 @@
}
}
-// This is a quite rare kernel function. An example of when it's called
-// is in QFG1VGA, after killing any monster.
+/**
+ * This is a quite rare kernel function. An example of when it's called
+ * is in QFG1VGA, after killing any monster.
+ */
reg_t kMergePoly(EngineState *s, int argc, reg_t *argv) {
// 3 parameters: raw polygon data, polygon list, list size
reg_t polygonData = argv[0];
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