Re: Compressing your levels

On Aug 26, 12:59 pm, Radomir 'The Sheep' Dopieralski
<n...@xxxxxxxxxxxx> wrote:
I stumbled upon this interesting video about "intelligent"
resizing of bitmap graphics:

<http://www.youtube.com/watch?v=vIFCV2spKtg>

Yeah, very impressive - I wish I had made it to that paper.

Because bitmpa graphics is very similar in its nature to roguelike
maps, many interesting algorithms from that domain can be used in
roguelike games. In this case, the algorithm (with a modified function
for weights of "pixels") can be used to "compress" parts of the dungeon
that are "uninteresting" -- large rooms, long runs of straight corridors,
empty space.

Then again, care must be taken, because all these features can have an
important strategic function. One should probably count the weights
*after* the monsters and items have been generated, and there is still
the risk of taking away the breathing space that players could use.

Maybe, instead of compression, one could see it as an post-map-
generation algorithm? Ie, after you build your level using some "take
lots of room" approach, you run seam removal to remove excess portions
and get a more tight nit dungeon?

One option would be to add some hard constraints (preservation of
connectedness, for example), along with the desired weighting and run
until a certain error threshold is reached.

Note for most dungeons which are generated compact, it is unlikely to
work well - it produces poor results for excessively detailed scenes.

Still the idea of removing vertical or horizontal runs of pixels with
minimal weight is very interesting.

To make it clear, the seams removed are 8-way connected runs of
pixels. If you restrict yourself to just removing columns/rows, the
quality goes down quickly.

I don't recall anything that fancy being done in the implementation -
dynamic programming for seam identification is straight forward to
implement.

I wonder if one could build a 7DRL around this? Every 30 time ticks
another portion of the dungeon is removed?
--
Jeff Lait
(POWDER: http://www.zincland.com/powder)

.

Relevant Pages

  • Re: Problem on an nxn grid
    ... "See Spot Run" in the vocabulary of Graph Theory. ... Gibbons's "Algorithmic Graph Theory" gives a pseudo-code ... parts of the Edmonds algorithm (such as the Hungarian ... All weights are assumed to be ...
    (sci.math)
  • RE: [REPORT] cfs-v4 vs sd-0.44
    ... The definition for proportional fairness assumes that each thread has a ... threads have fixed weights throughout the interval. ... approximate this ideal scheduler (often referred to as Generalized ... The goal of a proportional-share scheduling algorithm is to minimize the ...
    (Linux-Kernel)
  • Re: A roguelike system in Perl
    ... Mike Anderson's dungeon building algorithm and build a basic random dungeon ... My algorithm to redraw the screen ... I'd like to hear comments and suggestions on the demo maps. ...
    (rec.games.roguelike.development)
  • Re: Roguelikes in science fair projects
    ... > and implementing a roguelike engine", then I'd have no trouble at all. ... > twisty corridors connecting rooms and I know there are several ... > shortness of the path and the iterations/speed of the algorithm. ... "What makes an aesthetically pleasing dungeon?" ...
    (rec.games.roguelike.development)
  • finding shortest path...
    ... G = unoriented labeled connected graph G with n vertices and maximal ... Then the edges must be labeled by random weights from ... Output of the algorithm: ... The sequential algorithm is of type BB-DFS with the search depth ...
    (comp.programming)
Loading