Re: [pygame] Collision Resolver module

["René Dudfield" <renesd@xxxxxxxxx>]

Hi,

this looks pretty cool.

I think we should consider something like this for the next pygame.
Something to help with collision response.

Of course we need to figure out how to do this nicely.

I really like that the API to use it is only one function, and it
looks like it is written in a way so that it is fairly extensible.


A few thoughts:
- should be able to make use of different collision methods than just
rects.  For example pixel perfect collision detection that is in
pygame 1.8.

- We should test the API out on a couple of different games first.
Probably adding it to suitable existing games would be good.  As well
as to some of the pygame example games.


... and my comments from before:

- a generic method which does more efficient collision detection +
response for multiple sprites would be good.
- a new top level module for it would be bad.  It should probably be
incorporated in the sprite module.
- the examples/testsprite.py example would be the place to test out
the api.  It could then even compare performance to the naive approach
used there.


There is also the option of adding something like chipmunk directly to
pygame.  We should at least study it's API/implementation.

But anyway, I think it's a great idea - and is often an area where
many people have problems.  I'll put some more effort into discussing
this after we get pygame 1.8 out.

cu,





On Jan 3, 2008 7:41 PM,  <sjbrown@xxxxxxxxx> wrote:
> Brian,
>
> Thanks for your thoughtful response.  This is exactly the kind of feedback I
> am looking for. My comments inline.
>
>
> > first is it ought to have some synergy with pygame features that gives
> > a reason why it shouldn't be a seperate module or extension or simply
> > reference code. Like if the code does x there should be some reason
> > why a user can do x better or easier or simpler when the code is
> > included with pygame.
>
> Hmm.  Would you say the Sprite and SpriteGroup classes meet that criterion?
>
> I guess my argument here would be that it would be that resolving a
> collision is a logical next step from detecting a collision (which pygame
> already provides the functions for), so it dovetails nicely.  I think it
> would be easier when it's included because it would be right there staring
> them in the face.  I think it is a somewhat difficult problem, that seems
> simple on the surface, so users might not think to search out an external
> module, thinking it's easy to hack an algorithm out in 1 hour (I remember
> going down a couple dead ends trying to do the collision resolution in
> Subterraneman)
>
> > second is it ought to be useful in the way it appears to be useful.
> > Meaning it should lets users accomplish what they want faster or
> > easier when they think it's what they want, and it shouldn't lead
> > people down a path of trying to use it only to find it won't work or
> > uses a bad approach or something
>
> In my opinion, yes.  But I'm pretty close to the code, so I'm open to
> criticism of the API and documentation.
>
> > third (and this is really the most important thing) is someone needs
> > to do the work to make it in and stable and tested
>
> Agreed.  I can do more work here.
>
> > ... I don't
> > see an interface in your code that seems well integrated with either
> > rects or sprites to me. So if it were part of pygame would you expect
> > the interface to just be the "resolve_collisions" function that the
> > example uses, or something different?
>
> yeah, resolve_collisions is the only necessary interface to the module.  Now
> as to how to integrate this into pygame, I think it could either be a method
> of Rect (first argument, "movingRect" becomes "self") or as a standalone
> module somehow.  Suggestions?
>
> > for the second thing (being useful in a way that solves problems it
> > aims to solve)... I guess I'm not necessarily the audience for this
> > because I rarely use axis aligned rects in collision for anything but
> > a "broad phase" of collision before doing some more accurate test (in
> > which case the rect that contains the swept rect/hexagon would be just
> > as good as using the swept rect itself)
>
> This broad phase check could easily be implemented as a Strategy that looks
> like one of the CheckHexagon* Strategies, but only checks for collisions in
> "bigRect" and then returns.  Though that might necessitate changing the
> return values of resolve_collisions -- there'd be multiple xLimiters and
> yLimiters that you would then want to examine in the "narrow phase".
>
> > - for instance, you mentioned
> > this could be good for a racing game, but I can't imagine a racing
> > game that wouldn't want to rotate the rects as you turn (does this
> > handle that?)
>
> A new Strategy would need to be created, but all one should have to
> implement is the run_step method.
>
>
> > But trying to put myself in a place where rect collision is sufficient
> > - I feel compelled to say I disagree that this problem (colliding
> > along the swept movement path) "must be solved" for all the types you
> > mentioned in that category - in particular I think puzzle and rpg
> > games would be worse if you solved them that way than if you didn't.
> > In my opinion, those games are usually better off having those game
> > types use a grid and instantaneously move to any grid point that is
> > free, and then just animate the movement over time after having
> > changed grid positions, rather than trying to collide during the
> > movement animation.
>
> I agree, but I would categorize that as a top-down with a discrete map, not
> a continuous map.  It's the best terminology I could come up with.
>
> > I can see accurately finding collisions along move
> > paths as being an important issue to solve for platformers and
> > shoot-em-ups - however, I'm not sure the example demonstrates how the
> > collision resolver code as it is now properly solves things. In
> > particular the code only seems to support one moving object at a time
> > - and I'm sure in most shoot-em-up's all objects would be moving.
>
> The design is such that each moving rect would take a turn.  I know this
> allows for the rare case of two very fast moving objects to "pass through"
> each other logically.  I don't have a solution for this that is reasonably
> efficient.
>
> > Also, I don't think the code as it is properly resolves the problems
> > that I thought you said you want it to solve. Running the example I
> > can make it report a collision with multiple objects where it seems it
> > should only collide with one of the objects (like it would only hit
> > the second one if it would "pass through" the first),
>
> Are you referring to the red highlight?  The red highlight is just any
> object that was visited by the visitFn and was a *candidate* for the
> xLimiter or the yLimiter.  The objects that are returned as xLimiter and
> yLimiter at the end of resolve_collisions are the important ones when it
> comes to resolving a collision.  I have made a quick change to the example
> to make this more discernable.
>
> > and I don't see
> > the example demonstrating how this handles "if you displace the rect
> > due to a collision inside the sweep hexagon" and the displacement
> > would make follow on collisions.
>
> run the example with "pathological" as sys.argv[1], and then press left &
> down.  The first tick will demonstrate this.
>
> > of course I'm sure any objection I'd have could be solved, which
> > brings me to the third thing (someone having to do the work to
> > include) which is related to you saying "we shouldn't be content to
> > rest, providing just a wrapper to SDL" - basically providing "just a
> > wrapper to SDL" is a considerable thing
>
> Indeed.  I didn't mean to slight pygame at all.  Hope it wasn't taken that way.
>
> > we don't have precompiled binaries of pygame
> > for all platforms and python versions for the latest SDL right now, so
> > in my opinion there is a lot of pygame work that is more important
> > than this in my mind
>
> Agreed.  I don't want to distract from the thrust of getting 1.8 completed.
> I don't intend for it to be included in 1.8.  But, there's little I myself
> can contribute to the remaining 1.8 work.  This is something that I can
> contribute.
>
> > of course I could be missing the point on all this, so bottom line, I
> > think it would be much easier to be convinced that the module was both
> > useful in the context of making a complete game if there was a
> > complete game that uses the thing that you could point to and play
> > with,
>
> To complete the game I'm currently working on, that may be a long way off.
>
> > and that it would be much easier to be convinced that it
> > wouldn't cost a lot to integrate and keep bug-free if it had unit
> > tests and/or stress tests.
>
> I am working on those presently.
>
> -sjbrown
>
>
> > On Jan 1, 2008 10:49 AM,  <sjbrown@xxxxxxxxx> wrote:
> >> I don't think it's bloat, nor does it belong in a specific game engine.  A
> >> game engine is something designed to work for a particular genre of game.
> >> This is a general problem that will be seen in many types of game.
> >>
> >> Genres that this problem *must* be solved for:
> >> Platformers, Shoot-em-up, Any top-down with a continuous map (racing,
> >> puzzle, rpg), Any game with rectangle (as opposed to point) projectiles
> >>
> >> Genres that could optionally use this algorithm:
> >> Puzzles, simulations, adventure (any 2D "walking" game, including
> >> beat-em-ups), etc...
> >>
> >> In fact, I see it as the next logical step from the Rect.collide* and
> >> Sprite.*collide* functions.
> >>
> >> I started using Pygame because it was the only library that provided the
> >> tools to let me think about the interesting parts of creating a game, and
> >> took care of the boring details.  Plus, it provides a rich API that lets
> >> me
> >> write a game *well*.  This is what attracts people to Pygame, IMHO, so we
> >> shouldn't be content to rest, providing just a wrapper to SDL, instead,
> >> Pygame should aspire to providing a very rich (while being consistent,
> >> lean,
> >> and elegant) set of tools.
> >>
> >> -sjbrown
> >>
> >
> >
>
>
>
>
>