Techniques for bigger jump tables?

Discuss technical or other issues relating to programming the Nintendo Entertainment System, Famicom, or compatible systems. See the NESdev wiki for more information.

Moderator: Moderators

Drakim
Posts: 97
Joined: Mon Apr 04, 2016 3:19 am

Re: Techniques for bigger jump tables?

Post by Drakim »

Oziphantom wrote: Or if you have a large number and you have a large number of shared update functions. Do the more expensive look up once and then store the Bank and Ptr Lo and Ptr Hi along with State number for each entity. Thus each frame you load/store the bank then jump to the Lo/Hi function for maximum speed. And then when you need to change it you have the State number to modify and then do the more expensive 256+ 2byte -> 3 byte look up.
This was my original plan, before I even started this thread. It's plainly the superior solution, as the expensive big jump table lookup only happens once during the object creation.

The downside is that you end up using a lot more memory. Instead of just storing an Id in a byte (or two bytes if we use a big jump table), you'll now have to store the flags, sprite, update-, death-, and collision-routine addresses.

If you want to allow up to 8 game objects alive at once, you'll have to set aside 8 times as much memory. Just the things I mentioned above would result in 8*8 = 64 bytes of RAM spent. And it will keep growing as you add more stuff to enemies.

If you are using a mapper with more RAM, it shouldn't be much of a problem though. I still might end up using that solution. It's also cool because you can "modify" a living object to change it's behavior, like pointing it's update routine address to an RTS for when it's frozen in ice.
Drakim
Posts: 97
Joined: Mon Apr 04, 2016 3:19 am

Re: Techniques for bigger jump tables?

Post by Drakim »

Sumez wrote:While there's no way to argue that it will always be true, I feel it's extremely unlikely to have more than 256 entirely different types of objects that are still similar enough to justify sharing the same jump table. For example, is there a reason that a boss enemy should be interchangeable with a powerup that does nothing other than sit still and wait to be touched?
Moreover, I feel that once you're dealing with so many variations, you're beginning to work with repeated patterns that should justify ordering your logic differently - Having 256 different potential subroutines to jump to actually sounds more wasteful to me than the huge jump table itself.
Drakim wrote:More than 256 types of items/weapons?
This one is absolutely just data. A sword is unlikely to be more than just a set of bytes to indicate attack power, a graphic, a sell price, maybe a level requirement, etc. Having a jump table to handle different behaviors for each possible weapon for any place in the code that handles weapons/items, sounds absurdly excessive.
You got me confused and interested Sumez, because it sounds like you know something I don't. :mrgreen:

Let's make an imaginary example, a game with 300 distinct types of enemies. Now, as you pointed out, we obviously won't have 300 distinct collision routines, 300 distinct death routines, 300 distinct walking routines.

This is simply because a lot of enemies will share the same kind of reaction. For instance in Super Mario 3, the Green Koopa Troopa and the Red Koopa Troopa have a lot in common. But they also have some differences. They share the same pattern, collision routine, but they have different palletes and walking routines.

Thats why we won't have a separate green_koopa_collide and red_koopa_collide routines, they would be identical. Instead we point both the green koopa troopa and the red koopa troopa to the same collision routine, so that they share it.

But that's where we run into the problem. Even though we might only have 125 separate collision routines because of reuse, we still need 300 separate pointers. This is so that we can tell which of those 300 distinct enemies uses which of those 125 distinct collision routines.

So no matter how good we are at reusing routines, the big jump table problem isn't escaped at all!

At least, that's how I see the situation. Is there a clever way to avoid this?
User avatar
dougeff
Posts: 3079
Joined: Fri May 08, 2015 7:17 pm

Re: Techniques for bigger jump tables?

Post by dougeff »

"125 distinct collision routines."

I have 1 enemy collision routine that changes the size boundaries based on enemy type. That's 2 tables. One height. One width.

"300 distinct types of enemies."

I hope you have a team of a dozen artists and programmers and testers, and about 2-3 years.
nesdoug.com -- blog/tutorial on programming for the NES
Drakim
Posts: 97
Joined: Mon Apr 04, 2016 3:19 am

Re: Techniques for bigger jump tables?

Post by Drakim »

dougeff, I'm trying to understand what Sumez is explaining, so I made up imaginary examples. No team of programmers or artists needed.

Even so, while it's true that it's enough with one collision detection routine, the collision response for enemies can be many and varied. Enemies behave differently when Mario crashes into them. Some hurt Mario, some gets stomped, others get turned into a shell, etc.
User avatar
Sumez
Posts: 919
Joined: Thu Sep 15, 2016 6:29 am
Location: Denmark (PAL)

Re: Techniques for bigger jump tables?

Post by Sumez »

No doubt if you actually have 300 different types of enemies, I suppose there's no real way around having a 16 bit pointers to differentiate between them, I can't argue with that. Just like you'll need more than 8 bits to indicate your X coordinate if you want to work with a grid larger than 256 horizontally, and just the same that will obviously give you a bit of performance overhead (which by itself is a good reason why most games of the time make a point out of limiting themselves to max 256 different variations of anything), but at the end of the day it's a question of balancing your game design around what features you consider the most important.

However, even if you're using 16 bit addressing to refer to your enemy data, that doesn't mean you'll need to have any jump tables this big, which is what I was trying to demonstrate. :)
Drakim
Posts: 97
Joined: Mon Apr 04, 2016 3:19 am

Re: Techniques for bigger jump tables?

Post by Drakim »

Sumez wrote:However, even if you're using 16 bit addressing to refer to your enemy data, that doesn't mean you'll need to have any jump tables this big, which is what I was trying to demonstrate. :)
You are right about that. The "gotcha" when moving on from 1 byte indexes to 2 byte indexes is that addresses are 2 bytes anyways so you might as well just point directly at what you want instead of an index of things you want.

With the exception of using the bank/jump table trick mentioned earlier in this thread, I think just using an address without a jump table is the fastest way (short of spending the RAM to store every part of the enemy data easily accessible after it's been initialized).
Post Reply