Re: Data compression in roguelikes

In article <slrneb00lg.5ra.news@xxxxxxxxxxxxxxxxxxxx>,
news@xxxxxxxxxxxx says...
At Sat, 8 Jul 2006 19:57:14 +0100,
Gerry Quinn wrote:

2d arrays are the worst possible data structures for dungeon maps I can
imagine -- they take lots of memory for repeating the same thing over
and over and are very hard to use.

If they are hard to use, why does everyone use them?

They are easy for people. Not for computers.
Computers have problems with picture analysis.

But computers don't have to analyse the 2D arrays in this way.

(What's an ASCII screen map, incidentally? Looks like a 2D array to
me...)

Sure, optimize for display. After all you're doing it soo often, the
whole screen gets refreshed like what, once in 100 turns?

WHy would you want to optimize for operations that are made every
turn for every monster? It's displaying slow, so optimize for the display.

The point is, there's something fundamental to a roguelike there.

You
need sophisticated FOV algorithms to display them.

The FOV is about as simple as possible unless you abstract away to
rooms etc. like original Rogue. But even that had a 2D array as well.

Sore, for ceratin values of "simple".

If you are modelling FOV on a geometry that is a 2D array of squares,
there's little alternative.

Unless you go to a structure like a 3D game. I don;t believe that
makes things less complicated, though!

You need complicated
pathfinding algorithms to make your monsters move in them.

Dijkstra, or Dijkstra at two levels (one for a large-scale grid for
long-distance travelling.

What was the computational complexity of Dijkstra, again?

Doesn't matter, you need it, whatever structure you use.

Where would you get the large-scale grid from when you only have the
raster map?

You could generate nodes at random points, roughly evenly spaced, and
expand wavefronts from them until they meet, or until a fixed distance
is reached. If there are squares that have not been reached, put more
nodes in some of them and repeat.

You could probably then improve the grid with some heuristics based on
the distances.

However, I don't think large-scale pathfinding would be relevant to
most roguelikes. Teacking the player avatar can use a trail left by
his FOV, and out-of-sight monsters can use the mysterious teleportation
system known only to them and the programmer.

You need
scanning just to say what changed.

You've either got to scan whatever your structure is, or monitor the
changes.

And where do you record them, in the raster map? Or, no, don;t say that,
you use a *different* data structure?

I've not found anything I need to record elsewhere. If there are
objects with time-based effects in a square, they will be treated like
monsters - in which case of course they will only have an ID reference
on the map.

But if your system works for you, fine. To me it seems a bit over-
complicated. I think you'll have to finish the game to convince most
people of it, though!

- Gerry Quinn
.

Relevant Pages

  • Re: Automated information display
    ... The idea would be to have some data, say in CSV format and ... modern computers are capable of programming themselves. ... believe this is immediately obtainable trough programming of weak AI. ... display the data short of solving the entire AI problem. ...
    (comp.ai.philosophy)
  • [Un] Unangband 0.6.2 beta 2 has been released
    ... changed the scale of level feeling ... in this way we have less monsters of the same level in monster groups ... changed filename of a tip kind to be prettier to display ... Fix for Bug #13250: Tree trunks can be opened (and bashed with the same ...
    (rec.games.roguelike.angband)
  • [Un] Unangband 0.6.2 beta 2 has been released
    ... changed the scale of level feeling ... bumped the level of low-level monsters, ... changed filename of a tip kind to be prettier to display ... Fix for Bug #13250: Tree trunks can be opened (and bashed with the ...
    (rec.games.roguelike.announce)
  • Error Handling
    ... Below is my practice sript to display domain names. ... The computers listed may not acutally be on the network and I thought the ... Dim strComputerRole ... Sub DetectRole ...
    (microsoft.public.scripting.vbscript)
  • Error Handling
    ... Below is my practice sript to display domain names. ... The computers listed may not acutally be on the network and I thought the ... Dim strComputerRole ... Sub DetectRole ...
    (microsoft.public.scripting.wsh)