Pixel Collision

Page: 1 2 3 4
Apr 9 2012, 5:47 am
For simple cases like moving around an obstacle that's barely being bumped, like a case where a mob is pushing against two turfs but is clearly more in one than another, I would solve it like so: 1) Override Bump() so it's tracked in a list. 2) In Move(), check the bump list. If there are two items being bumped, or one barely bumped, compare the mob's position based on the direction they were moving, and within some threshold of minimal overlap (say, 4 pixels, or perhaps a fraction of the bumpee's size), move the mob sideways away from the item they're barely touching.

One thing you could make a good case for would be the inclusion of helper procs that would make this kind of thing easier to calculate. You can get a dir from one bounding box to another, but it doesn't tell you if one direction has either a complete or partial overlap. Nor is there a get_dir() that tells you the direction you'd need to align the centers of both boxes. You can get a distance from one box to another, but not the "oblique" distance (that is, you may be 20 pixels away in the x direction but -3 in y). Those procs would obviously help.
Apr 9 2012, 6:29 am
In response to Lummox JR
 
     ####
     #### <-- wall
+---+####
|mob|x
|-->|x
+---+

I'd use obounds() to get the space occupied by the xs in that diagram. It's a box that's in front of the mob and slightly narrower than them. If they bump a wall but that box is open, move them away from the wall. Based on what your environments look like there are different ways you might size and position the bounding box.

The Pixel Movement library has some helper procs that'd almost cover this. The front(p) proc returns a list of atoms in the bounding box that covers the p pixels in front of the mob, but doesn't take a width (it only uses the mob's width). It's not a complex proc and wouldn't be hard to add a second argument for the width.

There are also alternatives that don't involve sliding the mob automatically when they hit an obstacle like that (since most games don't actually do that). With the Pixel Movement library you will slide along the wall if you're pressing both the right and down arrows. There's no automatic sliding of the player and you still get around the obstacle easily. If you had situations like this:

       #####
       #####
+---+  #####
|mob|
|-->|
+---+

       #####
       #####
       #####

Where the mob is just the right size to fit through the opening, there are two preferable ways to handle it:

1. Make the mob naturally line up with tile boundaries as they move. For example, if you're moving to the right, make minor adjustments to line them up vertically with tile boundaries. Provided they can move themselves to within a few pixels of being lined up, these automatic adjustments will line them up the rest of the way.

2. Don't make passages that are exactly the player's size. Even if the player's icon looks like it fills the full 32x32 box, make their size 30x30 or 28x28. You won't notice a huge different and they'll be able to fit through narrow passages more easily.
Apr 9 2012, 12:51 pm (Edited on Apr 9 2012, 12:58 pm)
Forum_account wrote:
(ex: world/movement_mode = RPG_MOVEMENT, RACING_MOVEMENT, SHOOTER_MOVEMENT, etc.) that'll be sufficient.
What is the difference between rpg and shooter movement? Racing movement, I assume, is something that you control by rotating the vehicle? BYOND may not need to fully build this in by default, but attempting to build something similar to that with what BYOND currently provides you with is far beyond 99% of BYOND game developers. If BYOND properly supported angular movement (which was also in the original pixel movement request), and per-pixel hit detection (again in the original request), or just proper rotation of atoms, then building a "racing" control scheme would be easy and almost natural.

If you want default movement behavior that's more game-specific than BYOND can provide, you'll have to use a library.
You should NEVER have to use a library. Considering they just provide quicker access to systems that you could and should write yourself.

Forum_account wrote:
1. Make the mob naturally line up with tile boundaries as they move.
That sounds functionally limiting and graphically clunky. What happens if you want to place objects that don't line up exactly with tiles? Which is definitely something that should be done. It also sounds like it would provide a very similar effect to what I am requesting anyway, except that you would be snapping them to tiles all over the place, instead of dynamically moving them only when need be.

2. Don't make passages that are exactly the player's size.
That still sounds like it would rely on a much more intuitive control scheme than BYOND provides by default. And if you were to do that, once players walked into the visually sized hallway, they could walk into the edges of it, and look like they were awkwardly standing on top of walls.

Neither of these ways are preferable, and you keep claiming that most games don't include any type of "sliding". However, I have already provided several examples of high quality projects that DO use such systems.
Apr 9 2012, 1:04 pm
In response to Falacy
Falacy wrote:
Forum_account wrote:
If you want default movement behavior that's more game-specific than BYOND can provide, you'll have to use a library.
You should NEVER have to use a library. Considering they just provide quicker access to systems that you could and should write yourself.

FA's point that movement systems are going to very between games is valid, so respectfully I have to disagree. As a simple example, consider the difference between a projectile and a mob--you would never want a projectile to slightly adjust its position to step around an obstacle. And in many games, I could see simple collision checks being just fine, with "sidestep" behavior being needed only for some cases.

That said, as I mentioned I think it'd be nice to have a quicker way to setup any particular kind of custom setup you'd want. A general-purpose library would help, but I'm not averse to the idea of more core functionality if it's clear which procs would deliver the greatest benefit to the most possible movement systems.
Apr 9 2012, 1:09 pm (Edited on Apr 9 2012, 1:33 pm)
In response to Lummox JR
Lummox JR wrote:
FA's point that movement systems are going to very between games is valid, so respectfully I have to disagree.
It isn't a valid point to begin with, since practically any top-down BYOND-type game would benefit from having an edge sliding effect when using pixel movement. However, that wasn't even the point that you seem to be disagreeing with, which was that you shouldn't use libraries in general...

As a simple example, consider the difference between a projectile and a mob--you would never want a projectile to slightly adjust its position to step around an obstacle.
I have already brought up that very example here, actually. Which is why this system should simply be optional and customizable. However, most projectiles would be destroyed on impact, so even if they were sliding, such a feature would probably have little/no effect on them.

And in many games, I could see simple collision checks being just fine, with "sidestep" behavior being needed only for some cases.
You would most likely want it on all mobs in most projects. For example, I have worked on 3 primary pixel movement games since the release of pixel movement. All of these have completely different play-styles, one is an action fighter, one is a shooter, and one is a classic RPG. All of them would benefit from being able to naturally slide around the environment as you try to navigate the world, instead of getting awkwardly stuck on things.

but I'm not averse to the idea of more core functionality if it's clear which procs would deliver the greatest benefit to the most possible movement systems.
A proc to customize sliding, something similar to Bump(), might be best. Maybe with the combination of a few built in variables to determine whether it happens at all in the first place, or perhaps the Slide() proc could just provide such arguments when it gets called. For example, I may want my players sliding around the environment, but not necessarily around each other. Such control would be difficult to achieve without a simple proc to go through.

I also tested a few more games to see how they treat this. Star Ocean on the SNES offers a simple system where you automatically walk around edges, it is less of a sliding effect and more of a full change in direction. Super Mario RPG seems to have edge sliding that may even be pixel-specific, similar to what SuperAntx's Game Maker demo showed, but in a more top-down environment. Realm of the Mad God uses a sort of isometric camera, so when you are moving North against a \ angled wall, it will automatically move you Northeast. So far, every 2D game that I have tested offers a system like this in some way, and most 3D games naturally do too.
Apr 9 2012, 2:04 pm
In response to Falacy
As you have observed, different games handle this differently--some change direction, some preserve it. I also would like to add that for some games, moving toward the center of the nearest turf may also be a benefit (e.g., a pixel movement version of Lode Wars). In others you might see Dig Dug style movement, continuing in the current direction until aligned with a tile. All of these are valid, and I don't see it being feasible to build in a general case.

As with the implementation of pixel movement itself however, I do see the possibility of middle ground--especially in the form of procs that would help users handle these situations on their own. It seems to me a more positive direction to take this discussion would be in the form of 1) what kinds of sliding people would find advantageous, and 2) implementation approaches, especially any that have general applicability and would not impact existing games.
Apr 9 2012, 5:01 pm (Edited on Apr 9 2012, 5:14 pm)
In response to Lummox JR
Lummox JR wrote:
FA's point that movement systems are going to very between games is valid, so respectfully I have to disagree. As a simple example, consider the difference between a projectile and a mob--you would never want a projectile to slightly adjust its position to step around an obstacle. And in many games, I could see simple collision checks being just fine, with "sidestep" behavior being needed only for some cases.
That said, as I mentioned I think it'd be nice to have a quicker way to setup any particular kind of custom setup you'd want. A general-purpose library would help, but I'm not averse to the idea of more core functionality if it's clear which procs would deliver the greatest benefit to the most possible movement systems.

I would recomend running the Slide feature after running the Bump() proc, allowing for developers to simply insert the impact of the projectile within the Bump() proc, neglecting the slide function.

And uppon that note, overiding/providing additional commands to run uppon Bump() could cancel out slide aswell, which would please those who don't want the feature I suppose.

EDIT: Or, you could simply add a variable to movable atoms to decide how many pixels can touch to iniate sliding, this would solve most of the issues that would arrise with customization, like projectiles.
Apr 10 2012, 7:16 am
In response to NNAAAAHH
Since even the method of sliding varies between games, automating sliding doesn't make as much sense IMO as providing an easier way for users to implement it themselves.
Apr 10 2012, 10:12 am (Edited on Apr 10 2012, 12:27 pm)
Falacy wrote:
BYOND may not need to fully build this in by default, but attempting to build something similar to that with what BYOND currently provides you with is far beyond 99% of BYOND game developers.
You should NEVER have to use a library. Considering they just provide quicker access to systems that you could and should write yourself.

Those statements don't add up. It doesn't make sense to want to cater to the terrible DM developers *and* expect them to implement everything from scratch. If you want to be able to add a movement scheme to a game with minimal effort, it'd have to be done as a library. It's just too game specific for it to make sense for BYOND to provide it. In your examples about one aspect of movement (sliding around obstacles), you haven't yet mentioned two games that handle it quite the same way.

So far, every 2D game that I have tested offers a system like this in some way, and most 3D games naturally do too.

In 99% of the games that you believe have this feature, it's not working how you think it is. When you've moving and hit an obstacle at an oblique angle, it doesn't stop your movement entirely, it only stops your movement in the direction of the obstacle. For example, if you're moving northeast and hit a wall that runs north/south, in many games you'd continue to move north along the wall. This isn't an obstacle avoidance thing, that's just how movement works. BYOND doesn't provide this (it's arguably game-specific) but it's simple to add.

Edit: to address some other things:

Lummox JR wrote:
As with the implementation of pixel movement itself however, I do see the possibility of middle ground--especially in the form of procs that would help users handle these situations on their own.

Not only that, but the helper procs would likely be useful in many other situations. The parameters for bounds() and obounds() aren't always ideal, but they're sufficient. I haven't found any helper procs so far that can't be created as a simple wrapper around them.

Falacy wrote:
That sounds functionally limiting and graphically clunky. What happens if you want to place objects that don't line up exactly with tiles?

You only need to line up with tile boundaries to get through narrow passages, which would be created with dense turfs, not dense objects.

That still sounds like it would rely on a much more intuitive control scheme than BYOND provides by default. And if you were to do that, once players walked into the visually sized hallway, they could walk into the edges of it, and look like they were awkwardly standing on top of walls.

You just need the passage to be enough wider than the player that they don't have to land on the exact pixel to fit through, so they'd only be able to appear as being a pixel or two inside the wall. Many games use bounding boxes that are much smaller than the sprites (example), so slightly overlapping a wall doesn't matter.
Apr 10 2012, 5:15 pm (Edited on Apr 10 2012, 5:58 pm)
In response to Forum_account
Forum_account wrote:
Those statements don't add up. It doesn't make sense to want to cater to the terrible DM developers *and* expect them to implement everything from scratch.
How does that not make sense? The engine should handle as much as possible, making games GOOD by default, not making them crap text MUDs by default, that you have to go far out of your way to bring to any competent standards. Developers should have to work from "scratch", but that start should be a very high point to begin with.

In the specific example of vehicle movement systems. Currently, to get even the most basic setup going, you would have to design your own systems for angular calculations, angular movement, angular icon manipulation, and if you really wanted to make a proper system, angular or per-pixel hit detection on the vehicle. There is no reason that BYOND, as a supposed game engine, shouldn't already have support for every single one of those features.

If you want to be able to add a movement scheme to a game with minimal effort, it'd have to be done as a library.
Nothing ever has to be done as a library, because all a library is is a collection of code that you could write yourself, but instead are relying on somebody else to create for you.

It's just too game specific for it to make sense for BYOND to provide it. In your examples about one aspect of movement (sliding around obstacles), you haven't yet mentioned two games that handle it quite the same way.
All of these games essentially handle it the same way. If you want to look at it most simplistically, then Star Ocean handles it by just making you walk around objects. If that feature were supplied in BYOND, the only change you would have to make to accomplish a matching effect to every other game, would be to run something simple like: 
mob/Slide()
    var/preDir=src.dir
    .=..()
    if(.)    src.dir=preDir


In 99% of the games that you believe have this feature, it's not working how you think it is.
lol I like how you keep making this ridiculous claim, but have yet to provide any sensible explanations to support it, or even provided a short list of decent pixel-movement games that don't include such an effect.

When you've moving and hit an obstacle at an oblique angle, it doesn't stop your movement entirely, it only stops your movement in the direction of the obstacle. For example, if you're moving northeast and hit a wall that runs north/south, in many games you'd continue to move north along the wall. This isn't an obstacle avoidance thing, that's just how movement works. BYOND doesn't provide this (it's arguably game-specific) but it's simple to add.
That isn't really relevant to this argument. If you were to setup your own control scheme, using some simple loops within BYOND, then you would easily achieve that effect anyway. This issue is the opposite of that (when you are moving North, and hit a Northeast wall), without some sort of sliding effect, your movement would come to a complete stop.

You only need to line up with tile boundaries to get through narrow passages, which would be created with dense turfs, not dense objects.
That sounds pointlessly game specific and nonsensically inconsistent. When would you apply such alignment? What happens if I had two table objects near each other creating a narrow passage?

You just need the passage to be enough wider than the player that they don't have to land on the exact pixel to fit through, so they'd only be able to appear as being a pixel or two inside the wall.
With proper movement mechanics, there is no need for the passage to be any larger than the player to begin with. Though, in most cases, it is probably going to be larger than them anyway.

Many games use bounding boxes that are much smaller than the sprites (example), so slightly overlapping a wall doesn't matter.
In a top-down game, it is a bit different, since everything could commonly be considered as simple squares, and overlapping walls all over the place would look especially awkward. Then again, I don't find it particularly acceptable that the idle animation in a side-scroller is hanging into a wall, and it seems to be something that was corrected in later Megaman games. NES games aren't exactly the standard that we should be attempting to live up to...

Also, I made a more specific request for the discussion of this feature: http://www.byond.com/forum/?post=650496
Apr 11 2012, 6:10 am
In response to Falacy
Falacy wrote:
Forum_account wrote:
You just need the passage to be enough wider than the player that they don't have to land on the exact pixel to fit through, so they'd only be able to appear as being a pixel or two inside the wall.
With proper movement mechanics, there is no need for the passage to be any larger than the player to begin with. Though, in most cases, it is probably going to be larger than them anyway.

The problem is I haven't seen a description yet of what is "proper" and how it should be done. You mentioned in one game it shows you moving in the side-step direction, in another it doesn't change direction. There's also a case to be made for aligning with the wall tile (if it's pushable, or diggable) or doing nothing. Some setups disallow diagonal movement, and some take it further by not allowing a mover to switch to a "side" direction while between tiles. I can think of several different kinds of sidestep movement that would all be appropriate. So it seems easier not to try to pick one, but as I said to come up with a base list of helper procs that would make it easier to implement any of them.
Apr 11 2012, 6:18 am (Edited on Apr 11 2012, 6:26 am)
In response to Lummox JR
Lummox JR wrote:
You mentioned in one game it shows you moving in the side-step direction, in another it doesn't change direction.
I provided a simple snippet in my previous post, if the default action was naturally moving in the side-step direction, overriding that with an extra directional change (to visually maintain direction) would be easy, and no different than it already is with normal movement.

There's also a case to be made for aligning with the wall tile (if it's pushable, or diggable) or doing nothing.
Doing nothing should be easily accomplished within this system, either by the setting of variables, or returning in the Slide() proc. Centering on a tile seems like a different concept, though I suppose it could be included with this, in some sort of negative/reverse manner.

Some setups disallow diagonal movement, and some take it further by not allowing a mover to switch to a "side" direction while between tiles.
Not really sure what you mean with side directions between tiles, but diagonal movement in general shouldn't be necessary, especially not in pixel movement. You simply move the player north and east, instead of northeast.

but as I said to come up with a base list of helper procs that would make it easier to implement any of them.
I can't see "helper" procs being very helpful towards this. You would have to know where you collided with something, how much that hitbox and your hitbox overlapped/how much of your hitbox was hanging into open areas, and if your hitbox on either side could effectively move past the areas that it was openly hanging into.

Also, Side Step does sound like a better term for this than Sliding.
Jul 3 2012, 10:11 pm
After recieving a BYOND Alert about a reply to this to only find nothing here, I assume either the person deleted their comment or was way-off topic and had their post deleted; I would like to bump this. I'd still love to see a optional pixel-colision option to go along with the optional pixel-movement.
Feb 8 2016, 4:54 am
This topic has been thoroughly derailed, in more ways than one, but I will try to look past all of that.

Lummox JR wrote:
I will mention that when we implemented pixel movement, pixel collision was something we considered and still have on the table. Tom's suggestion for this was that we could have a simple bit mask for each icon+state that would be animation-insensitive (I don't see animation sensitivity being practical). This would have to be optional, as the rectangular bounding box is far more useful.

No, animation sensitive pixel collision really isn't practical for BYOND, but I think simple bit masks would be too limiting for this feature. You should be able to specify an icon_state to use for the collision.

A new var called bound_state can be used for this. It would default to the current icon_state. If the specified state happens to be animated, then the first frame of the animation will be used. If the bound_state is directional, then the direction based on the value of the atom's dir var, at the time of setting the bound_state, will be used. This means the bound_state will not actively change its direction with the atom, because that would probably be too unpredictable, unless there is some magic way of handling that. If directional bounds were used, it would require forced movement and turn prevention, in some cases, to prevent any overlap with dense objects.

To specify exactly how the boundaries are determined, a var called bound_mode could be used. This would use a few new constants:

BOUND_RECT: This is the default value, which makes collisions behave exactly as they do now, using the existing bound vars.

BOUND_OPAQUE: This becomes the default value when bound_state is used. This causes only the completely opaque areas to be considered for collision.

BOUND_TRANSLUCENT: This will cause any areas that are not absolutely transparent, to be used in the collision. This means it includes the same areas as BOUND_OPAQUE, as well as semi-transparent ones.

BOUND_NONE: This makes the atom act as if it were a "ghost", with no density, and no boundaries of any kind. This means it can pass right through other atoms without triggering their cross procs. Spooky!
Feb 8 2016, 9:06 am
This is already possible, I think I'll do a tutorial.
Feb 8 2016, 9:09 am
@Multiverse: There are a lot of very specific corner cases that can result from changing bounding shapes based on something like icon state-level granularity. Professional games simply don't do anything like this. Yes, pixel collision is a thing, but it's largely avoided in the industry for a lot of reasons.

It's just too complex for very little benefit. I agree with bounding shapes, more or less, but true pixel-level collision with icon-state granularity? Yeah. No. It's just too insane and no engine in the history of ever has really bothered using it to any significant effect.
Feb 8 2016, 9:33 am
Ishuri wrote:
This is already possible, I think I'll do a tutorial.

Good luck with that. I can only imagine how terribly slow that would end up being. Just to start with, you will have to iterate over every single pixel, using icon.GetPixel(), to generate a 2D list matrix for collisions. Then, as things are about to collide, on every tick, you have to compare the trajectories of the nearest dense pixels in the matrices, to check for any contact. Don't forget to consider any anomalies, like different step_size values.

There's a reason why something like that would have to be built-in.

Ter13 wrote:
It's just too complex for very little benefit. I agree with bounding shapes, more or less, but true pixel-level collision with icon-state granularity? Yeah. No. It's just too insane and no engine in the history of ever has really bothered using it to any significant effect.

The other option is to use a form of optical character shape recognition to determine an approximate shape based on an icon_state, and then use that as the bounding area. The same basic concept would still apply, but it would be far less complex and resource intensive.
Feb 8 2016, 9:38 am
The other option is to use a form of optical character shape recognition to determine an approximate shape based on an icon_state, and then use that as the bounding area. The same basic concept would still apply, but it would be far less complex and resource intensive.

*Another.

A better option would be to generate a hull using a set of convex polygons and then perform SAT-based collision testing on said convex polyhull. This is how most sane games handle it.
Feb 8 2016, 9:55 am
I remember back in the day when games like Mortal Kombat had cheats to make the bounding boxes visible and it was just a bunch of rectangles piled on top of each other, even the big boys get ugly deep down.
Feb 8 2016, 9:56 am
In response to Ter13
That basically means you will end up with objects that act like this. Depending on the game, and the type of shape you are dealing with, that may not be ideal, which could force developers to use multiple objects rather than just one. In that case, a more complex system could actually end up being more efficient in the end.
Page: 1 2 3 4