It is currently Thu Dec 14, 2017 7:51 pm

All times are UTC - 7 hours





Post new topic Reply to topic  [ 33 posts ]  Go to page 1, 2, 3  Next
Author Message
 Post subject: Object update order
PostPosted: Wed May 25, 2016 3:40 pm 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10164
Location: Rio de Janeiro - Brazil
The order in which game objects are updated can affect the way objects interact with each other. Ideally, each object's A.I. will run only once per frame, so we can assume that objects that can affect others (mainly their position, but other attributes too) should be updated first. Moving platforms, for example: if the player is standing on a moving platform and the platform is updated first, all the player's A.I. has to do is apply the same displacement that was applied to the platform, before running its regular physics code.

But what about objects that can affect each other, such as enemies and the player, that can hurt each other? Depending on who's updated first, there may be a 1-frame delay before a collision between them is handled. This is not such a big problem, the only side effect is that sometimes we see the objects overlapping for a frame and sometimes we don't, and that's hardly noticeable.

There are more complicated cases, such as blocks that can be pushed by the player but can also carry the player. When the player is pushing the block, the player's A.I. should run first, so the block can copy its displacement. When the player is riding the block, however, it's the player that has to copy the block's displacement.

In my engine, I have a number of object groups that I update in order, so I can handle the block issue by moving the block between different groups depending on its state, this is fast and not such a big deal.

I do wonder how other programmers handle these issues, though. Do you visit objects more than once? Do you update objects out of order when necessary? What are other possible solutions to handle object interactions?

Note that some of the problems I presented above exist only because I'm trying to program objects in a way that only the object itself can alter its state. Objects can consult the state of other objects, but they can't change anything. That's a way to keep each object's code centralized, but I'm not sure that's the most accurate model of the real world, though... When an object pushes another, it does in fact modify that object's position, regardless of what it's doing.


Top
 Profile  
 
 Post subject: Re: Object update order
PostPosted: Wed May 25, 2016 4:50 pm 
Offline
User avatar

Joined: Fri Apr 08, 2016 5:58 pm
Posts: 93
Location: California, USA
Now isn't this a familiar conversation!

I spend a lot of time wondering about this myself, but I have pretty limited experience with applying this to actual NES games. I've been theorizing about an object handling routine that visits each object more than once, but uses different logic each time. This is largely based on conversations in the thread I linked, what with the 'inbox' variables that Kasumi talked about. But until I apply it I'd just be talking out of my ass, so I'll hang back and see who has interesting ideas here.


Top
 Profile  
 
 Post subject: Re: Object update order
PostPosted: Wed May 25, 2016 5:43 pm 
Offline
User avatar

Joined: Sat Jul 25, 2015 1:22 pm
Posts: 501
Interesting to see that discussion made you think about the issue a bit more as well.

I figured you guys would know best when it comes to objects modifying one anothers' positions. I haven't done this yet, but I thought about it some more since we talked about it. I would think you would need to treat these more like BG collisions than object collisions, meaning to check them right after object movement and before executing any other logic.

If they are two solid objects which eject one another, but also cause damage upon collision, then I'd think one of the objects would need to be accepted as a valid position. The simplest example would be to say that only player positions get corrected by objects. Any non-player objects, like enemies, and moving platformers, are only subject to BG collisions.

I think you'd first need to move these "infallible" objects, without performing object collisions. Then, during your player logic, apply movement, check object collisions, set flags for the damage you'll need to process, eject from object collisions, then check BG collision and eject from those second.

I'm a little unclear about whether or not this causes the possibility of two objects overlapping at the end due to 1. colliding with one another, ejecting player into wall 2. ejecting from wall back over enemy. If so, then that seems to me the logical route versus overlapping the wall. I would think though, that if you separate object collisions into X and Y axis, like BG collisions, then it may solve that issue.

This however, doesn't cover enemies riding platforms. So I think platforms would need a different object type. That would be an optimization also, since the platforms won't need a lot of the logic enemies will. They may not even need BG collisions, depending on how you program them.

Now the box you can ride and pick up creates an interesting paradox. One on hand, it's an infallible platform, and on the other hand, it's modified by player position. If it's carried by the player, it needs to share the player's velocity in any given frame. If it's one you can throw, then it needs to check against enemies and cause collisions with them, so in that case, the enemy becomes the infallible object.

I'd think I'd probably try having the box become a different type of object when it's lifted. So, that would create four object types, and I think they could be handled in this order:

1. "Infallible" Platforms - objects which players and enemies can stand on, not subject to movement from any collisions, probably not subject to BG collisions
2. Enemy Objects - check against platforms and BG
3. Player Objects - check against platforms, enemies, and BG, set values for moveable objects
4. Moveable Objects - check against platformers, enemies, and BG

I would think the reasoning behind only allowing an object to modify itself is so any movements are corrected by collision, as well as the objects' state being corrected. With this model, I don't think you'd have a problem with that. The moveable objects (things being carried) would need to be set, not to the velocity variable of the player carrying it, but rather the actual number of pixels it moved that frame. So it seems it must come after the player. It can still make all of these movements inside of its loop though.

I see a couple possible issues though. One is a matter of how you want to carry objects. If they are carried in front of the player, the carried object won't test against backgrounds until it's too late. If you're carrying the box above your head, this model would work well for game rules where in the box above your head falls behind the character when they go under a ceiling which is too low. If a method of stopping player movement entirely is preferred, then there would be issues. Modifying the player's hitbox size to the size of the carried object would create problems. Specifically, the carried object would then cause the player to take damage when contacting an enemy. You may prefer it to be immune to damage or maybe even hurt the enemy.

Ultimately, thinking about this topic more thoroughly has brought me to believe it's more complex than one may think at first glance, and is most likely largely dependent on game rules. Perhaps someone with more experience would have a more concrete answer, but I hope my thoughts on the matter may at least encourage brainstorming on the matter.

One thought that I have on the general topic of update orders and collisions is that it's most efficient to check collisions from your longest object list. If I'm checking collisions from 1 player vs. 32 bullets, I have to have a loop to run through all 32 bullets, and a way of verifying which bullets are active. These steps are already covered in the logic loop for the bullets themselves, so collision checking from 1 bullet to 1 player (or 2 players) becomes a simple unrolled routine that executes for any bullet that survives to the end of its own movement loop. I'm not sure though, if that can be juggled inside of the platform/carry object paradox you proposed, however.


Top
 Profile  
 
 Post subject: Re: Object update order
PostPosted: Thu May 26, 2016 1:03 am 
Offline
User avatar

Joined: Mon Oct 06, 2014 12:37 am
Posts: 187
I have some experience in this area, both on the NES, and in other forms of programming.

I tend to keep each "type" of object, split into standard groupings:
1 = The Player
2 = Objects (Blocks, Platforms)
3 = Monsters
4 = Particles/Effects

The first use of this organization, is that I can more easily sort them when updating the OAM, so particles will flicker first, before monsters, then objects, and eventually the player, in the worst-case scenario. It's all a juggling act.

The second use of this, allows me to use bit-flags during object-processing, for dynamic object interaction. The player moving an object in the map, or standing on a moving enemy/platform, for example.

For the record-- I check object/background collision before updating object logic, because with some clever optimizations, it's considerably faster than processing things the other way around.


Top
 Profile  
 
 Post subject: Re: Object update order
PostPosted: Thu May 26, 2016 7:23 am 
Offline

Joined: Thu Aug 12, 2010 3:43 am
Posts: 1589
tokumaru wrote:
I do wonder how other programmers handle these issues, though. Do you visit objects more than once? Do you update objects out of order when necessary? What are other possible solutions to handle object interactions?

Don't forget the option of an object directly affecting another. (EDIT: oh right you don't do that >_> but it's the common approach in older games) E.g. in the moving platform example, chances are when the platform moves it will apply its displacement on the player as well (rather than waiting for the player object to do it). Yeah there's the issue of going through walls, but if your physics engine checks for collisions always (even when your momentum is 0) it may just self-correct itself the next frame when it notices a collision against a wall and pushes you out. Or you could just add the displacement by invoking the physics engine itself, that is (if you have enough CPU time to spare for it, and if movement is in just one axis then it may be simplified).

Of course if you go the data-oriented programming way then you don't let objects modify neither others nor themselves like that, the physics code is a separate step from object behavior =P (there's still the worry about when a collision response causes yet more collisions to be handled)


Top
 Profile  
 
 Post subject: Re: Object update order
PostPosted: Thu May 26, 2016 8:02 am 
Offline
User avatar

Joined: Mon Jan 03, 2005 10:36 am
Posts: 2983
Location: Tampere, Finland
tokumaru wrote:
In my engine, I have a number of object groups that I update in order, so I can handle the block issue by moving the block between different groups depending on its state, this is fast and not such a big deal.

Just out of curiosity, are you using linked lists for your object groups?

_________________
Download STREEMERZ for NES from fauxgame.com! — Some other stuff I've done: kkfos.aspekt.fi


Top
 Profile  
 
 Post subject: Re: Object update order
PostPosted: Thu May 26, 2016 8:24 am 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10164
Location: Rio de Janeiro - Brazil
thefox wrote:
Just out of curiosity, are you using linked lists for your object groups?

Yes. I have functions for adding and removing objects to/from each group:

Code:
   ;add the object to a group of objects
   lda Object::FirstObjects+Group
   sta Object::InstancesNext, x
   stx Object::FirstObjects+Group
   rts

Code:
   ;remove the object from a group of objects
   lda Object::InstancesNext, x
   ldy Object::Previous
   bmi :+
   sta Object::InstancesNext, y
   rts
:   sta Object::FirstObjects+Group
   rts

The index of the object is specified in the X register. Object::Previous is a "global" variable that contains the index of the object that was processed before the current one (it's set to $ff before the first object of each group is updated).


Top
 Profile  
 
 Post subject: Re: Object update order
PostPosted: Thu May 26, 2016 9:14 am 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10164
Location: Rio de Janeiro - Brazil
Guilty wrote:
Now isn't this a familiar conversation!

Indeed... I actually thought of posting this in that thread back then, but for some reason I didn't.

Quote:
This is largely based on conversations in the thread I linked, what with the 'inbox' variables that Kasumi talked about.

I really like the "message" approach. I have been thinking of ways to make it work for the various types of interactions objects need. The biggest problem I see is what I described above, that there might be a 1 frame delay before an object gets a message if I don't run its logic twice.

darryl.revok wrote:
I would think you would need to treat these more like BG collisions than object collisions, meaning to check them right after object movement and before executing any other logic.

This is my conclusion as well, which is why I decided to update solid objects that can't be pushed first, so that they act almost like background elements, and all other objects can collide with them.

Quote:
If they are two solid objects which eject one another, but also cause damage upon collision, then I'd think one of the objects would need to be accepted as a valid position. The simplest example would be to say that only player positions get corrected by objects. Any non-player objects, like enemies, and moving platformers, are only subject to BG collisions.

I know this is the case in the Sonic games. I can understand why programmers would do it like this, an with careful enemy placement this doesn't become so apparent to players, but I can't stop thinking how nice it'd be if enemies could react to dynamic barriers, moving platforms and such...

Quote:
I'd think I'd probably try having the box become a different type of object when it's lifted.

This is a good idea, better than handling the change using states and changing the update order.

Quote:
1. "Infallible" Platforms - objects which players and enemies can stand on, not subject to movement from any collisions, probably not subject to BG collisions
2. Enemy Objects - check against platforms and BG
3. Player Objects - check against platforms, enemies, and BG, set values for moveable objects
4. Moveable Objects - check against platformers, enemies, and BG

This is exactly how I was planning to use the 4 object groups I currently support (I can change the number of groups by simply changing a constant, though, if necessary).

Quote:
I would think the reasoning behind only allowing an object to modify itself is so any movements are corrected by collision, as well as the objects' state being corrected.

To me the reasoning is actually to encapsulate all the code that deals with each object, so that I can modify details about the object during development without having to go hunting for fragments of code that deal with it that might be hidden in other objects.

Quote:
With this model, I don't think you'd have a problem with that. The moveable objects (things being carried) would need to be set, not to the velocity variable of the player carrying it, but rather the actual number of pixels it moved that frame.

Yes, and this displacement is conveniently available in each object's "speed" variables. Unless the object was stopped by an obstacle, a case that would need special handling.

Quote:
Ultimately, thinking about this topic more thoroughly has brought me to believe it's more complex than one may think at first glance, and is most likely largely dependent on game rules.

True. I guess that most of the time games end up largely simplifying the model, at least back in the 8 and 16-bit days.

Quote:
One thought that I have on the general topic of update orders and collisions is that it's most efficient to check collisions from your longest object list. If I'm checking collisions from 1 player vs. 32 bullets, I have to have a loop to run through all 32 bullets, and a way of verifying which bullets are active. These steps are already covered in the logic loop for the bullets themselves, so collision checking from 1 bullet to 1 player (or 2 players) becomes a simple unrolled routine that executes for any bullet that survives to the end of its own movement loop.

Yes... I'm still thinking it having enemies collide with the player, instead of the other way around, isn't the best option.

Alp wrote:
I tend to keep each "type" of object, split into standard groupings:
1 = The Player
2 = Objects (Blocks, Platforms)
3 = Monsters
4 = Particles/Effects

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?

Sik wrote:
in the moving platform example, chances are when the platform moves it will apply its displacement on the player as well (rather than waiting for the player object to do it).

Having objects directly modify the positions of other objects does seem like the simplest approaches in some cases, and may even be a more accurate modeling of the real world, but since a platform can carry many objects, but an object can only ride one platform, in this case it's simpler to have each object reference the one it's standing on than the other way around.


Top
 Profile  
 
 Post subject: Re: Object update order
PostPosted: Thu May 26, 2016 9:45 am 
Offline

Joined: Thu Aug 12, 2010 3:43 am
Posts: 1589
tokumaru wrote:
Having objects directly modify the positions of other objects does seem like the simplest approaches in some cases, and may even be a more accurate modeling of the real world, but since a platform can carry many objects, but an object can only ride one platform, in this case it's simpler to have each object reference the one it's standing on than the other way around.

Fair enough, but this logic can still get you out in other situations that don't seem as obvious.

Mind you, the approach of handling all physics as a separate step from object logic would probably work with your limitation of objects not modifying other objects. In fact, it may even make physics "just work" even for object combinations you didn't think on.


Top
 Profile  
 
 Post subject: Re: Object update order
PostPosted: Thu May 26, 2016 11:08 am 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10164
Location: Rio de Janeiro - Brazil
I'm considering allowing objects to modify another object's positions, but nothing else. Positions and bounding boxes are, as far as I can predict, universal, so this should be fairly safe to do. There might be a 1 frame delay between the object being pushed and it reacting to being pushed, but that would probably go unnoticed. Objects popping or jittering is what draws attention.


Top
 Profile  
 
 Post subject: Re: Object update order
PostPosted: Thu May 26, 2016 2:15 pm 
Offline
User avatar

Joined: Sat Jul 25, 2015 1:22 pm
Posts: 501
tokumaru wrote:
I'm considering allowing objects to modify another object's positions, but nothing else.

Would you modify the object's position or its velocity? If you could modify its velocity, then its movement would still be encapsulated.
Quote:
There might be a 1 frame delay between the object being pushed and it reacting to being pushed, but that would probably go unnoticed.

I was thinking about an issue with the model I described, is that an enemy will be hit by a thrown box at the end of a frame, after its been buffered. It will get the message of its collision on the next frame, and will have already acted on the player for the frame in which it was hit. My guess is that would be insignificant. Everything would still be functioning on the same frame.

I think the specific game rules make a difference. Like, can you push a box that an enemy can stand on? That would throw a wrench in the model I described. I'm kind of thinking of the item being picked up becoming a weapon.

A deliberate wait before pushing a box in a game is pretty standard for a couple reasons. It makes sense, due to inertia of the box, and helps differentiate the intentions of the player's controller input. Can the logic be worked in a way so that handling the case of a player moving a platform object is okay to "wrap" around to the next frame?

(Also, will enemies also be modifying objects? That would introduce a lot more considerations)

So just kind of brainstorming off the top of my head, I think at the end of the frame, if the player has pushed against a moveable box for 16 frames or so, send a message to move box. The next frame, box moves, and sends a message to move player. Move the player either way so the box doesn't move for an extra frame. Check controller to see if player is still pushing against the box. Control will be sent around for another loop of box movement if player is still pressing same direction.

Having the box first is pretty important actually, because you could push it into a wall. In that case, box needs to be the first one to stop movement, so it will need to check BG collisions.


Top
 Profile  
 
 Post subject: Re: Object update order
PostPosted: Thu May 26, 2016 5:01 pm 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10164
Location: Rio de Janeiro - Brazil
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.

Quote:
My guess is that would be insignificant. Everything would still be functioning on the same frame.

Exactly. 1 frame at 60Hz is too fast for anyone to notice in a lot of cases. Positions are more troublesome because they can cause popping and jittering, which are very noticeable.

Quote:
Like, can you push a box that an enemy can stand on? That would throw a wrench in the model I described. I'm kind of thinking of the item being picked up becoming a weapon.

I think most 8 and 16-bit games have levels designed to avoid these situations, because simple engines simply can't handle that stuff.

Quote:
So just kind of brainstorming off the top of my head, I think at the end of the frame, if the player has pushed against a moveable box for 16 frames or so, send a message to move box. The next frame, box moves, and sends a message to move player. Move the player either way so the box doesn't move for an extra frame. Check controller to see if player is still pushing against the box. Control will be sent around for another loop of box movement if player is still pressing same direction.

So the game basically alternates between the player pushing the box and the box pulling the player? Seems a bit strange, but it's a way to keep the box as a single object and still working as a platform for other objects.


Top
 Profile  
 
 Post subject: Re: Object update order
PostPosted: Thu May 26, 2016 5:22 pm 
Offline
User avatar

Joined: Sat Jul 25, 2015 1:22 pm
Posts: 501
tokumaru wrote:
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.
Does your engine update the sprite buffer during the object loop?

In my previous game engine I was doing the full OAM buffer as its own routine. It was just the first way that I thought to do it. More recently I put the buffering inside of the object loops. This makes a lot of sense for things like bullets which don't have metasprite routines. However, I'm thinking about switching it back, at least for non-bullet objects, so I can handle sprite counts higher than 64 more easily.

Even if you can update the sprite buffer for the object later, moving it again sounds sticky. Other objects could possibly depend on its position. You could push a box overtop of an enemy. It wouldn't react to that until the next frame, but then the box could move again. So there would be one frame worth of overlap between a pushed box and an object it's pushing in turn.

I see a different problem with the model though. Platforms don't check against anything, so a pushed box can't stop on account of another object. That's okay if you can continue to push the other object, but what if you can't? What if it's too heavy, or you push it into a wall?

I guess an obvious solution would be to check platforms against the positions of objects last state before moving. It sounds like this model is becoming costly in processing to include so many features.

I do think though that moving an object at the end of the frame that other (already processed) objects depend on for position, is a potentially bad idea.


Top
 Profile  
 
 Post subject: Re: Object update order
PostPosted: Thu May 26, 2016 8:49 pm 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10164
Location: Rio de Janeiro - Brazil
darryl.revok wrote:
Does your engine update the sprite buffer during the object loop?

I tried many things... First I used to process objects in random order and I updated the sprite buffer at that time. Then, when I realized I'd need to have control over the order in which objects are updated, I tried to come up with a type of sprite cycling that would still work if the objects were updated in order, and failing that I ultimately decided to split the update and drawing procedures completely, so I'm using 2 loops now.

Quote:
Even if you can update the sprite buffer for the object later, moving it again sounds sticky. Other objects could possibly depend on its position.

Hum... Say that a box has just finished its update step, and is supposedly resting at its final position. Then an enemy moves towards the box, detects the collision and ejects itself. Finally, the player pushes the block from the other side. If we allow the box to be moved, it would overlap the enemy. To catch something like this we'd have to update the box again, have it collide with objects again, so that it could push the enemy as well. Then we'd have to update the enemy again, and so on... Yeah, I guess that allowing objects to move other objects isn't a good idea at all. It solves nothing, because we still have to make the object validate the new position.

I have thought of another way to process objects, but haven't thought of all the implications yet:

1- Handle any messages the object may have received LAST frame;
2- Put the object in the drawing queue, using the current position and metasprite;
3- Handle any messages the object may have received THIS frame;
4- Process physics and collisions, send messages as necessary;

This would cause the previous state of the objects to be displayed on the screen (i.e. there'd be a 1-frame input lag), but all messages would be processed before the object was displayed, ensuring that the displayed state is always stable. Not that I have any RAM left for a drawing queue, though!


Top
 Profile  
 
 Post subject: Re: Object update order
PostPosted: Thu May 26, 2016 9:49 pm 
Offline
User avatar

Joined: Sat Jul 12, 2014 3:04 pm
Posts: 950
I am reminded of a devblog/LP which addresses moving platforms and stacked objects in this post, kinda.


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

All times are UTC - 7 hours


Who is online

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