[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
Re: [pygame] The Giant - 'cool project I'm working on now' - thread.
Knapp wrote:
Yes, I thought that perhaps I did not get it also. So now that I think
I do get it. What about using to sprites and pixel perfect collision?
One would be the shape and the other would be the hole. If sprites
with holes don't work then use a bunch of sprites to create the hole's
edges.
Did I get it this time? Still not totally sure.
Another way is to use the center point of the object and set up paths
that the object must stay within that are defined by rectangles. Can
you rotate the objects?
I am not sure what you mean by drag objects along the edges of other
objects or why you would want to do it. I still feel that sprite
collision might be the way to go.
The real problem is collision response in a way, rather than collision
detection. Consider a situation where you want to place a ball at a
precise spot on a surface. You grab the ball, and move your pointer
into the surface. Then you want to slide it left or right because it's
not right where you want it. Now, since the ball is already touching
the surface, if the collision response is something like 'if
collide(ball, table): dontmove()' then you can't slide the ball, you
have to pick it up off the table and move it. That's what I mean by
sliding along a surface.
Another important example is putting something inside a hole. It's a
design game, so I don't care if objects "teleport" through other objects
while you're dragging them around. Let's say you have an area enclosed
on all sides, and an object that fits inside:
######
######
## ## OO
## ## OO
######
###### object
area
With most collision response mechanisms, you would need to position the
mouse _exactly_ in the center of the area, because otherwise the object
will be colliding with the walls of the area, so it can't move. With
the mechanism I'm working on, if you drag it anywhere near the hole, it
will pop inside.
I've thought of doing this in a pixel-perfect way (actually that would
be better for my game), but I can't think of an efficient way to do it.
I'm not sure if the algorithm I have in mind for a vector-based solution
is efficient enough, but it's at least feasible. I think it might be
possible to do it using image processing tools (I think this is related
to convolution, for example), but I don't know enough about it to go
that route.
A demo is worth a thousand words, so I've attached a little demo using
just circles which almost works if you want to play with it. Just
python circles.py There's some floating point issues so sometimes the
circles end up inside each other, but it mostly works and shows what I'm
after.
--Mike
"""
This module contains code for the dragging routines I plan to implement, but
for the simplified case where the only shapes are circles. It's still pretty
complicated, but at least in this case I can make some simplifications.
"""
from vector import *
from random import randint
import math
# TODO: something better for tolerance
eps = 0.0001
class Circle( object ):
def __init__( self, center, radius ):
self.center = center
self.radius = float( radius )
def collide( self, other ):
"returns a list of 0, 1, or 2 collision points between this circle and another"
c1,r1 = self.center, self.radius
c2,r2 = other.center, other.radius
radsq = (r1 + r2)**2
diff = c2 - c1
lensq = abs2(diff)
if lensq > radsq:
# circles are non-intersecting
return []
else:
alpha = (r1**2 - r2**2)/(2*lensq) + 0.5
gamma = sqrt(r1**2 / lensq - alpha**2)
if abs(gamma) < eps:
# two intersections are close - call them one
return c1 + alpha*diff
#return []
else:
# there are two separate intersections
return [c1 + alpha*diff + gamma*rot(diff),
c1 + alpha*diff - gamma*rot(diff)]
def contains( self, point ):
diff = point - self.center
result = abs2(diff) < self.radius**2 - eps
return result
def grow_by( self, other ):
# TODO: reconcile the semantics with the general case
return Circle( self.center, self.radius + other.radius )
def closest_point( self, point ):
relative = point - self.center
normalized = relative * self.radius / abs( relative )
return normalized + self.center
def invert( self ):
return Circle( self.center, self.radius )
def __repr__( self ):
return "Circle(" + repr( self.center ) + ", " + repr( self.radius ) + ")"
class CircleUnion( object ):
class Intersection( object ):
def __init__( self, loc, c1, c2 ):
dc1 = c1.center - loc
dc2 = c2.center - loc
# c1 -> loc -> c2 is counterclockwise, swap c1 and c2
if dot(dc1,rot( dc2 )) < -eps:
c1, c2 = c2, c1
dc1,dc2 = dc2, dc1
self.loc = loc
self.c1 = c1
self.dc1 = dc1
self.c2 = c2
self.dc2 = dc2
self.bumped = self.loc + (dc1/abs(dc1) + dc2/abs(dc2))
def __repr__( self ):
return 'Intersection at ' + repr( self.loc ) + ' centers ' + repr( self.c1.center ) + ' and ' + repr( self.c2.center )
class Component( object ):
def __init__( self, circle ):
self.circles = [circle]
self.intersections = []
def contains( self, point ):
for c in self.circles:
if c.contains( point ):
return True
return False
def closest_point( self, x ):
"""Finds the closest point to x on the boundary of this component,
assuming that x lies within the component"""
if len(self.intersections) == 0:
return self.circles[0].closest_point( x )
# find closest intersection to x
_, closest = min( [(abs2(ix.bumped - x),
ix) for ix in self.intersections] )
# translate intersection to origin
dx = x - closest.loc
dc1 = closest.dc1
dc2 = closest.dc2
# check if x is in the arc of c1
if dot(dx, dc1) > 0 and dot(dx, rot(dc1)) > 0:
return closest.c1.closest_point( x )
# similarly if x is in the arc of c2
if dot(dx, dc2) > 0 and dot(dx, rot(dc2)) < 0:
return closest.c2.closest_point( x )
# if neither, the closest point to x must be the intersection of the two.
return closest.loc
def __init__( self, circles ):
# compute the list of intersections
intersections = []
for i in range( 0, len(circles) ):
c1 = circles[i]
for j in range(0,i):
c2 = circles[j]
intersections += [CircleUnion.Intersection( loc, c1, c2 ) for loc in c1.collide( c2 )]
# build the connected components
# TODO: this is inefficient
components = dict( [(c, CircleUnion.Component(c)) for c in circles] )
for ix in intersections:
comp = components[ix.c1]
comp.intersections.append( ix )
if components[ix.c2] != comp:
comp.intersections += components[ix.c2].intersections
for c in components[ix.c2].circles:
comp.circles.append( c )
components[c] = comp
self._comp_map = components
self._comp_set = frozenset( components.values() )
# discard intersections that are contained in some circle
for comp in self._comp_set:
comp.intersections = filter( lambda ix: not filter( lambda circ: circ.contains( ix.loc ), comp.circles ), comp.intersections ) # TODO: this is too slick
def closest_point( self, x ):
for comp in self._comp_set:
if comp.contains( x ):
return comp.closest_point( x )
return x
def shadow( obstacles, object ):
return CircleUnion( [o.grow_by( object ) for o in obstacles] )
################################################################################
## Demo code ##
################################################################################
def rundemo():
import pygame
screen = pygame.display.set_mode((800,600))
paper = pygame.Surface((800,600))
paper.fill((255,255,255))
class CSprite( pygame.sprite.Sprite ):
def __init__( self, x, y, r ):
pygame.sprite.Sprite.__init__( self )
self.rect = pygame.Rect( x - r, y - r, 2*r, 2*r )
self.circle = Circle( Vec(x,y), r )
self.image = pygame.Surface( (2*r, 2*r) ).convert()
self.image.set_colorkey( (0,0,0), pygame.RLEACCEL )
pygame.draw.circle( self.image, (0, 0, 255), (r,r), r, 1 )
def set_pos( self, pos ):
self.rect.center = int(pos.x), int(pos.y)
self.circle.center = pos
class Demo( object ):
def __init__( self, N ):
self.circles = pygame.sprite.RenderUpdates()
for i in range(0,N):
to_add = CSprite( randint( 100, 700 ), randint(100, 500), randint(20, 100) )
to_add.set_pos( shadow( [c.circle for c in self.circles], to_add.circle ).closest_point( to_add.circle.center ) )
self.circles.add( to_add )
# self.circles.add( CSprite( 250, 300, 75 ) )
# self.circles.add( CSprite( 400, 150, 75 ) )
# self.circles.add( CSprite( 550, 300, 75 ) )
# self.circles.add( CSprite( 400, 300, 75 ) )
self.dragging = None
self.offset = None
self.shadow = None
self.background = paper
self.debug = False
def mousedown( self, point ):
dragging = None
for c in self.circles:
if c.circle.contains( point ):
dragging = c
if dragging:
self.offset = dragging.circle.center - point
self.shadow = shadow( [c.circle for c in self.circles if c != dragging], dragging.circle )
if self.debug:
self.background = paper.copy()
for comp in self.shadow._comp_set:
r,g,b = randint(64,192), randint(64,192), randint(64,192)
for c in comp.circles:
pygame.draw.circle( self.background, (r+32,g+32,b+32), (c.center.x, c.center.y), c.radius, 1 )
for ix in comp.intersections:
pygame.draw.circle( self.background, (r,g,b), (ix.loc.x, ix.loc.y), 3 )
pygame.draw.circle( self.background, (r,g,b), (ix.bumped.x, ix.bumped.y), 2 )
screen.blit( self.background, (0,0) )
pygame.display.flip()
self.dragging = dragging
def mouseup( self, point ):
self.dragging = None
if self.debug:
self.background = paper
screen.blit( paper, (0,0) )
self.circles.draw( screen )
pygame.display.flip()
def mousemove( self, point ):
if self.dragging:
newpos = self.shadow.closest_point( point + self.offset )
pygame.draw.circle( screen, (0,128,0), newpos - self.offset, 3 )
self.dragging.set_pos( newpos )
def run( self ):
pygame.mouse.set_visible( 1 )
pygame.event.set_allowed( None )
pygame.event.set_allowed( pygame.constants.MOUSEBUTTONDOWN )
pygame.event.set_allowed( pygame.constants.MOUSEBUTTONUP )
pygame.event.set_allowed( pygame.constants.MOUSEMOTION )
pygame.event.set_allowed( pygame.constants.KEYUP )
pygame.event.set_allowed( pygame.constants.QUIT )
screen.blit( paper, (0,0) )
self.circles.draw( screen )
pygame.display.flip()
while True:
event = pygame.event.wait()
self.circles.clear( screen, self.background )
if event.type == pygame.constants.QUIT:
sys.exit( 0 )
elif event.type == pygame.constants.KEYUP and event.key == pygame.constants.K_ESCAPE:
break
elif event.type == pygame.constants.KEYUP and event.key == pygame.constants.K_TAB:
self.debug = not self.debug
elif event.type == pygame.constants.KEYUP and event.key == pygame.constants.K_RETURN:
for c in self.circles:
print c.circle
for comp in self.shadow._comp_set:
for ix in comp.intersections:
print ix
elif event.type == pygame.constants.MOUSEBUTTONDOWN:
self.mousedown( Vec( *event.pos ) )
elif event.type == pygame.constants.MOUSEBUTTONUP:
self.mouseup( Vec( *event.pos ) )
elif event.type == pygame.constants.MOUSEMOTION:
self.mousemove( Vec( *event.pos ) )
pygame.display.update( self.circles.draw( screen ) )
Demo( 7 ).run()
if __name__ == '__main__':
rundemo()
#
# vim: ts=4 sw=4 ai
#
from math import sqrt
################################################################################
class Vec:
def __init__( self, x, y ):
self.x = float(x)
self.y = float(y)
def __iadd__( self, other ):
self.x += other.x
self.y += other.y
return self
def __isub__( self, other ):
self.x -= other.x
self.y -= other.y
return self
def __idiv__( self, other ):
self.x /= other.x
self.y /= other.y
return self
def __imul__( self, other ):
self.x *= other
self.y *= other
return self
def __add__( self, other ):
return Vec( self.x + other.x, self.y + other.y )
def __sub__( self, other ):
return Vec( self.x - other.x, self.y - other.y )
def __mul__( self, other ):
return Vec( self.x * other, self.y * other )
def __rmul__( self, other ):
return self * other
def __div__( self, other ):
return Vec( self.x / other, self.y / other )
def __rdiv( self, other ):
return None
def __abs__( self ):
return sqrt( self.x*self.x + self.y*self.y )
def __neg__( self ):
return Vec( - self.x, - self.y )
def __repr__( self ):
return "Vec( %s, %s )" % (repr( self.x ), repr( self.y ))
def __str__( self ):
return "Vec( %s, %s )" % (self.x, self.y)
def __getitem__( self, index ):
return (self.x,self.y)[index]
def __len__( self ):
return 2
def dot(a, b):
return a.x * b.x + a.y * b.y
def abs2( v ):
return dot( v, v )
def rot( v ):
"rotate a vector one-quarter turn clockwise. This could be called the 2D cross product"
return Vec( v.y, -v.x )