# Pygame: circular motion with Bresenham's algorithm

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: 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)**2 + (self.jom.y-centercurv)**2
#goright = (self.jom.x+1
eR = -2*self.jom.x+2*centercurv+1
eD1 = -2*self.jom.x - 2*self.jom.y + 2*centercurv + 2*centercurv + 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()


## 1 Answer

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.

• 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. – rcs May 5 '13 at 20:42
• Also, how do you account for the new position not being integer values? Do you round up or round down – rcs May 5 '13 at 22:29
• @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. – Steven Stadnicki May 6 '13 at 6:04
• (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. – Steven Stadnicki May 6 '13 at 6:06