Author Topic: Importance of persistence  (Read 12206 times)

theloon

  • Newcomer
  • Posts: 21
  • Karma: +0/-0
    • View Profile
Importance of persistence
« on: August 21, 2012, 04:27:16 PM »
I have an Atari 2600 Rogue-like project.  I'm heavily using procedural and or pseudo random techniques for my dungeons.  Right now I have each item persistent all through the dungeon and levels until the player picks it up.  Then EVERY other instance of that item in every level of the dungeon changes location.

Most PC Rogue-likes probably expect things can be moved around and remain stationary.  On the Atari 2600 I have 26 8-bit variables to use for the ENTIRE game.  I just don't see how to store item location information like on a PC.

Is my compromise above enough?  How strong is persistence for a Rogue-like?

Pueo

  • Rogueliker
  • ***
  • Posts: 263
  • Karma: +0/-0
    • View Profile
    • Email
Re: Importance of persistence
« Reply #1 on: August 21, 2012, 04:57:27 PM »
I'm not sure how much space 26 8-bit variables translates to, but could you just store only the level you're on and then when they get to the next level, get rid of the last one?  I don't think persistence is a required part of RLs, the original Rogue only had one level at a time (each time you entered the level, it got rid of the last one).
{O.o}
 |)__)
   ” ”   o RLY?

Darren Grey

  • Rogueliker
  • ***
  • Posts: 2027
  • Karma: +0/-0
  • It is pitch black. You are likely to eat someone.
    • View Profile
    • Games of Grey
Re: Importance of persistence
« Reply #2 on: August 21, 2012, 09:36:14 PM »
If you're game is designed right then it should be fine to allow no retreat, so only the current level is ever needed.

Krice

  • (Banned)
  • Rogueliker
  • ***
  • Posts: 2316
  • Karma: +0/-2
    • View Profile
    • Email
Re: Importance of persistence
« Reply #3 on: August 22, 2012, 06:25:37 AM »
On the Atari 2600 I have 26 8-bit variables to use for the ENTIRE game.  I just don't see how to store item location information like on a PC.

I remember the time with 8-bit computers that had serious resource limitations and personally I can't think any good reason to return to that by selecting a platform from that time. If it's some kind of challenge then it's ok, but then you should not ask stupid questions, you should already know what you are doing.

Leaf

  • Rogueliker
  • ***
  • Posts: 64
  • Karma: +0/-0
    • View Profile
    • Email
Re: Importance of persistence
« Reply #4 on: August 22, 2012, 02:24:16 PM »
That's a tough one!

You might use a procedural algorithm to generate a list of loot locations.  Then you could use a couple of your precious variables as bitfields to indicate which entries in the list are still there.  You'd not be able to let the player drop things, but I don't think that would be a problem.  They pick up a +1 sword, it only replaces what is in their inventory if it's better than what they have?

Yea, I'd do that, and not let them return to previously visited levels as was already discussed.

requerent

  • Rogueliker
  • ***
  • Posts: 355
  • Karma: +0/-0
    • View Profile
Re: Importance of persistence
« Reply #5 on: August 23, 2012, 02:30:31 AM »
Suppose you have a separate seed for level generation.

RNG(seed,depth) returns a deterministic random value used to generate a given level. IE, if you're moving on to depth 8, we use RNG(seed,8) to get a value that we can use to generate the next level. generateLevel(RNG(seed,currentDepth+1), currentDepth, ... ), or something.

This will make it so that your levels are deterministically generated from an original random seed, effectively allowing you to store all of the map data within the seed used by the algorithm (which it itself is generated from the original seed used by the RNG for level generation). We only need to know which depth we are coming from and which depth we are going to and we can get the same level every time. The obvious problem with this is that our map will generate new instances of the same monsters, items, etc.

To resolve duplications, I would split it up into three phases. The first phase is to tell our level generator which items/monsters not to generate. When we leave a map, we can store which objects were removed from the map via a bitstring or some other minimal data-type. We only need to store the object relative to the order in which objects were generated. That is, if you kill the monster that was generated first (by the algorithm), we only need to know not to generate the first monster. We can give each object a unique binary enumeration and run a binary tree compression algorithm to ensure that the amount of information we're storing is minimal. If we're going upstairs, we can have something like -> GenerateLevel(RNG(seed,currentDepth-1),currentDepth, phase1[currentDepth-1], ... ). Where phase1 is the pointer to an array for each depth that stores a binary compressed value of the monsters and items that should not be generated.

We could potentially stop here and be satisfied with pseudo-persistence. However, when a level is regenerated the monsters/items will spawn with full health at their original spawn points. Phase2 will simply be storing xcoord, ycoord, and HP of monsters and items remaining on the map. Undisturbed monsters/items can be generated as per the normal generation algorithm, but objects that have moved or been hurt need to have those values stored in some way. Then when we regenerate the level we can move/adjust the HP of the objects accordingly. To reduce the memory footprint, we can store +/- 2-3 depths worth of monsters/items. Then, after you distance yourself enough from a level, we can say those objects have healed and returned to their original locations as specified by the level generator. At which point we would only need to use the values of phase1 to determine what is supposed to be in the level and what is not.

Phase 3 is for items NOT native to a level. We need to be able to fetch the seed used to generate that object and it's current depth and coordinates. This is the most memory taxing, as it isn't very coherent for an item dropped on a different level to suddenly disappear when previous items of that level are still there. There are mechanics that you could use to make this more interesting, but it boils down to just about the same memory footprint. Ideally, you would enumerate every item generated and have a separate RNG seed for items. RNG(itemSeed,itemID) will give you the seed necessary to generate that item. So if phase3 is a pointer to an array of tuples that stores the itemID (the order in which the item was generated), the xcoord and ycoord, we can ensure that items that have migrated to different levels stay there after we've left. These items will be culled from their original levels via the phase1 for that depth, so we don't need to know where it came from originally.

Phase2 can be culled over time and phase1 will only store very small values. If your mechanics are designed well, players won't be dropping a superfluously large number of items on levels where they weren't generated, ensuring that phase3 doesn't get out of hand.

IDK if this is the best approach, but some ideas here might get you started. Persistence isn't at all necessary though.

Ari Rahikkala

  • 7DRL Reviewer
  • Rogueliker
  • *
  • Posts: 64
  • Karma: +0/-0
    • View Profile
    • Email
Re: Importance of persistence
« Reply #6 on: August 30, 2012, 11:23:31 AM »
26 bytes. That's a hell of a not much to work with. Haskell on 64-bit machine takes 40 bytes to store a string consisting of one character... 40 bytes plus the memory needed to actually store the character itself. How lucky we are to live in this time.

That's a tough one!

You might use a procedural algorithm to generate a list of loot locations.  Then you could use a couple of your precious variables as bitfields to indicate which entries in the list are still there.  You'd not be able to let the player drop things, but I don't think that would be a problem.  They pick up a +1 sword, it only replaces what is in their inventory if it's better than what they have?

Yea, I'd do that, and not let them return to previously visited levels as was already discussed.

You could get pretty far with this, I think. One problem you might have is that, well, suppose you use all of your leftover memory so you have 208 possible items in the game. Let's also say that you somehow manage to fit in equipment slots that are indexes into the item list. Let's say your weapon is at index 200. Okay, that's fine. You just start with the seed and generate all the 199 items before it and throw them away (or, more likely, pull out enough values to get it to the state where it would be when generating the 200th item). I'm not sure how slow the Atari 2600 is, but I suspect that you don't really want to generate hundreds of items' worth of random numbers every time you're using an item's stats. What you want is to be able to get the nth random number quickly.

http://mathoverflow.net/questions/104915/pseudo-random-algorithm-allowing-o1-computation-of-nth-element has a few approaches that might work. The latter seems especially nice - you just use a hash function as your PRNG, and to get the nth random value, you compute hash(seed+n). But try it without this first, I really have no feel for what's "a lot of computation" on ancient computers and this might be completely unnecessary complexity.

theloon

  • Newcomer
  • Posts: 21
  • Karma: +0/-0
    • View Profile
Re: Importance of persistence
« Reply #7 on: August 30, 2012, 09:19:39 PM »
On the Atari 2600 I have 26 8-bit variables to use for the ENTIRE game.  I just don't see how to store item location information like on a PC.

I remember the time with 8-bit computers that had serious resource limitations and personally I can't think any good reason to return to that by selecting a platform from that time. If it's some kind of challenge then it's ok, but then you should not ask stupid questions, you should already know what you are doing.

So, you are stating:
* You wouldn't try to program a Rogue for a constrained system
* I shouldn't ask questions because I should know already?

Thanks, thanks for that.

theloon

  • Newcomer
  • Posts: 21
  • Karma: +0/-0
    • View Profile
Re: Importance of persistence
« Reply #8 on: August 30, 2012, 09:35:20 PM »
Thanks guys for the advice so far.  I'm going to be reading and re-reading the responses and links to fully understand things.

I wondered how strong Rogue fans felt about items staying in place once you've dropped them.  I think using a pseudo random seed for item and monster location is the key.  It allows un-picked up objects to stay in place no matter what x/y/z location the player wanders.  I may use up some variables for a kind of weak persistence within a dungeon level.  Maybe the last and second to last monster spawn will stay empty.  Maybe the last and second to last item will have their locations recorded for that level.

I really appreciate the feedback!  Thanks for taking the time to mull things over with me :)

guest509

  • Guest
Re: Importance of persistence
« Reply #9 on: August 31, 2012, 12:06:20 AM »
  Ignore Krice on this. He's constantly negative. Often correct, but constantly negative.

  You kinda want items to stay in place on the same level, but from level to level don't worry. You can make it so people cannot return to the above levels so you can just wipe them each time. This has already been said.

  The real challenge is that there are a limited number of objects allowed per line or you start to get flicker. Flicker can really suck. Back in the day we didn't mind because we were used to it. Try playing Pacman 2600 nowadays with all the flicker. Or maybe they made the ghost flicker for some reason I'm unaware of?

  How big are your levels? One screen? That's what Rogue did, as well as Nethack, Prime and Brogue. All very nice and well respected games.

  I'm actually trying, slowly, to put together a game harkening back to the Atari 2600 version of Berzerk. Love the simple game play. I'm not attempting to use 2600 limitations though. Not that brave. I'm going with the fully bloated modern way!

  Remember to have fun. This is, after all, a hobby. :-)

Krice

  • (Banned)
  • Rogueliker
  • ***
  • Posts: 2316
  • Karma: +0/-2
    • View Profile
    • Email
Re: Importance of persistence
« Reply #10 on: August 31, 2012, 06:54:44 AM »
So, you are stating:
* You wouldn't try to program a Rogue for a constrained system
* I shouldn't ask questions because I should know already?

Yes. Why go back to restrictions of some old system? It's not fun. It doesn't produce good games. The way programmers were able to work with limited resources has already been done better than you possibly can ever do, so you lose in that too. You can't win this way.

Leaf

  • Rogueliker
  • ***
  • Posts: 64
  • Karma: +0/-0
    • View Profile
    • Email
Re: Importance of persistence
« Reply #11 on: August 31, 2012, 08:02:13 AM »
I respectfully submit that I think it can be useful and fun to see how much you can push out of a very limited system, as an exercise if nothing else.

I rather enjoy fiddling with 6502 systems now and then.  I am not hardcore enough for the Atari 2600, though. :P

There are still plenty of 6502s and 8051s with like 8k or less still being used in cheap embedded systems.  It's a whole different programming paradigm, and very interesting if you are into that sort of thing.

guest509

  • Guest
Re: Importance of persistence
« Reply #12 on: August 31, 2012, 11:44:15 AM »
  Krice seems to forget he's on a forum dedicated to a style of gaming based on the system restrictions of the early 80's.

TheCreator

  • Rogueliker
  • ***
  • Posts: 370
  • Karma: +0/-0
    • View Profile
    • Fame
    • Email
Re: Importance of persistence
« Reply #13 on: August 31, 2012, 12:09:49 PM »
  Krice seems to forget he's on a forum dedicated to a style of gaming based on the system restrictions of the early 80's.

One could say that the restrictions of the ice age helped to free the never-ending resources of human creativity and that in turn allowed wonderful inventions like cars, skyscrapers or computers. So why don't we leave our warm homes and go back to the ice age? Jo, you lead us ;).
Fame (Untitled) - my game. Everything is a roguelike.

theloon

  • Newcomer
  • Posts: 21
  • Karma: +0/-0
    • View Profile
Re: Importance of persistence
« Reply #14 on: August 31, 2012, 12:28:44 PM »
Not many people think a Rogue-like on an Atari 2600 is a good idea.  Not many people are up to the challenge either.  It's OKAY if others think it's a bad idea.  It's OKAY if it seems impossible to some.  What's not okay is to limit yourself because others think it's a "stupid question."  Krice can have his opinions.

I think what I'm feeling here is that SOME persistence is a good idea at least on the floor the player is exploring.
« Last Edit: August 31, 2012, 12:59:41 PM by theloon »