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

Sprite movement: All possible combinations

Sprite movement: All possible combinations
by on (#156195)
Today, I started implementing the movement of the player character.

In the moment, she can walk and jump. You can control the height of the jump and you can move forward during jumping and falling, but not backwards. (So, it's a mix between the no-control-jump from "Castlevania" and the 100%-control-jump from "Contra".)

This is my corresponding code so far:
Code:
enum { StandingH, Moving };
enum { StandingV, Jumping, Falling };

struct SpriteAttributes
{
      byte X;
      byte Y;
      bool RightToLeft;
      byte StatusHorizontal;
      byte StatusVertical;
      byte JumpCounter;
};

struct SpriteAttributes PlayerAttr;

void ProcessMovement(void)
{
   switch (PlayerAttr.StatusVertical)
   {
   case StandingV:
      if (Button(ButtonA))
      {
         PlayerAttr.StatusVertical = Jumping;
         PlayerAttr.JumpCounter = 0;
      }
      break;

   case Jumping:
      if (PlayerAttr.JumpCounter < 54 && Button(ButtonA))
      {
         ++PlayerAttr.JumpCounter;
         --PlayerAttr.Y;
      }
      else
         PlayerAttr.StatusVertical = Falling;
      break;

   case Falling:
      if (PlayerAttr.Y < TopPlatformPixels)
         ++PlayerAttr.Y;
      else
         PlayerAttr.StatusVertical = StandingV;
      break;
   }

   if (Button(ButtonRight))
   {
      if (PlayerAttr.StatusVertical == StandingV)
      {
         PlayerAttr.RightToLeft = false;
         ++PlayerAttr;
      }
      else if (!PlayerAttr.RightToLeft)
         ++PlayerAttr;

      PlayerAttr.StatusHorizontal = Moving;
   }
   else if (Button(ButtonLeft))
   {
      if (PlayerAttr.StatusVertical == StandingV)
      {
         PlayerAttr.RightToLeft = true;
         --PlayerAttr;
      }
      else if (PlayerAttr.RightToLeft)
         --PlayerAttr;

      PlayerAttr.StatusHorizontal = Moving;
   }
   else
      PlayerAttr.StatusHorizontal = StandingH;
}


Now, there are a good bunch of combinations. And that's not all. I will need attacking on the ground, attacking in the air, being stunned after being hit.
And then there's the whole interaction with the background, like falling down when you walk over a platform or when you don't land on one after jumping.
And of course the opponents have a similar movement set that are not controlled by controller input, but by the environment. For example, turn around when you reach the end of a platform.

So, my question is: Is there a specific technique to summarize these actions and what you can and can't do in each situation? Hardcoding everything could get a bit complicated.
Re: Sprite movement: All possible combinations
by on (#156199)
For a character controller, this is not very complicated yet. ;)

I think you're doing the correct thing by having separate "vertical" and "horizontal" states. If your character controller update is broken up into distinct steps, you can have separate, simpler states that modify each step independently, rather than trying to come up with a unique state and code path for every possible combination.

In this case, my approach probably would have just had two vertical states, standing and not, and "JumpCounter" would just be a modifier to the not-standing state. Like, the "Jumping" state seems redundant to the value of "JumpCounter", so it might be best to only use "JumpCounter" so that I can't accidentally set one without the other. I'd also separate the actual motion of the player from decisions about the direction of motion, so that collision resolution becomes a separate step that doesn't need to care about other states.

e.g.
Code:
// determine standing state

if (player_touching_ground())
{
   standing = true;
}
else
{
   standing = false;
}

// adjust vertical motion state

if (standing)
{
   if (jump_button)
   {
      jump_counter = 54;
      vertical_move = -1;
   }
   else
   {
      jump_counter = 0;
      vertical_move = 0;
   }
}
else
{
   if (jump_counter)
   {
      --jump_counter;
      vertical_move = -1;
   }
   else
   {
      vertical_move = +1;
   }
}

// move player vertically

new_y = player.y + vertical_move;
if (vertical_move < 0 && collide_up(player.x, new_y))
{
   jump_counter = 0;
}
else if (vertical_move > 0 && collide_down(player.x, new_y))
{
   jump_counter = 0;
}
else
{
   player.y = new_y;
}
Re: Sprite movement: All possible combinations
by on (#156232)
rainwarrior wrote:
For a character controller, this is not very complicated yet. ;)

Yeah, it's just the beginning. Also, the whole stuff is supposed to work for the opponents as well.

Thanks for the hints so far.

I guess, I'll first have to find out which things can be done simultaneously:

Walking/Standing horizontally is one status.
Being in the air/Being on the ground is another status.
Attacking is yet another status.
Being stunned after a hit is another status.
Having mercy invincibility is another status.

These things can happen simultaneously, with some restrictions of course: You cannot attack when you're stunned. But you can get stunned when you're attacking. Those two things are not mutually exclusive in the same way standing and walking are.


Then I guess I'll separate between the intended action and the actual status of the sprite. Like in:
Code:
if (action == Jump)
    status = Jumping;

This way I can pass the intended actions as parameters. And the function can then calculate whether the action can be tranformed into a status.

For example, when the function is called with the jump action, but the current status of the character isn't "standing", then the status won't change to "jumping".

Separating action from status also enables me to use the same function for player and enemy characters. Since I can have another function that transforms button inputs into actions for the player. And yet another function decides the action based on the current status for the opponents. And the main movement function then again creates the new status based on the intended action.

Player: Controller input --> Intended action --> Status update
Enemy: Status check --> Intended action --> Status update


But to summarize it: I really do have to write this from top to bottom, thinking of the various possible actions and then converting them to the corresponding status based on the current status and individually including it into my code, right?
There is no really clever idea (or "design pattern") to program this in an efficient way? Something like lookup tables that decide which thing can result in which thing or whatever smart people might have come up with? I'm really stuck to having to be creative myself and include my own movement algorithm? There's no general purpose algorith that always works in these situations?
Re: Sprite movement: All possible combinations
by on (#156257)
I have never seen a "generic" character controller. It's kind of a core component of most games, and it's got very customized needs in every game.

It is not uncommon to do what you're doing, w.r.t. having a character update that takes an input parameter for control, so that the same character controller can be used for many characters, including the player controlled one.

In a lot of modern games I've seen OOP used to create families of character controllers with common shared stuff in the base classes. You can actually do OOP style programming in assembly, usually with function pointers or tables that let characters share code. (The arcade game Joust appears to take an approach like this.)

Function pointers can be used to encapsulate states too, e.g. when you change states, you just reassign the "update" function pointer to the update function for the new state. I'm not sure I'd take this approach in an NES game, but I've done all of these things (and others) in various projects.


Tokumaru took an unusual approach that implemented a "yield" where each object has its own thread, and passes control back to the manager that jumps between threads to update all the objects. A little unorthodox on the NES, I think, but it could work well if you're comfortable with it: http://forums.nesdev.com/viewtopic.php?f=2&t=12728

In that approach, each character is running code in its own self-contained set of update loops, and changing states for a character is just a JMP to a different update loop.
Re: Sprite movement: All possible combinations
by on (#156260)
Implementing Yield in by saving/restoring the program counter isn't weird, even Shantae does that.
Re: Sprite movement: All possible combinations
by on (#156264)
I didn't say it was weird, but I don't believe it is very commonly used.
Re: Sprite movement: All possible combinations
by on (#156370)
rainwarrior wrote:
In a lot of modern games I've seen OOP used to create families of character controllers with common shared stuff in the base classes. You can actually do OOP style programming in assembly, usually with function pointers or tables that let characters share code.

In a PC game, I probably would have used object oriented programming, using C++. But for the NES, I try to keep it simple with as few code as possible.

So, I'll probably do a function that has the movements for everything. I.e. in theory every character can walk, jump, attack, be hit shortly, be permanently stunned and hover over the screen. Only that the input function will call this function with only the appropriate parameters, i.e. the movement of opponent A will never pass the parameter for jumping or hovering etc. and the player character will never be updated with the parameter "hovering = true".

Since we already established that pointer operations are pretty slow when you use C and since I use C for a reason (so that I don't have to implement the game logic in Assembly), I will probably not use pointers for data or functions.
Instead, I'll declare a global array of a struct. The struct will have all properties of a character (x, y, statuses etc.). And the array is big enough for the maximum number of characters on screen. And the movement function will simply use the array index to determine which character's values will be updated. I.e. the update function works with a known array and only has to calculate the offset/index instead of using a pointer to find the memory location where the data are stored.
Re: Sprite movement: All possible combinations
by on (#156373)
DRW wrote:
Instead, I'll declare a global array of a struct. The struct will have all properties of a character (x, y, statuses etc.). And the array is big enough for the maximum number of characters on screen. And the movement function will simply use the array index to determine which character's values will be updated. I.e. the update function works with a known array and only has to calculate the offset/index instead of using a pointer to find the memory location where the data are stored.

That would work well as long as you only need sequential lookup. If you want random lookup you would need to multiply the index with the size of the struct to get the character struct's offset. And as you may know the nes doesn't have a multiply operation. So for random access it would be better to create a big array for each property

so instead of:
Code:
struct foo_t {
    uint8_t a;
    uint8_t b;
};
struct foo_t foo[32];

foo[index].a = ...

you could do:
Code:
uint8_t foo_a[32];
uint8_t foo_a[32];

foo_a[index] = ...
Re: Sprite movement: All possible combinations
by on (#156374)
O.k., that makes sense: Getting the memory location of structValue[index] requires the program to calculate the address as &structValue + index * sizeof(structValue) while arrayValue[index] only requires an addition: &arrayValue + index.

I assume an array of integers is not a problem either, even though an integer has two bytes, right? Because the calculation still doesn't require a multiplication, but can be done with a shift: &intArrayValue + (index << 1)

I'm asking because my x position of a character will be an int instead of a byte/unsigned char since enemy characters shall be able to be outside the screen without being instantly forgotten. Otherwise you get the "Ninja Gaiden" phenomenon where one enemy leaves the screen and the next (the same) enemy appears immediately.

Oh and by the way: I doubt that I'll have 32 characters on-screen, so your example arrays are a bit big. :wink:
(I use the zero sprite for parallax scrolling and nine sprites and the sprite overflow for the status bar split. So, I'm left with 54 sprites for gameplay. Each regular character has 10 sprites (yes, bigger than the standard 16 x 32 characters from most games). Which means I can have 5 characters plus a small enemy like a flying object plus some additional sprite when the main character attacks and therefore stretches her arm.)
Re: Sprite movement: All possible combinations
by on (#156375)
A third variation, known as "structure of arrays" as opposed to "array of structs":
Code:
struct foo_t {
    uint8_t a[32];
    uint8_t b[32];
};
struct foo_t foo;

Basically the same advantage as the striped array version, but you get to use the struct . in your syntax instead of underscore.

DRW wrote:
Since we already established that pointer operations are pretty slow when you use C

You were doing pointers + as function parameter + with indexing + 100 times in a row. Just fetching and calling a single function pointer isn't nearly so bad. (Not saying you need it for this, just saying you don't need to avoid pointers entirely; naive array copying was kind of a worst case example.)
Re: Sprite movement: All possible combinations
by on (#156377)
rainwarrior wrote:
A third variation, known as "structure of arrays" as opposed to "array of structs"

Sure, but that's just a syntactical difference.

rainwarrior wrote:
You were doing pointers + as function parameter + with indexing + 100 times in a row. Just fetching and calling a single function pointer isn't nearly so bad.

Maybe not, but using the global arrays would still be faster. And this is not an office program where you need a dynamic list where you insert and delete items. The maximum number of characters that are on-screen simulatenously is fixed anyway. So the global array/arrays are the better alternative either way.
Re: Sprite movement: All possible combinations
by on (#156378)
DRW wrote:
I assume an array of integers is not a problem either, even though an integer has two bytes, right? Because the calculation still doesn't require a multiplication, but can be done with a shift: &intArrayValue + (index << 1)

In theory, yes, but the shift is the least of your problems. Any use of 16 bit variables generally requires ~10x as much work as corresponding 8 bit stuff.

In practice, this is what CC65's generated code seems to be, with the -O flag:
Code:
// C
intArrayValue[index] = value;

// generated assembly:
   ldx     #$00
   lda     _index
   asl     a
   bcc     L004D
   inx
   clc
L004D:
   adc     #<(_intArrayValue)
   sta     ptr1
   txa
   adc     #>(_intArrayValue)
   sta     ptr1+1
   ldx     #>_value
   lda     #<_value
   ldy     #$00
   sta     (ptr1),y
   iny
   txa
   sta     (ptr1),y

Note that an asl by itself is not sufficient, since "index" could be greater than 127; so the underlying index has to be 16 bit rather than 8 bit, and that can't be optimized out.

Without -O it is a bit more cumbersome, with use of the C-stack, etc.
Re: Sprite movement: All possible combinations
by on (#156379)
Wow. So, should I rather have two byte variables for the x position?
Re: Sprite movement: All possible combinations
by on (#156384)
Well, separating it into to 8 bit variables would mean a bunch of extra logic too, right? Probably just as bad. Personally, I would just use 16 bit variables until the performance problem comes up. (Then I'd think about ways of getting around it that work for the problem at hand.)

Was just trying to give a warning that 16 bit variables are a lot more performance intensive than they might seem. It's not just twice the work; it's a lot more than that (even in hand-coded assembly).

In contrast to that array copying stuff from before, I don't think the CC65 generated code in this case is bad, actually. The compiler would really need more information to make more optimization than it does. For instance, if you could guarantee that index was less than 128, it could skip the use of ptr1 and just use absolute indexing, etc. but in most cases it just can't know (unless index was an immediate value instead).
Re: Sprite movement: All possible combinations
by on (#156385)
rainwarrior wrote:
Well, separating it into to 8 bit variables would mean a bunch of extra logic too, right?

Probably yes. Basically, the characters need to be able to walk outside the screen. When a character leaves the screen on the left side, they are removed from the logic and the spot in the array can be used for another character that comes from the right.
But on the right side itself, there needs to be an offscreen buffer, so that the movements don't look too ridiculous.
I mean, imagine a character that can only walk back and forth and when he reaches the gap of a platform, he turns around.
If my game was designed so that characters only have their actual screen position, this means that when a platform is only slightly visible on the right side and a character is supposed to appear on it, he will walk on the spot and turn around every frame since he contantly reaches the left side of the platform and the right screen border. And his movements in one direction will get longer the more of the platform will be visible, but he'll always turn around when he reaches the screen border.
That doesn't look particularly realistic, so I want him to be able to walk along the plattform offscreen, so that his reappearance on the screen aligns with the time he would actually walk on the platform if it was completely on the screen.
Re: Sprite movement: All possible combinations
by on (#156386)
DRW wrote:
If my game was designed so that characters only have their actual screen position, this means that when a platform is only slightly visible on the right side and a character is supposed to appear on it, he will walk on the spot and turn around every frame since he contantly reaches the left side of the platform and the right screen border. And his movements in one direction will get longer the more of the platform will be visible, but he'll always turn around when he reaches the screen border.

Ninja Gaiden is riddled with this kind of problem. :S (I am not a fan of that game, largely because of this one issue.)
Re: Sprite movement: All possible combinations
by on (#156387)
Yes, that's the game I also mentioned some posts ago.

Maybe I should design the game in a way that the characters cannot appear until a certain portion of the platform is visible.
Or, since the game is auto-scrolling, I should maybe set the walking spped of enemies to smaller or equal than the scrolling speed, so that characters cannot reach the right border anymore once they're on the screen.
Re: Sprite movement: All possible combinations
by on (#156393)
Quote:
character is supposed to appear on it, he will walk on the spot and turn around every frame


My game suffers from the same flaw (not quite so bad), but I couldn't think of a simple way to fix it. Just adding a second byte for enemy X coordinates won't work because the level data isn't loaded more than 1 metatile past the rightmost of the screen, so at most, the enemies would only be able to scroll 16 pixels more to the right before they run into unloaded level data. I could set a timer, and have them be undrawn for a set amount of frames, but that seems like a lame solution.
Re: Sprite movement: All possible combinations
by on (#156397)
dougeff wrote:
Just adding a second byte for enemy X coordinates won't work because the level data isn't loaded more than 1 metatile past the rightmost of the screen, so at most, the enemies would only be able to scroll 16 pixels more to the right before they run into unloaded level data.


This isn't really a problem depending on how you code it. In my engine, enemies can exist anywhere in the map, no matter how many screens away. Unless you have to decode your map into RAM, it's actually not an issue.

To calculate where an enemy can be, it doesn't need access to any of the graphics from your background tiles, it just needs to access the collision data from your metatiles. If your objects have a 16-bit position, they can access the proper collision data from your map in ROM no matter how far off the screen they are.
Re: Sprite movement: All possible combinations
by on (#156401)
The levels are compressed in the ROM, decompressed into 200-3ff RAM, as a metatile map, which doubles as the collision map. But it loads it column by column, on the fly, so the data is not accessible past 1 metatile right of the screen.
Re: Sprite movement: All possible combinations
by on (#156406)
Is that just to save ROM space or is that necessary for storing whether or not a power up box has been hit?

I found it essential to have enemies able to exist anywhere on the map for the game I'm making, but I don't have any sort of destructible or modifiable tiles yet, so I wasn't sure how I was going to approach that. Off the top of my head, I was thinking about creating a space in RAM just to store the data necessary to catalog the changes only for destructible tiles, and then having a special collision type in my metatiles that tell the program to check against the destructible tiles in RAM. I hadn't really thought about it too much yet though. That's just the first idea I had.
Re: Sprite movement: All possible combinations
by on (#156410)
ROM space.

The bank that level data is in is 98% full. (With compression). Without, it would be way too long.
Re: Sprite movement: All possible combinations
by on (#156431)
Is a 2 screen wide map too big for RAM?
Re: Sprite movement: All possible combinations
by on (#156443)
No, you could probably cram 4-5 screens into the RAM
Re: Sprite movement: All possible combinations
by on (#156466)
Does your game have vertical scrolling? If it doesn't, you can fit 32 collumns in $0200-$03ff.
Re: Sprite movement: All possible combinations
by on (#157118)
I'm busy proofreading my code, and what I find funny is how many times I check if the players on ground or in the air, when I could check it once, and have just 2 different branch paths.