This page is a mirror of Tepples' nesdev forum mirror (URL TBD).
Last updated on Oct-18-2019 Download

Backtracking

Backtracking
by on (#222447)
I realize this question may not have a simple answer but maybe you guys can get me pointed in the right direction. How does one handle backtracking in, say, a side-scrolling game, and keep the memory required manageable? Specifically I'm thinking of situations where the map changes during gameplay, say you break a block, or open a treasure chest. How does the game "remember" that you did that, without using many pages worth of memory?
Re: Backtracking
by on (#222448)
Depends on the game (e.g. SMB3 just uses extra RAM), but if you want to keep the memory usage low just keep the number of changeable items low, that's really the crux of it.

...and just in case: if you aren't storing the state as a single bits rather than a whole byte, do that too for 8:1 more space.
Re: Backtracking
by on (#222449)
The word "destructibility" has been used for this problem in the past. Search for it if you're interested.
Re: Backtracking
by on (#222450)
I normally have a mandatory single bit per object in the level, so that even a large number of objects such as 1024 will only need 128 bytes of RAM for their alive/dead states. The bits are in the same order as the objects in the object list, that's how I know which bits correspond to which object. When objects are killed/destroyed, their bits are cleared, making it so the objects aren't loaded again when the player revisits the area in the future.

Objects that need more than one bit of state can have more memory allocated to them statically at assembly time. Each entry in the list of objects can optionally have an index, which indicates the first byte it uses in an array dedicated to keeping object states. This can be used to remember anything more complex than the simple alive/dead state that all objects have.

Even a certain degree of terrain destructibility can be achieved like this, since a byte is enough to remember the states of structures with up to 8 bricks. Even hundreds of breakable blocks in a level can have their state tracked with just tens of bytes.
Re: Backtracking
by on (#222451)
(I wrote this before I saw the posts from tepples and tokumaru...)
I'm a bit of a noob, so it would be helpful if you could elaborate. Specifically, I don't really know how one goes about storing the game's state, by which I'm guessing you mean data describing, for example, which blocks are broken where, etc. What I've been able to think of so far is that you could have a portion of the level map loaded into RAM and record changes there, essentially replacing the block that is broken with empty space in the data. But I realize that this isn't going to be the most memory efficient, especially if you want to have backtracking. So what it sounds like to me you're saying is that individual bits can be used to say "this block is intact" or "this block is broken". But I don't know how to format that data to, say, identify the location of the block the bit refers to, for purposes of both drawing and checking for collisions. Say I decide that I can have 8 changeable items per screen so I could store that in a byte. But those changeable items are in different locations on different screens. How does the program know which one is which? Does that make sense?

(After seeing those posts)
Thanks for the info, tepples. "Destructibility" I guess is the word I was looking for. I tried searching for "backtracking" and didn't immediately find an answer.

tokumaru, can you point me to more information regarding creating an object list? I'm pretty new at coding in assembly so it isn't immediately obvious to me how to do things like that when I'm not writing in an object-oriented language.
Re: Backtracking
by on (#222452)
What you're asking is (this is how I'd paraphrase it) "how do I store stuff in memory in a format that makes the most sense, so that I don't have to constantly copy new stuff in there". It's an excellent question for any kind of game development, especially on classic consoles with limited resources.

Using OO or not, the concept still applies universally. I haven't dug through your older posts, but what PLs (programming languages) are you familiar with? Any C-based ones? If so, think of raw data structures in RAM like a struct, except literally as granular as a single byte. The format of the data is entirely up to you (see my previous paragraph), and how you access/use it is entirely up to you. Quite literally this is one of the core aspects of a game engine.

There are TONS of things you get to track: position of sprites (enemies are often made up of multiple sprites), overall X/Y position for the "window" of what the player sees on the screen background-wise (read: think of a large horizontally-oriented map, like a level in Super Mario Bros; you can't see the whole thing, only portions of it), the collision data that might be relevant to the visible map area, "layer" data (what might be drawn before something else), any objects on the screen (not just enemies, think chests or broken blocks like in SMB), etc.. The list is almost endless, depending on how complex your game is.

So in general, yes, any "dynamic" data (that might affect the environment as a whole) is stored in RAM in some manner or another. See 2nd paragraph for "how its stored" (re: formats). Everyone on the NES does it their own way. And most homebrewers, from what I've seen, start with something that seems simple, then a few months down the road realise their first design (for the format of the data) was horrible and wasteful, revamp the entire thing, etc. -- and this happens several times until they get something that feels perfect for their type of game.

Now you understand why commercial companies tended to use the same general game engines with improvements/tweaks applied over time. :-)
Re: Backtracking
by on (#222454)
Nate5700 wrote:
tokumaru, can you point me to more information regarding creating an object list? I'm pretty new at coding in assembly so it isn't immediately obvious to me how to do things like that when I'm not writing in an object-oriented language.

Unfortunately I don't think you will find many resources online on how to perform these kinds of little tasks in assembly. Mainly because there are a million different ways to implement these things, and every little choice you make along the way will have a great impact on what the final program looks like.

The simplest way to make a list is to manually write the data using the .db/.byte statement of your assembler of choice. Here's an example of what a list of objects could look like:

Code:
.db OBJECT_TYPE_COIN ; type
.db $0240 ;X coordinate
.db $0080 ;Y coordinate
.db $00 ;custom parameter

.db OBJECT_TYPE_NINJA ;type
.db $0308 ;X coordinate
.db $00b0 ;Y coordinate
.db $49 ;custom parameter

(...)

This is a list where each object takes 6 bytes, and it's sorted by the X coordinate so we can scroll sideways through the list.

One way to use this list is to have pointers indicating the next 2 candidates for activation,one on each side of the screen. As the screen scrolls, imaginary lines slightly before and slightly after the screen move along with it. Whenever the camera and the imaginary lines move, you check if the next candidate for activation entered the space between the 2 imaginary lines. If so, you take that object's index and check the state table to see whether it's alive. If so, load it and move the pointer to the next candidate. Keep loading any objects that entered the active area and moving the pointer, until you find the first object that's not yet inside the active area. This will be the next candidate for the next time you scroll.

When I load an object, I like to clear its alive bit to prevent it from being loaded again while it's already active. Deactivating objects isn't as simple as activating them, because their spawn point (the X coordinate defined for it in the object table) may be outside of the active area, but since many types of objects can move, their current position might still be inside the active area, so you can't just deactivate them. My solution is to have the objects themselves decide when they should be deactivated, instead of having the engine do it automatically. This means that simple static objects (say, coins) can simply check whether they're inside e active area, but moving objects will only deactivate themselves if both the spawn point and their current position are out of the active area.

When an object is deactivated but it's still alive, its "alive bit" is restored, so it can be loaded again in the future. If the object has been killed/destroyed, the bit shouldn't be restored, so the object is never loaded again.

If you already have programming knowledge in high level languages, the way to implement this in assembly will eventually come to you as you work on your game (like koitsu said, the concepts used in game programming are universal, no matter the language), and you can keep asking questions here when things get confusing. But if you don't have enough programming knowledge to comprehend how this stuff works on general, I'd say it's better that you start with simpler games before trying a scrolling game with backtracking.
Re: Backtracking
by on (#222457)
Koitsu,

I've coded in C/C++, Java, most recently Haxe (one not as many folks are familiar with but it's quite similar to Java). Anyway, it's been a while since I've done anything in C or C++ but I do remember what a struct is, so that's a helpful analogy. I guess what I'm getting hung up on is having to allocate the memory manually for each thing and having that space reserved, as opposed to just saying "struct xyz" and that all happening automatically. In other words, how to keep it all organized? For some things it seems simple, like having labels for bytes in RAM like "scroll_x" and "scroll_y". But for stuff that's more dynamic? Like, it doesn't make sense for every enemy in the game to have its own RAM space to track it's location and alive/dead state. So I guess I just need a bucket of RAM reserved to keep things like that in kind of a tabular format and load/unload things into/from it as needed. I guess I'm just wondering if there are tried and tested methods for this that are commonly used.

tokumaru, thanks for elaborating on your method, I see you're talking about having a list in the actual level data in ROM if I'm understanding correctly, so the alive/dead bits in RAM are simply stored in the same order, yes? That seems to make sense. I agree with you about starting simple, I've written some code but I've never been what one would term an "expert". Still, I like to ask questions like this both to satisfy my curiosity and evaluate what I can achieve, whether that's now or in the future.
Re: Backtracking
by on (#222460)
So the question is to be about how to manage memory for a game that doesn't look like it will all fit into your limited RAM at once? There's no one method for this, but here's a common one:


In a lot of games, the "active" part of a level is a sliding window that follows the player.

The level data itself, and the placement of all its items and destructible parts is some read-only data. At any given time, you have loaded the portion of data that belongs in the active window and copied it into RAM in some way.

So, there are a handful of active items/objects/characters that are currently in RAM. Maybe you have 16 open "slots" of memory there that objects can temporarily reside in when they're active. When you scroll an active object offscreen, you free up its slot. When you scroll a new object onscreen, you look for an empty slot to stick it in.

In this kind of system, your level data is some sort of structure that you can load in piece by piece at the edges of the active window. In a horizontal scrolling game, maybe that's horizontal strips of tiles to place, with a list of creatures placed in that strip. When you load that strip, all those creatures go into active RAM slots.

If you run out of slots, maybe you run the risk of a new creature not appearing when it should, if the previous ones have not disappeared. There are plenty of "despawn" exploits in games due to this kind of problem.

As far as destructible items, enemies that can be removed, etc. you might keep a bitfield in RAM that tracks whether they still exist, which takes effect at that moment of loading when they're supposed to become active. If their bit marks them as gone/destroyed, you skip it and don't need to find a RAM slot for it. So you have "compact" storage for keeping track of inactive things, and then bigger data structure for the active ones. (tokumaru was describing this kind of method above.)


There are other ways to do it though. If you can fit a whole "room" worth of stuff into RAM, maybe you can load and unload only at room transitions. Scrolling on 2 axes probably requires more planning for efficient loading of data than just doing horizontal or vertical scrolling alone. There's a lot of management techniques. Sometimes even a whole game can fit in RAM, it really depends on scope.
Re: Backtracking
by on (#222465)
@rainwarrior

I think the question is more like "how can I manage memory without making a mess when the nes won't do it automatically like c/c++ haxe?". I think in his current situation is not yet where he doesn't have enough memory but more want to figure out a way to manage it easily, especially when having things that can be updated dynamically.

I can understand how he feel, since I don't really have a complete project and still trying way to manage memory without creating some unmanageable tangled mess. I think the best way it to start with simple struct, it help to manage it like C/C++ and try to create something simple first. Don't worry about memory usage at first, just try to define your memory map. Once it's working fine, then optimize the struct for less memory. Of course if some of them are simple and can be done right away (bit flags) then just do it. If you are not sure yet, just get the thing working first.
Re: Backtracking
by on (#222469)
Hmm, well if that is the question, maybe the simplest answer is that all variables should usually be treated as global static allocations. There is no malloc/free, new/delete, and especially no RAII.

Plan out what you need to store in memory, and put it into global arrays that are always there. Figure out how to manage getting data into those arrays, and how and when to you can evict data from those arrays (e.g. mark it as unused so that you can move the next thing into it).

In more complicated cases, you might have different memory layouts that you use at different times. These can overlap, and account for things you need on a temporary basis. (e.g. after a level finishes, you might have a cutscene during which you're free to reuse the memory in a different way before you go to the next level).


There are exceptions to this general rule, but when RAM is very limited it's hard to use generic temporary allocations. You need to get more specific about your game's needs to address it effectively. (Or maybe another way to put this is that memory usage should probably be an integral part of your game's design, because it's likely you will run out otherwise.)
Re: Backtracking
by on (#222472)
Nate5700 wrote:
I've coded in C/C++, Java, most recently Haxe (one not as many folks are familiar with but it's quite similar to Java). Anyway, it's been a while since I've done anything in C or C++ but I do remember what a struct is, so that's a helpful analogy. I guess what I'm getting hung up on is having to allocate the memory manually for each thing and having that space reserved, as opposed to just saying "struct xyz" and that all happening automatically. In other words, how to keep it all organized? For some things it seems simple, like having labels for bytes in RAM like "scroll_x" and "scroll_y". But for stuff that's more dynamic? Like, it doesn't make sense for every enemy in the game to have its own RAM space to track it's location and alive/dead state. So I guess I just need a bucket of RAM reserved to keep things like that in kind of a tabular format and load/unload things into/from it as needed. I guess I'm just wondering if there are tried and tested methods for this that are commonly used.

The 3 posts above mine here are applicable to this question, but the short answer is this:

Higher-level languages -- which C falls under in this case -- hide a very large amount of the work actually going on at the CPU level. I'm speaking generally and abstractly here (i.e. what I say is for the most part true but not entirely): a CPU itself has no real concept of memory management. There is no CRT/crt0 (C run-time library) in the CPU. There is no concept of malloc/free (part of libc or other base library) in the CPU. In fact, for the most part, there is no concept of a kernel in the CPU. The CPU will do whatever it's told. Present-day CPUs (x86/x64) are complicated and have insane layers of memory modelling and features that I don't want to get into. Ignore all that and think simple.

With the NES, you are literally writing assembly code that runs native on the CPU. Software-wise, it doesn't get more low level than that. On common-day x86 this is also true (as long as you ignore the x86/x64 microcode part) (I used to code in 286/386 assembly back in the day, so I'm a bit familiar with that platform too, but today things are a complicated mess). On the NES, there is no OS, there is no BIOS, it's literally "CPU starts running your code at address $8000" and you do everything yourself (esp. relating to memory).

Strictly speaking about memory: What you know on the NES is the following: it has 2KBytes of RAM located within address range $0000 to $07FF. That's it. The end. Really. :-) How you choose to use (access, use, segregate/split up/etc.) is entirely up to you and the code you write. There is no concept of "dynamically allocated memory" at the CPU level (on any CPU, actually!); actual machine code has to do this.

I had a bigger write up here, but I decided to put it on pastebin since it very quickly gets a bit off-topic (that is to say, off the topic of memory layout/management) very quickly, so you can read it only if you want to: https://pastebin.com/LPi7ZfK7

Asking if there are tried-and-true methods for all of this (good layout, etc.) is a good question, and appreciated, but I think most of the answers you'll get on this subject are very specific. For example, if you were to ask that about, say, map design -- because you idealise having huge open worlds (say, twice as large as the overworld Zelda 1) -- people might be able to say "well it depends on X/Y/Z/A/B/C. Can you give us some insight into those?", you answer, and they say "I'd suggest you lay out your map data like this, and here's why".

But when it comes to just general RAM/memory layout, I don't think there's any kind of commonplace "good recommendation".

I think one of the blockers here, conversationally, is that you don't know 6502 assembly. Once you get familiar with that, you're going to learn the limits of the CPU, and why certain things are the way they are. A big one is that you're going to learn why there is so much on the 6502 that relates to or revolves around the number 256 (specifically, pages of memory, where a page is always 256 bytes in size, ex. $0000 to $00FF is page 0 (zero page), $0100 to $01FF is page 1, etc.)), and that how you go about accessing >256 bytes (or even doing things like handling a number larger than 256, e.g. a score), is kind of "weird" compared to existing PLs and x86/x64 CPUs you're used to today (64-bit linear addressing is a LOT of addressing space!). You'll also learn just how annoying multiplication/division is on the 6502, and how a lot of how you do code (and everything, actually!) tries to minimise use of anything other than bitshifts for *2 (4, 8, 16...) or /2 (4, 8, 16...). This is getting a bit off-topic; my point is that once you learn 6502, a lot of the "memory layout" questions you have you'll be able to answer yourself, and if you get stumped on something precise, you'll know what to ask.

In general, I don't think anyone has really ever tried to document "what's universally best" for this type of thing on a particular architecture (NES) or CPU (6502), with regards to doing a game. It's because everyone ends up doing it differently -- and that's the same thing seen in commercial NES games too (Capcom had their own way of doing stuff, Konami did, Nintendo did, Rare did, Acclaim did, etc.).
Re: Backtracking
by on (#222473)
Storing permanent states is a huge part of older games with limited memory, and if you look at actual NES games out there, very few even do it.
Even Dragon Warrior, an RPG, doesn't even remember more than the last 5 or so chests you opened. Open more, and the old ones will reappear.
And even in modern games with huge open worlds, physics simulations, and stuff that can be freely moved around, prioritizing what is important to remember and what isn't, is a huge part of their design.

Fortunately, games with large amount of states that need to be remembered are also so big that they need saveram in the cartridge, which adds a bunch of extra memory anyway, but using methods like what's been discussed in this thread are still necessary to keep the usage low of course.
Super Mario Bros. 3 is a popular example, using cartridge RAM to store the states of destructable bricks in the stages, but even in this game it's worth pointing out that it never remembers the state outside of the room (or stage?) you are currently in.

So what I'm saying is that a big part of these kinds of problems can (and should) be solved via game design. Are there points in your game where remembering certain states isn't necessary? Maybe an area becomes closed off from backtracking at some point? Maybe some states are more important to remember than others? For example, if the player beat a boss, or used a one-use key to open a lock, you want to remember that, but once you leave the current "room", it might not be important that they moved a box.
You could also get really creative and look at states that are dependent on eachother (or force it, if necessary!). For example, if you have seven locks in one area that you want to remember individually, but exiting the area isn't possible until all of them are open. Once you leave that place you just need to save one flag (one bit) indicating that all locks are open. Creative use of tools like that can make it appear like your game remembers a lot more than should be possible.
Re: Backtracking
by on (#222480)
Thanks everyone for being so helpful. I'm sorry my knowledge level hasn't been high enough to really condense the question into something more specific, but what it basically boils down to is what rainwarrior says here:

rainwarrior wrote:
Figure out how to manage getting data into those arrays, and how and when to you can evict data from those arrays (e.g. mark it as unused so that you can move the next thing into it).


So what I've really been wondering is what the data in those arrays should look like. And it sounds like the answer is "it's up to you and the design of your game".

So even though that doesn't really give me an answer, it does give me an answer. tokumaru's example of his method maybe isn't something I'd replicate exactly, but it establishes the principle.

FWIW, the design I had in mind is sort of a hybrid single-screen platformer, where each level is made of multiple "rooms". So what I want to do is be able to backtrack to previous rooms in the level and have the game remember what was broken or opened, but the game wouldn't scroll freely. The game wouldn't need to remember what objects were changed beyond what was done in that particular level.

I'll give it some more thought and play around with it. Please don't mind if I ask more questions as I go. I appreciate you all being thoughtful and willing to work with someone who's still learning.
Re: Backtracking
by on (#222485)
That depends on how many screens and how many breakable things you want per screen. Do you want one or two things per screen, or as dense as the huge masses of breakable bricks in WORLD 4-2 in Super Mario Bros.?
Re: Backtracking
by on (#222492)
Well, definitely not as dense as World 4-2.

I'm thinking maybe up to two chests, plus some breakable blocks, like 7 or 8 max, plus coins (well, ears of corn for the collectible, actually). So maybe 24 objects per screen max? That would be three bytes of status bits, per screen. Not really sure how big I'll go as far as screens per level, maybe as many as 6 to 10. So 32 bytes might be enough. That doesn't include enemies, but I'm kicking around the idea of having the enemies respawn if you backtrack.
Re: Backtracking
by on (#222506)
Here's how... I think... Indivisible works. For keeping dead enemies dead. (It's probably slightly different in practice.)

I build the levels in some tool (like tiled) and place enemies, then export it. Then, a program I wrote builds the level data for the game.

A counter starts at zero. Every time an enemy is encountered, it puts the value of the counter in the game's data with the type and position of the enemy, then increases the counter.

Now every enemy has a unique number (a destroy number). When the enemy is created (scrolled to), that number is stored in the enemy's RAM (just like its position is).

The object loop starts. The enemy divides its destroy number by eight (three lsr instructions). That gives it which byte in the "alive state" RAM to check. It does a modulus eight (and #7), which gives it which bit within that byte corresponds to it.
Code:
lda destroyNumber,x;X is the enemy's index
lsr a
lsr a
lsr a;Divide it by 8
sta temp

lda destroyNumber,x
and #7;Anding by  (power of 2-1) is like modulus by the power of 2 number.
tay
lda bytetable,y;This gives us which bit corresponds to our destroy number from within the alive state RAM
sta temp2

ldy temp;This lets us load the byte our bit is in in the alive state RAM
lda alivestate,y
and temp2;This will be non zero if we are alive, and zero if we are not alive.
beq destroyobject;If we're not alive, don't run or initialize the object. The player will never see it.
eor alivestate,y;This effectively "kills" us, by flipping the bit that says we're alive
sta alivestate,y;And storing it
;This prevents the same object from being created twice while one is still on screen.
;If the player kills the enemy/opens the chest/whatever, you destroy the object, but don't set the bit to one again.
;If the object simply scrolls of screen, set the bit again before you destroy it.
jmp endobjectinitialization
bytetable:
.db %10000000, %01000000, %00100000, %00010000, %00001000, %00000100, %00000010, %00000001

(That code may not be 100% right... I'll check it a bit later, and fix if so.) Edit: It's probably cool now.

With 256 destructible objects, you need only need 32 bytes as has been stated before. Even for things that you might want only as part of the background, you can still create invisible objects for them that update the screen conditionally.

You might also find this post interesting: viewtopic.php?f=2&t=17355&p=218452&hilit=script#p218452

Edit: That post covers a way you might store the bits on a screen to screen basis. But basically, it's that on screen load, you copy that screen's alive state RAM to a temporary 32 bytes from a larger block of it, then copy any changes back on level unload. (Each screen knows where it's alive state RAM starts within the larger buffer, because the offset is stored as part of the screen data.) So you have "only" 256 bits per screen/level, but your buffer can basically be as large as your total RAM.
Re: Backtracking
by on (#222508)
Slightly inspired by metroid* (even though it applies this to a whole world), you could separate object data (always in ROM) from ”has been manipulated bits” (naturally in ram). The list details everything else we need to know.

4 bytes per object. TypeID, WhichScreen, Ypos, Xpos. Which objectID is implied by its place in the array. Lets say we use a page of ROM per stage, so 64 items per what you define as a stage could either be the whole level or a section.



or if you’re fine with lowered position granularity (which makes sense if all these objects are represented on the BG layer), you can bake X and Y into a single byte, and if you only have max 16 types and max 16 screens per stage, you can bitpack those as well. So, either 85 or 128 mauipulable background objects in that case. The one with the 85 is a bit of a problem since you can’t easily index into the right position as quick as possible with a simple power of two.

Then you have the list of toggle bits for your object. They’re bitpacked, so you need 8, 11, or 16 bytes of RAM to be overwritten next level. Assuming you only need one toggle state per object.

Maybe you can imply which are on which screen of the stage by their order in the array. Con: locks you to an evenly distributed number of manipulable objects per screens’ worth of data, rather than placing all of them freely. Pro: actually ought to make the code more straightforward. (If we’re looking up an object on screen n, use index (n*object size*objectsperscreen)+whichobject And you’d get even more objects or additional data (special properties?) per object; your choice.

Lastly, you could lower the X and Y granularity not to bitpack them both, but to imply which screen in a nybble, and which coarse position in the other (another bitpacking scheme).



That’s all the techniques i can think of on top of my head.

*note that metroid is only using this for obtainable items; not breakable blocks... which are overwritten by the scroll seam. The amnesia It works in metroid because it an alien planet that is kind of living. They even regenerate blocks with a timer which provides a rationale for blocks being reset when you backtrack.