[Scummvm-cvs-logs] SF.net SVN: scummvm:[38829] scummvm/trunk/engines/sci
fingolfin at users.sourceforge.net
fingolfin at users.sourceforge.net
Tue Feb 24 06:07:15 CET 2009
Revision: 38829
http://scummvm.svn.sourceforge.net/scummvm/?rev=38829&view=rev
Author: fingolfin
Date: 2009-02-24 05:07:15 +0000 (Tue, 24 Feb 2009)
Log Message:
-----------
SCI: Replaced vertex list used for dijkstra algo by Common::List; got rid of include/list.h
Modified Paths:
--------------
scummvm/trunk/engines/sci/engine/kpathing.cpp
Removed Paths:
-------------
scummvm/trunk/engines/sci/include/list.h
Modified: scummvm/trunk/engines/sci/engine/kpathing.cpp
===================================================================
--- scummvm/trunk/engines/sci/engine/kpathing.cpp 2009-02-24 04:56:35 UTC (rev 38828)
+++ scummvm/trunk/engines/sci/engine/kpathing.cpp 2009-02-24 05:07:15 UTC (rev 38829)
@@ -29,7 +29,6 @@
#include "sci/include/engine.h"
#include "sci/engine/aatree.h"
-#include "sci/include/list.h"
#include "sci/gfx/gfx_widgets.h"
#include "common/list.h"
@@ -111,9 +110,6 @@
Vertex *cle_prev; // previous element
} entries;
- // Dijkstra list entry
- LIST_ENTRY(Vertex) dijkstra; // TODO: Convert this
-
// Distance from starting vertex
float dist;
@@ -1379,21 +1375,20 @@
// Parameters: (PathfindingState *) s: The pathfinding state
// Returns : (void)
Polygon *polygon;
+
// Vertices of which the shortest path is known
- LIST_HEAD(done_head, Vertex) done;
+ VertexList done;
+
// The remaining vertices
- LIST_HEAD(remain_head, Vertex) remain;
+ VertexList remain;
- LIST_INIT(remain);
- LIST_INIT(done);
-
// Start out with all vertices in set remain
for (PolygonList::iterator it = s->polygons.begin(); it != s->polygons.end(); ++it) {
polygon = *it;
Vertex *vertex;
CLIST_FOREACH(vertex, &polygon->vertices, entries) {
- LIST_INSERT_HEAD(&remain, vertex, dijkstra);
+ remain.push_front(vertex);
}
}
@@ -1401,14 +1396,16 @@
// Loop until we find vertex_end
while (1) {
- int i;
- Vertex *vertex, *vertex_min = 0;
- float min = HUGE_DISTANCE;
-
// Find vertex at shortest distance from set done
- LIST_FOREACH(vertex, &remain, dijkstra) {
+ VertexList::iterator it;
+ VertexList::iterator vertex_min_it = remain.end();
+ Vertex *vertex_min = 0;
+ float min = HUGE_DISTANCE;
+ for (it = remain.begin(); it != remain.end(); ++it) {
+ Vertex *vertex = *it;
if (vertex->dist < min) {
- vertex_min = vertex;
+ vertex_min_it = it;
+ vertex_min = *vertex_min_it;
min = vertex->dist;
}
}
@@ -1423,10 +1420,10 @@
return;
// Move vertex from set remain to set done
- LIST_REMOVE(vertex_min, dijkstra);
- LIST_INSERT_HEAD(&done, vertex_min, dijkstra);
+ done.push_front(vertex_min);
+ remain.erase(vertex_min_it);
- for (i = 0; i < s->vertices; i++) {
+ for (int i = 0; i < s->vertices; i++) {
// Adjust upper bound for all vertices that are visible from vertex_min
if (IS_VISIBLE(s, vertex_min->idx, i)) {
float new_dist;
Deleted: scummvm/trunk/engines/sci/include/list.h
===================================================================
--- scummvm/trunk/engines/sci/include/list.h 2009-02-24 04:56:35 UTC (rev 38828)
+++ scummvm/trunk/engines/sci/include/list.h 2009-02-24 05:07:15 UTC (rev 38829)
@@ -1,109 +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$
- *
- */
-
-/*
- * Copyright (c) 1991, 1993
- * The Regents of the University of California. All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- * notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in the
- * documentation and/or other materials provided with the distribution.
- * 3. Neither the name of the University nor the names of its contributors
- * may be used to endorse or promote products derived from this software
- * without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- *
- * @(#)queue.h 8.5 (Berkeley) 8/20/94
- */
-
-/* 2006-04-21 Modified by Walter van Niftrik. */
-
-#ifndef _SCI_LIST_H
-#define _SCI_LIST_H
-
-#include "common/scummsys.h"
-
-namespace Sci {
-
-/* List definitions. */
-#define LIST_HEAD(name, type) \
-struct name { \
- type *lh_first; /* first element */ \
-}
-
-#define LIST_ENTRY(type) \
-struct { \
- type *le_next; /* next element */ \
- type **le_prev; /* address of previous next element */ \
-}
-
-#define LIST_INIT(head) do { \
- (head).lh_first = NULL; \
-} while (0)
-
-#define LIST_INSERT_HEAD(head, elm, field) do { \
- if (((elm)->field.le_next = (head)->lh_first) != NULL) \
- (head)->lh_first->field.le_prev = &(elm)->field.le_next;\
- (head)->lh_first = (elm); \
- (elm)->field.le_prev = &(head)->lh_first; \
-} while (0)
-
-#define LIST_REMOVE(elm, field) do { \
- if ((elm)->field.le_next != NULL) \
- (elm)->field.le_next->field.le_prev = \
- (elm)->field.le_prev; \
- *(elm)->field.le_prev = (elm)->field.le_next; \
-} while (0)
-
-#define LIST_FOREACH(var, head, field) \
- for ((var) = ((head)->lh_first); \
- (var); \
- (var) = ((var)->field.le_next))
-
-/* List access methods. */
-#define LIST_EMPTY(head) ((head)->lh_first == NULL)
-#define LIST_FIRST(head) ((head)->lh_first)
-#define LIST_NEXT(elm, field) ((elm)->field.le_next)
-
-
-} // End of namespace Sci
-
-#endif /* !_SCI_LIST_H */
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