aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--engines/sci/engine/aatree.cpp162
-rw-r--r--engines/sci/engine/aatree.h217
-rw-r--r--engines/sci/engine/kpathing.cpp90
3 files changed, 200 insertions, 269 deletions
diff --git a/engines/sci/engine/aatree.cpp b/engines/sci/engine/aatree.cpp
deleted file mode 100644
index 4cbe1b5c0a..0000000000
--- a/engines/sci/engine/aatree.cpp
+++ /dev/null
@@ -1,162 +0,0 @@
-/* ScummVM - Graphic Adventure Engine
- *
- * ScummVM is the legal property of its developers, whose names
- * are too numerous to list here. Please refer to the COPYRIGHT
- * file distributed with this source distribution.
- *
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of the GNU General Public License
- * as published by the Free Software Foundation; either version 2
- * of the License, or (at your option) any later version.
-
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU General Public License for more details.
-
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software
- * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
- *
- * $URL$
- * $Id$
- *
- */
-
-#include "sci/engine/aatree.h"
-
-#include "sci/sci_memory.h"
-
-namespace Sci {
-
-struct aatree {
- struct aatree *left, *right;
- int level;
- void *key;
-};
-
-// Sentinel node
-static aatree_t bottom = {&bottom, &bottom, 0, NULL};
-
-static void skew(aatree_t **t) {
- if ((*t)->left->level == (*t)->level) {
- // Rotate right
- aatree_t *temp = *t;
- *t = (*t)->left;
- temp->left = (*t)->right;
- (*t)->right = temp;
- }
-}
-
-static void split(aatree_t **t) {
- if ((*t)->right->right->level == (*t)->level) {
- // Rotate left
- aatree_t *temp = *t;
- *t = (*t)->right;
- temp->right = (*t)->left;
- (*t)->left = temp;
- (*t)->level++;
- }
-}
-
-static int delete_node(void *x, aatree_t **t, aatree_t *deleted, int (*compar)(const void *, const void *)) {
- int retval = -1;
-
- if (*t != &bottom) {
- // Search down the tree
- aatree_t **n;
-
- if (compar(x, (*t)->key) < 0)
- n = &(*t)->left;
- else {
- n = &(*t)->right;
- deleted = *t;
- }
-
- retval = delete_node(x, n, deleted, compar);
-
- // At the bottom of the tree we remove the element (if it is present)
- if ((*n == &bottom) && (deleted != &bottom) && (compar(x, deleted->key) == 0)) {
- aatree_t *temp;
- deleted->key = (*t)->key;
- temp = *t;
- *t = (*t)->right;
- free(temp);
- retval = 0;
- } else if (((*t)->left->level < (*t)->level - 1) || ((*t)->right->level < (*t)->level - 1)) {
- (*t)->level--;
- if ((*t)->right->level > (*t)->level)
- (*t)->right->level = (*t)->level;
- skew(t);
- skew(&(*t)->right);
- skew(&(*t)->right->right);
- split(t);
- split(&(*t)->right);
- }
- }
-
- return retval;
-}
-
-aatree_t *aatree_new() {
- return &bottom;
-}
-
-int aatree_insert(void *x, aatree_t **t, int (*compar)(const void *, const void *)) {
- int retval = -1;
- int c;
-
- if (*t == &bottom) {
- *t = (aatree_t *)sci_malloc(sizeof(aatree_t));
-
- if (*t == NULL)
- return 1;
-
- (*t)->key = x;
- (*t)->left = &bottom;
- (*t)->right = &bottom;
- (*t)->level = 1;
- return 0;
- }
-
- c = compar(x, (*t)->key);
-
- if (c < 0)
- retval = aatree_insert(x, &(*t)->left, compar);
- else if (c > 0)
- retval = aatree_insert(x, &(*t)->right, compar);
-
- skew(t);
- split(t);
- return retval;
-}
-
-int aatree_delete(void *x, aatree_t **t, int (*compar)(const void *, const void *)) {
- return delete_node(x, t, &bottom, compar);
-}
-
-aatree_t *aatree_walk(aatree_t *t, int direction) {
- if ((direction == AATREE_WALK_LEFT) && (t->left != &bottom))
- return t->left;
-
- if ((direction == AATREE_WALK_RIGHT) && (t->right != &bottom))
- return t->right;
-
- return NULL;
-}
-
-void *aatree_get_data(aatree_t *t) {
- return t->key;
-}
-
-void aatree_free(aatree_t *t) {
- if (t == &bottom)
- return;
-
- aatree_free(t->left);
- aatree_free(t->right);
-
- free(t);
-}
-
-} // End of namespace Sci
diff --git a/engines/sci/engine/aatree.h b/engines/sci/engine/aatree.h
index dea2ad1c66..74c97cf308 100644
--- a/engines/sci/engine/aatree.h
+++ b/engines/sci/engine/aatree.h
@@ -26,61 +26,172 @@
#ifndef SCI_ENGINE_AATREE_H
#define SCI_ENGINE_AATREE_H
+#include "common/func.h"
+
namespace Sci {
-/* Andersson tree implementation. Stores data pointers in a balanced binary
-** tree. A user-supplied comparison function defines the ordering. For the
-** semantics of this function see qsort(3)
-*/
-
-typedef struct aatree aatree_t;
-
-// Left child
-#define AATREE_WALK_LEFT 0
-// Right child
-#define AATREE_WALK_RIGHT 1
-
-aatree_t *aatree_new();
-/* Allocates a new aatree
-** Parameters: (void)
-** Returns : (aatree_t *) A newly allocated aatree
-*/
-
-void aatree_free(aatree_t *t);
-/* Deallocates an aatree
-** Parameters: (aatree_t *) t: The aatree
-** Returns : (void)
-*/
-
-int aatree_delete(void *x, aatree_t **t, int (*compar)(const void *, const void *));
-/* Deletes a data element from an aatree
-** Parameters: (void *) x: The data element to delete
-** (aatree_t **) t: The aatree
-** compar: The comparison function
-** Returns : (int) 0 on success, -1 if x wasn't found in t
-*/
-
-int aatree_insert(void *x, aatree_t **t, int (*compar)(const void *, const void *));
-/* Inserts a data element into an aatree
-** Parameters: (void *) x: The data element to insert
-** (aatree_t **) t: The aatree
-** compar: The comparison function
-** Returns : (int) 0 on success, -1 if x already exists in t
-*/
-
-aatree_t *aatree_walk(aatree_t *t, int direction);
-/* Walks to either the left or right child of a node
-** Parameters: (aatree_t *) t: The node
-** (int) direction: AATREE_WALK_LEFT or AATREE_WALK_RIGHT
-** Returns : (aatree_t *) The requested child of t or NULL if it doesn't
-** exist
-*/
-
-void *aatree_get_data(aatree_t *t);
-/* Returns the data element of a node
-** Parameters: (aatree_t *) t: The node
-** Returns : (void *) The data element
-*/
+// Andersson tree implementation.
+
+template<typename Key>
+struct AATreeNode {
+ AATreeNode() : _left(this), _right(this), _level(0) { }
+ AATreeNode(const Key &key, AATreeNode *left, AATreeNode *right, int level) : _key(key), _left(left), _right(right), _level(level) { }
+
+ Key _key;
+ AATreeNode *_left, *_right;
+ int _level;
+};
+
+template<typename Key, class LessFunc = Common::Less<Key> >
+class AATree {
+public:
+ AATree() {
+ _bottom = new AATreeNode<Key>;
+ _root = _bottom;
+ }
+
+ AATree(const AATree<Key, LessFunc> &tree) {
+ _bottom = new AATreeNode<Key>;
+ _root = copyTree(tree._root, tree._bottom);
+ }
+
+ const AATree<Key, LessFunc> &operator=(const AATree<Key, LessFunc> &tree) {
+ if (this != &tree) {
+ freeNode(_root);
+ _root = copyTree(tree._root, tree._bottom);
+ }
+
+ return *this;
+ }
+
+ ~AATree() {
+ freeNode(_root);
+ delete _bottom;
+ }
+
+ void insert(const Key &key) {
+ insertNode(key, _root);
+ }
+
+ bool remove(const Key &key) {
+ return removeNode(key, _root);
+ }
+
+ // Returns a pointer to the smallest Key or NULL if the tree is empty.
+ const Key *findSmallest() {
+ AATreeNode<Key> *node = _root;
+
+ if (node == _bottom)
+ return NULL;
+
+ while (node->_left != _bottom)
+ node = node->_left;
+
+ return &node->_key;
+ }
+
+private:
+ AATreeNode<Key> *_root;
+ AATreeNode<Key> *_bottom;
+ LessFunc _less;
+
+private:
+ void freeNode(AATreeNode<Key> *node) {
+ if (node == _bottom)
+ return;
+
+ freeNode(node->_left);
+ freeNode(node->_right);
+
+ delete node;
+ }
+
+ void skew(AATreeNode<Key> *&node) {
+ if (node->_left->_level == node->_level) {
+ // Rotate right
+ AATreeNode<Key> *temp = node;
+ node = node->_left;
+ temp->_left = node->_right;
+ node->_right = temp;
+ }
+ }
+
+ void split(AATreeNode<Key> *&node) {
+ if (node->_right->_right->_level == node->_level) {
+ // Rotate left
+ AATreeNode<Key> *temp = node;
+ node = node->_right;
+ temp->_right = node->_left;
+ node->_left = temp;
+ node->_level++;
+ }
+ }
+
+ bool removeNode(const Key &key, AATreeNode<Key> *&node) {
+ bool ok = false;
+ static AATreeNode<Key> *last, *deleted = _bottom;
+
+ if (node != _bottom) {
+ // Search down the tree and set pointers last and deleted
+ last = node;
+
+ if (_less(key, node->_key))
+ ok = removeNode(key, node->_left);
+ else {
+ deleted = node;
+ ok = removeNode(key, node->_right);
+ }
+
+ if ((node == last) && (deleted != _bottom) && !_less(key, deleted->_key) && !_less(deleted->_key, key)) {
+ // At the bottom of the tree we remove the element (if it is present)
+ deleted->_key = node->_key;
+ deleted = _bottom;
+ node = node->_right;
+ delete last;
+ return true;
+ }
+
+ if ((node->_left->_level < node->_level - 1) || (node->_right->_level < node->_level - 1)) {
+ // On the way back, we rebalance
+ node->_level--;
+ if (node->_right->_level > node->_level)
+ node->_right->_level = node->_level;
+
+ skew(node);
+ skew(node->_right);
+ skew(node->_right->_right);
+ split(node);
+ split(node->_right);
+ }
+ }
+
+ return ok;
+ }
+
+ void insertNode(const Key &key, AATreeNode<Key> *&node) {
+ if (node == _bottom) {
+ node = new AATreeNode<Key>(key, _bottom, _bottom, 1);
+
+ assert(node);
+ return;
+ }
+
+ if (_less(key, node->_key))
+ insertNode(key, node->_left);
+ else if (_less(node->_key, key))
+ insertNode(key, node->_right);
+
+ skew(node);
+ split(node);
+ }
+
+ AATreeNode<Key> *copyTree(AATreeNode<Key> *node, const AATreeNode<Key> *bottom) {
+ if (node == bottom)
+ return _bottom;
+
+ return new AATreeNode<Key>(node->_key, copyTree(node->_left, bottom), copyTree(node->_right, bottom), node->_level);
+ }
+};
} // End of namespace Sci
diff --git a/engines/sci/engine/kpathing.cpp b/engines/sci/engine/kpathing.cpp
index b5f34d3f07..2dcf17c793 100644
--- a/engines/sci/engine/kpathing.cpp
+++ b/engines/sci/engine/kpathing.cpp
@@ -644,10 +644,10 @@ static int vertex_compare(const void *a, const void *b) {
return -1;
}
-static void clockwise(Vertex *v, Common::Point *p1, Common::Point *p2) {
+static void clockwise(const Vertex *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 *) v: The first vertex of the edge
+ // Parameters: (const Vertex *) 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
@@ -662,45 +662,33 @@ static void clockwise(Vertex *v, Common::Point *p1, Common::Point *p2) {
}
}
-static int edge_compare(const void *a, const void *b) {
+struct EdgeIsCloser: public Common::BinaryFunction<const Vertex *, const Vertex *, bool> {
// 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
-
- if (a == b)
- return 0;
+ // Parameters: (const Vertex *const &) a, b: The first vertices of the edges
+ // Returns : (bool) true if a is closer to vertex_cur than b, false otherwise
+ bool operator()(const Vertex *const &a, const Vertex *const &b) const {
+ Common::Point v1, v2, w1, w2;
- // Order vertices clockwise so we know vertex_cur is to the right of
- // directed edges (v1, v2) and (w1, w2)
- clockwise((Vertex *)a, &v1, &v2);
- clockwise((Vertex *)b, &w1, &w2);
+ // Check for comparison of the same edge
+ if (a == b)
+ return false;
- // 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
+ // We can assume that the sweeping line intersects both edges and
+ // that the edges do not properly intersect
- // b is left of a
- if (left_on(v1, v2, w1) && left_on(v1, v2, w2))
- return -1;
-
- // b is right of a
- if (left_on(v2, v1, w1) && left_on(v2, v1, w2))
- return 1;
+ // Order vertices clockwise so we know vertex_cur is to the right of
+ // directed edges (v1, v2) and (w1, w2)
+ clockwise(a, &v1, &v2);
+ clockwise(b, &w1, &w2);
- // a is left of b
- if (left_on(w1, w2, v1) && left_on(w1, w2, v2))
- return 1;
+ // At this point we know that one edge must lie entirely to one side
+ // of the other, as the edges are not collinear and cannot intersect
+ // other than possibly sharing a vertex.
- // a is right of b
- return -1;
-}
+ return ((left_on(v1, v2, w1) && left_on(v1, v2, w2)) || (left_on(w2, w1, v1) && left_on(w2, w1, v2)));
+ }
+};
static int inside(Common::Point p, Vertex *vertex) {
// Determines whether or not a line from a point to a vertex intersects the
@@ -731,19 +719,20 @@ static int inside(Common::Point p, Vertex *vertex) {
return 0;
}
-static int visible(Vertex *vertex, Vertex *vertex_prev, int visible, aatree_t *tree) {
+typedef AATree<const Vertex *, EdgeIsCloser> EdgeAATree;
+
+static int visible(Vertex *vertex, Vertex *vertex_prev, int visible, EdgeAATree &tree) {
// Determines whether or not a vertex is visible from vertex_cur
// Parameters: (Vertex *) vertex: The vertex
// (Vertex *) 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
+ // (EdgeAATree &) tree: The tree of edges intersected by the
+ // sweeping line
// Returns : (int) 1 if vertex is visible from vertex_cur, 0 otherwise
- Vertex *edge;
+ const Vertex *const *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
@@ -755,17 +744,13 @@ static int visible(Vertex *vertex, Vertex *vertex_prev, int visible, aatree_t *t
if (vertex_prev && !visible && between(p, w, vertex_prev->v))
return 0;
- // Find leftmost node of tree */
- while ((tree_n = aatree_walk(tree_n, AATREE_WALK_LEFT)))
- tree = tree_n;
-
- edge = (Vertex*)aatree_get_data(tree);
+ edge = tree.findSmallest();
if (edge) {
Common::Point p1, p2;
// Check for intersection with sweeping line before vertex
- clockwise(edge, &p1, &p2);
+ clockwise(*edge, &p1, &p2);
if (left(p2, p1, p) && left(p1, p2, w))
return 0;
}
@@ -778,7 +763,7 @@ static void visible_vertices(PathfindingState *s, Vertex *vert) {
// updates the visibility matrix
// Parameters: (PathfindingState *) s: The pathfinding state
// (Vertex *) vert: The vertex
- aatree_t *tree = aatree_new();
+ EdgeAATree tree;
Common::Point p = vert->v;
Polygon *polygon;
int i;
@@ -804,7 +789,7 @@ static void visible_vertices(PathfindingState *s, Vertex *vert) {
clockwise(vertex, &high, &low);
if ((high.y < p.y) && (low.y >= p.y) && (low != p))
- aatree_insert(vertex, &tree, edge_compare);
+ tree.insert(vertex);
}
}
@@ -824,13 +809,13 @@ static void visible_vertices(PathfindingState *s, Vertex *vert) {
// Delete anti-clockwise edges from tree
v1 = CLIST_PREV(vert_sorted[i]);
if (left(p, vert_sorted[i]->v, v1->v)) {
- if (aatree_delete(v1, &tree, edge_compare))
+ if (!tree.remove(v1))
sciprintf("[avoidpath] Error: failed to remove edge from tree\n");
}
v1 = CLIST_NEXT(vert_sorted[i]);
if (left(p, vert_sorted[i]->v, v1->v)) {
- if (aatree_delete(vert_sorted[i], &tree, edge_compare))
+ if (!tree.remove(vert_sorted[i]))
sciprintf("[avoidpath] Error: failed to remove edge from tree\n");
}
@@ -840,19 +825,16 @@ static void visible_vertices(PathfindingState *s, Vertex *vert) {
for (j = i; (j >= 1) && collinear(p, vert_sorted[i]->v, vert_sorted[j]->v); j--) {
v1 = CLIST_PREV(vert_sorted[j]);
if (left(vert_sorted[j]->v, p, v1->v))
- aatree_insert(v1, &tree, edge_compare);
+ tree.insert(v1);
v1 = CLIST_NEXT(vert_sorted[j]);
if (left(vert_sorted[j]->v, p, v1->v))
- aatree_insert(vert_sorted[j], &tree, edge_compare);
+ tree.insert(vert_sorted[j]);
}
}
}
free(vert_sorted);
-
- // Free tree
- aatree_free(tree);
}
static float distance(FloatPoint a, FloatPoint b) {
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-24 00:01:59 +0000