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

Tokumaru's PC saving trick

Tokumaru's PC saving trick
by on (#146265)
A couple of times, Tokumaru has mentioned a trick he uses for doing object routines, where after a game object is finished with one move, it can save the program counter, and continue where it left off.

It sounds pretty useful, but I don't know exactly how to make use of it. Can you give an example of how a character like Mario would work using this trick. I'm guessing you wouldn't be able to do directional jumps by walking and jumping at the same time, like I typically do.
Re: Tokumaru's PC saving trick
by on (#146287)
I would probably use this for changing states: don't save the PC and the object will do the same thing it did last frame, jump somewhere new and save the PC and the object will do something new.

It's particularly useful for scripted state changes, like an object that does certain things in a certain order, because you can code the whole behavior as a series of loops without having to officially create new states, with names and entries in a table of states.

It basically makes state management easier, which is done implicitly rather than explicitly.

EDIT: I can't think of a good example for Mario, or any other character directly controlled by the player, since their states are mostly controlled by player input, but let's consider a simple enemy that just patrols an area, walking left and right and stopping for a few frames after bumping on walls before turning around. This enemy's A.I. could go something like this:

Code:
WalkRight:
   ;-save the PC (will resume from the next command);
   ;-increment X coordinate;
   ;-call physics subroutine;
   ;-if no wall was hit, RTS;

WaitRight:
   ;-set delay to 30 (half a second);
   ;-save the PC (will resume from the next command);
   ;-decrement delay;
   ;-if delay is not 0, RTS;

WalkLeft:
   ;-save the PC (will resume from the next command);
   ;-decrement X coordinate;
   ;-call physics subroutine;
   ;-if no wall was hit, RTS;

WaitLeft:
   ;-set delay to 30 (half a second);
   ;-save the PC (will resume from the next command);
   ;-decrement delay;
   ;-if delay is not 0, RTS;
   JMP WalkRight

This example is a bit silly, because this is a very dumb enemy and I completely ignored collisions with the player, which obviously have to be taken care of (I would probably use subroutines for this, since this would happen in all states), but you get the picture. You get to program sequences of behaviors that seamlessly spill into the next, without having to bother creating formal states or a system for jumping between them with pointer tables and the like. If you want to switch states just jump to (or naturally flow into) it, that the new state will initialize itself (e.g. setting the delay) and mark the point at which it repeats (by saving the PC).
Re: Tokumaru's PC saving trick
by on (#146289)
Sounds a lot like coroutines. (http://en.wikipedia.org/wiki/Coroutine)

And I agree that this concept can be very useful. State machines that implement an equivalent behavior can get very wild otherwise.
Re: Tokumaru's PC saving trick
by on (#146292)
thefox wrote:
Sounds a lot like coroutines. (http://en.wikipedia.org/wiki/Coroutine)

Indeed!

Quote:
State machines that implement an equivalent behavior can get very wild otherwise.

Yes, the whole point is to avoid a traditional state machine, and code everything as sequentially as possible.

psycopathicteen, now I understand what you said about Mario... Just because "jumping" and "running" are different states you're saying that he wouldn't be able to do both at the same time, right? Well, that will depend on how you code your states. For me, the difference between "running" and "jumping" is whether the object has to stick to the ground or not, whether vertical physics is applied or not, how much influence player input has over the horizontal speed, but in both cases the horizontal physics will keep working. So yes, if you code the states properly, objects can do more than one thing in the same state.
Re: Tokumaru's PC saving trick
by on (#146444)
What's the benefeit for doing it this instead of just storing an immediate label? Is it to avoid making 2 8-bit writes to memory?
Re: Tokumaru's PC saving trick
by on (#146450)
psycopathicteen wrote:
What's the benefeit for doing it this instead of just storing an immediate label? Is it to avoid making 2 8-bit writes to memory?

Implicit state management. You don't have to do any of these, for example:

Code:
StatePointers:
   .dw WalkingRight
   .dw WaitingRight
   .dw WalkingLeft
   .dw WaitingLeft


Code:
   lda #$02
   sta ObjectState, x


Code:
   lda ObjectState, x
   asl
   tay
   lda StatePointers+0, y
   sta Temp+0
   lda StatePointers+1, y
   sta Temp+1
   jmp (Temp)

Might not look like much, but once you have dozens of objects, each with their own set of possible states, things start getting harder to manage as you add/move/remove states. You have to think of a way to index the pointers by object AND by state, you have to change the codes for the states as you add/remove them (or create constants for all of them), things like that.

Besides getting rid of these annoyances, you get the ellegant "roll onto the next state" effect for the more linear behaviors, which is almost like a script system. You could make cutscenes with "scripted" actions like walking around, making gestures and talking without having to create full-fledged states for each little action that would be used only once but would still clutter the list of state pointers.
Re: Tokumaru's PC saving trick
by on (#146456)
So it's more useful for the 6502, than it is for the 65816? On the 65816, I can do "lda #special_move, sta AI_routine."
Re: Tokumaru's PC saving trick
by on (#146479)
psycopathicteen wrote:
So it's more useful for the 6502, than it is for the 65816?

I don't know much about the 65816, but yeah, I imagine that being able to manipulate 16-bit pointers directly makes the whole process less clumsy, but I don't think that steals all the merit from the PC saving method.

I'm out of arguments to defend this technique though, so If you still don't see any advantage this method has over others, that's fine, I never claimed it was superior to other methods, just that I'm comfortable using it (it isn't even MY trick, like the thread title might suggest). :?

I'm not sure I got the point of this thread though... did you really want to know more about the technique or did you just want to point out a flaw you thought you detected (since in the very first post you guessed it wouldn't work for certain behaviors)? Then in your other posts you basically just dissed all the advantages I pointed out. Twice already I pointed out the script-like behavior that this technique allows, which would certainly be helpful on the SNES as well, but both times you only focused on 8-bit vs. 16-bit data transfers, which have nothing to do with actual algorithms, they're just small implementation details.
Re: Tokumaru's PC saving trick
by on (#146482)
No, I didn't make this thread to point out flaws, or criticize it. I just wanted to know more information about it, because I'm looking for ways on making my code more manageable, and I thought it was a neat idea.

I'll reread your posts to see if I missed anything important. I'm not really that familiar with scripts. I probably misunderstood what you said.
Re: Tokumaru's PC saving trick
by on (#146483)
Is it anything like continuation-passing style?
Re: Tokumaru's PC saving trick
by on (#146485)
I've used a similar way of handling state in the past. This was in C++, so saving and resuming the PC wasn't really an option, but it has a similar way of treating the state as a pointer to code.

Code:
struct Object
{
   int x,y,etc; // common object state data, position, velocity, etc.
   int tick_time; // if 0 do tick this frame, otherwise decrement once per frame
   void (*tick)(Object*); // function pointer to be called when tick_time is 0
   void (*damage)(Object*); // function pointer to be called when object is damaged
   void (*draw)(Object*); // function pointer for drawing object
};

// bee object

void bee_init(Object* o)
{
   o->tick = bee_tick_wait;
   o->damage = bee_damage;
   o->draw = bee_draw_normal;
   o->tick_time = 0;
}

void bee_damage(Object* o)
{
   --o->hp;
   if (o->hp <= 0)
   {
      // change state to animate death
      o->tick = bee_tick_die;
      o->draw = bee_draw_die;
      o->tick_time = 0;
      return;
   }
   else
   {
      // change visual state to indicate damage
      o->draw = bee_draw_damaged;
   }
}

void bee_tick_wait(Object* o)
{
   if (player_near(o))
   {
      // change to attack state
      o->tick = bee_tick_attack;
      o->tick_time = 0;
      return;
   }
   else
   {
      // check again in 30 frames
      o->tick_time = 30;
   }
}

void bee_tick_attack(Object* o)
{
   move_toward_player(o);
   if (player_touching(o))
   {
      // attack successful, go back to wait state
      damage_player();
      o->tick = bee_tick_wait;
      o->tick_time = 60; // don't update for 60 frames
      return;
   }
   o->tick_time = 0; // update every frame
}


I think it's not that different, conceptually, from what tokumaru is doing. Basically he would have the ability to put a YIELD macro or something similar in the middle of a function to defer execution for a frame, whereas I would have to break it into multiple functions, more or less, but the basic idea is the same: when you're done for the frame, store a pointer to the next code you want to run on this object.
Re: Tokumaru's PC saving trick
by on (#146486)
Okay I understand it better now. If your doing a cutscene, you don't need to explicitly make a routine for every little thing your character does.
Re: Tokumaru's PC saving trick
by on (#146487)
psycopathicteen wrote:
I'm not really that familiar with scripts. I probably misunderstood what you said.

Since Gunstar Heroes is being discussed in that other thread, and I just checked it out to comment on that thread, let me use it as an example. At the very beginning, there's an intro sequence, where the characters run, look up, talk, point at things... that's essentially a scripted animation. How would you code that in your game? Have you though of a way yet?

There are many ways you can do it, but one I can think of that wouldn't be a pain in the ass would be to write all the actions of each object in sequence, and advance (roll over) to the next state based on whatever is more convenient (end of action, other object's actions, frame count, etc.). This allows you to use the same objects you use in-game (with all their animations, physics, actions) for these animations, all you have to do is code the whole script as if it were a state and force that state when the cutscene starts.

The alternative would probably be coding an actual scripting engine (which is really not worth it unless you're coding a game that heavily relies on scripts, such an RPG), faking all the action with animations, tediously recreating it frame by frame.

This is sort of a "bonus" that comes with the technique though. The main point is still to simplify the state management. If you ask me, simply not having to name every little intermediary action is already a hell of an advantage!

tepples wrote:
Is it anything like continuation-passing style?

I'm sleepy and I didn't understand a word of that article! :lol:

rainwarrior wrote:
This was in C++

I always wondered how this would work in a high-level language. Interesting solution!

Quote:
Basically he would have the ability to put a YIELD macro or something similar in the middle of a function to defer execution for a frame

Or simply RTS if I wanted the object to keep doing what it's currently doing.
Re: Tokumaru's PC saving trick
by on (#146489)
tokumaru wrote:
tepples wrote:
Is it anything like continuation-passing style?

I'm sleepy and I didn't understand a word of that article! :lol:

That's because it's poorly written.

The idea is the current "state" of a function is both an argument and its return value. Returning from the function is like a "yield" or a "sleep", expecting it to be called again later with the state it returned, allowing it to resume.

It mostly comes up in functional programming languages, because they often lack access to a global context outside the function, so it's like doing multithreading "by hand", passing the current context as an argument and return value.
Re: Tokumaru's PC saving trick
by on (#146497)
Quote:
it isn't even MY trick, like the thread title might suggest

I also use a PC saving trick, and I don't know how I got the idea, but I remember I was using traditional state machines originally. Not only it is annoying and a bit counterintuitive to program, but also it wastes a lot of ROM to have all this state dispatching and state saving instructions that you don't need anymore with a clever manipulation of the stack.

I also be sure to call object code directly from the main program when the stack is $ff. That way, for boss enemies, since they are more complicated they often need sub-states, so they can leave whathever they want on the stack and it'll still work. It just "offset" the stack of the remaining of the game by a couple of bytes. Whenever the game loop exists I make sure to set the stack pointer to $ff again, to avoid it become permanent (for example if the player dies during a boss battle, the boss will not terminate and leave bytes on the stack). This only work for one boss at a time of course, but I am pretty sure it's not a huge limitation.
Re: Tokumaru's PC saving trick
by on (#146780)
This is an awesome idea, I don't think coroutines completely clicked for me until I read this thread. Thanks guys. How do you save the PC? The only way I could think to do it using ca65 would be something like (I did not think about or account for details such as the order of bytes, or how I will need to modify the PC to ensure that it re-enters the object routine at the correct location)

Code:

   ;likely incorrect pseudo code to ask whether I'm on the right track
   jsr :+
:  pla
   sta my_pc_variable_in_zp
   pla
   sta my_pc_variable_in_zp+1



Is there a better way? In any case, I'm definitely going to try this technique on my next project.
Re: Tokumaru's PC saving trick
by on (#146781)
You'd jsr sched_yield, and then sched_yield would pull and save the return address, go to the next object, load and push the next object's return address, and rts to that.
Re: Tokumaru's PC saving trick
by on (#146782)
Cool...makes sense. thanks!
Re: Tokumaru's PC saving trick
by on (#146783)
If you don't need to access the stack during your object evaluation (though you could switch to the regular stack):

Code:
ObjStatePtr1 = $0100
ObjStatePtr2 = $0102
ObjStatePtr3 = $0104
ObjDone      = $0106

.proc Init

    ; init pointers pseudo code: (I'm not writing the Asm for this)

    ; set ObjStatePtr1 = Object1_StartAddress
    ; set ObjStatePtr2 = Object2_StartAddress
    ; set ObjStatePtr3 = Object3_StartAddress
    ; set ObjDone       = ExitObj

.endproc

.proc StartObj
   
    ; set S to zero
    tsx
    stx saveS
    ldx #$00
    txs
    ; jump to first object state
    rts

.endproc

.proc ExitObj
   
    ; restore S
    ldx saveS
    txs
    rts

.endproc

.proc NextObj
    pla
    pla
    rts
.endproc

.proc Object1_StartAddress

    ; do some stuff
    ; and more stuff
   
    ; then mark this as the start point for next time:
    jsr NextObj

.endproc

; ..etc



Might have some mistakes, but I think that is correct.
Re: Tokumaru's PC saving trick
by on (#146784)
tepples wrote:
You'd jsr sched_yield, and then sched_yield would pull and save the return address, go to the next object, load and push the next object's return address, and rts to that.
Aha, now I understand. The "PC saving trick" is actually a scheduler, like you'd see in any (good) multitasking operating system. The only difference is that the game scheduler will probably be simpler than the operating system scheduler.

An operating system scheduler will use time slices, and preempt a task that runs for its entire time slice to prevent a single task from running forever. A game scheduler can rely on tasks yielding, effectively giving them infinite time slices.

An operating system scheduler will attempt to run all tasks fairly, possibly with priority levels so higher priority tasks will run more often. A game scheduler can rely on tasks only needing to run once per vblank, so it can run them one after another and then idle until the next vblank.

Hmm, maybe I should get back into operating system development...
Re: Tokumaru's PC saving trick
by on (#146785)
In general, it's called "cooperative multitasking". The Windows 3.1 scheduler and the "MultiFinder"/"Process Manager" scheduler of Mac OS 6 through 9 used it.

In theory, you could do preemptive multitasking with time slices using a programmable interval timer, such as the CPU cycle counter of FME-7 or the scanline counter of MMC3. In practice, there's probably not enough RAM to make preemptive worthwhile on an NES. But on a Super NES it's possible; it has as much RAM as the first Macintosh and a movable direct page and stack.
Re: Tokumaru's PC saving trick
by on (#146793)
tepples wrote:
In general, it's called "cooperative multitasking". The Windows 3.1 scheduler and the "MultiFinder"/"Process Manager" scheduler of Mac OS 6 through 9 used it.
That would be why I'm not familiar with it; DOS-like operating systems aren't really my area of expertise. (Actually, calling Windows 3.1 "DOS-like" might be unfair; it runs in protected mode, which implies some level of process isolation like a "modern" operating system.)
tepples wrote:
But on a Super NES it's possible; it has as much RAM as the first Macintosh and a movable direct page and stack.
For a real operating system, you also have to worry about relocating code. The 6502 series don't really lend themselves to that sort of thing. The Macintosh's 68k has PC-relative addressing, which solves a lot of relocation-related problems.
Re: Tokumaru's PC saving trick
by on (#146796)
Joe wrote:
Actually, calling Windows 3.1 "DOS-like" might be unfair; it runs in protected mode, which implies some level of process isolation like a "modern" operating system.

Windows 3.1 had memory protection ("General Protection Fault") but not preemption. Windows 95 had both. (BSODs in the 9x series were caused by defective VxD drivers, which had privileges to override memory protection.) Mac OS 6-9 had neither; FreeBSD-based OS X has both.

Quote:
For a real operating system, you also have to worry about relocating code. The 6502 series don't really lend themselves to that sort of thing. The Macintosh's 68k has PC-relative addressing, which solves a lot of relocation-related problems.

The 65816 has BRL (add 16-bit value to PC) and PER (push PC + 16-bit value) to support position-independent code. GS/OS (Apple's successful attempt to replicate the functionality of Mac OS on the Apple IIGS) would relocate an executable at load time by adding its base address to the list of fixups in the OMF header, in much the same way that MS-DOS loads MZ-format executables.
Re: Tokumaru's PC saving trick
by on (#146804)
You don't really need relocatable code, you can solve it by paging RAM into a virtual address space, so each program can just operate as if it owns its space. The operating system swaps in a new page table as part of the context switch. The code itself doesn't need to be "relocatable" in any special way.

You could actually implement this with PRG banking on the NES, if you really wanted to. Each program would run from the context of its own bank.

On a unpaged system where code typically runs from RAM, sure, relocatable code would let you run an arbitrary set of programs with relatively fast context switching, but you could implement a much slower paging by just shuffling the data around manually. (Depends how fast you need to switch.) If the set of programs isn't arbitrary, you could just compile them all at their own locations, why limit yourself to relocatable code?

(You can do it, of course, I'm just saying there's other ways that might be better. Hard to suggest which when it's only hypothetical anyway.)
Re: Tokumaru's PC saving trick
by on (#146824)
Quote:
Windows 3.1 had memory protection ("General Protection Fault") but not preemption.

Does this means that if you make a program that has an infinite loop at some point by error in Windows 3.1, your entire system crashed? Sounds like it should have been a painful experience.
Re: Tokumaru's PC saving trick
by on (#146828)
We used to reboot our computers a lot more often.

Also, I don't remember multi-tasking at all back then like I do now. I never had WWW internet before Windows 95, and I was used to just doing one thing at a time on the computer, mostly. Very different than now. Even using a modem to connect to BBSes, I would basically do just that until I was finished with the call.
Re: Tokumaru's PC saving trick
by on (#146842)
Bregalad wrote:
Quote:
Windows 3.1 had memory protection ("General Protection Fault") but not preemption.

Does this means that if you make a program that has an infinite loop at some point by error in Windows 3.1, your entire system crashed? Sounds like it should have been a painful experience.

You had to press Ctrl+Alt+Del to send an interrupt that forces an unresponsive process to quit. Because that could cause kernel data structures to become inconsistent, it was advised to reboot soon afterward.

Later versions of classic Mac OS introduced Cmd+Option+Esc, but that worked only if the application was calling certain syscalls. Otherwise, you needed to use the MacsBug button on the back of the machine. Power users memorized this:
Code:
SM 0 A9F4
G 0

This poked a short program into $000000 and ran it:
Code:
.org $000000
  SYSCALL $9F4

The 68000 reserves opcodes $A000-$AFFF for syscalls, much like BRK on 65816, and $F000-$FFFF for coprocessor emulation, much like COP on 65816. On classic Mac OS, syscall $9F4 is ExitToShell. It often (but not always) worked well enough to get back to Finder, save the rest of your work in other applications, and restart the computer cleanly.