From 197c2bbb99771228f0161ede64b15b456881b28f Mon Sep 17 00:00:00 2001 From: Walter van Niftrik Date: Sun, 5 Apr 2009 00:06:22 +0000 Subject: SCI: Replaced AATree by Common::List in AvoidPath. AATree does not help when the input size is this small. svn-id: r39855 --- engines/sci/engine/aatree.h | 198 ---------------------------------------- engines/sci/engine/kpathing.cpp | 100 ++++++++++---------- 2 files changed, 52 insertions(+), 246 deletions(-) delete mode 100644 engines/sci/engine/aatree.h (limited to 'engines/sci') diff --git a/engines/sci/engine/aatree.h b/engines/sci/engine/aatree.h deleted file mode 100644 index e1d7c61b85..0000000000 --- a/engines/sci/engine/aatree.h +++ /dev/null @@ -1,198 +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$ - * - */ - -#ifndef SCI_ENGINE_AATREE_H -#define SCI_ENGINE_AATREE_H - -#include "common/func.h" - -namespace Sci { - -// Andersson tree implementation. - -template -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 > -class AATree { -public: - AATree() { - _bottom = new AATreeNode; - _root = _bottom; - } - - AATree(const AATree &tree) { - _bottom = new AATreeNode; - _root = copyTree(tree._root, tree._bottom); - } - - const AATree &operator=(const AATree &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() const { - AATreeNode *node = _root; - - if (node == _bottom) - return NULL; - - while (node->_left != _bottom) - node = node->_left; - - return &node->_key; - } - -private: - AATreeNode *_root; - AATreeNode *_bottom; - LessFunc _less; - -private: - void freeNode(AATreeNode *node) { - if (node == _bottom) - return; - - freeNode(node->_left); - freeNode(node->_right); - - delete node; - } - - void skew(AATreeNode *&node) { - if (node->_left->_level == node->_level) { - // Rotate right - AATreeNode *temp = node; - node = node->_left; - temp->_left = node->_right; - node->_right = temp; - } - } - - void split(AATreeNode *&node) { - if (node->_right->_right->_level == node->_level) { - // Rotate left - AATreeNode *temp = node; - node = node->_right; - temp->_right = node->_left; - node->_left = temp; - node->_level++; - } - } - - bool removeNode(const Key &key, AATreeNode *&node) { - bool ok = false; - static AATreeNode *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 *&node) { - if (node == _bottom) { - node = new AATreeNode(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 *copyTree(AATreeNode *node, const AATreeNode *bottom) { - if (node == bottom) - return _bottom; - - return new AATreeNode(node->_key, copyTree(node->_left, bottom), copyTree(node->_right, bottom), node->_level); - } -}; - -} // End of namespace Sci - -#endif // SCI_ENIGNE_AATREE_H diff --git a/engines/sci/engine/kpathing.cpp b/engines/sci/engine/kpathing.cpp index cfb5fbad2b..759bc275ec 100644 --- a/engines/sci/engine/kpathing.cpp +++ b/engines/sci/engine/kpathing.cpp @@ -24,7 +24,6 @@ */ #include "sci/engine/state.h" -#include "sci/engine/aatree.h" #include "sci/engine/kernel.h" #include "sci/gfx/gfx_widgets.h" #include "sci/gfx/gfx_state_internal.h" // required for gfxw_port_t, gfxw_container_t @@ -682,33 +681,33 @@ static void clockwise(const Vertex *v, const Common::Point *&p1, const Common::P } } -struct EdgeIsCloser: public Common::BinaryFunction { - // Compares two edges that are intersected by the sweeping line by distance - // from vertex_cur - // 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 { - const Common::Point *v1, *v2, *w1, *w2; +/** + * Compares two edges that are intersected by the sweeping line by distance from vertex_cur + * @param a the first edge + * @param b the second edge + * @return true if a is closer to vertex_cur than b, false otherwise + */ +static bool edgeIsCloser(const Vertex *a, const Vertex *b) { + const Common::Point *v1, *v2, *w1, *w2; - // Check for comparison of the same edge - if (a == b) - return false; + // Check for comparison of the same edge + if (a == b) + return false; - // 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 - // 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); + // 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); - // 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. + // 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. - return ((left_on(*v1, *v2, *w1) && left_on(*v1, *v2, *w2)) || (left_on(*w2, *w1, *v1) && left_on(*w2, *w1, *v2))); - } -}; + return ((left_on(*v1, *v2, *w1) && left_on(*v1, *v2, *w2)) || (left_on(*w2, *w1, *v1) && left_on(*w2, *w1, *v2))); +} static int inside(const Common::Point &p, Vertex *vertex) { // Determines whether or not a line from a point to a vertex intersects the @@ -739,17 +738,15 @@ static int inside(const Common::Point &p, Vertex *vertex) { return 0; } -typedef AATree EdgeAATree; - /** * Determines whether or not a vertex is visible from vertex_cur. * @param vertex the vertex * @param vertex_prev the previous vertex in the sort order, or NULL * @param visible true if vertex_prev is visible, false otherwise - * @param tree the tree of edges intersected by the sweeping line + * @param intersected the list of edges intersected by the sweeping line * @return true if vertex is visible from vertex_cur, false otherwise */ -static bool visible(Vertex *vertex, Vertex *vertex_prev, bool visible, const EdgeAATree &tree) { +static bool visible(Vertex *vertex, Vertex *vertex_prev, bool visible, const VertexList &intersected) { const Common::Point &p = vertex_cur->v; const Common::Point &w = vertex->v; @@ -763,17 +760,27 @@ static bool visible(Vertex *vertex, Vertex *vertex_prev, bool visible, const Edg if (vertex_prev && !visible && between(p, w, vertex_prev->v)) return false; - const Vertex *const *edge = tree.findSmallest(); + if (intersected.empty()) { + // No intersected edges + return true; + } - if (edge) { - const Common::Point *p1, *p2; + // Look for the intersected edge that is closest to vertex_cur + VertexList::const_iterator it = intersected.begin(); + const Vertex *edge = *it++; - // Check for intersection with sweeping line before vertex - clockwise(*edge, p1, p2); - if (left(*p2, *p1, p) && left(*p1, *p2, w)) - return false; + for (; it != intersected.end(); ++it) { + if (edgeIsCloser(*it, edge)) + edge = *it; } + const Common::Point *p1, *p2; + + // Check for intersection with sweeping line before vertex + clockwise(edge, p1, p2); + if (left(*p2, *p1, p) && left(*p1, *p2, w)) + return false; + return true; } @@ -784,7 +791,8 @@ static bool visible(Vertex *vertex, Vertex *vertex_prev, bool visible, const Edg * @return list of vertices that are visible from vert */ static VertexList *visible_vertices(PathfindingState *s, Vertex *vert) { - EdgeAATree tree; + // List of edges intersected by the sweeping line + VertexList intersected; VertexList *visVerts = new VertexList(); const Common::Point &p = vert->v; @@ -806,7 +814,7 @@ static VertexList *visible_vertices(PathfindingState *s, Vertex *vert) { clockwise(vertex, high, low); if ((high->y < p.y) && (low->y >= p.y) && (*low != p)) - tree.insert(vertex); + intersected.push_front(vertex); } } } @@ -818,24 +826,20 @@ static VertexList *visible_vertices(PathfindingState *s, Vertex *vert) { Vertex *v1; // Compute visibility of vertex_index[i] - is_visible = visible(s->vertex_index[i], s->vertex_index[i - 1], is_visible, tree); + is_visible = visible(s->vertex_index[i], s->vertex_index[i - 1], is_visible, intersected); // Update visibility matrix if (is_visible) visVerts->push_front(s->vertex_index[i]); - // Delete anti-clockwise edges from tree + // Delete anti-clockwise edges from list v1 = CLIST_PREV(s->vertex_index[i]); - if (left(p, s->vertex_index[i]->v, v1->v)) { - if (!tree.remove(v1)) - sciprintf("[avoidpath] Error: failed to remove edge from tree\n"); - } + if (left(p, s->vertex_index[i]->v, v1->v)) + intersected.remove(v1); v1 = CLIST_NEXT(s->vertex_index[i]); - if (left(p, s->vertex_index[i]->v, v1->v)) { - if (!tree.remove(s->vertex_index[i])) - sciprintf("[avoidpath] Error: failed to remove edge from tree\n"); - } + if (left(p, s->vertex_index[i]->v, v1->v)) + intersected.remove(s->vertex_index[i]); // Add clockwise edges of collinear vertices when sweeping line moves if ((i < s->vertices - 1) && !collinear(p, s->vertex_index[i]->v, s->vertex_index[i + 1]->v)) { @@ -843,11 +847,11 @@ static VertexList *visible_vertices(PathfindingState *s, Vertex *vert) { for (j = i; (j >= 1) && collinear(p, s->vertex_index[i]->v, s->vertex_index[j]->v); j--) { v1 = CLIST_PREV(s->vertex_index[j]); if (left(s->vertex_index[j]->v, p, v1->v)) - tree.insert(v1); + intersected.push_front(v1); v1 = CLIST_NEXT(s->vertex_index[j]); if (left(s->vertex_index[j]->v, p, v1->v)) - tree.insert(s->vertex_index[j]); + intersected.push_front(s->vertex_index[j]); } } } -- cgit v1.2.3