Topics

1

Programming / Sewer generation

« on: July 03, 2016, 02:53:23 PM »

I am working on a roguelike that's supposed to take place in a sewer system.

My idea is to first generate the underground canals themselves, border them with walkways and then let a dungeon builder plan out some dwelling places for denizens in the sewers.

Unfortunately I am quite stumped on how to generate the system of canals in the first place.
Canals should either begin at a feed or another canal and should end either at a sink or a canal. The graph of canals should be a forest.
Every feed and every sink has a capacity and the sum of capacities of sinks in a given tree should be at least as large as the sum of the capacities of feeds in the same tree.

One idea I have is to keep a list of all feeds, ordered in capacity from highest to lowest. Take the feed with the highest capacity, do a Dijkstra search for the nearest sink, substract the minimum of the capacities of the feed and sink from their respective capacities, if the capacity of the feed is still not 0, reinsert it into the list of feeds, if the sink has a capacity of 0 remove it as a valid target, repeat.
The Dijkstra search could be cheaper across tiles where there already is water. Also it needs to be tuned somehow to prefer straight lines – keeping track of the direction of the last step and making a step in any other direction more costly should do the trick.

This seems kind of nice for my purposes, but it has one large flaw: All of the canals end up with a width of exactly one tile. I had the idea of making canal tiles blocking for the Dijkstra search and making tiles next to a canal cheaper instead, but that means that canals will end up winding around sinks/feeds and will also path to different sinks than if they could just path straight through the canal.

Different idea: Every canal tile is represented by a canal ID and it's distance from the source of the canal of that ID. Every canal ID is also associated with a capacity.
The Dijkstra search runs as normal, but steps between tiles with the same canal ID can only happen downstream, that is, to tiles with ha higher distance to the source of that canal. When a canal is created, all the tiles it crosses are appropriately set, only that any tile with an existing canal ID downstream from where the canal enters that old canal and upstream from where the canal leaves the old canal gets a new canal ID. The capacity of the new canal is checked to decide whether it needs to be widened. The tiles created by widening get their distance value from the lowest distance neighbor tile of the same ID.

That seems awfully complex. Does anybody have experience with generating something like this? Or ideas how to simplify what I tried to describe here? Questions for clarification? Some pointers how the previous may fail spectacularly?

If it is of any consequence: I am writing this in Common Lisp with the help of "defenum", "fset" and "croatoan".

2

Programming / CL scent-map - datastructures and algorithms for maps in a broader sense

« on: February 12, 2012, 05:06:20 PM »

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 http://hg.sharesource.org/clscentmapYou 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
(SAME-DIRECTION-P DIRECTION (OPPOSITE-DIRECTION (OPPOSITE-DIRECTION DIRECTION))) => T
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 rec.games.roguelikes 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.

3

Programming / Limb-oriented skill system - You see any pitfalls?

« on: October 14, 2009, 02:11:40 PM »

I am working on the design for my first roguelike right now.
So I had the idea to make a limb-based skill system that takes into account the physical composition of a creature. This should go beyond what's DF is doing but it should be easy to understand in principle, although it might be complex under the hood.

So far I've got only a system that may be appropriate for battle-related skills (because those should use the whole body).

The basic idea is to have limbs attached to each other in a hierarchical order, like a non-binary tree. The root of this tree should be the center of mass (one hand below your belly-button if you are a human). The nodes of this root are the different bodyparts where the connections between this nodes are joints which have a certain degree of freedom (between 0 inclusive and 100 exclusive in percent) - the joint to my upper arm is way more flexible then my elbow.
For every bodypart there now is a dextirity and a strength expressed through a number between -100 and 100 exclusive in percentages (so actually its between -1 and 1). Every attack is done through a special limb - a punch is delivered through your hand, a kick is done with your foot while you can choke someone with your upper or lower arm.
The chance-to-hit for an attack is calculated thorugh the limb you use to deliver the attack. The basic chance-to-hit is the dextirity of that limb. This chance is modified by the following rules:
Go one limb up, multiply the chance-to-hit with the joint rating between the bodyparts. If this is positive, this is the percentage that the original rating is moved into the direction of 100%. When this is negative, it's the percentage the chance-to-hit is moved into the direction of -100%.
This is done recursively to the center of mass.
The damage dealt through an attack is calculated similarly, except that the chance-to-hit of the next-upper bodypart is multiplied with (1 - joint-flexibility) instead of the joint-flexibility.

This seems calculation-intensive on first sight, but the calculated stats for the different bodyparts only change, when the strength or dexterity of a bodypart above the bodypart in question change or when the joint-flexibility of a joint above the bodypart in question change.

This system allows for different fighting styles which use different bodyparts in their attacks. You could even see weapons as just additional limbs with their own joint-flexibility, strength and dextirity. The negative ratings for strength and dexterity could be used to model pain or blockades.


Now this looks all shiny and nice to me, but there surely are some really nasty implications which I overlooked.
Some opinions on this?