Difference between revisions of "SCI/FreeSCI/Pathfinding/Implementation"

Jump to navigation Jump to search

SCI/FreeSCI/Pathfinding/Implementation (view source)

Revision as of 10:32, 30 January 2009

416 bytes added ,  10:32, 30 January 2009
Fix broken links, the SVN is not working anymore. Beautify link in reference
(Beautify links in reference, replace section numbers by their names and linkify them)
(Fix broken links, the SVN is not working anymore. Beautify link in reference)
 
Line 3: Line 3:


This report does not contain the actual program text that we produced. The program text is spread across the following four files that can be found on-line:
This report does not contain the actual program text that we produced. The program text is spread across the following four files that can be found on-line:
* http://svn.a-eskwadraat.nl/wsvn/FreeSCI/freesci/branches/glutton/src/engine/kpathing.c?op=file&rev=1571&sc=0
* [http://void.cs.colorado.edu/cgi-bin/darcsweb.cgi?r=glutton;a=annotate_shade;h=20060520133532-00091-969972be3900210a314816cfff729940128ac439.gz;f=src/engine/kpathing.c src/engine/kpathing.c] <!-- revision 1571 -->
* http://svn.a-eskwadraat.nl/wsvn/FreeSCI/freesci/branches/glutton/src/scicore/aatree.c?op=file&rev=1571&sc=0
* [http://void.cs.colorado.edu/cgi-bin/darcsweb.cgi?r=glutton;a=annotate_shade;h=20060520133532-00091-969972be3900210a314816cfff729940128ac439.gz;f=src/scicore/aatree.c src/scicore/aatree.c] <!--revision 1571) -->
* http://svn.a-eskwadraat.nl/wsvn/FreeSCI/freesci/branches/glutton/src/include/aatree.h?op=file&rev=1571&sc=0
* [http://void.cs.colorado.edu/cgi-bin/darcsweb.cgi?r=glutton;a=annotate_shade;h=20060520133532-00091-969972be3900210a314816cfff729940128ac439.gz;f=src/include/aatree.h src/include/aatree.h] <!-- revision 1571 -->
* http://svn.a-eskwadraat.nl/wsvn/FreeSCI/freesci/branches/glutton/src/include/list.h?op=file&rev=1571&sc=0
* [http://void.cs.colorado.edu/cgi-bin/darcsweb.cgi?r=glutton;a=annotate_shade;h=20060520133532-00091-969972be3900210a314816cfff729940128ac439.gz;f=src/include/list.h src/include/list.h] <!-- revision 1571 -->


==Data types==
==Data types==
Line 13: Line 13:
A potential pitfall here is overflow. However, in our case this is not a big problem as FreeSCI is written for machines with an integer size of at least 32 bits and the integer size in SCI is only 16 bits.
A potential pitfall here is overflow. However, in our case this is not a big problem as FreeSCI is written for machines with an integer size of at least 32 bits and the integer size in SCI is only 16 bits.


The two main choices for the polygon data type are an array of vertices, or a circular list of vertices. Arrays are convenient when vertices of a polygon are processed sequentially, but this is not the case here as the visibility graph algorithm processes the vertices by angle. Therefore we chose lists instead of arrays. As C does not provide any built-in list data types we took and modified the list macros from FreeBSD’s queue.h header file <ref>The FreeBSD Project, FreeBSD source code file queue.h, revision
The two main choices for the polygon data type are an array of vertices, or a circular list of vertices. Arrays are convenient when vertices of a polygon are processed sequentially, but this is not the case here as the visibility graph algorithm processes the vertices by angle. Therefore we chose lists instead of arrays. As C does not provide any built-in list data types we took and modified the list macros from FreeBSD’s queue.h header file <ref>The FreeBSD Project, [http://www.freebsd.org/cgi/cvsweb.cgi/~checkout~/src/sys/sys/queue.h?rev=1.66&content-type=text/plain FreeBSD source code file queue.h], revision
1.66, http://www.freebsd.org/cgi/cvsweb.cgi/~checkout~/src/sys/sys/queue.h?rev=1.66&content-type=text/plain, 2006.</ref>. We decided to order the vertices in such a way that the barred area is always left of an edge. That means that barred, total and near-point access polygons use anticlockwise ordering, and contained access polygons use clockwise ordering. As we have seen in Section 3.5, SCI games do not have such a fixed vertex ordering, so we added code to detect the current vertex ordering, and reverse it if necessary.
1.66, 2006.</ref>. We decided to order the vertices in such a way that the barred area is always left of an edge. That means that barred, total and near-point access polygons use anticlockwise ordering, and contained access polygons use clockwise ordering. As we have seen in Section 3.5, SCI games do not have such a fixed vertex ordering, so we added code to detect the current vertex ordering, and reverse it if necessary.


For the balanced search tree required for the visibility graph algorithm we implemented an Andersson tree <ref>A. Andersson. Balanced Search Trees Made Simple, Third Workshop on Algorithms and Data Structures, pp 60-71, Springer-Verlag, 1993, ISBN 3540571558.</ref>. Andersson trees are easier to implement than other BB-trees yet offer similar performance. For storing the visibility graph itself we decided to use an adjacency matrix.
For the balanced search tree required for the visibility graph algorithm we implemented an Andersson tree <ref>A. Andersson. Balanced Search Trees Made Simple, Third Workshop on Algorithms and Data Structures, pp 60-71, Springer-Verlag, 1993, ISBN 3540571558.</ref>. Andersson trees are easier to implement than other BB-trees yet offer similar performance. For storing the visibility graph itself we decided to use an adjacency matrix.
Timofonic
245

edits

Retrieved from "https://wiki.scummvm.org/index.php?title=Special:MobileDiff/10055"

Navigation menu