Re: Data compression in roguelikes

At Sat, 8 Jul 2006 19:57:14 +0100,
Gerry Quinn wrote:

In article <slrneavner.iid.news@xxxxxxxxxxxxxxxxxxxx>,
news@xxxxxxxxxxxx says...
At Sat, 8 Jul 2006 16:37:28 +0100,
Gerry Quinn wrote:

Not if you have well thought and optimal data structures.
Hint: storing Angband-style map as a 2d array is not optimal.

Optimal data structures are the structures that are easiest to use,
unless there is some kind of bottleneck involved. 2D arrays seem
pretty optimal in that regard, given that that's how they will probanly
be implemented in the game. Say you have a 200 x 100 array, 12 bytes
per square - that's only 240 K, an insignificant amount in most
circumstances.

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.

(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.


You need to scan them to find nearby
objects and monsters, tile by tile every turn for every monster.

That's certainly the easiest way to do it, though you could scan the
monsters and objects if they store their position (currently my
monsters do, but my items don't).

But there's no easy way to do 'nearby' in 2D+.

It's as simple as sqrt(x*x+y*y)<d. Sure, you still iterate through all
the items/monster in given location (which can be as small as a room),
but I assume there is much more map squares than items/monsters on them.


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".

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?
Where would you get the large-scale grid from when you only have the
raster map?


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?

They are expensive, both in terms
of memory and computational power.

I think they are cheap on memory, cheap on computational power, cheap
on comprehension and cheap on difficulty...

And cheap on words.

--
Radomir `The Sheep' Dopieralski

"Computer Science is no more about computers than
astronomy is about telescopes." [Edsger Wybe Dijkstra]
.

Relevant Pages

  • Re: New developer with a couple of questions
    ... link structures like monsters/objects data to the world map array? ... placed on that cell. ... storing the map position in the monsters, ... world is based on cells, so you can use an array for your map, making ...
    (rec.games.roguelike.development)
  • Re: Data compression in roguelikes
    ... storing Angband-style map as a 2d array is not optimal. ... objects and monsters, tile by tile every turn for every monster. ... I think they are cheap on memory, cheap on computational power, cheap ...
    (rec.games.roguelike.development)
  • Re: Cheap tricks for map data structure
    ... map in a roguelike: not the usual list of rooms, monsters and items, ... but instead a two-dimensional array, ... map = 2d array of tiles. ...
    (rec.games.roguelike.development)
  • Re: rgcdes not dead
    ... one is to hand out less health and ammunition, ... monsters frustratingly awkward. ... Not to mention that it's a rare map that needs more tactics than basic ... you at the start, half the level's on your automap, and you don't know ...
    (rec.games.computer.doom.editing)
  • traffic flow in roguelikes
    ... constant flow of monsters from a staircase to a goal-point; ... algorithm for handling this traffic flow. ... By a "map" I mean a subset of Z * Z, ... produce a covering of M by visible subsets; ...
    (rec.games.roguelike.development)
Loading