It is currently Sun Dec 17, 2017 4:32 pm

All times are UTC - 7 hours





Post new topic Reply to topic  [ 33 posts ]  Go to page Previous  1, 2, 3  Next
Author Message
 Post subject: Re: Object update order
PostPosted: Fri May 27, 2016 9:33 am 
Offline
User avatar

Joined: Fri Apr 08, 2016 5:58 pm
Posts: 93
Location: California, USA
I'm not sure I understand how you guys are setting up your objects. Currently I just have $0400 dedicated to object data, and each object begins with a byte declaring its type, then four bytes for its coordinates, then four bytes for velocities, then whatever additional stuff the object may need. Objects are ticked in the order they appear in RAM. I've never given any thought to it outside of that though... what is this linked list deal? Is that less RAM intensive or something? What's the implementation there...?


Top
 Profile  
 
 Post subject: Re: Object update order
PostPosted: Fri May 27, 2016 10:13 am 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10169
Location: Rio de Janeiro - Brazil
Guilty wrote:
Currently I just have $0400 dedicated to object data, and each object begins with a byte declaring its type, then four bytes for its coordinates, then four bytes for velocities, then whatever additional stuff the object may need. Objects are ticked in the order they appear in RAM.

This approach probably works for simpler games, but there are some things that simply can't be done with this setup.

I currently have 24 object slots, each containing 32 bytes of attributes:

- type (1 byte);
- next object (1 byte); (next empty slot or next object in the same group)
- logic routine index (1 byte);
- X coordinate (3 bytes);
- Y coordinate (3 bytes);
- X speed (2 bytes);
- Y speed (2 bytes);
- angular speed (2 bytes);
- angle (1 byte);
- slope threshold (1 bytes); (used when walking off ledges)
- link to related object (1 byte);
- bounding box index (1 byte);
- pattern offset (1 byte); (mainly for double buffering patterns)
- sprite attributes (1 byte);
- animation script pointer (2 bytes);
- animation counter (1 byte);
- extended state index (1 byte); (memory position that's preserved after the object is unloaded)
- index in the list of level objects (2 bytes); (to manipulate dead/alive state)
- compact spawn coordinates (2 bytes); (to control object destruction)
- general purpose (3 bytes);

A lot of objects don't need all this information, and they're free to use the memory for other things if necessary.

Quote:
what is this linked list deal? Is that less RAM intensive or something? What's the implementation there...?

A linked list is a means of grouping things without having to reorder them. A variable indicates the first element in a list, and each element links to the next element. An invalid link (e.g. $ff) indicates the end of the list.

I, for example, have a list of free slots, so I can just grab the first one when I need to instantiate a new object, instead of having to go looking for a free slot. I also use linked lists to create different groups of objects, to control the order in which they're updated. Objects in group 0 go first, then those in group 1, and so on. When an object is instantiated, it inserts itself in the appropriate group. Another use for object groups is reducing the number of collision checks without having to check for object types. In a shooting game, for example, you could have a group only for bullets, so that collisions against them can be optimized.

EDIT: Another thing I consider important when dealing with object RAM is to use a structure of arrays instead of an array of structures, since the 6502 works better with the former. If I stored object attributes linearly, and I had more than 256 bytes worth of object RAM, I'd have to use a pointer and I'd need to load Y with the offset of each attribute I wanted to access before doing it. Things are not nearly as bad if everything is linear but fits in 256 bytes or less, because then you can use code like lda ObjectRAM+OBJECT_TYPE, x, where X contains the offset to the object and OBJECT_TYPE is a constant containing the offset to that specific attribute. I still prefer to use a structure of arrays though, so I can do lda ObjectType, x, where X is simply the slot index, meaning I don't need to shift bits when dealing with slot indices and slots are not restricted to sizes that are powers of 2. For example, if I need a new attribute to implement a new feature I can simply find 24 (or how many active objects the engine supports) bytes anywhere and create an array there.


Top
 Profile  
 
 Post subject: Re: Object update order
PostPosted: Fri May 27, 2016 1:18 pm 
Offline
User avatar

Joined: Fri Apr 08, 2016 5:58 pm
Posts: 93
Location: California, USA
I'll now ask a series of questions to see what kinds of things I need to consider when differing from your technique.
tokumaru wrote:
- logic routine index (1 byte);

Is this really needed? I simply call upon a specific logic routine that depends on the object, and if the object has more than one state then it can select that state's logic from there. RTS tricks.
Quote:
- X coordinate (3 bytes);
- Y coordinate (3 bytes);

24-bit coordinates? Are your play fields larger than 16 screens wide/tall or do you just need a lot of sub-pixel precision?
Quote:
- slope threshold (1 bytes); (used when walking off ledges)

I don't know what kind of game you're making, but wouldn't may objects not require this byte at all? I mean, particle effects and such. Or is this just the format for the 'actor' group of objects?
Quote:
- pattern offset (1 byte); (mainly for double buffering patterns)

As in, offset in the pattern table? That way this object can load its own tiles into CHR ram whenever it needs? That's a pretty cool trick if so, but I worry about vBlank time needed for all those ppu updates. And I also don't understand 'double buffering patterns'? Something something Battletoads.
Quote:
- sprite attributes (1 byte);

I feel like the sprite attributes could just be determined by an object's current state. Or do you store it here during object logic and return to it for a second pass to draw it?
Quote:
- animation script pointer (2 bytes);

This could be an index to a table as well, right? Save more RAM?
Quote:
- extended state index (1 byte); (memory position that's preserved after the object is unloaded)

This is really interesting to me and I don't understand the concept.
Quote:
- index in the list of level objects (2 bytes); (to manipulate dead/alive state)

This is so that the object doesn't get loaded again when you leave the playing field and come back, right? Cool idea.
Quote:
- compact spawn coordinates (2 bytes); (to control object destruction)

This is to keep objects from straying too far away from their 'home' location, yeah?

Quote:
Another thing I consider important when dealing with object RAM is to use a structure of arrays instead of an array of structures, since the 6502 works better with the former.

I believe I understand this, but my terminology may be fuzzy. The method I described would be considered a structure of arrays, yes? Even though different objects may take up different array lengths of RAM?
Thanks for the patience, I don't know of any other place to learn about these kinds of concepts.


Top
 Profile  
 
 Post subject: Re: Object update order
PostPosted: Fri May 27, 2016 3:05 pm 
Offline
User avatar

Joined: Sat Jul 25, 2015 1:22 pm
Posts: 501
You'll probably want to add variables to your objects as they're needed. Nothing wrong with doing what works now and putting another variable when you have a routine to use it.

Guilty wrote:
tokumaru wrote:
- logic routine index (1 byte);

Is this really needed? I simply call upon a specific logic routine that depends on the object, and if the object has more than one state then it can select that state's logic from there. RTS tricks.

These things seem trivial at first, but pulling up this info from your object data every frame can get costly on top of a complex game. If you have the RAM, sometimes its worth the cycle savings to preserve some things.

Quote:
Quote:
- sprite attributes (1 byte);

I feel like the sprite attributes could just be determined by an object's current state. Or do you store it here during object logic and return to it for a second pass to draw it?

I'm a little confused by this one. Does this negate the possibility of using flipped sprites inside of a metasprite, or multiple palettes in one metasprite? Mine is set so that if my objects are facing left, the horizontal flip bit is EORed, so a sprite which is reversed when right will un-reverse when facing left.
I suppose you'd get some ROM savings for not needing that per tile, if you don't need the functionality of it. Metasprite definitions can sure add up. I find myself needing to reverse on a per-tile basis a bit though.

Quote:
Quote:
- animation script pointer (2 bytes);

This could be an index to a table as well, right? Save more RAM?

If it was, this would be a pain to derive each frame. If you have one state per one animation, then sure, it's not too hard, but it's often a bit inefficient to program things that way. It all depends on the game. Complex metaspriting gets pretty heavy on the cycles. If you have to go through a lot of logic to get your animation pointer, just save it.


Top
 Profile  
 
 Post subject: Re: Object update order
PostPosted: Fri May 27, 2016 4:12 pm 
Offline
User avatar

Joined: Fri Apr 08, 2016 5:58 pm
Posts: 93
Location: California, USA
darryl.revok wrote:
If it was, this would be a pain to derive each frame. If you have one state per one animation, then sure, it's not too hard, but it's often a bit inefficient to program things that way. It all depends on the game. Complex metaspriting gets pretty heavy on the cycles. If you have to go through a lot of logic to get your animation pointer, just save it.

Er, 'pain to derive' in terms of cpu cycles? Because right now I've got a series of predefined metasprites, a series of predefined animations (which contain indexes to those metasprites) and indexed lists of both. Each object that needs animation calls on a subroutine that finds the current metasprite using a given animation index and animation time, and that data is fed into the metasprite drawing routine. I haven't exactly timed out the duration of the routine or anything but I don't think that's too much to ask of the NES? After all, graphics typically take up the bulk of the cpu tick anyways...? Stop me if I'm wrong of course.


Top
 Profile  
 
 Post subject: Re: Object update order
PostPosted: Fri May 27, 2016 4:34 pm 
Offline
User avatar

Joined: Sat Jul 25, 2015 1:22 pm
Posts: 501
I wouldn't think that the bulk of your CPU time should be spent on graphics. If you run a very complex metasprite engine, that's going to significantly cut into the number of objects you can have on screen, the complexity of your game logic and interactions. If your metasprite engine is robust enough to reject individual tiles instead of just full objects, meaning that an object half off-screen doesn't wrap around to the other side, then that's more overhead gone. Do you want your metasprite engine to handle colors/h/v flip per tile? If so, that's a bit more. It's all about what's most important to you. Time it out and see how long it takes to find your pointers if you want, but you really won't know for sure until you build the rest of your game engine. You may change the way your objects work 5 times before you're done. Doing a lot of indirect indexed addressing on a list of objects adds up. What's more important, the cycles or the bytes? Have you got to a point that either of them matter? If not, then I'd say continue with what's most comfortable to program and maintain, because I'm sure you'll have to make changes before you're done in one way or another.


Top
 Profile  
 
 Post subject: Re: Object update order
PostPosted: Fri May 27, 2016 4:41 pm 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10169
Location: Rio de Janeiro - Brazil
Guilty wrote:
tokumaru wrote:
- logic routine index (1 byte);

Is this really needed? I simply call upon a specific logic routine that depends on the object, and if the object has more than one state then it can select that state's logic from there. RTS tricks.

The purpose of this variable is precisely to make this selection. I prefer to directly look up an address than check a bunch of state variables before deciding what to do.

Quote:
Quote:
- X coordinate (3 bytes);
- Y coordinate (3 bytes);

24-bit coordinates? Are your play fields larger than 16 screens wide/tall or do you just need a lot of sub-pixel precision?

I plan on having "Sonic 3"-sized levels, so I support up to 128 screens wide/tall. I'll probably not go that far, but I do want vast areas to run and jump through, instead of room-basef levels.

Quote:
Quote:
- slope threshold (1 bytes); (used when walking off ledges)

I don't know what kind of game you're making, but wouldn't may objects not require this byte at all? I mean, particle effects and such. Or is this just the format for the 'actor' group of objects?

This is used for handling peaks. When the leading point of an object starts to descend, its Y position is locked to the top of the peak until either the left or right points go past the highest point of the peak. The point that does becomes the primary collision point. This variable indicates where the highest point is. Objects that walk along the ground need this, but the format is the same for every object. Objects that don't need this can use the byte for other things, or not touch it at all.

Quote:
Quote:
- pattern offset (1 byte); (mainly for double buffering patterns)

As in, offset in the pattern table? That way this object can load its own tiles into CHR ram whenever it needs? That's a pretty cool trick if so, but I worry about vBlank time needed for all those ppu updates. And I also don't understand 'double buffering patterns'? Something something Battletoads.

Double buffering means displaying a copy of the graphics while you update a hidden copy, that gets displayed when it's complete. Only the player does this, but being able to relocate tiles allows me to combine enemies differently across different levels, for example.

Quote:
Quote:
- sprite attributes (1 byte);

I feel like the sprite attributes could just be determined by an object's current state. Or do you store it here during object logic and return to it for a second pass to draw it?

Since I have to store things like direction, map plane, and such, I might as well do it in the same format the OAM expects and save time. This byte is EORed with each attribute byte that comes from the metasprite definitions. I also use the bits the NES doesn't for other sprite related stuff, like whether sprites should be written to OAM bottom to top or top to bottom.

Quote:
Quote:
- animation script pointer (2 bytes);

This could be an index to a table as well, right? Save more RAM?

If this was an index to a table of animations, if need a second byte to specify the frame, so I might as well just point to the frame within the animation directly, and not bother calculating the address every frame.

Quote:
Quote:
- extended state index (1 byte); (memory position that's preserved after the object is unloaded)

This is really interesting to me and I don't understand the concept.

Each object gets 1 bit of state by default, enough to specify a permanent dead/alive state, but some objects need more than that. These objects use this byte to indicate which byte(s) in a separate table it uses for its extended permanent state.

Quote:
Quote:
- index in the list of level objects (2 bytes); (to manipulate dead/alive state)

This is so that the object doesn't get loaded again when you leave the playing field and come back, right? Cool idea.

Yes. Also to keep them dead for good when they actually die.

Quote:
Quote:
- compact spawn coordinates (2 bytes); (to control object destruction)

This is to keep objects from straying too far away from their 'home' location, yeah?

Could be, but the main purpose is to not unload objects while their spawn point of still in range. This could cause them to mysteriously vanish, until the player moved enough to get the spawn point out of range and back in. To avoid this, I only unload objects of both their spawn coordinates and current coordinates are out of range.

Quote:
Quote:
Another thing I consider important when dealing with object RAM is to use a structure of arrays instead of an array of structures, since the 6502 works better with the former.

I believe I understand this, but my terminology may be fuzzy. The method I described would be considered a structure of arrays, yes? Even though different objects may take up different array lengths of RAM?

To me yours sounds like an array of structures... Do you have all bytes for the first object, then all bytes for the second object, and so on? If so, that's an array of structures. Structures of arrays may not look as neat when you look at the memory map, but they're nearly always faster to manipulate with the 6502.


Top
 Profile  
 
 Post subject: Re: Object update order
PostPosted: Sat May 28, 2016 9:39 am 
Offline

Joined: Wed May 19, 2010 6:12 pm
Posts: 2433
tokumaru wrote:
darryl.revok wrote:
Would you modify the object's position or its velocity? If you could modify its velocity, then its movement would still be encapsulated.

Directly moving an object is a way to make an object that's pushed after it has already been processed not to be displayed in the wrong place. Changing the velocity after it's been processed will do nothing until the next frame, so it doesn't really fix the problem.



The way I did it, I had the moving platform perform the initial collision with players and enemies, and give a signal that they're on that object. Then it's up to the player or enemie's tile collision routine to follow the moving platform around, and do the rest of the collision.


Top
 Profile  
 
 Post subject: Re: Object update order
PostPosted: Sat May 28, 2016 10:44 am 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10169
Location: Rio de Janeiro - Brazil
Sounds good, but... When objects are touching, their bounding boxes usually don't overlap, they just... touch. This means that when an object is riding a platform, there's no collision to detect. Unless you cheat by allowing 1 pixel overlaps or something.


Top
 Profile  
 
 Post subject: Re: Object update order
PostPosted: Tue May 31, 2016 2:41 am 
Offline
User avatar

Joined: Mon Oct 06, 2014 12:37 am
Posts: 187
tokumaru wrote:
How do moving platforms work with this scheme? If the player is updated before the platforms, couldn't he end up falling when a platform moves instead of following it?

Based on the player's relative position to a platform object, a collision check is performed, setting a bit-flag if positive-- resulting in the platform "dragging" the player object, when updating.

It has no effect on the player's overall state, so they can still walk around while being transported.


Top
 Profile  
 
 Post subject: Re: Object update order
PostPosted: Tue May 31, 2016 11:06 am 
Offline

Joined: Wed May 19, 2010 6:12 pm
Posts: 2433
tokumaru wrote:
Sounds good, but... When objects are touching, their bounding boxes usually don't overlap, they just... touch. This means that when an object is riding a platform, there's no collision to detect. Unless you cheat by allowing 1 pixel overlaps or something.


It only does horizontal collision when on platforms. When a character jumps it manually disconnects it from a platform.


Top
 Profile  
 
 Post subject: Re: Object update order
PostPosted: Mon Aug 15, 2016 5:56 pm 
Offline
User avatar

Joined: Fri Apr 08, 2016 5:58 pm
Posts: 93
Location: California, USA
Bringing this thread back from the dead.
@tokumaru, I'm working on object implementation again and I'm really curious how your objects are referencing their variables. Currently the only way I can imagine your system working is if you arrange each 'column' in ram to be an object (say, $4001, $4011, $4021, ...) and then the objects would read their variables through a read such as $4000,x where X is the slot to which they've been assigned. But then you would be limited to 16 objects, unless you had each group assigned to different pages of RAM. How does a given object check its own variables if it could be in any slot?


Top
 Profile  
 
 Post subject: Re: Object update order
PostPosted: Mon Aug 15, 2016 6:13 pm 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 19354
Location: NE Indiana, USA (NTSC)
$4000 is the APU. Did you mean $0400?

Yes, you can put different property stripes in different pages of RAM. So if you have 16 objects, each with 20 bytes of properties, you can put 16 properties in one page and 4 properties in the next.

An object references its properties by having its move subroutine take X (the index into the property arrays) as an argument.


Top
 Profile  
 
 Post subject: Re: Object update order
PostPosted: Mon Aug 15, 2016 6:46 pm 
Offline
User avatar

Joined: Wed Apr 02, 2008 2:09 pm
Posts: 1046
Code:
spriteramstart = $0300
objectnum = 20

OBJaddrhigh = spriteramstart+objectnum*0
OBJaddrlow = spriteramstart+objectnum*1

OBJxhigh = spriteramstart+objectnum*2
OBJxlow = spriteramstart+objectnum*3
OBJyhigh = spriteramstart+objectnum*4
OBJylow = spriteramstart+objectnum*5

OBJwidth = spriteramstart+objectnum*6
OBJheight = spriteramstart+objectnum*7


OBJtype = spriteramstart+objectnum*8
OBJrequests = spriteramstart+objectnum*9

OBJdestroynum = spriteramstart+objectnum*10

OBJextra00 = spriteramstart+objectnum*11
OBJextra01 = spriteramstart+objectnum*12
OBJextra02 = spriteramstart+objectnum*13
OBJextra03 = spriteramstart+objectnum*14
OBJextra04 = spriteramstart+objectnum*15
OBJextra05 = spriteramstart+objectnum*16
OBJextra06 = spriteramstart+objectnum*17
OBJextra07 = spriteramstart+objectnum*18
OBJextra08 = spriteramstart+objectnum*19

OBJxvel = spriteramstart+objectnum*20
OBJxvelsub = spriteramstart+objectnum*21
;etc

You're not limited to 16 objects. You can change at any time by changing object num. And variables are indeed accessed with OBJaddrhigh,x (or whatever piece of RAM they want) where X is their object number.

Edit: I suppose it's true you'd be limited to 16 if you didn't want page crossing, but I don't think it's too big a concern. In the worst case, you can arrange the RAM so that variables that will suffer the page cross penalty are ones that aren't accessed frequently.

_________________
https://kasumi.itch.io/indivisible


Top
 Profile  
 
 Post subject: Re: Object update order
PostPosted: Mon Aug 15, 2016 7:19 pm 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 5899
Location: Canada
Kasumi wrote:
I suppose it's true you'd be limited to 16 if you didn't want page crossing, but I don't think it's too big a concern. In the worst case, you can arrange the RAM so that variables that will suffer the page cross penalty are ones that aren't accessed frequently.

You could just add a few bytes of padding where needed to get to the end of a page (if not aligned already). Also, if your assembler has a .res keyword or equivalent (or .align) it's convenient for that sort of thing:
Code:
OBJa = spriteramstart+objectnum*3
OBJb = spriteramstart+objectnum*4
OBJc = spriteramstart+padding+objectnum*5

; vs

OBJa: .res objectnum
OBJb: .res objectnum
.align 256 ; pads to next page
OBJc: .res objectnum


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 33 posts ]  Go to page Previous  1, 2, 3  Next

All times are UTC - 7 hours


Who is online

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