4
\$\begingroup\$

I'm trying to figure out a way to move an object in a circular path. I read about Bresenham's circle algorithm, but all the codes available online draw an entire circle.

For my game, I want it so that when the ball enters a region, it'll begin to move in a circular path and when it leaves the region, it'll go back into moving in a straight path from its tangential velocity.

As of right now, I'm trying to figure out the algorithm to include in my game loop. I have the object updating its position every iteration. I use Bresenham's algorithm to decide whether to go right or go diagonal. I want it to draw the upper left portion of a circle

This is what I get:

the result

Here is my code at the moment:

# Drawing Curves with Midpt Circle Theorem
import pygame, sys, random, math
from pygame.locals import *

class Game(object):
    def __init__(self):
        pygame.init()
        self.screen = pygame.display.set_mode((400,400))


        self.screen.fill((255, 255, 255)) 
        self.jom = pygame.Rect(100,100,2,2)

    def run(self):


        running = True

        while running:
            for event in pygame.event.get():
                if event.type == QUIT:
                    running = False
                elif event.type == KEYDOWN:
                    if event.key == K_ESCAPE:
                        running = False


            pygame.draw.rect(self.screen, (0,0,0), self.jom)



            ## Center of Curvature
            centercurv = (104,103)


            ## Update Position
                ## eqn of circle (x-104)**2 + (y-103)**2 - r**2 = 0, r == 5
            #circleeqn = (self.jom.x-centercurv[0])**2 + (self.jom.y-centercurv[1])**2
            #goright = (self.jom.x+1
            eR = -2*self.jom.x+2*centercurv[0]+1
            eD1 = -2*self.jom.x - 2*self.jom.y + 2*centercurv[0] + 2*centercurv[1] + 2
            print(eR,eD1)
            if abs(eR)-abs(eD1) > 0:
                #self.jom.x += 2
                self.jom.y -= 1
                print('1')
            elif abs(eR)-abs(eD1) < 0:
                #self.jom.x+=2
                print('2')
            else:
                if eR < 0 and eD1 < 0:
                    #self.jom.x+=2
                    print('3')
                elif eR > 0 and eD1 > 0:
                    self.jom.y -= 1
                    print('4')
            self.jom.x += 1

            pygame.display.flip()

        print('Quitting')
        pygame.quit()
        sys.exit()


if __name__ == '__main__':
game = Game()
game.run()
\$\endgroup\$

1 Answer 1

3
\$\begingroup\$

Bresenham's algorithm is specifically built to draw circles with fixed-point mathematics; that is, to rasterize circles. For what you're doing you're almost certainly better off with a much more abstract representation of your circular motion — that is, you want to keep track of your character's angular velocity and to simply move it with constant angular velocity about the center point of the circle. This decouples the representation of your ball's physical state (position and velocity) from the display of that state, which is a Very Good Idea. Abstractly, this would look something like:

while (not in containing region) {
  ball.Position += deltaTime*ball.Velocity;
}
if ( entering containing region ) {
  Vector RelativePosition = ball.Position - region.CircleCenter;
  float AngularVelocity = length(ball.Velocity)/length(RelativePosition);
}
while ( in containing region ) {
  float s = sin(AngularVelocity*deltaTime);
  float c = cos(AngularVelocity*deltaTime);
  Vector newRelativePos;
  newRelativePos.x = c*ball.RelativePosition.x - s*ball.RelativePosition.y;
  newRelativePos.y = s*ball.RelativePosition.x + c*ball.RelativePosition.y;
  RelativePosition = newRelativePos;
  ball.Position = region.CircleCenter + RelativePosition;
}
if ( leaving containing region ) {
  Vector normalizedPosition = RelativePosition.normalize();
  // linear velocity is orthogonal to normalized position
  ball.Velocity.x = -AngularVelocity*normalizedPosition.y;
  ball.Velocity.y = AngularVelocity*normalizedPosition.x;
}

This essentially says 'while the ball is in free motion, just update by the usual Pnew = Pold+V*dt rule, but when the ball is contained, update the position using constant angular velocity by saying θnew = θold+ω*dt and then P = Pcenter+(RelativeP rotated by θ), where RelativeP is Pentry-Pcenter — the relative position on entry to the volume.

\$\endgroup\$
4
  • \$\begingroup\$ Thank you so much. I have not thought about angular velocity. I have a stupid question though, how did you find the newRelativePos? I couldn't exactly understand why cball.RelativePosition.x - sball.RelativePosition.y returns the new relative x value. \$\endgroup\$
    – rcs
    May 5, 2013 at 20:42
  • \$\begingroup\$ Also, how do you account for the new position not being integer values? Do you round up or round down \$\endgroup\$
    – rcs
    May 5, 2013 at 22:29
  • \$\begingroup\$ @rcs Not a stupid question at all! It's a very complicated matter. Essentially, I'm treating the RelativePosition as a vector from the region's CircleCenter to the position of the ball; this vector gets initialized as the region is entered, and then updated every tick while the ball is in the region. The 'update' is the two lines setting the x and y positions (and note that we update both x and y based off of the old values, then assign both over back to RelativePosition at once); those two lines are equivalent to multiplying by the 2d rotation matrix for rotation by &omega;*dt. \$\endgroup\$ May 6, 2013 at 6:04
  • \$\begingroup\$ (See en.wikipedia.org/wiki/Rotation_matrix for more details on rotation matrices). And I would store the position as float not just while it's in the region but all the time - it'll lead to cleaner updates. Generally I would just round-to-nearest, but how you convert from floating-point position to integer screen-space position is almost entirely up to you, and there are advantages to the different methods. \$\endgroup\$ May 6, 2013 at 6:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .