Welcome, Guest. Please login or register. Did you miss your activation email?

Author Topic: Can we get collision detection in SFML?  (Read 8543 times)

0 Members and 1 Guest are viewing this topic.

Critkeeper

  • Jr. Member
  • **
  • Posts: 62
    • View Profile
Can we get collision detection in SFML?
« on: March 12, 2015, 07:36:34 pm »
Its a simple fast multimedia library, so I can understand if you just wanna reply "nope" on that basis alone, but hear me out:

Collision detection can be useful outside of games. For example, detecting the collision/intersection of a cursor with an "ok" box, or more generally using it as a factor in GUI message handling.

Collision detection is usually application specific, but it isn't the only application specific data structure. For example, std::list used to have O(1) splice() and O(n) size(), but the C++ committee decided to swap the performance characteristics so that list would have O(1) size like every other stl data structure. Despite the fact that lists (among other data structures) can have an application specific implementation, the c++ committee tries to satisfy as many people as possible by providing a "generally good" implementation.

Is collision detection so application specific that there is no such thing as a "generally good" collision detection algorithm across most applications?

Why can't we have collision detection in SFML to satisfy as many people as possible?
if(CritKeeper.askQuestion()){return question.why();}

Jesper Juhl

  • Hero Member
  • *****
  • Posts: 1405
    • View Profile
    • Email
Re: Can we get collision detection in SFML?
« Reply #1 on: March 12, 2015, 08:01:03 pm »
Do you want 2d or 3d collision detection?
Do you want collision detection just between bounding boxes (or circles or arbitrary polygons or spheres) (axis alligned or not)?
Do you want pixel perfect collision detection (what about partially transparent pixels)?
Do you want collision detection just for sf::Shape or also for sprites? Other classes?
Etc, etc.. There are many many ways to determine what constitutes a collision and I'd say "yes, it's a problem better dealt with outside of SFML". 
But that's just me ;-)
« Last Edit: March 12, 2015, 08:09:07 pm by Jesper Juhl »

Critkeeper

  • Jr. Member
  • **
  • Posts: 62
    • View Profile
Re: Can we get collision detection in SFML?
« Reply #2 on: March 12, 2015, 08:08:00 pm »
automatic AABB 2d collision on any "rect2d" isn't too much to ask for and has applications outside of games.
« Last Edit: March 12, 2015, 08:10:32 pm by Critkeeper »
if(CritKeeper.askQuestion()){return question.why();}

binary1248

  • SFML Team
  • Hero Member
  • *****
  • Posts: 1405
  • I am awesome.
    • View Profile
    • The server that really shouldn't be running
Re: Can we get collision detection in SFML?
« Reply #3 on: March 12, 2015, 08:12:09 pm »
Collision detection can be useful outside of games. For example, detecting the collision/intersection of a cursor with an "ok" box, or more generally using it as a factor in GUI message handling.
What people often don't know, is that within the context of games and physical simulations, people often get lazy and leave out the second part of the term: Collision detection and response. Simply detecting whether 2 entities are "colliding" with each other can often be reduced to a simple bounding volume intersection test. The naive approach would not solve edge cases such as ghosting, but it works out for "sane" scenarios without becoming too complex.

Now, I already mentioned intersection testing, and that is what you are probably referring to as "collision detection", and yes, intersection testing can be useful in a variety of application types, which is why it is already part of SFML.

Collision detection is usually application specific, but it isn't the only application specific data structure. For example, std::list used to have O(1) splice() and O(n) size(), but the C++ committee decided to swap the performance characteristics so that list would have O(1) size like every other stl data structure. Despite the fact that lists (among other data structures) can have an application specific implementation, the c++ committee tries to satisfy as many people as possible by providing a "generally good" implementation.
Intersection testing is not application specific, but what you have to add onto it to turn it into "collision detection" does become application specific, too application specific to be in SFML as a general purpose multimedia library.

And about std::list: Strictly speaking, they didn't choose to change std::list::size() to be constant time complexity in favour of splice(), they just stated that any conforming STL container has to have a constant size() operation, and std::list was the odd one out until that point. The fact that splice() had to be changed was a result of that new requirement because the way std::list was implemented had to be changed. They weren't "trying to satisfy as many people as possible" with this change, just trying to make the STL more consistent. This is also exactly the reason why they want to get rid of the std::vector<bool> specialization.

Is collision detection so application specific that there is no such thing as a "generally good" collision detection algorithm across most applications?
Yes. And considering that in any application/game where real "collision detection" is required, and not just a simple intersection test, it will be tightly coupled with the collision response anyway. We aren't going to provide you with half of the picture so that you have to paint the other half so it fits what we already gave you.

Why can't we have collision detection in SFML to satisfy as many people as possible?
Did you ever consider that there might be people who like a lean/clean/consistent API as well? ;)
SFGUI # SFNUL # GLS # Wyrm <- Why do I waste my time on such a useless project? Because I am awesome (first meaning).

Critkeeper

  • Jr. Member
  • **
  • Posts: 62
    • View Profile
Re: Can we get collision detection in SFML?
« Reply #4 on: March 12, 2015, 10:05:45 pm »
I think I understand what you are saying, so let me state what I meant, rather than what I typed.

By "collision detection" all I meant was that there should be something like a flag on an sfml sprite / shape / anything that has a bounding box that tells me whether it is intersecting with anything else that has a box/shape/area, if I pass a flag to the shapes/boxes involved telling them to "turn on collision detection for this entity" in the constructor.

That doesn't really complicate the API at all and the performance penalty under the hood for managing the intersection system is opt-in.

This has lots of applications outside of games because as you said, it is just intersection detection.

Currently sfml intersection detection requires you to query for an intersection between two provided shapes. What I am suggesting  is that querying for intersection is slow and can often be complicated if the entities in question are not localized to a single data structure, and it would be simpler if "intersection" were a property rather than a return value. In other words, the shape/sprite/whatever just "magically knows" whether it is intersecting or not, because work is being done behind the scene to update that property based on all other registered shapes/boxes/whatevers.

The user doesn't have to know how the shapes/boxes/whatevers are implemented underneath and inside SFML, only SFML does has to know that. And SFML can exploit that knowledge to provide more efficient persistent intersection detection that the user could. Boxes are pretty transparent, but curves or arbitrary polygons are not necessarily.

Under the hood this allows SFML to use temporal coherence for efficiency. Temporal coherence is the property that two intersecting shapes will likely be intersecting next frame, and two non-intersecting shapes will likely be not intersecting next frame. A query based approach does not exploit temporal coherence-- you have to keep querying whether the two shapes intersect over and over in order to determine when the shapes stop intersecting or start intersecting.

A persistent collision system can provide a guarantee that the intersection state will remain valid as long as the API is used to move / transform / translate / rotate the entities involved. If an intersection occurs then the system can record information for each type of transformation that determines what transformations (and which arguments) could cause the intersection state to change. For example, if a box is wholly contained within another box, then rotation and stretching about their centers cannot alter the intersection state. But translating could. The intersection is compute only when the intersection state is set, and until it is cleared the data stored and modified is the information pertaining to what has to happen to change the state. This is more abstract an idea than AABB and the implementation can be extended to arbitrarily complicated polygons and curves while remaining invisible to the user.

The benefit of offering something like this through SFML is that collision detection systems of choice can be built on top of it. For example, to get sweeping collision detection for bullets you can create a new sfml::shape who's outline is the outline of the swept out area of the bullet along its trajectory. It is totally up to you how you want to determine or compute that swept out shape, but the intersection part of the problem is solved on the SFML side, rather than the application side.

So yes, I am saying you should provide half of the picture so that I can paint the other half so and I don't think that is greedy or bad or lazy or anything but sane.

There is no reason that intersection HAS to be a query. Query is just one tool in the software engineering toolkit. It isn't the best one for intersection testing for most multimedia applications in my honest opinion-- a persistent state model would be better.
« Last Edit: March 12, 2015, 10:26:07 pm by Critkeeper »
if(CritKeeper.askQuestion()){return question.why();}

binary1248

  • SFML Team
  • Hero Member
  • *****
  • Posts: 1405
  • I am awesome.
    • View Profile
    • The server that really shouldn't be running
Re: Can we get collision detection in SFML?
« Reply #5 on: March 12, 2015, 10:56:10 pm »
By "collision detection" all I meant was that there should be something like a flag on an sfml sprite / shape / anything that has a bounding box that tells me whether it is intersecting with anything else that has a box/shape/area, if I pass a flag to the shapes/boxes involved telling them to "turn on collision detection for this entity" in the constructor.

That doesn't really complicate the API at all and the performance penalty under the hood for managing the intersection system is opt-in.
How does adding parameters to the API that not everybody might use in a typical use case not complicate it at all? You are already making a lot of assumptions that do not hold in most scenarios outside of game development. Does everybody deal with entities? What if they have their own more sophisticated entity system? If people build GUIs with thousands of graphical elements, there will be unused data members in every single one of them, not to mention the inactive data paths that imply unnecessary checks. It simply can't be "opt-in" if the system is "activated" from runtime data (parameters) as opposed to statically via the preprocessor/templates.

This has lots of applications outside of games because as you said, it is just intersection detection.
Providing concrete examples would help to convince people, and allow them to debate over whether those examples are actually valid.

Currently sfml intersection detection requires you to query for an intersection between two provided shapes. What I am suggesting  is that querying for intersection is slow and can often be complicated if the entities in question are not localized to a single data structure, and it would be simpler if "intersection" were a property rather than a return value. In other words, the shape/sprite/whatever just "magically knows" whether it is intersecting or not, because work is being done behind the scene to update that property based on all other registered shapes/boxes/whatevers.

The user doesn't have to know how the shapes/boxes/whatevers are implemented underneath and inside SFML, only SFML does has to know that. And SFML can exploit that knowledge to provide more efficient persistent intersection detection that the user could.
With each of your statements, you are becoming more and more application specific. Why would entities have to be localized to a single data structure? Sure you can do this in your own code, but how would others actually benefit from this? Not to mention, like I said... the concept of "entities" doesn't even apply to every scenario.

Also, you can't simply say "whether something is intersecting or not". It simply doesn't make sense. With what is what intersecting? An intersection in set theory is the set which contains the common elements from 2 or more sets. Intersection is a binary operator, so if you wanted to register whether an intersection persists between 2 "entities" you would have to at least store it as a bool along with information about the counterpart as well. In the simplest scenario, you would be checking for intersections between "active entities" (those for which checks are enabled) between every possible pair of entities in your container since the "checking" entity has no knowledge of whether the target entity is actually registered for checking. I hope I don't have to explain how this grows quadratically... You might say: Well... all the registered entities are referenced in a separate container so they don't have to check for this. Then I have to ask: Doesn't this contradict what you initially said about everything being in a single data structure?

Under the hood this allows SFML to use temporal coherence for efficiency. Temporal coherence is the property that two intersecting shapes will likely be intersecting next frame, and two non-intersecting shapes will likely be not intersecting next frame. A query based approach does not exploit temporal coherence-- you have to keep querying whether the two shapes intersect over and over in order to determine when the shapes stop intersecting or start intersecting.
Even more application specificity... What does temporal coherence mean to those who simply don't care? Does it even make sense to speak of such a thing if you aren't ticking a simulation every frame?

The benefit of offering something like this through SFML is that collision detection systems of choice can be built on top of it. For example, to get sweeping collision detection for bullets you can create a new sfml::shape who's outline is the outline of the swept out area of the bullet along its trajectory. It is totally up to you how you want to determine or compute that swept out shape, but the intersection part of the problem is solved on the SFML side, rather than the application side.
Even you are bringing up the topic of collision response now. Like I said, these things are tightly coupled. Someone who goes through the effort of implementing the second half (which is probably the substantially bigger part) will not be bothered by implementing the first half themselves as well. There is no point in providing something for people to use "just so they can make use of the library more". We don't want to lure people into using something that might even be suboptimal for their specific scenario, and given the wide variety of collision detection implementations this will almost certainly be the case.

There is no reason that intersection HAS to be a query. Query is just one tool in the software engineering toolkit. It isn't the best one for intersection testing for most multimedia applications in my honest opinion-- a persistent state model would be better.
You should really try to think outside the box when you say something like "for most multimedia applications". I can't really tell whether you have actually considered anything besides the very specific use case you have presented here. Bear in mind that this toolkit will have to be used by many many people with very different requirements. If I go to a hardware store and get a set of tools to undertake some home improvement, I'm definitely not going to wheel home half a car of tools that the salesman told me might be useful before even knowing what I was intending to do ;).
SFGUI # SFNUL # GLS # Wyrm <- Why do I waste my time on such a useless project? Because I am awesome (first meaning).

alienonolympus

  • Newbie
  • *
  • Posts: 4
    • View Profile
    • Email
Re: Can we get collision detection in SFML?
« Reply #6 on: June 06, 2015, 02:43:56 pm »
Sorry if this post does not fit some kind of format or requirement, since I am a complete newbie. :)

I've just stumbled across this suggestion and I like it.

You should really try to think outside the box when you say something like "for most multimedia applications". I can't really tell whether you have actually considered anything besides the very specific use case you have presented here. Bear in mind that this toolkit will have to be used by many many people with very different requirements.

For simple 2D games, this is very useful. It will save a whole bunch of time messing around with variables.

Mario

  • SFML Team
  • Hero Member
  • *****
  • Posts: 879
    • View Profile
Re: Can we get collision detection in SFML?
« Reply #7 on: June 08, 2015, 01:01:38 pm »
For very simple games you can just use sf::Rect::intersect(). The collision response (i.e. moving back to no collision) isn't that hard either.