Author Topic: CL scent-map - datastructures and algorithms for maps in a broader sense  (Read 4018 times)


  • Rogueliker
  • ***
  • Posts: 52
  • Karma: +0/-0
    • View Profile
So, I know Common Lisp is not widely used in the roguelike community (or anywhere else, for that matter) but it is my favourite language and therefore I need some basis on which I can build a roguelike.
I, for now, started with a library for maps. Right now I've got the representation of a single tile and maps done.
The results can be downloaded via
Code: [Select]
hg clone need mercurial to do this.

The basic principle behind a map is the following: A map consists of a set of directions and a set of positions, where tiles (called "cells" in the library) can be stored. In any map for any position and neighbour another position can be computed. This can be used to construct a graph, by filling the positions of a map with cells and then connecting those cells to each other based on the positions that lie in the defined directions. With this it's trivial to define subclasses of cell-grid (the basic map class) to get maps where any tile has 4, 6 or 8 neighbours (Von-Neumann- hexagonal and Moore-neighbourhood, respectively), general graph-like maps or whatever you can make up. Just define a way of finding a position, calling a function on every possible position and define how to translate the defined directions into the neighbours of a position.
Cell grids with Von-Neumann-, hexagonal and Moore-neighbourhood are already implemented as well as cell grids which are just a general graph.

The "real" work is done in the cells. Any cell knows what neighbour lies in which direction, so anything related to that (movement, diffusion of scent, fov) can be computed on it. Any cell doubles as a stack of cells, so actors, items, buildings, different types of terrain and whatever can be implemented as cells. Pushing a cell onto another cell preserves the neighbours, so the cell pushed has the neighbours of the cell it was pushed onto, popping a cell of a stack disconnects that cell of all it's neighbours and connects the underlying cell to those neighbours, all with directions intact of course.
Currently there are basic cells without any functionality and cells which can be blocked or not. Terrain cells, scent tracking cells, actors and items are planned to be implemented later.

Directions are an own class on which the generic functions SAME-DIRECTION-P and OPPOSITE-DIRECTION need to be defined.
Currently simple directions (which are compared per EQ and are their own opposite), angular directions (who have a angle in the interval [0 360)) and named directions (who have a name and a defined opposite direction with a name) are implemented. Anything goes, as long as
holds true for any value of DIRECTION.

Missing functionality includes
- diffusing and storing scent
- computing a view of a map as seen from a certain position
- map generation algorithms

I designed the current interface via concentrating on the needed generic functions. That means, that any map generation algorithms will be implemented via a class whose slots are the parameters to the map generator. Generating a map is done via calling the generic function GENERATE-MAP on one such object and an optional post-processor, that might place items and monsters, fill dead ends...

I posted about this on before and the reaction was less then enthusiastic.
I was told that my approach used too much overhead. Yet I don't see any way to do all that stuff as clean as I did it until now - for a new kind of map topology I only need to implement a few methods with a well defined interface and with only that I have a plethora of functions available to do anything I need to do on maps. Debugging is almost trivial in most cases and even using different kinds of topologies in the same game has it's uses - imagine the difference between a castle and a cave and you might know what I mean, not even taking into account the kinds of spells that can be implemented through this.

Any comments?
And, for inspiration: What functions need to be available in terms of terrain? Being blocked shouldn't depend on terrain alone.
« Last Edit: February 12, 2012, 06:08:32 PM by Antsan »


  • Rogueliker
  • ***
  • Posts: 81
  • Karma: +0/-0
  • Most of your personality is unconscious.
    • View Profile
    • Mysterious Castle
    • Email
Re: CL scent-map - datastructures and algorithms for maps in a broader sense
« Reply #1 on: February 22, 2012, 11:25:22 AM »
Very interesting...

I hacked together something not entirely unlike your scheme, but using C++ and template meta-programming, minus the directions as a class. I found that it made designing algorithms far simpler and more powerful.

I'm not very familiar with Lisp, but will take a look at your implementation when I find time (where has all my time gone?).

For whatever it's worth, I think that such an approach is the future of complex procedural map generation, where there is a lot of generation stages interspersed with complex analysis.

Good stuff! I'll get back to you when I wrap my head around it.


  • Rogueliker
  • ***
  • Posts: 201
  • Karma: +1/-1
    • View Profile
    • Email
Re: CL scent-map - datastructures and algorithms for maps in a broader sense
« Reply #2 on: February 22, 2012, 04:57:08 PM »
Don't know if you've seen the CL bindings to libtcod, but if you go the libtcod site you'll find them.