It is currently Tue Dec 12, 2017 3:01 pm

All times are UTC - 7 hours





Post new topic Reply to topic  [ 8 posts ] 
Author Message
PostPosted: Mon Jul 11, 2016 2:19 pm 
Offline

Joined: Wed Feb 03, 2016 10:39 pm
Posts: 32
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?


Top
 Profile  
 
PostPosted: Mon Jul 11, 2016 2:48 pm 
Offline

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


Top
 Profile  
 
PostPosted: Mon Jul 11, 2016 3:07 pm 
Offline
User avatar

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


Top
 Profile  
 
PostPosted: Mon Jul 11, 2016 7:33 pm 
Offline

Joined: Mon Nov 10, 2008 3:09 pm
Posts: 431
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)


Top
 Profile  
 
PostPosted: Mon Jul 11, 2016 10:33 pm 
Offline
User avatar

Joined: Mon Oct 06, 2014 12:37 am
Posts: 187
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.


Top
 Profile  
 
PostPosted: Tue Jul 12, 2016 5:59 am 
Offline
User avatar

Joined: Fri Nov 19, 2004 7:35 pm
Posts: 3968
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.

_________________
Here come the fortune cookies! Here come the fortune cookies! They're wearing paper hats!


Top
 Profile  
 
PostPosted: Tue Jul 12, 2016 10:46 pm 
Offline
User avatar

Joined: Mon Oct 06, 2014 12:37 am
Posts: 187
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.


Top
 Profile  
 
PostPosted: Wed Jul 13, 2016 12:08 pm 
Offline

Joined: Sun May 03, 2015 8:19 pm
Posts: 92
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.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 8 posts ] 

All times are UTC - 7 hours


Who is online

Users browsing this forum: No registered users and 9 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