A few days ago I read a paper about antiobjects in game development (go
here) and just 2 days ago I was stricken with inspiration and came up with a class structure (written in Common Lisp), that not only supports scent tracking (as described in the paper above) but also arbitrary definitions of neighbourhood and descriptions of positions.
[edit]Forgot to provide the source. Here is a version without package definition:
http://paste.lisp.org/+2NVQ. Scent diffusion is broken, as any cell only updates those smells it has already in it's hash-table.[/edit]
To explain: Any map can be represented as a graph. The neighbourhood of a node in that graph is the set of all nodes that share an edge with said node. In a graph representing a map the nodes are positions and in normal movement a critter can reach any neighbour of a node with a single step. Most roguelikes use the so called Moore Neighbourhood (which includes orthogonal and diagonal movement) and there are few using the Von-Neumann Neighbourhood (with only orthogonal movement) and there are even less with hexagonal neighbourhood.
For the purposes of game programming any node in such a graph has to be addressable via a position description. A position description for a two-dimensional array is a pair of integers in the correct range, but a position description might be a sequence of directed steps from a certain starting point.
Nodes are called cells in this implementation. A cell can represent any kind of object that keeps track of it's own scent. Scent is stored in a hash-table (with :test 'eq), so one can define as many scents as one can name and gensym. A cell doubles as a cell stack. That means that cells can be pushed on top of each other, so that one cell blocks the scent tracking of the cell below. Of course you can write subclasses of CELL to define cells that update the scent of cells below itself, so that maybe a wolf (that is an instance of the class ACTOR that is a subclass of CELL) doesn't prevent the scent of the floor under it spreading. Hm, maybe I should make the CELL class abstract and make some subclasses...
The CELL-GRID class implements a relatively easy way to define neighbourhoods and position descriptions via a few generic functions (this means, you make a subclass of CELL-GRID and define specialized methods on those generic functions).
Here an example implementation of a cell grid that uses the von-neumann-neighbourhood:
;;;; first to define a subclass of CELL-GRID
(defclass von-neumann-cell-grid (cell-grid)
((%content :type (array (or cell null)
2)
:reader content
:initarg :content)
(%x-wrap :type boolean ; whether the map should wrap around at the borders in direction of the x axis
:reader x-wrap
:initform nil
:initarg :x-wrap)
(%y-wrap :type boolean ; like x-wrap, only with the y axis
:reader y-wrap
:initform nil
:initarg :y-wrap)))
;;;; a function for instanciating a von-neumann cell grid
(defun make-von-neumann-cell-grid (make-cell-function x-dim y-dim &key x-wrap
y-wrap)
;;; POPULATE-CELL-GRID is specialized on CELL-GRID and thus is usable for
;;; any subclass of CELL-GRID that implements GET-POSITION, SET-POSITION,
;;; POSITION-NEIGHBOURHOOD and EVALUATE-POSITIONS. it stores the result of
;;; calling MAKE-CELL-FUNCTION (look at the last line!) at every position and connects
;;; that with its desired neighbours. Neighbourhood, as used later when operating on single
;;; cells, is not determined through the cell grid but via the cell itself. This allows some nice
;;; stuff, e.g. portals.
(populate-cell-grid (make-instance 'von-neumann-cell-grid
:content
(make-array `(,x-dim ,y-dim)
:element-type '(or cons null)
:initial-element '())
:x-wrap x-wrap
:y-wrap y-wrap)
make-cell-function))
;;;; defining methods for getting and setting a position
(defmethod get-position ((cell-grid von-neumann-cell-grid)
&rest position)
(apply #'aref
(content cell-grid)
position))
(defmethod set-position ((cell-grid von-neumann-cell-grid)
value &rest position)
(setf (apply #'aref
(content cell-grid)
position)
value))
;;;; this method defines, how to apply a function to any position in a cell grid
(defmethod evaluate-positions ((cell-grid von-neumann-cell-grid)
(function function)
&rest arguments)
(let ((x-max (- (first (array-dimensions (content cell-grid)))
1))
(y-max (- (second (array-dimensions (content cell-grid)))
1)))
(loop for x ; for an array applying a function on any cell is quite simple. just loop over all possible x....
from 0
to x-max
do (loop for y ; ... and y values and...
from 0
to y-max
do (apply function cell-grid (append arguments `(,x ,y))))))) ; apply the function as required
;;; as this last line always contains (apply function cell-grid (append arguments #|insert position here|#
;;; it might be better to define a macro that just gets told how to iterate/recurse over positions
;;;; this method returns a list of the non-nil contents of all desired neighbours of a node
(defmethod position-neighbourhood ((cell-grid von-neumann-cell-grid)
&rest position)
(let ((x (first position))
(y (second position))
(x-max (- (first (array-dimensions (content cell-grid)))
1))
(y-max (- (second (array-dimensions (content cell-grid)))
1))
(x-wrap (x-wrap cell-grid))
(y-wrap (y-wrap cell-grid)))
(remove nil (list (if (> x 0)
(aref (content cell-grid)
(- x 1)
y)
(if x-wrap ; this allows us for wrapping the map around
(aref (content cell-grid)
x-max y)))
(if (> y 0)
(aref (content cell-grid)
x (- y 1))
(if y-wrap
(aref (content cell-grid)
x y-max)))
(if (< x x-max)
(aref (content cell-grid)
(+ x 1)
y)
(if x-wrap
(aref (content cell-grid)
0 y)))
(if (< y y-max)
(aref (content cell-grid)
x (+ y 1))
(if y-wrap
(aref (content cell-grid)
x 0)))))))
Some important generic functions are:
(defgeneric push-position (cell-grid value &rest position)) => cell-grid to put an object into the map.
(defgeneric pop-position (cell-grid &rest position)) => old-position-top to remove a cell from the map (beware, floor is also a cell that might be removed and no cell is basically a wall with no interaction with the environment. old-position-top is the cell popped of the position.
(defgeneric move-position (cell-grid source target)) => cell-grid to move a cell from one position to another. As positions are lists, both source and target have to be lists.
(defgeneric cell-neighbourhood (cell-grid &rest position)) => neighbour-list returns the neighbours of the cell at the given position. This is different from POSITION-NEIGHBOURHOOD as it does not return cells that are not connected to the cell at the position and returns cells that are connected to said cell but not adjacent to that cell according to the CELL-GRID.
Any comments?
Author
Topic: The Roguelike Development Megathread (Read 245529 times)