diff options
| -rw-r--r-- | Makefile.am | 10 | ||||
| -rw-r--r-- | chickadee/audio.scm | 2 | ||||
| -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.scm | 2 | ||||
| -rw-r--r-- | chickadee/graphics/model.scm | 2 | ||||
| -rw-r--r-- | chickadee/graphics/path.scm | 2 | ||||
| -rw-r--r-- | chickadee/scripting/agenda.scm | 2 | ||||
| -rw-r--r-- | chickadee/scripting/channel.scm | 4 | ||||
| -rw-r--r-- | doc/api.texi | 365 | ||||
| -rw-r--r-- | examples/grid.scm | 2 |
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) |