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

Most efficient way to deal with multiple types of objects/AI

Most efficient way to deal with multiple types of objects/AI
by on (#175176)
What do you think is the most efficient way to deal with multiple types of object/AI on the NES? I can think of a couple different ways to do so, but I'm not sure which one is the best, most efficient, or most common, etc. Here are the ways I can think of off the top of my head:

1. Have a subroutine for each category of object that deals with updating (and generally dealing with) all objects of a given type. Eg: updates all bouncing balls every frame.

2. Have a subroutine that updates a single object which is jumped to based on information about the object held in RAM. Eg: bouncing balls have a RAM variable "AI" that specifies which subroutine to call to deal with the individual ball.

3. Have a subroutine that deals with all objects of a given type, but this subroutine calls a second subroutine which actually updates the individual objects. Eg: updates all bouncing balls every frame by calling a sub that updates an individual ball for each ball present in the game world.

What do you use, and what do you think is the most efficient for the NES?
Re: Most efficient way to deal with multiple types of object
by on (#175177)
thenewguy wrote:
What do you think is the most efficient way to deal with multiple types of object/AI on the NES? I can think of a couple different ways to do so, but I'm not sure which one is the best, most efficient, or most common, etc.

Mostly it depends on how different the object classes are from one another, such as how they participate in collision.

thenewguy wrote:
1. Have a subroutine for each category of object that deals with updating (and generally dealing with) all objects of a given type. Eg: updates all bouncing balls every frame.

Thwaite has separate routines to update player cursor, update all missiles, then all explosions, then all smoke particles. This separation works well because the only possible collision is between a missile and an explosion. The battle phase in RHDE behaves similarly because the object types (player cursor, units, and missiles) are so different from one another.

thenewguy wrote:
2. Have a subroutine that updates a single object which is jumped to based on information about the object held in RAM. Eg: bouncing balls have a RAM variable "AI" that specifies which subroutine to call to deal with the individual ball.

Haunted: Halloween '85 uses a jump table indexed by actor_class for enemies' action instructions (AI) because they're more similar than different, in that the player loses health when colliding any of them (or gains health if they're actually power-ups instead of enemies), and most take damage when they collide with the player's fist. They may use certain state variable for different things. For example, the AI for a crow uses an actor's "progress through the current frame of animation" variable to store its base hovering height. But the camera itself is different enough from actors to get its own dedicated routine.
Re: Most efficient way to deal with multiple types of object
by on (#175179)
thenewguy wrote:
What do you use, and what do you think is the most efficient for the NES?

Approach 1 is usually the most efficient. Approach 2 is probably the most versatile.

Approach 3 I don't understand, as it seems to have all the drawbacks of both without any of the advantages.

What do I use? I don't believe in one-size-fits-all solutions. Most likely I would try approach 2 first, and measure it to see how many balls I can run at once. If that's enough balls, I'll stop there. If it's not, I'll think about approach 1. However, if I was interested in "as many balls as possible", I might try approach 1 first. Different goals necessitate a different approach!

On a related topic, here's a semi-recent talk by Mike Acton about "data oriented design". A lot of the specifics are about modern systems, but the way he reasons about stuff is pretty interesting and applicable elsewhere. Mostly I'm reminded of it because it gets into some of the reasons why approach 1 tends to be more efficient.
https://www.youtube.com/watch?v=rX0ItVEVjHc
Re: Most efficient way to deal with multiple types of object
by on (#175209)
Combination
thenewguy wrote:
1. Have a subroutine for each category of object that deals with updating (and generally dealing with) all objects of a given type. Eg: updates all bouncing balls every frame.

2. Have a subroutine that updates a single object which is jumped to based on information about the object held in RAM. Eg: bouncing balls have a RAM variable "AI" that specifies which subroutine to call to deal with the individual ball.


Use 1 for the most common types of object, and 2 for everything else. For example, Contra uses 1 for player characters and bullets (player characters are always present and bullets are often present in large numbers), and 2 for enemies (many types of enemies exist, of which only one or two are usually in play at a given moment)
Re: Most efficient way to deal with multiple types of object
by on (#175217)
tepples wrote:
Haunted: Halloween '85 uses a jump table indexed by actor_class for enemies' action instructions (AI) because they're more similar than different, in that the player loses health when colliding any of them (or gains health if they're actually power-ups instead of enemies), and most take damage when they collide with the player's fist. They may use certain state variable for different things. For example, the AI for a crow uses an actor's "progress through the current frame of animation" variable to store its base hovering height. But the camera itself is different enough from actors to get its own dedicated routine.

My own byte-code system made use of a jump-table in the main body of the subroutine.

If you're tight on ROM space, a byte-code interpreter can be both more efficient and versatile, so long as you're willing to use a few more RAM bytes on objects, to keep things fast. (Specifically, address pointers to reference the object's data entry, when switching tasks.)

The subroutines handling the objects are optimized to be as generic as possible, to handle every object's behavior, rather than a ton of copied code for each instance.
Re: Most efficient way to deal with multiple types of object
by on (#175230)
Some games explicitly saved the program counter when an object subroutine wanted to suspend, and restored it when resuming the object's code. Examples include WayForward's games on the Game Boy Color, but there are plenty of others too.
Saving a single state byte when an object wants to suspend, and using jump tables to resume is another way to achieve the exact same thing without using two byte stores, it's just more complicated to set up. This is what Tepples described.

"Suspend" means that an object is done and is returning to the code to handle other objects, and "Resume" means calling the object code. By using suspend/resume logic, you can make more complicated objects that don't need to start at the same entry point each time they are handled.
Re: Most efficient way to deal with multiple types of object
by on (#175298)
Dwedit wrote:
Saving a single state byte when an object wants to suspend, and using jump tables to resume is another way to achieve the exact same thing without using two byte stores, it's just more complicated to set up. This is what Tepples described.

Well, yeah. This is what happens during a "normal" frame, in my game logic.

But when the status counter reaches 0, the interpreter needs to decode a new state from 2 data bytes, to set up the object's next action. Nibble reading is already quite slow (even optimized), and in the worst case, 8 objects would request a new status, bogging things down.

So 2 extra RAM bytes per object is just a safety net, to keeps thing running smoothly.
Re: Most efficient way to deal with multiple types of object
by on (#175334)
Dwedit wrote:
Some games explicitly saved the program counter when an object subroutine wanted to suspend, and restored it when resuming the object's code.

"Suspend" means that an object is done and is returning to the code to handle other objects, and "Resume" means calling the object code. By using suspend/resume logic, you can make more complicated objects that don't need to start at the same entry point each time they are handled.


Tecmo Super Bowl does this. Each object (player) has 3 different program counter locations that get saved in the objects memory.
One for speed updates and collision handling, one for player actions(passing,diving for a tackle,etc) and one for what part of the play script the player is on.