Generalized map protocol in Common Lisp
Thomas Bartscher
Now I don't know anything about performance at all and I've never written a roguelike before, so I don't know whether the protocol is usable at all. I need feedback.
Basically there are two basic classes from which anything else inherits. One is the CELL class, which represents one single position/place/object and the CELL-GRID class, which represents a full map.
A CELL stores all scents and diffusion coefficients for different smells (and one default value, when the diffusion coefficient for one scent hasn't been defined explicitely), the neighbours used in the diffusion equation and cells that are "blocked" by that cell. I intend of storing functions that operate on the scent of a blocked cell, so that not any scent is automatically blocked off but might seep through. The number of neighbours in a cell is not fixed and might be arbitrarily large.
The CELL-GRID class is responsible for maintaining a certain graph structure and controlling, how cells are added to and removed from said graph. Furthermore the CELL-GRID class is used to etermine, how a list of objects is translated into a cell in a cell grid. This list of objects is normally called a "position" and could be a list of integers to access an array or a list of vectors describing a sequence of movements through some space to find a certain position or a list of the symbols :north, :east, :south, :west to find a cell via following directions.
This is achieved through 4 generic functions that are not implemented for CELL-GRID but must be implemented for any instantiatable subclass of CELL-GRID.
Those four functions are:
GET-POSITION CELL-GRID &REST POSITION
to translate a position to a cell object
SET-POSITION CELL-GRID &REST POSITION
to store a value at a certain position. I hope to get rid of the requirement to implement this in the subclass via somehow utilizing GET-POSITION here.
POSITION-NEIGHBOURHOOD CELL-GRID &REST POSITION
this returns a list of all the neighbour positions of a position. This is *not* the same as the list of the neighbours of the cell at that position, as neighbour positions not necessarily contain a cell and if there is a cell this is not automatically connected to the cell at POSITION.
EVALUATE-POSITIONS CELL-GRID FUNCTION &REST ARGUMENTS
This should call FUNCTION on every position in CELL-GRID such that the argument list of FUNCTION first contains CELL-GRID, followed by the ARGUMENTS and closed by the position. It returns CELL-GRID. Imagine it like this:
(loop for position
in ;;somehow calculate all positions
do (apply function
cell-grid (append arguments position)))
With that I was able to implement array based maps that have a moore-neighbourhood, a von-neumann-neighbourhood and a hexagonal grid. With a named neighbourhood topology (any neighbour position is referred to by a name) one could implement maps like in Smart Kobold with ease.
Thoughts on that? Any interest in the actual code?
win
wrote:
> After reading a paper about antiobjects (can be found athttp://dl.acm.org/citation.cfm?id=1176630) I was stricken with inspiration and in 2 sessions of roughly 6 hours each I hacked together a small library implementing a map protocol in Common Lisp which allows for arbitrary map topologies and implements scent tracking where different scents are named by symbols. Furthermore I think that the class used for representing a single map cell can be used to represent any object that has a position in the game.
It sounds very interesting to me. Could you paste the code so I can
play around with it? http://paste.lisp.org/
Thomas Bartscher
I only pasted cell.lisp and cell-grid.lisp. That doesn't include the subclasses implementing von neumann, hexagonal and moore neighbourhood. I also deleted package definitions and such.
Smell diffusion is broken, I noticed - it only takes smells into account, that the currently updated cell already has stored in its hash table.
I'm not quite sure whether to publish that code as an own project on google code (or some similar service).
Krice
wrote:
> Any interest in the actual code?
Did not understand much of what you were saying. Is this a
map generator? Can you show what kind of maps it generates?
Thomas Bartscher
It provides two classes: One class (CELL) that represents exactly one tile or something that stands on one tile and one class (CELL-GRID) that makes sure that those tiles have the correct relation to each other in terms of what is next to what.
My approach to a map is different from the usual approach (I guess, usually you use a plain array of tile objects). I build a map out of cells and tell each cell which other cells are adjacent to it. The cell grid is there to make sure that you can automatize this process to return a graph of reasonably connected cells.
Look here:
http://paste.lisp.org/+2NVW
This code implements 2 abstract classes, array-cell-grid and array-2d-cell-grid. Based on array-2d-cell-grid I can implement cell grids which use the moore neighbourhood (cells are connected orthogonally and diagonally), a hexagonal neighbourhood (I cannot explain this, but I guess most people can imagine what it is by it's name) or a von-neumann neighbourhood (cells are connected orthogonally) only via implementing 1 method for each (and technically 1 function for each for instantiating an object of the corresponding class).
paul-d...@sbcglobal.net
> After reading a paper about antiobjects (can be found at
> http://dl.acm.org/citation.cfm?id=1176630 )
Oof. "Antiobjects" indeed. Talk about mistaking your domain for your
program.
> I was stricken with inspiration and in 2 sessions of roughly 6 hours
> each I hacked together a small library implementing a map protocol in
> Common Lisp which allows for arbitrary map topologies and implements
> scent tracking where different scents are named by
> symbols. Furthermore I think that the class used for representing a
> single map cell can be used to represent any object that has a
> position in the game. Now I don't know anything about performance at
> all and I've never written a roguelike before, so I don't know whether
> the protocol is usable at all. I need feedback.
Arbitrary map topologies will be a lot of overhead (in time and space)
for something you'd never do, wouldn't they?
Thomas Bartscher
> Thomas Bartscher <thomas.b...@googlemail.com> writes:
>
> > After reading a paper about antiobjects (can be found at
> > http://dl.acm.org/citation.cfm?id=1176630 )
>
> Oof. "Antiobjects" indeed. Talk about mistaking your domain for your
> program.
>
> > I was stricken with inspiration and in 2 sessions of roughly 6 hours
> > each I hacked together a small library implementing a map protocol in
> > Common Lisp which allows for arbitrary map topologies and implements
> > scent tracking where different scents are named by
> > symbols. Furthermore I think that the class used for representing a
> > single map cell can be used to represent any object that has a
> > position in the game. Now I don't know anything about performance at
> > all and I've never written a roguelike before, so I don't know whether
> > the protocol is usable at all. I need feedback.
>
> Arbitrary map topologies will be a lot of overhead (in time and space)
> for something you'd never do, wouldn't they?
paul-d...@sbcglobal.net
> Am Sonntag, 28. August 2011 01:06:30 UTC+2 schrieb paul-d...@sbcglobal.net:
>> Thomas Bartscher <thomas.b...@googlemail.com> writes:
>>
>> > After reading a paper about antiobjects (can be found at
>> > http://dl.acm.org/citation.cfm?id=1176630 )
>>
>> Oof. "Antiobjects" indeed. Talk about mistaking your domain for your
>> program.
> I'm not sure what you're talking about. I wasn't sure why the paper
> talked about how antiobjects where somehow different from objects, but
> maybe you are talking about something else?
I'm talking about the paper. A person would only coin the term
"antiobjects" for those tiles if they were confused in the worst way
about what objects represent. The collaborative diffusion thing is
clever though; they just badly needed an editor.
>> > I was stricken with inspiration and in 2 sessions of roughly 6 hours
>> > each I hacked together a small library implementing a map protocol in
>> > Common Lisp which allows for arbitrary map topologies and implements
>> > scent tracking where different scents are named by
>> > symbols. Furthermore I think that the class used for representing a
>> > single map cell can be used to represent any object that has a
>> > position in the game. Now I don't know anything about performance at
>> > all and I've never written a roguelike before, so I don't know whether
>> > the protocol is usable at all. I need feedback.
>>
>> Arbitrary map topologies will be a lot of overhead (in time and space)
>> for something you'd never do, wouldn't they?
> Yes, that's certainly true. That's why one maybe should use this
> library only if he intends on using it's features, right?
Right... I can see it being useful for connecting rooms, but not on the
tile level. Regular tilings will always be more efficiently implemented
in the traditional way, and I don't see tiles connected every which way
being useful at all.
Thomas Bartscher
> Right... I can see it being useful for connecting rooms, but not on the
> tile level. Regular tilings will always be more efficiently implemented
> in the traditional way, and I don't see tiles connected every which way
> being useful at all.
For how to use this on a per-tile-basis: First, there is always something as portal and I am not sure how you would do a map like in Smart Kobold in any other way than on a per-tile basis.
Second there is space for experimentation. I am trying to come up with something. Currently I have an idea about permanent teleporting paths that are activated by saying the right words in the correct order when standing on the right position (implementing the movement code for this is trivial, just a matter of reading user input word per word and moving actor position onto the matching neighbour), but I am not sure whether this is actually doable in a way that's playable.
narf_the_mouse
You could have the player single-key select from a list of words, like
in a generic inventory screen.
It sounds like an interesting way to map; be interesting to see what you
make of it. :)
Jeff Lait
<thomas.bartsc...@googlemail.com> wrote:
> Am Montag, 29. August 2011 16:54:28 UTC+2 schrieb paul-d...@sbcglobal.net:> Right... I can see it being useful for connecting rooms, but not on the
> > tile level. Regular tilings will always be more efficiently implemented
> > in the traditional way, and I don't see tiles connected every which way
> > being useful at all.
>
> I'll see into that. A subclass of CELL being ROOM might be enough.
>
> For how to use this on a per-tile-basis: First, there is always something as
> portal and I am not sure how you would do a map like in Smart Kobold in any
> other way than on a per-tile basis.
I'm not sure if I understand this properly, but Smart Kobold uses a
set of rooms each of which has a regular tiling. Each room (a MxN 2d
array of POD tiles) also has a list of portals within the the room.
So while portals are stored as special objects, tiles themselves are
not.
The important thing isn't whether the underlying data structure stores
generalized connectivity. The important things is for the interface
to it to support generalized connectivity. I did this through making
Position (traditionally a x, y pair) the heavyweight object that
worries about connectivity. Then one rewrites the algorithms in terms
of positions and directions and you gain topological invariance for
free.
> Second there is space for experimentation. I am trying to come up with something.
Being able to rewire portals on the fly was quite useful in Vicious
Orcs. Not just for the portal spell, but also for creating/collapsing
dungeons for plot reasons.
--
Jeff Lait
(POWDER: http://www.zincland.com/powder)
Thomas Bartscher
> On 29/08/2011 8:53 AM, Thomas Bartscher wrote:
> >> Right... I can see it being useful for connecting rooms, but not on the
> >> tile level. Regular tilings will always be more efficiently implemented
> >> in the traditional way, and I don't see tiles connected every which way
> >> being useful at all.
> > I'll see into that. A subclass of CELL being ROOM might be enough.
> >
> > For how to use this on a per-tile-basis: First, there is always something as portal and I am not sure how you would do a map like in Smart Kobold in any other way than on a per-tile basis.
> > Second there is space for experimentation. I am trying to come up with something. Currently I have an idea about permanent teleporting paths that are activated by saying the right words in the correct order when standing on the right position (implementing the movement code for this is trivial, just a matter of reading user input word per word and moving actor position onto the matching neighbour), but I am not sure whether this is actually doable in a way that's playable.
>
> You could have the player single-key select from a list of words, like
> in a generic inventory screen.
Thomas Bartscher
> On Aug 29, 11:53 am, Thomas Bartscher
> > Am Montag, 29. August 2011 16:54:28 UTC+2 schrieb paul...@sbcglobal.net:> Right... I can see it being useful for connecting rooms, but not on the
> > > tile level. Regular tilings will always be more efficiently implemented
> > > in the traditional way, and I don't see tiles connected every which way
> > > being useful at all.
> >
> > I'll see into that. A subclass of CELL being ROOM might be enough.
> >
> > For how to use this on a per-tile-basis: First, there is always something as
> > portal and I am not sure how you would do a map like in Smart Kobold in any
> > other way than on a per-tile basis.
>
> I'm not sure if I understand this properly, but Smart Kobold uses a
> set of rooms each of which has a regular tiling. Each room (a MxN 2d
> array of POD tiles) also has a list of portals within the the room.
> So while portals are stored as special objects, tiles themselves are
> not.
How to do this in my library: Use the moore-cell-grid, fill it with POD tiles (use the make-cell-function parameter in the make-moore-grid function), then fill the edges to other rooms with cells, create the next room in a similar manner, connect the cells on the borders in the correct manner.
Of course now build in methods for movement on cells are worthless and therefore the cell-neighbourhood has to interpreted by the programmer when a cell is encountered in movement.
> The important thing isn't whether the underlying data structure stores
> generalized connectivity. The important things is for the interface
> to it to support generalized connectivity. I did this through making
> Position (traditionally a x, y pair) the heavyweight object that
> worries about connectivity. Then one rewrites the algorithms in terms
> of positions and directions and you gain topological invariance for
> free.
Well, the data structure for the cell grid only implements an interface. That stuff about position and direction is very interesting though, I stumbled upon those two on my own. I am still not sure how to handle them and I needed to rewrite all neighbours of a cell to have a name (that indicates the direction the neighbour is lying in).
The thing is that this way directions can be self-opposing or, well, directional. That means, when you go twice in the same direction in the first case you end up where you came from where in the second case just happens what one would normally expect to happen.
Thomas Bartscher
Jeff Lait
wrote:
> Wait, I just realized that your directions are relative and not absolute.
> I name them and thus a cell always knows where north is. How are you
> doing that without loosing track of where to move?
Short answer: There are no cells.
The user of the map interacts with Positions. From a position, I can
give an absolute direction: "North, South". The position is a struct
of x, y, angle, and room id. The local angle in the position
transforms the "North" given by the user into the actual underlying
topology.
Thus, there is no requirement that pos->north->south == pos. Indeed,
since the result of pos->north() is a new position, it could have its
own local angle be different than pos.
Jacob's Matrix uses this angle shifting heavily to get people lost.
The Jacob's Matrix "maze" is actually quite trivial in connectivity.
The problem comes from the constant angle twists. I've learned from
experience that this is way confusing to users and to avoid it as much
as possible.
The recent history of my 7DRLs has been an attempt to reduce the
confusion engendered by letting rooms connect any which way. Normal
roguelikes benefit highly from people building an absolute map in
their minds of where things are in the game. When you mess with that,
you cause lots of problems.
I went into this in more detail with my IRDC presentation, so I really
need to package that up!
Numeron
> On Aug 29, 3:20 pm, Thomas Bartscher <thomas.b...@googlemail.com>
I am interested to know how do you do pathfinding for AI when there may be multiple relative positions for a single destination? For example, if you have a smallish area which is connected back in on itself, does your pathfinding algorithm account for this? If so, how does it weight a certain direction?
I can think that one work around may be to run FOV for monsters, and then use the result of that to pathfind. With very tight loops however, there is still the potential for the player to appear in the FOV more than once, and navigating to areas out of sight is still a problem - with the potential to end up highly suboptimal between areas.
I think I will go and check this IRDC talk out.
-Numeron
Thomas Bartscher
> On Aug 29, 3:20 pm, Thomas Bartscher <thomas.b...@googlemail.com>
> wrote:
> > Wait, I just realized that your directions are relative and not absolute.
> > I name them and thus a cell always knows where north is. How are you
> > doing that without loosing track of where to move?
>
> Short answer: There are no cells.
> The user of the map interacts with Positions. From a position, I can
> give an absolute direction: "North, South". The position is a struct
> of x, y, angle, and room id. The local angle in the position
> transforms the "North" given by the user into the actual underlying
> topology.
I don't quite understand *how*. I mean, a position representing a tile can occur multiple times on a map as it is seen by the user in multiple rotations. North, as seen by the user, occurs in only *one* rotation. Either you store multiple positions per tile when one tile appears multiple times or there is something different going on.
> Thus, there is no requirement that pos->north->south == pos. Indeed,
> since the result of pos->north() is a new position, it could have its
> own local angle be different than pos.
Hm, so pos->north is not equivalent to (get-neighbour cell :north).
So I need a function (get-local-neighbour cell :north) that translates :north into the correct direction, depending on the angle of cell.
That may be just me being a bit feverish, but I fell pretty dumb right now. I don't understand at all, how your algorithm works.
> Jacob's Matrix uses this angle shifting heavily to get people lost.
> The Jacob's Matrix "maze" is actually quite trivial in connectivity.
> The problem comes from the constant angle twists. I've learned from
> experience that this is way confusing to users and to avoid it as much
> as possible.
>
> The recent history of my 7DRLs has been an attempt to reduce the
> confusion engendered by letting rooms connect any which way. Normal
> roguelikes benefit highly from people building an absolute map in
> their minds of where things are in the game. When you mess with that,
> you cause lots of problems.
>
> I went into this in more detail with my IRDC presentation, so I really
> need to package that up!
I would definitely like to see this. Maybe then I can finally see the light.
Thomas Bartscher
Jeff Lait
> multiple relative positions for a single destination? For example, if you
> have a smallish area which is connected back in on itself, does your pathfinding
> algorithm account for this? If so, how does it weight a certain direction?
It doesn't weight on a certain direction. A* requires you to have a
conservative distance metric. One thing hard to compute with
arbitrary connections is dist(A, B).
Pathfinding is thus just a breadth first search. For most of the
7DRLs this is just distance tables from a point.
> I can think that one work around may be to run FOV for monsters, and then
> use the result of that to pathfind. With very tight loops however, there
> is still the potential for the player to appear in the FOV more than once,
> and navigating to areas out of sight is still a problem - with the potential
> to end up highly suboptimal between areas.
I do often use player FOV for pathfinding wherever possible, because
that is nice and efficient. While it is true a monster can show up
twice in the FOV, any consistent tie breaker would work. The only
risk is the monster deciding to ping-pong between two routes.
> I think I will go and check this IRDC talk out.
I need to get it online first.
Jeff Lait
wrote:
> Am Dienstag, 30. August 2011 22:14:42 UTC+2 schrieb Jeff Lait:> On Aug 29, 3:20 pm, Thomas Bartscher <thomas.b...@googlemail.com>
> > wrote:
> > > Wait, I just realized that your directions are relative and not absolute.
> > > I name them and thus a cell always knows where north is. How are you
> > > doing that without loosing track of where to move?
>
> > Short answer: There are no cells.
>
> But in what I gathered about your approach positions are very close
> to what cells are, only with outgoing directions fixed at the 8
> moore-neighbourhood ones. Of course that could originate in my
> incorrect understanding of your approach.
There are cells internal to the map, of course! But the map user
doesn't hold onto a "cell". This means the actual representation of
cells is irrelevant to users of the map.
> > The user of the map interacts with Positions. From a position, I can
> > give an absolute direction: "North, South". The position is a struct
> > of x, y, angle, and room id. The local angle in the position
> > transforms the "North" given by the user into the actual underlying
> > topology.
>
> I don't quite understand *how*. I mean, a position representing a tile
> can occur multiple times on a map as it is seen by the user in multiple
> rotations. North, as seen by the user, occurs in only *one* rotation.
> Either you store multiple positions per tile when one tile appears
> multiple times or there is something different going on.
The map never stores positions. (Well, it does in some cases, but not
in the sense of one per cell!)
Positions are generated solely on demand. Think of a position as a
(x, y, angle) triple. I'm allowed to copy and make as many of these
as I want outside of the map without telling the map about it. I can
even do some operations, like rotate (x, y, angle++), without talking
to the map. And the triple can have methods like ::north added that
call back to the map to update the position.
> > Thus, there is no requirement that pos->north->south == pos. Indeed,
> > since the result of pos->north() is a new position, it could have its
> > own local angle be different than pos.
>
> Hm, so pos->north is not equivalent to (get-neighbour cell :north).
> So I need a function (get-local-neighbour cell :north) that translates
> :north into the correct direction, depending on the angle of cell.
Not the angle of the cell, the angle of the position.
North might be a bit misleading since we consider that an absolute
measure. Think instead of each position having a "Facing". A
position represents some creature standing on a tile. So it has a
location (x, y) and a direction the creature faces. Then there is
Forward, Backward, Left, and Right, which correspond to the screen's
physical up/down left/right, or the hjkl on the keyboard. So when
someone steps through a portal that rotates their facing, they are
doing just that, going through a twisty passage that leaves north
pointing somewhere else on the screen.
So, you can keep get-neighbour cell :north, but when you implement get-
neighbour position :forward, you need to step in a cardinal direction
determined by angle.
(Note for reasons of my sanity, I only allow 90 degree rotations in
angle. Indeed, allowing 8 way movement is a bit tricky in a portal
system since pos->left->up != pos->up->left in general!)
> That may be just me being a bit feverish, but I fell pretty dumb right
> now. I don't understand at all, how your algorithm works.
I'm likely explaining it poorly. It is both an obvious and subtle
distinction I'm trying to make between "cells" and "positions".
The traditional OO roguelike would have cells be the actual map data.
They contain a list of items, monsters, a tile type, etc. Then you
have a Cartesian pair, (x, y), which lets you get a cell:
cell = map->getCell(x, y);
if (cell->getMonster()) {...}
I've often disagreed with this approach, instead I'd used to advocate
it is better to stop at the map level and hide the cell from users.
The problem of revealing the cell is that you may want to pass it down
to a function:
void foo(CELL *cell)
But how do you then find that cell's neighbours? You need to store
the x/y coordinate of the cell inside the cell, which results in
position being stored both within the cell data structure explicitly
and also implicitly by the map holding the cell in a regular grid.
Duplication like this is always suspicious in data structures and is
just asking for annoying book keeping bugs.
I used to always advocate people move everything to the map:
if (map->getMonster(x, y)) { ... }
This also allows optimizations, like storing monsters outside of the
cell structure, or not having a cell struct at all. It also avoids
the passing of cell to functions problem, since you now just have to
pass:
void foo(MAP *map, x, y)
In one of these discussions some other people here pointed out that
there is a third option: construct a flyweight that properly captures
what both usage patterns desire. It took me a few years, but I
eventually moved into that pattern through successive 7DRLs. And now
I don't want to look back :>
The idea of the flyweight is we recognize the thing we, as users of a
map, *really* care about isn't the cell, it is instead a pointer into
the map. We want this to subsume the (map, x, y) set passed around in
foo. I call this the Position, or POS for short.
The evolution of this idea is easy to trace.
First, you create a VEC2, a (x, y) pair so you don't have to pass
around x and y all the time, but just a single variable. This cuts
in half the lines of code for a lot of map work.
Next, we recognize we often need to track the current map as well for
x,y to be meaningful. Since having a global MAP * like in POWDER is a
bad idea, we through it into a single struct, (map, x, y) and call
this POS.
Once we have POS, we realize all the functions that traditionally
people want to put on their heavyweight CELL classes actually belong
on the POS class. pos->getMonster() is better than map->getCell(x,y)-
>getMonster() or map->getMonster(x,y).
The final code looks suspiciously like the CELL based code I deride as
inefficient and impractical, which should not be too surprising, as
the people writing that code had good ideas about what the code should
look like :>
Thomas Bartscher
http://sharesource.org/project/clscentmap/
The source can be downloaded with:
hg clone http://hg.sharesource.org/clscentmap
Mercurial is needed for this.
Cells and cell grids should be usable now. I will try to put together some kind of reference.