236
edits
Difference between revisions of "SCI/FreeSCI/Pathfinding/Implementation"
SCI/FreeSCI/Pathfinding/Implementation (view source)
Revision as of 10:32, 30 January 2009
, 10:32, 30 January 2009Fix 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:// | * [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:// | * [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:// | * [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:// | * [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, | 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, 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. | ||