Author Topic: How are huge game worlds stored in memory?  (Read 19552 times)

TSMI

  • Rogueliker
  • ***
  • Posts: 65
  • Karma: +0/-0
    • View Profile
    • Email
How are huge game worlds stored in memory?
« on: January 12, 2014, 04:55:17 AM »
Take ADOM as an example, which has an overworld, several different towns, dungeons, and persistent NPCs associated with certain locations...

How are these stored in memory? Is each town serialized, then deserialized when you enter into it? Or they all actually loaded into memory at any one given time?

I am really confused about how to model linked levels in general, actually. Obviously only one is usually "active" at any one time - the one the player is on. But then there are edge cases, like in ADOM where a nearby monster will follow you down some stairs.

Quendus

  • Rogueliker
  • ***
  • Posts: 447
  • Karma: +0/-0
  • $@ \in \{1,W\} \times \{1,H\}$
    • View Profile
    • Klein Roguelikes
Re: How are huge game worlds stored in memory?
« Reply #1 on: January 12, 2014, 05:59:19 AM »
On modern hardware, you'd need a gigantic world to hit storage limits when just holding the whole world in memory. Especially in ASCII games with tile-based worlds that don't need to worry about graphics storage or high-detail environments. Huge games and large games written on legacy hardware might need to (de)serialise data for inactive levels.

Having nearby monsters follow the player down stairs like in Crawl or ADOM is quite achievable without having more than one level under active simulation at a time - just capture all monsters in range when leaving and schedule them to appear at an appropriate time. If you want to do it "properly", then you just need a container for levels that can load and free levels when necessary, and mark one or more as the active.

IBOL

  • Rogueliker
  • ***
  • Posts: 102
  • Karma: +0/-0
    • View Profile
    • IBOLOGY LLC
    • Email
Re: How are huge game worlds stored in memory?
« Reply #2 on: January 12, 2014, 07:46:32 AM »
Hi,
I am doing "persistence" for the first time in my current project, and I handled it like this:

the current world mm[]  (map or whatever) is an array big enough to hold everything about a single location (one sector of space or one planet, etc.)
(all mine are 30x30, with  7 data elements for each tile)

when you leave an area, you save it to a file that can hold all that information.

monsters and items are saved in linked lists. the map references the monster or item instance.
mm[23,7].monster=7  ;  mm[1,1].item=48

monsters and items are each defined on their own, with 30-40 characteristics.

I don't bother to save all the data about each item and monster. I save what "KIND" it is.... supplies, corona shield, pirate, space amoeba,
and when you re-enter the area, I re-generate all the stuff about the items.

there is no technical reason not to save the individual items and monsters, I just did it to keep my data files small (about 11k per area)

like I said, this is my first foray into persistence, and it works very well.
once you wrap your head around what's important, you'll get it.

[edit]
and yeah, if you want a monster to follow you , just cheat, and 'bring it with you' ... don't delete it when you change areas, and then place it near the stairs with you...
« Last Edit: January 12, 2014, 07:54:00 AM by IBOL »
Randomly Approaching The Infinite Realms.
http://ibology.org/

Trystan

  • Rogueliker
  • ***
  • Posts: 164
  • Karma: +0/-0
    • View Profile
    • my blog
Re: How are huge game worlds stored in memory?
« Reply #3 on: January 12, 2014, 08:06:26 AM »
Many of the big roguelikes were started decades ago when hardware was orders of magnitude less capable than they are today. Your car probably has more computing power than the hardware of the first Nethack or Angbands. You would need a very very very large world to hit the limits of what a decent computer within the last 5 or so years can handle. For simplicity's sake it's probably best to start with keeping everything in memory. If your profiler shows that's a problem, then you can keep the local and nearby chunks (such as current level, previous level, and next level) in memory and store the rest. If your data structures and abstractions are right, then they can swap in/out the chunks when needed without you having to deal with it.

There are quite a few tutorials on making Minecraft-like games that have interesting things to say about this very topic. They often have worlds that are over 8 times the Earth's surface (http://notch.tumblr.com/post/443693773/the-world-is-bigger-now) and made of arrays that are 255 x 255 x 255 - or whatever - that they swap in and out of memory as needed. Or generate new chunks on the fly. In realtime.

Krice

  • (Banned)
  • Rogueliker
  • ***
  • Posts: 2316
  • Karma: +0/-2
    • View Profile
    • Email
Re: How are huge game worlds stored in memory?
« Reply #4 on: January 12, 2014, 12:02:39 PM »
You would need a very very very large world to hit the limits of what a decent computer within the last 5 or so years can handle.

The problem is that often people don't just run one program at a time and there are less powerful mini laptops with not a lot of memory to spare.

miki151

  • Rogueliker
  • ***
  • Posts: 264
  • Karma: +0/-0
    • View Profile
Re: How are huge game worlds stored in memory?
« Reply #5 on: January 12, 2014, 03:16:01 PM »
Even if you have 100 levels and each is 50x40, that's 200k tiles. Most of them can be reduced to an enum describing their type. I think few roguelikes are big enough to have this kind of problem, usually they will hit CPU power constraints earlier.
KeeperRL, Dungeon Keeper in roguelike style:
http://keeperrl.com

Krice

  • (Banned)
  • Rogueliker
  • ***
  • Posts: 2316
  • Karma: +0/-2
    • View Profile
    • Email
Re: How are huge game worlds stored in memory?
« Reply #6 on: January 12, 2014, 10:26:53 PM »
Even if you have 100 levels and each is 50x40, that's 200k tiles.

Kaduria has close to ten layers of map data per each level and levels can be sometimes much bigger than 50x40. Besides there is game object data as well, not just tiles.

Trystan

  • Rogueliker
  • ***
  • Posts: 164
  • Karma: +0/-0
    • View Profile
    • my blog
Re: How are huge game worlds stored in memory?
« Reply #7 on: January 13, 2014, 01:16:17 AM »
You would need a very very very large world to hit the limits of what a decent computer within the last 5 or so years can handle.

The problem is that often people don't just run one program at a time and there are less powerful mini laptops with not a lot of memory to spare.

True, but when the profiler shows that's a problem - and where to fix it - then it can be addressed. I've never seen a roguelike fail because of problems with memory or cpu usage. I've seen many roguelikes fail because of the problems of unneeded complexity, loss of interest, and imagined problems. I'd advise anyone to first make a game the simplest way you can and then once you have something that's popular and fun and beginning to run into performance problems, you can tweak it.

tuturto

  • Rogueliker
  • ***
  • Posts: 259
  • Karma: +0/-0
    • View Profile
    • pyherc
Re: How are huge game worlds stored in memory?
« Reply #8 on: January 13, 2014, 04:55:25 AM »
And with modern OSes, you're usually dealing with virtual memory and not with the actual one. So the OS can swap some of the data on the hard drive.
Everyone you will ever meet knows something you don't.
 - Bill Nye

miki151

  • Rogueliker
  • ***
  • Posts: 264
  • Karma: +0/-0
    • View Profile
Re: How are huge game worlds stored in memory?
« Reply #9 on: January 13, 2014, 08:03:48 AM »
Even if you have 100 levels and each is 50x40, that's 200k tiles.

Kaduria has close to ten layers of map data per each level and levels can be sometimes much bigger than 50x40. Besides there is game object data as well, not just tiles.
With some tricks you can at least reduce the memory consumption of tiles that have never been visited and don't contain any items. I would guess is they are the huge majority of all tiles. Game object data is a different story, true, but it doesn't explode that quickly if you're trying to make a big world.

And with modern OSes, you're usually dealing with virtual memory and not with the actual one. So the OS can swap some of the data on the hard drive.
Interesting, I thought the OSes will only swap an entire process to the disk if they decide so. Still, it's not a good idea to use a big percent of the computer's memory, as other apps like the browser will get swapped too, making the experience really bad.
« Last Edit: January 13, 2014, 08:06:31 AM by miki151 »
KeeperRL, Dungeon Keeper in roguelike style:
http://keeperrl.com

guest509

  • Guest
Re: How are huge game worlds stored in memory?
« Reply #10 on: January 13, 2014, 09:23:54 PM »
For me I do not save the maps so much as I save the objects and their location.

The player object knows what rooms it is in, so when the room location changes I go through all the objects in my game and display that ones with that room location, or if it's a new room then generate all the objects with my level builder. Walls, baddies, items. They all have a grid location and a room/level location.

To bring baddies down stairs with you, when your player goes down the stairs check the spaces adjacent, save that monster, and have it show up on the stairs in the next level as soon as your player vacates the stairs. Or place it adjacent to the stairs, whatever your design calls for. You don't need to be figuring out the state of that other level for just a couple of monster to follow you.

I guess some games might give the illusion they are running turns in every area each time the player takes a turn, but I'm not sure any game is actually figuring out the movement of the boss on level 20 while you are moving out on level 1.

For games with an overworld and separate modes or screens for towns and dungeons, those dungeons probably aren't even created until you enter them. And then when you leave they are just saved to the hard drive or even an array if the game isn't too massive. They aren't 'running' while the player isn't in them, though some games when you re-enter a dungeon it will run a few turns just to look like things have changed, been running, since you were last there, it's an illusion.

Krice

  • (Banned)
  • Rogueliker
  • ***
  • Posts: 2316
  • Karma: +0/-2
    • View Profile
    • Email
Re: How are huge game worlds stored in memory?
« Reply #11 on: January 13, 2014, 11:02:09 PM »
With some tricks you can at least reduce the memory consumption of tiles that have never been visited and don't contain any items.

Must be an interesting trick, because usually maps are just simple 2D arrays.

TSMI

  • Rogueliker
  • ***
  • Posts: 65
  • Karma: +0/-0
    • View Profile
    • Email
Re: How are huge game worlds stored in memory?
« Reply #12 on: January 14, 2014, 01:24:18 AM »
Alright, I've figured out my level switching code. It's pretty modular, so if I need to read/write from hard disk at a later date I can. It's all in memory at the moment now, until it gets obnoxious I'll leave it like that.

guest509

  • Guest
Re: How are huge game worlds stored in memory?
« Reply #13 on: January 14, 2014, 06:47:16 AM »
Are you wanting to be going up and down levels? Or straight dive down? You probably wouldn't be asking this if you didn't want to figure out how to go back up and have your levels still be there.

TSMI

  • Rogueliker
  • ***
  • Posts: 65
  • Karma: +0/-0
    • View Profile
    • Email
Re: How are huge game worlds stored in memory?
« Reply #14 on: January 14, 2014, 08:03:49 AM »
Are you wanting to be going up and down levels? Or straight dive down? You probably wouldn't be asking this if you didn't want to figure out how to go back up and have your levels still be there.

Go up and down, so persistent levels.

It works, but I'm doing a lot of things that are expensive in terms of memory.