It is currently Wed Oct 17, 2018 8:34 pm

All times are UTC - 7 hours





Post new topic Reply to topic  [ 18 posts ]  Go to page 1, 2  Next
Author Message
 Post subject: Backtracking
PostPosted: Tue Jul 31, 2018 5:45 pm 
Offline

Joined: Sun Jun 25, 2017 3:32 pm
Posts: 18
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?


Top
 Profile  
 
 Post subject: Re: Backtracking
PostPosted: Tue Jul 31, 2018 5:47 pm 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 6887
Location: Canada
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.


Top
 Profile  
 
 Post subject: Re: Backtracking
PostPosted: Tue Jul 31, 2018 6:10 pm 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20662
Location: NE Indiana, USA (NTSC)
The word "destructibility" has been used for this problem in the past. Search for it if you're interested.


Top
 Profile  
 
 Post subject: Re: Backtracking
PostPosted: Tue Jul 31, 2018 6:12 pm 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10897
Location: Rio de Janeiro - Brazil
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.


Top
 Profile  
 
 Post subject: Re: Backtracking
PostPosted: Tue Jul 31, 2018 6:25 pm 
Offline

Joined: Sun Jun 25, 2017 3:32 pm
Posts: 18
(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.


Top
 Profile  
 
 Post subject: Re: Backtracking
PostPosted: Tue Jul 31, 2018 6:46 pm 
Offline
User avatar

Joined: Sun Sep 19, 2004 9:28 pm
Posts: 3634
Location: Mountain View, CA
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. :-)


Top
 Profile  
 
 Post subject: Re: Backtracking
PostPosted: Tue Jul 31, 2018 7:04 pm 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10897
Location: Rio de Janeiro - Brazil
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.


Top
 Profile  
 
 Post subject: Re: Backtracking
PostPosted: Tue Jul 31, 2018 8:16 pm 
Offline

Joined: Sun Jun 25, 2017 3:32 pm
Posts: 18
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.


Top
 Profile  
 
 Post subject: Re: Backtracking
PostPosted: Tue Jul 31, 2018 9:45 pm 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 6887
Location: Canada
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.


Top
 Profile  
 
 Post subject: Re: Backtracking
PostPosted: Tue Jul 31, 2018 10:26 pm 
Offline
User avatar

Joined: Tue Jun 24, 2008 8:38 pm
Posts: 2004
Location: Fukuoka, Japan
@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.


Top
 Profile  
 
 Post subject: Re: Backtracking
PostPosted: Tue Jul 31, 2018 10:58 pm 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 6887
Location: Canada
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.)


Top
 Profile  
 
 Post subject: Re: Backtracking
PostPosted: Wed Aug 01, 2018 12:07 am 
Offline
User avatar

Joined: Sun Sep 19, 2004 9:28 pm
Posts: 3634
Location: Mountain View, CA
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.).


Top
 Profile  
 
 Post subject: Re: Backtracking
PostPosted: Wed Aug 01, 2018 12:13 am 
Offline
User avatar

Joined: Thu Sep 15, 2016 6:29 am
Posts: 773
Location: Denmark (PAL)
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.


Top
 Profile  
 
 Post subject: Re: Backtracking
PostPosted: Wed Aug 01, 2018 1:43 am 
Offline

Joined: Sun Jun 25, 2017 3:32 pm
Posts: 18
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.


Top
 Profile  
 
 Post subject: Re: Backtracking
PostPosted: Wed Aug 01, 2018 5:59 am 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20662
Location: NE Indiana, USA (NTSC)
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.?


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 18 posts ]  Go to page 1, 2  Next

All times are UTC - 7 hours


Who is online

Users browsing this forum: Ksubi and 5 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group