summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--Makefile.am10
-rw-r--r--chickadee/audio.scm2
-rw-r--r--chickadee/data/array-list.scm (renamed from chickadee/array-list.scm)2
-rw-r--r--chickadee/data/grid.scm (renamed from chickadee/math/grid.scm)4
-rw-r--r--chickadee/data/heap.scm (renamed from chickadee/heap.scm)2
-rw-r--r--chickadee/data/path-finding.scm (renamed from chickadee/math/path-finding.scm)4
-rw-r--r--chickadee/data/queue.scm (renamed from chickadee/queue.scm)4
-rw-r--r--chickadee/graphics/engine.scm2
-rw-r--r--chickadee/graphics/model.scm2
-rw-r--r--chickadee/graphics/path.scm2
-rw-r--r--chickadee/scripting/agenda.scm2
-rw-r--r--chickadee/scripting/channel.scm4
-rw-r--r--doc/api.texi365
-rw-r--r--examples/grid.scm2
14 files changed, 207 insertions, 200 deletions
diff --git a/Makefile.am b/Makefile.am
index 3f7b7d0..9a108d5 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -44,21 +44,21 @@ SOURCES = \
chickadee/game-loop.scm \
chickadee/json.scm \
chickadee/base64.scm \
- chickadee/heap.scm \
- chickadee/array-list.scm \
- chickadee/queue.scm \
chickadee/freetype.scm \
chickadee/readline.scm \
chickadee/async-repl.scm \
+ chickadee/data/heap.scm \
+ chickadee/data/array-list.scm \
+ chickadee/data/queue.scm \
+ chickadee/data/grid.scm \
+ chickadee/data/path-finding.scm \
chickadee/math.scm \
chickadee/math/vector.scm \
chickadee/math/bezier.scm \
chickadee/math/matrix.scm \
chickadee/math/quaternion.scm \
chickadee/math/rect.scm \
- chickadee/math/grid.scm \
chickadee/math/easings.scm \
- chickadee/math/path-finding.scm \
chickadee/audio/mpg123.scm \
chickadee/audio/openal.scm \
chickadee/audio/vorbis.scm \
diff --git a/chickadee/audio.scm b/chickadee/audio.scm
index 86b52b2..b340f06 100644
--- a/chickadee/audio.scm
+++ b/chickadee/audio.scm
@@ -22,11 +22,11 @@
;;; Code:
(define-module (chickadee audio)
- #:use-module (chickadee array-list)
#:use-module (chickadee audio mpg123)
#:use-module ((chickadee audio openal) #:prefix openal:)
#:use-module (chickadee audio vorbis)
#:use-module (chickadee audio wav)
+ #:use-module (chickadee data array-list)
#:use-module (chickadee math)
#:use-module (chickadee math vector)
#:use-module (chickadee utils)
diff --git a/chickadee/array-list.scm b/chickadee/data/array-list.scm
index e18f9bf..eb3e32a 100644
--- a/chickadee/array-list.scm
+++ b/chickadee/data/array-list.scm
@@ -15,7 +15,7 @@
;;; along with this program. If not, see
;;; <http://www.gnu.org/licenses/>.
-(define-module (chickadee array-list)
+(define-module (chickadee data array-list)
#:use-module (chickadee utils)
#:use-module (ice-9 format)
#:use-module (rnrs base)
diff --git a/chickadee/math/grid.scm b/chickadee/data/grid.scm
index 7b2b6d6..085fbcb 100644
--- a/chickadee/math/grid.scm
+++ b/chickadee/data/grid.scm
@@ -23,8 +23,8 @@
;;
;;; Code:
-(define-module (chickadee math grid)
- #:use-module (chickadee array-list)
+(define-module (chickadee data grid)
+ #:use-module (chickadee data array-list)
#:use-module (chickadee math rect)
#:use-module (chickadee math vector)
#:use-module (ice-9 match)
diff --git a/chickadee/heap.scm b/chickadee/data/heap.scm
index 3a7d17e..2dd4027 100644
--- a/chickadee/heap.scm
+++ b/chickadee/data/heap.scm
@@ -15,7 +15,7 @@
;;; along with this program. If not, see
;;; <http://www.gnu.org/licenses/>.
-(define-module (chickadee heap)
+(define-module (chickadee data heap)
#:use-module (ice-9 format)
#:use-module (rnrs base)
#:use-module (srfi srfi-9)
diff --git a/chickadee/math/path-finding.scm b/chickadee/data/path-finding.scm
index d89c2fc..c9cadf9 100644
--- a/chickadee/math/path-finding.scm
+++ b/chickadee/data/path-finding.scm
@@ -20,8 +20,8 @@
;;
;;; Code
-(define-module (chickadee math path-finding)
- #:use-module (chickadee heap)
+(define-module (chickadee data path-finding)
+ #:use-module (chickadee data heap)
#:use-module (srfi srfi-9)
#:export (make-path-finder
path-finder?
diff --git a/chickadee/queue.scm b/chickadee/data/queue.scm
index 39f6318..157001c 100644
--- a/chickadee/queue.scm
+++ b/chickadee/data/queue.scm
@@ -15,11 +15,11 @@
;;; along with this program. If not, see
;;; <http://www.gnu.org/licenses/>.
-(define-module (chickadee queue)
+(define-module (chickadee data queue)
#:use-module (ice-9 format)
#:use-module (srfi srfi-9)
#:use-module (srfi srfi-9 gnu)
- #:use-module (chickadee array-list)
+ #:use-module (chickadee data array-list)
#:export (make-queue
queue?
queue-length
diff --git a/chickadee/graphics/engine.scm b/chickadee/graphics/engine.scm
index 3b8e743..7fe6def 100644
--- a/chickadee/graphics/engine.scm
+++ b/chickadee/graphics/engine.scm
@@ -1,5 +1,5 @@
(define-module (chickadee graphics engine)
- #:use-module (chickadee array-list)
+ #:use-module (chickadee data array-list)
#:use-module (chickadee graphics gl)
#:use-module (chickadee math matrix)
#:use-module (gl)
diff --git a/chickadee/graphics/model.scm b/chickadee/graphics/model.scm
index 309b00f..9de562b 100644
--- a/chickadee/graphics/model.scm
+++ b/chickadee/graphics/model.scm
@@ -22,8 +22,8 @@
;;; Code:
(define-module (chickadee graphics model)
- #:use-module (chickadee array-list)
#:use-module (chickadee base64)
+ #:use-module (chickadee data array-list)
#:use-module (chickadee json)
#:use-module (chickadee math matrix)
#:use-module (chickadee math quaternion)
diff --git a/chickadee/graphics/path.scm b/chickadee/graphics/path.scm
index ee501ce..27eb0b1 100644
--- a/chickadee/graphics/path.scm
+++ b/chickadee/graphics/path.scm
@@ -22,8 +22,8 @@
;;; Code:
(define-module (chickadee graphics path)
- #:use-module (chickadee array-list)
#:use-module (chickadee config)
+ #:use-module (chickadee data array-list)
#:use-module (chickadee graphics blend)
#:use-module (chickadee graphics buffer)
#:use-module (chickadee graphics color)
diff --git a/chickadee/scripting/agenda.scm b/chickadee/scripting/agenda.scm
index a5097dc..eb1fa65 100644
--- a/chickadee/scripting/agenda.scm
+++ b/chickadee/scripting/agenda.scm
@@ -16,9 +16,9 @@
;;; <http://www.gnu.org/licenses/>.
(define-module (chickadee scripting agenda)
+ #:use-module (chickadee data heap)
#:use-module (ice-9 match)
#:use-module (srfi srfi-9)
- #:use-module (chickadee heap)
#:export (make-agenda
agenda?
current-agenda
diff --git a/chickadee/scripting/channel.scm b/chickadee/scripting/channel.scm
index b54d3e2..c12ab9e 100644
--- a/chickadee/scripting/channel.scm
+++ b/chickadee/scripting/channel.scm
@@ -16,11 +16,11 @@
;;; <http://www.gnu.org/licenses/>.
(define-module (chickadee scripting channel)
+ #:use-module (chickadee data queue)
+ #:use-module (chickadee scripting script)
#:use-module (ice-9 match)
#:use-module (srfi srfi-9)
#:use-module (srfi srfi-9 gnu)
- #:use-module (chickadee queue)
- #:use-module (chickadee scripting script)
#:export (make-channel
channel?
channel-get!
diff --git a/doc/api.texi b/doc/api.texi
index 6a1361d..96803b8 100644
--- a/doc/api.texi
+++ b/doc/api.texi
@@ -4,6 +4,7 @@
* Graphics:: 2D and 3D rendering.
* Audio:: Make some noise.
* Scripting:: Bringing the game world to life.
+* Data Structures:: Spatial partitioning and more.
@end menu
@node Kernel
@@ -531,8 +532,6 @@ detection.
* Quaternions:: Rotations about an arbitrary axis.
* Easings:: Easing functions for interesting animations.
* Bezier Curves:: Cubic Bezier curves and paths in 2D space.
-* Path Finding:: Generic A* path finding.
-* Grid:: Spatial partitioning for bounding boxes.
@end menu
@node Basics
@@ -1377,183 +1376,6 @@ Modify the 2D vector @var{dest} in-place to contain the coordinates
for @var{bezier} at @var{t}.
@end deffn
-@node Path Finding
-@subsection Path Finding
-
-Most game worlds have maps. Often, these games have a need to move
-non-player characters around in an unscripted fashion. For example,
-in a real-time strategy game, the player may command one of their
-units to attack something in the enemy base. To do so, the unit must
-calculate the shortest route to get there. It wouldn't be a very fun
-game if units didn't know how to transport themselves efficiently.
-This is where path finding algorithms come in handy. The
-@code{(chickadee math path-finding)} module provides a generic
-implementation of the popular A* path finding algorithm. Just add a
-map implementation!
-
-The example below defines a very simple town map and finds the
-quickest way to get from the town common to the school.
-
-@example
-(define world-map
- '((town-common . (town-hall library))
- (town-hall . (town-common school))
- (library . (town-common cafe))
- (school . (town-hall cafe))
- (cafe . (library school))))
-(define (neighbors building)
- (assq-ref town-map building))
-(define (cost a b) 1)
-(define (distance a b) 1)
-(define pf (make-path-finder))
-(a* pf 'town-common 'school neighbors cost distance)
-@end example
-
-In this case, the @code{a*} procedure will return the list
-@code{(town-common town-hall school)}, which is indeed the shortest
-route. (The other possible route is @code{(town-common library cafe
-school)}.)
-
-The @code{a*} procedure does not know anything about about any kind of
-map and therefore must be told how to look up neighboring nodes, which
-is what the @code{neighbors} procedure in the example does. To
-simulate different types of terrain, a cost procedure is used. In
-this example, it is just as easy to move between any two nodes because
-@code{cost} always returns 1. In a real game, perhaps moving from
-from a field to a rocky hill would cost a lot more than moving from
-one field to another. Finally, a heuristic is used to calculate an
-approximate distance between two nodes on the map. In this simple
-association list based graph it is tough to calculate a distance
-between nodes, so the @code{distance} procedure isn't helpful and
-always returns 1. In a real game with a tile-based map, for example,
-the heuristic could be a quick Manhattan distance calculation based on
-the coordinates of the two map tiles. Choose an appropriate heuristic
-for optimal path finding!
-
-@deffn {Procedure} make-path-finder
-Return a new path finder object.
-@end deffn
-
-@deffn {Procedure} path-finder? obj
-Return @code{#t} if @var{obj} is a path finder.
-@end deffn
-
-@deffn {Procedure} a* path-finder start goal neighbors cost distance
-
-Return a list of nodes forming a path from @var{start} to @var{goal}
-using @var{path-finder} to hold state. @var{neighbors} is a procedure
-that accepts a node and returns a list of nodes that neighbor it.
-@var{cost} is a procedure that accepts two neighboring nodes and
-returns the cost of moving from the first to the second as a real
-number. @var{distance} is a procedure that accepts two nodes and
-returns an approximate distance between them.
-@end deffn
-
-@node Grid
-@subsection Grid
-
-The @code{(chickadee math grid)} module provides a simple spatial
-partitioning system for axis-aligned bounding boxes
-(@pxref{Rectangles}) in 2D space. The grid divides the world into
-tiles and keeps track of which rectangles occupy which tiles. When
-there are lots of moving objects in the game world that need collision
-detection, the grid greatly speeds up the process. Instead of
-checking collisions of each object against every other object (an
-O(n^2) operation), the grid quickly narrows down which objects could
-possibly be colliding and only performs collision testing against a
-small set of objects.
-
-In addition to checking for collisions, the grid also handles the
-resolution of collisions. Exactly how each collision is resolved is
-user-defined. A player bumping into a wall may slide against it. An
-enemy colliding with a projectile shot by the player may get pushed
-back in the opposite direction. Two players colliding may not need
-resolution at all and will just pass through each other. The way this
-works is that each time an object (A) is moved within the grid, the
-grid looks for an object (B) that may possibly be colliding with A. A
-user-defined procedure known as a ``filter'' is then called with both
-A and B. If the filter returns @code{#f}, it means that even if A and
-B are colliding, no collision resolution is needed. In this case the
-grid won't waste time checking if they really do collide because it
-doesn't matter. If A and B are collidable, then the filter returns a
-procedure that implements the resolution technique. The grid will
-then perform a collision test. If A and B are colliding, the resolver
-procedure is called. It's the resolvers job to adjust the objects
-such that they are no longer colliding. The grid module comes with a
-very simple resolution procedure, @code{slide}, that adjusts object A
-by the smallest amount so that it no longer overlaps with B. By using
-this filtering technique, a game can resolve collisions between
-different objects in different ways.
-
-@deffn {Procedure} make-grid [cell-size 64]
-Return a new grid partitioned into @var{cell-size} tiles.
-@end deffn
-
-@deffn {Procedure} grid? obj
-Return @code{#t} if @var{obj} is a grid.
-@end deffn
-
-@deffn {Procedure} cell? obj
-Return @code{#t} if @var{obj} is a grid cell.
-@end deffn
-
-@deffn {Procedure} cell-count cell
-Return the number of items in @var{cell}.
-@end deffn
-
-@deffn {Procedure} grid-cell-size grid
-Return the cell size of @var{grid}.
-@end deffn
-
-@deffn {Procedure} grid-cell-count grid
-Return the number of cells currently in @var{grid}.
-@end deffn
-
-@deffn {Procedure} grid-item-count grid
-Return the number of items in @var{grid}.
-@end deffn
-
-@deffn {Procedure} grid-add grid item x y @
- width height
-
-Add @var{item} to @var{grid} represented by the axis-aligned bounding
-box whose lower-left corner is at (@var{x}, @var{y}) and is
-@var{width} x @var{height} in size.
-@end deffn
-
-@deffn {Procedure} grid-remove grid item
-Return @var{item} from @var{grid}.
-@end deffn
-
-@deffn {Procedure} grid-clear grid
-Remove all items from @var{grid}.
-@end deffn
-
-@deffn {Procedure} grid-move grid item position filter
-Attempt to move @var{item} in @var{grid} to @var{position} (a 2D
-vector) and check for collisions. For each collision, @var{filter}
-will be called with two arguments: @var{item} and the item it collided
-with. If a collision occurs, @var{position} may be modified to
-resolve the colliding objects.
-@end deffn
-
-@deffn {Procedure} for-each-cell proc grid [rect]
-Call @var{proc} with each cell in @var{grid} that intersects
-@var{rect}, or every cell if @var{rect} is @code{#f}.
-@end deffn
-
-@deffn {Procedure} for-each-item proc grid
-Call @var{proc} for each item in @var{grid}.
-@end deffn
-
-@deffn {Procedure} slide item item-rect other other-rect goal
-
-Resolve the collision that occurs between @var{item} and @var{other}
-when moving @var{item-rect} to @var{goal} by sliding @var{item-rect}
-the minimum amount needed to make it no longer overlap
-@var{other-rect}.
-@end deffn
-
@node Graphics
@section Graphics
@@ -5383,3 +5205,188 @@ after it has been received.
@deffn {Procedure} channel-clear! channel
Clear all messages and scripts awaiting messages in @var{channel}.
@end deffn
+
+@node Data Structures
+@section Data Structures
+
+@menu
+* Grids:: Spatial partitioning with a fixed grid.
+* Path Finding:: Generic A* path finding.
+@end menu
+
+@node Grids
+@subsection Grids
+
+The @code{(chickadee data grid)} module provides a simple spatial
+partitioning system for axis-aligned bounding boxes
+(@pxref{Rectangles}) in 2D space. The grid divides the world into
+tiles and keeps track of which rectangles occupy which tiles. When
+there are lots of moving objects in the game world that need collision
+detection, the grid greatly speeds up the process. Instead of
+checking collisions of each object against every other object (an
+O(n^2) operation), the grid quickly narrows down which objects could
+possibly be colliding and only performs collision testing against a
+small set of objects.
+
+In addition to checking for collisions, the grid also handles the
+resolution of collisions. Exactly how each collision is resolved is
+user-defined. A player bumping into a wall may slide against it. An
+enemy colliding with a projectile shot by the player may get pushed
+back in the opposite direction. Two players colliding may not need
+resolution at all and will just pass through each other. The way this
+works is that each time an object (A) is moved within the grid, the
+grid looks for an object (B) that may possibly be colliding with A. A
+user-defined procedure known as a ``filter'' is then called with both
+A and B. If the filter returns @code{#f}, it means that even if A and
+B are colliding, no collision resolution is needed. In this case the
+grid won't waste time checking if they really do collide because it
+doesn't matter. If A and B are collidable, then the filter returns a
+procedure that implements the resolution technique. The grid will
+then perform a collision test. If A and B are colliding, the resolver
+procedure is called. It's the resolvers job to adjust the objects
+such that they are no longer colliding. The grid module comes with a
+very simple resolution procedure, @code{slide}, that adjusts object A
+by the smallest amount so that it no longer overlaps with B. By using
+this filtering technique, a game can resolve collisions between
+different objects in different ways.
+
+@deffn {Procedure} make-grid [cell-size 64]
+Return a new grid partitioned into @var{cell-size} tiles.
+@end deffn
+
+@deffn {Procedure} grid? obj
+Return @code{#t} if @var{obj} is a grid.
+@end deffn
+
+@deffn {Procedure} cell? obj
+Return @code{#t} if @var{obj} is a grid cell.
+@end deffn
+
+@deffn {Procedure} cell-count cell
+Return the number of items in @var{cell}.
+@end deffn
+
+@deffn {Procedure} grid-cell-size grid
+Return the cell size of @var{grid}.
+@end deffn
+
+@deffn {Procedure} grid-cell-count grid
+Return the number of cells currently in @var{grid}.
+@end deffn
+
+@deffn {Procedure} grid-item-count grid
+Return the number of items in @var{grid}.
+@end deffn
+
+@deffn {Procedure} grid-add grid item x y @
+ width height
+
+Add @var{item} to @var{grid} represented by the axis-aligned bounding
+box whose lower-left corner is at (@var{x}, @var{y}) and is
+@var{width} x @var{height} in size.
+@end deffn
+
+@deffn {Procedure} grid-remove grid item
+Return @var{item} from @var{grid}.
+@end deffn
+
+@deffn {Procedure} grid-clear grid
+Remove all items from @var{grid}.
+@end deffn
+
+@deffn {Procedure} grid-move grid item position filter
+Attempt to move @var{item} in @var{grid} to @var{position} (a 2D
+vector) and check for collisions. For each collision, @var{filter}
+will be called with two arguments: @var{item} and the item it collided
+with. If a collision occurs, @var{position} may be modified to
+resolve the colliding objects.
+@end deffn
+
+@deffn {Procedure} for-each-cell proc grid [rect]
+Call @var{proc} with each cell in @var{grid} that intersects
+@var{rect}, or every cell if @var{rect} is @code{#f}.
+@end deffn
+
+@deffn {Procedure} for-each-item proc grid
+Call @var{proc} for each item in @var{grid}.
+@end deffn
+
+@deffn {Procedure} slide item item-rect other other-rect goal
+
+Resolve the collision that occurs between @var{item} and @var{other}
+when moving @var{item-rect} to @var{goal} by sliding @var{item-rect}
+the minimum amount needed to make it no longer overlap
+@var{other-rect}.
+@end deffn
+
+@node Path Finding
+@subsection Path Finding
+
+Most game worlds have maps. Often, these games have a need to move
+non-player characters around in an unscripted fashion. For example,
+in a real-time strategy game, the player may command one of their
+units to attack something in the enemy base. To do so, the unit must
+calculate the shortest route to get there. It wouldn't be a very fun
+game if units didn't know how to transport themselves efficiently.
+This is where path finding algorithms come in handy. The
+@code{(chickadee data path-finding)} module provides a generic
+implementation of the popular A* path finding algorithm. Just add a
+map implementation!
+
+The example below defines a very simple town map and finds the
+quickest way to get from the town common to the school.
+
+@example
+(define world-map
+ '((town-common . (town-hall library))
+ (town-hall . (town-common school))
+ (library . (town-common cafe))
+ (school . (town-hall cafe))
+ (cafe . (library school))))
+(define (neighbors building)
+ (assq-ref town-map building))
+(define (cost a b) 1)
+(define (distance a b) 1)
+(define pf (make-path-finder))
+(a* pf 'town-common 'school neighbors cost distance)
+@end example
+
+In this case, the @code{a*} procedure will return the list
+@code{(town-common town-hall school)}, which is indeed the shortest
+route. (The other possible route is @code{(town-common library cafe
+school)}.)
+
+The @code{a*} procedure does not know anything about about any kind of
+map and therefore must be told how to look up neighboring nodes, which
+is what the @code{neighbors} procedure in the example does. To
+simulate different types of terrain, a cost procedure is used. In
+this example, it is just as easy to move between any two nodes because
+@code{cost} always returns 1. In a real game, perhaps moving from
+from a field to a rocky hill would cost a lot more than moving from
+one field to another. Finally, a heuristic is used to calculate an
+approximate distance between two nodes on the map. In this simple
+association list based graph it is tough to calculate a distance
+between nodes, so the @code{distance} procedure isn't helpful and
+always returns 1. In a real game with a tile-based map, for example,
+the heuristic could be a quick Manhattan distance calculation based on
+the coordinates of the two map tiles. Choose an appropriate heuristic
+for optimal path finding!
+
+@deffn {Procedure} make-path-finder
+Return a new path finder object.
+@end deffn
+
+@deffn {Procedure} path-finder? obj
+Return @code{#t} if @var{obj} is a path finder.
+@end deffn
+
+@deffn {Procedure} a* path-finder start goal neighbors cost distance
+
+Return a list of nodes forming a path from @var{start} to @var{goal}
+using @var{path-finder} to hold state. @var{neighbors} is a procedure
+that accepts a node and returns a list of nodes that neighbor it.
+@var{cost} is a procedure that accepts two neighboring nodes and
+returns the cost of moving from the first to the second as a real
+number. @var{distance} is a procedure that accepts two nodes and
+returns an approximate distance between them.
+@end deffn
diff --git a/examples/grid.scm b/examples/grid.scm
index f552d1a..c83dac7 100644
--- a/examples/grid.scm
+++ b/examples/grid.scm
@@ -1,5 +1,5 @@
(use-modules (chickadee)
- (chickadee math grid)
+ (chickadee data grid)
(chickadee math vector)
(chickadee math rect)
(chickadee graphics color)