Re: [pygame] exact algebraic numbers?
Michael George schrieb: Hello, For my game I need to represent right isosceles triangles, and do operations including translation and rotation in 15 degree increments. Unfortunately, I cannot tolerate rounding error, because it will cause bad visual and gameplay artifacts. I'm thinking of representing points as vectors where the components are of the form a + b * sqrt(2) + c * sqrt(3) + d * sqrt(6) where a, b, c, and d are rationals. I believe numbers of this form are sufficient for my purposes, although I haven't worked out all the proofs yet. Anyway, I was wondering if anyone has done anything similar and can suggest a library I can use for manipulating such vectors before I go off and implement it myself. Thanks! --Mike Hi I don't think that you can avoid rounding errors, unless you use a math library that takes the math errors of the computer into account (which can differ from hardware to hardware). I'm not sure, why you want to represent points in such a complicated way, but I don't know the theory about it and I'm not a mathematician. One way to go is to accumulate the angle of a rotation (same for translation) and use the accumulated angle on a object to transform it into the right orientation (if you do use a previously rotated object then you will get much more rounding errors over time!). Using that way one would have a variable 'angle' which would be incremented in 15 degree steps (15, 30, 45,...) and use it to construct the rotation matrix (or whatever it is used to rotate). This should be precise enough. Unless you can draw using subpixels, you will have rounding errors when trying to draw the points on integer coordinates of the screen anyway. Maybe I'm wrong. ~DR0ID
Re: [pygame] exact algebraic numbers?
On Sun, Nov 29, 2009 at 5:59 AM, Michael George mdgeo...@cs.cornell.edu wrote: Hello, For my game I need to represent right isosceles triangles, and do operations including translation and rotation in 15 degree increments. Unfortunately, I cannot tolerate rounding error, because it will cause bad visual and gameplay artifacts. I'm thinking of representing points as vectors where the components are of the form a + b * sqrt(2) + c * sqrt(3) + d * sqrt(6) where a, b, c, and d are rationals. I believe numbers of this form are sufficient for my purposes, although I haven't worked out all the proofs yet. Anyway, I was wondering if anyone has done anything similar and can suggest a library I can use for manipulating such vectors before I go off and implement it myself. Thanks! --Mike hi, python 2.6 and 3.1 have a fractions module: http://docs.python.org/library/fractions.html The Fraction class inherits from the abstract base class numbers.Rational: http://docs.python.org/library/numbers.html#numbers.Rational To avoid rounding (and other numerical) errors, the typical technique is to apply the transformations each time from the identity matrix. So in a game where a rotation happens at say 1.0 - 1.444 degrees each frame, you keep count of the total rotation (eg 1.444) and apply the total rotation every frame. Rather than applying the 1.0 rotation one frame, and then applying the 1.444 rotation the next frame. Over 10,000 frames or so, you can see there would be little rounding error. You can also use integers instead of floats, but divide the value by 1,000,000 or so. eg, 1.444 degrees could be 1,444,000. Then as you do not get the floating point problems. If all of your angles are between 0-360, and the angle increments are also small it turns out ok. Python has a long type, so you can get a lot of precision this way, and avoid floating point problems somewhat. Just before you use the rotation, you can divide the number by 1,000,000 or so(1444000 / 100 == 1.444). cu.
[pygame] Announce: PygWeb2.0rc
Hello! We would like to announce we have finished working on the PygWeb website that was originally intended to replace the current site on pygame.org http://pygame.org. Although this caused some controversy and the maintainer(s) of pygame.org http://pygame.org did not seem interested, we kept working. We now have a fully functional website with the same basic functions provided by the current pygame.org http://pygame.org website, but also many new features: - a *real* user system with small profile pages, statistics, privacy settings and more - improved project management with intelligent tagging, uploading multiple screen shots, integrating youtube videos and a project of the month poll (as replacement for spotlight) - a snippets section that allows users to post small, useful snippets of source code that others may learn from or reuse. Its quite the same idea like the pygame code repository (pcr), but easier to manage and to use. It also supports tagging and bookmarking. - comments on nearly every content on the website, except for documentation and a few other pages - lots of feeds (Atom RSS), eg. for all new projects, new releases of either one special project or all projects, news, project of the month, ... - subscriptions for most content with feeds, ie. you could get a mail on every new release of your favorite game or on pygame news - full text search: Search in some subsections or the whole site - consistent markup support including most common markup languages like reStructuredText, Markdown, Textile, Creole, bbCode (its very easy to add one) for all formatted text. All text edit fields have an preview option. - timezone localization, even for anonymous users (the latter needs js) - a shiny, modern style and an option to add more styles and every user can use the style he likes best (more styles are yet to be written) - apis to access data programmatically: XML-RPC, for simple read requests, and REST, for enlarged read and write requests. A small example of use could be a check for newer version option in your game or even a possibility to directly download the new version - enclosed irc bot with some useful commands (some use the website database) and an optional announcer feature (eg. announce news or even new releases) - integrated Trac that provides a wiki, bug tracer, svn browser, plugin system (with lots of plugins out there) and more - full admin interface with some nice and useful features to administer the site easily - lots of configuration settings to change specific behavior (but with good default values) Our site is open source and if someone would like to host it we will support it and help in getting it setup. We would, of course, like to see it on pygame.org http://pygame.org, but that's up to the owner of pygame.org http://pygame.org or the community. The demo site sill runs at http://pygameweb.no-ip.org/ . There is already some data from pygame.org http://pygame.org for seriously testing content and also to show that we could successfully migrate data. The irc bot can be tested in #pygame on freenode. Just write b0t help to get a list of available commands. Besides looking for a host for the site, we would like to get some more testers and feedback. There may still be some bugs or details that could be improved. If you want a shiny, modern, new website representing your favorite python game library, get in touch! It's up to you! Regards, Julian and Devon
Re: [pygame] exact algebraic numbers?
DR0ID wrote: Michael George schrieb: Hello, For my game I need to represent right isosceles triangles, and do operations including translation and rotation in 15 degree increments. Unfortunately, I cannot tolerate rounding error, because it will cause bad visual and gameplay artifacts. I'm thinking of representing points as vectors where the components are of the form a + b * sqrt(2) + c * sqrt(3) + d * sqrt(6) where a, b, c, and d are rationals. I believe numbers of this form are sufficient for my purposes, although I haven't worked out all the proofs yet. Anyway, I was wondering if anyone has done anything similar and can suggest a library I can use for manipulating such vectors before I go off and implement it myself. Thanks! --Mike Hi I don't think that you can avoid rounding errors, unless you use a math library that takes the math errors of the computer into account (which can differ from hardware to hardware). I'm not sure, why you want to represent points in such a complicated way, but I don't know the theory about it and I'm not a mathematician. One way to go is to accumulate the angle of a rotation (same for translation) and use the accumulated angle on a object to transform it into the right orientation (if you do use a previously rotated object then you will get much more rounding errors over time!). Using that way one would have a variable 'angle' which would be incremented in 15 degree steps (15, 30, 45,...) and use it to construct the rotation matrix (or whatever it is used to rotate). This should be precise enough. Unless you can draw using subpixels, you will have rounding errors when trying to draw the points on integer coordinates of the screen anyway. Maybe I'm wrong. ~DR0ID For the curious: The reason I need exact arithmetic is not for drawing, but for collision response. I'm trying to implement a game that allows dragging of objects while maintaining the fact that they do not intersect one another. I want to be able to drag one object so that it abuts another. So if a user surrounds one object with other objects, then drags the center object away, I want them to be able to pop it back into the hole. If there's rounding errors, then it won't necessarily fit. That's the easiest example, but I'm pretty sure there are others where things won't work right. In this case, I'm dealing with very specific shapes, namely right triangles with legs of length 1. Those can be represented with integer coordinates ((0, 0), (0,1), (1,0)). However it turns out my snapping algorithm requires division, so I need rational numbers. So far, so good. But if you rotate a triangle by 45 degrees, you start needing to deal with sqrt(2) in the coordinates. For example, ((0,0), (sqrt(2)/2, sqrt(2)/2), (-sqrt(2)/2)). Luckily, numbers of the form a + b*sqrt(2) are good enough for this case, and you can still divide them exactly using integer arithmetic! Similarly, you may recall from high school geometry (I had to look it up) that a cos 30 = sqrt(3)/2. So if I allow rotation by 30 degrees, then I can represent those by a + b*sqrt(3). But it turns out that composing rotations requires multiplication, so to get 15 degrees for example, you can rotate by 45 and then back by 30, and multiplying it out you get ((0,0), (sqrt(2) + sqrt(6), -sqrt(2) + sqrt(6))/4, [left for reader]). So in general, you can represent all of the points on the unit circle in 15 degree increments using only integer arithmetic using the form a + b*sqrt(2) + c*sqrt(3) + d*sqrt(6). These are closed under multiplication and addition, still not sure about division (you might need quotients of these things in general, or worse). I need to relearn my abstract algebra. --Mike
Re: [pygame] exact algebraic numbers?
Hi Mike, Such algebraic numbers are used in computational geometry, you can take a look at CGAL http://www.cgal.org, it's a powerfull Computational geometry written in C++ (a python binding exists) and it has an algebraic kernel for exact computation of points on a circle or on a sphere. I'm not sure that it includes the transformations because it is done to maintain data structures like meshes, etc... Well you have to see if it suits your need and if the effort of installing it is woth it! Regards. Olivier 2009/11/29 René Dudfield ren...@gmail.com On Sun, Nov 29, 2009 at 5:59 AM, Michael George mdgeo...@cs.cornell.edu wrote: Hello, For my game I need to represent right isosceles triangles, and do operations including translation and rotation in 15 degree increments. Unfortunately, I cannot tolerate rounding error, because it will cause bad visual and gameplay artifacts. I'm thinking of representing points as vectors where the components are of the form a + b * sqrt(2) + c * sqrt(3) + d * sqrt(6) where a, b, c, and d are rationals. I believe numbers of this form are sufficient for my purposes, although I haven't worked out all the proofs yet. Anyway, I was wondering if anyone has done anything similar and can suggest a library I can use for manipulating such vectors before I go off and implement it myself. Thanks! --Mike hi, python 2.6 and 3.1 have a fractions module: http://docs.python.org/library/fractions.html The Fraction class inherits from the abstract base class numbers.Rational: http://docs.python.org/library/numbers.html#numbers.Rational To avoid rounding (and other numerical) errors, the typical technique is to apply the transformations each time from the identity matrix. So in a game where a rotation happens at say 1.0 - 1.444 degrees each frame, you keep count of the total rotation (eg 1.444) and apply the total rotation every frame. Rather than applying the 1.0 rotation one frame, and then applying the 1.444 rotation the next frame. Over 10,000 frames or so, you can see there would be little rounding error. You can also use integers instead of floats, but divide the value by 1,000,000 or so. eg, 1.444 degrees could be 1,444,000. Then as you do not get the floating point problems. If all of your angles are between 0-360, and the angle increments are also small it turns out ok. Python has a long type, so you can get a lot of precision this way, and avoid floating point problems somewhat. Just before you use the rotation, you can divide the number by 1,000,000 or so(1444000 / 100 == 1.444). cu. -- Rouiller Olivier 06 79 66 89 63 Résidence Léonard de Vinci App. A008 59650 Villeneuve d'Ascq
[pygame] Re: Announce: PygWeb2.0rc
On Nov 29, 7:32 am, jug j...@fantasymail.de wrote: Hello! We would like to announce we have finished working on the PygWeb website that was originally intended to replace the current site on pygame.org http://pygame.org. I'm kind of new to PyGame but the new site looks far better than the old one and, being in Django, would seem to be a huge step forward. What's the issue? Is there some reason that a better web site would not be better? S
Re: [pygame] Announce: PygWeb2.0rc
Nice work, Jug ! if clicking on the code tab, the whol website recenter and has smaller width (1024) than before. you may have to test with high browser resolution -Horst -- Horst JENS horst.j...@chello.at http://members.chello.at/horst.jens signature.asc Description: Dies ist ein digital signierter Nachrichtenteil
Re: [pygame] Re: Announce: PygWeb2.0rc
I'm only recounting what I saw and what was said, not commenting on this: The issue is some people felt Jug and the others went ahead without proper discussion before-hand. /me signs off. On Sun, Nov 29, 2009 at 8:01 AM, ssteinerX sstein...@gmail.com wrote: On Nov 29, 7:32 am, jug j...@fantasymail.de wrote: Hello! We would like to announce we have finished working on the PygWeb website that was originally intended to replace the current site on pygame.org http://pygame.org. I'm kind of new to PyGame but the new site looks far better than the old one and, being in Django, would seem to be a huge step forward. What's the issue? Is there some reason that a better web site would not be better? S -- Tyler Laing Science and Tech Editor The Phoenix Newspaper (1) 250 863-4869 University of British Columbia - Okanagan University Way Kelowna, BC UNC 109 Student Services Building
Re: [pygame] Re: Announce: PygWeb2.0rc
On Nov 29, 2009, at 12:40 PM, Tyler Laing wrote: I'm only recounting what I saw and what was said, not commenting on this: The issue is some people felt Jug and the others went ahead without proper discussion before-hand. Ok, well I'd say the results speak for themselves. I only have one question; how is updating the new site different from the old? Is the Django site still serving most things from static pages and just using the database to store comments and such, or did they use one of the little CMS doo-dads available for use with Django? S
Re: [pygame] exact algebraic numbers?
Michael George wrote: I'm trying to implement a game that allows dragging of objects while maintaining the fact that they do not intersect one another. I want to be able to drag one object so that it abuts another. Another way to approach this is to allow a tolerance when deciding whether two objects abut. If the tolerance is less than a pixel, the player won't be able to tell the difference. a + b*sqrt(2) + c*sqrt(3) + d*sqrt(6). These are closed under multiplication and addition, still not sure about division Hmm. Possibly it might be, although the formulas are going to get pretty horrendous. For example, a quick calculation shows that 1 / (a + b*sqrt(2)) = (a - b*sqrt(2)) / (a*a-2*b*b) which you can get by multiplying top and bottom by (a - b*sqrt(2)). Attempting the first stage of a similar trick using the full form, I got (a + b*sqrt*(2) + c*sqrt(3) + d*sqrt(6)) * (a - b*sqrt(2)) = (a*a-2*b*b) + (a*c-2*b*d)*sqrt(3) + (a*d-b*c)*sqrt(6) This no longer contains a sqrt(2) term, which is encouraging. Presumably one could then go on to multiply this by (a*a-2*b*b) - (a*c-2*b*d)*sqrt(3) to eliminate the sqrt(3) term, and then E - F*sqrt(6) for some E and F to be determined. But the back of my envelope is not wide enough to accommodate any more of this. As for libraries dealing with this kind of stuff, there might be something in Sage. But you're probably not going to want to bolt Sage into your game... -- Greg
Re: [pygame] exact algebraic numbers?
Greg Ewing wrote:
But the back of my envelope is not wide enough
to accommodate any more of this.
A little bit further and you would have seen the fail: sqrt(3) * sqrt(6)
= 3 * sqrt(2) and we're back where we started. However my algebra book
assures me (non-constructively) that {1, sqrt(2), sqrt(3), sqrt(6)} is
a basis for the smallest field over the rationals containing sqrt(2) and
sqrt(3), so it should be possible to divide. I just have to chase the
proofs backwards to figure out how. I'll let you know.
As for libraries dealing with this kind of stuff, there
might be something in Sage. But you're probably not going to
want to bolt Sage into your game...
Ah, I'd not seen sage, that looks cool. I agree though, prolly don't
want it as part of my game :).
--Mike
Re: [pygame] exact algebraic numbers?
Michael George wrote:
Greg Ewing wrote:
But the back of my envelope is not wide enough
to accommodate any more of this.
A little bit further and you would have seen the fail: sqrt(3) *
sqrt(6) = 3 * sqrt(2) and we're back where we started. However my
algebra book assures me (non-constructively) that {1, sqrt(2),
sqrt(3), sqrt(6)} is a basis for the smallest field over the rationals
containing sqrt(2) and sqrt(3), so it should be possible to divide. I
just have to chase the proofs backwards to figure out how. I'll let
you know.
In the end the solution came out rather nicely. Here's my
implementation (sans comparisons) for anyone who is interested.
--Mike
import fractions
from math import sqrt
FLOAT_SQRT2 = sqrt(2)
FLOAT_SQRT3 = sqrt(3)
FLOAT_SQRT6 = sqrt(6)
class Number(object):
Represents a number of the form [a1 + a2*sqrt(2) + a3*sqrt(3) + a6*sqrt(6)]/d, where ai and d are integers
__slots__ = ['a1', 'a2', 'a3', 'a6', 'd']
def __init__(self, a1=0, a2=0, a3=0, a6=0, d=1):
self.a1 = a1
self.a2 = a2
self.a3 = a3
self.a6 = a6
self.d = d
self.reduce()
def __copy__(self):
return Number(self.a1, self.a2, self.a3, self.a6, self.d)
#
# string conversions
#
def __repr__(self):
return 'Number(%d,%d,%d,%d,%d)' % tuple(self)
def __str__(self):
return '[%d%+d*sqrt(2)%+d*sqrt(3)%+d*sqrt(6)]/%d' % tuple(self)
def __unicode__(self):
return u'[%d%+d\u221a2%+d\u221a3%+d\u221a6]/%d' % tuple(self)
#
# comparison operators
#
def __eq__(self, other):
a1, a2, a3, a6, ad = self
b1, b2, b3, b6, bd = other
return ad*b1 == bd*a1 \
and ad*b2 == bd*a2 \
and ad*b3 == bd*a3 \
and ad*b6 == bd*a6
def __neq__(self, other):
return not self.__eq__(other)
def __cmp__(self, other):
# TODO
return NotImplemented
def __nonzero__(self):
return self.a1 != 0 \
or self.a2 != 0 \
or self.a3 != 0 \
or self.a6 != 0
#
# sequence operators
#
def __iter__(self):
return iter((self.a1, self.a2, self.a3, self.a6, self.d))
#
# arithmetic operators
#
def __add__(self, other):
a1, a2, a3, a6, ad = self
b1, b2, b3, b6, bd = other
return Number(bd*a1 + ad*b1,
bd*a2 + ad*b2,
bd*a3 + ad*b3,
bd*a6 + ad*b6,
ad*bd)
def __sub__(self, other):
return self + (-other)
def __mul__(self, other):
a1, a2, a3, a6, ad = self
b1, b2, b3, b6, bd = other
c1 = a1*b1 + 2*a2*b2 + 3*a3*b3 + 6*a6*b6
c2 = a1*b2 + a2*b1 + 3*a3*b6 + 3*a6*b3
c3 = a1*b3 + 2*a2*b6 + a3*b1 + 2*a6*b2
c6 = a1*b6 + a2*b3 + a3*b2 + a6*b1
cd = ad*bd
return Number(c1, c2, c3, c6, cd)
def __div__(self, other):
return self * other.inv()
def __radd__(self, other):
return self + other
def __rsub__(self, other):
return (-self) + other
def __rmul__(self, other):
return self * other
def __rdiv__(self, other):
return self.inv() * other
def __neg__(self):
return Number(-self.a1, -self.a2, -self.a3, -self.a6, self.d)
def __pos__(self):
return self
def __abs__(self):
# TODO
pass
def __complex__(self):
return complex(self.__float__())
def __float__(self):
return self.a1 + self.a2*FLOAT_SQRT2 + self.a3*FLOAT_SQRT3 + self.a6*FLOAT_SQRT6
#
# helper functions
#
def conj2(self):
conjugate the sqrt(2) portion
return Number(self.a1, -self.a2, self.a3, -self.a6, 1)
def conj3(self):
conjugate the sqrt(3) portion
return Number(self.a1, self.a2, -self.a3, -self.a6, 1)
def inv(self):
factor1 = self.conj2()
current = self * factor1
assert current.a2 == current.a6 == 0
factor2 = current.conj3()
current = current * factor2 # = self * factor1 * factor2
assert current.a2 == current.a3 == current.a6 == 0
return Number(current.d, 0, 0, 0, current.a1) * factor1 * factor2
def reduce(self):
gcd = reduce(fractions.gcd, self)
self.a1 = self.a1 / gcd
self.a2 = self.a2 / gcd
self.a3 = self.a3 / gcd
self.a6 = self.a6 / gcd
self.d = self.d / gcd
NMBR1 = Number(1,0,0,0,1)
SQRT2 = Number(0,1,0,0,1)
SQRT3 = Number(0,0,1,0,1)
SQRT6 = Number(0,0,0,1,1)
Re: [pygame] Updates to my Writing Games Tutorial.
Thanks, you guys, for the compliments. I'm also interested to hear criticism - particularly if there are sections that are difficult to read. I'm trained in Computer Science, not English, so if there are improvments I could make, let me know. sjbrown On Nov 24, 2009 7:17 AM, inigo delgado inigo.delg...@gmail.com wrote: Sorry ssteiner, it was an incomplete mail added to my nasty english... I want to say that i haven't seen this tutorial and i like it much, i've seen many tutorials of how to make -how to make animations, collissions, movements...- a game but not about to how to develop -programmatically, with patterns- a game... It can be -and it must be- because i've googled to few or because i've googled bad... but I promise you I haven't seen before a tutorial like this with so many specificated dessign patterns for games... NICE, GREAT work sjbron delicioussed -- Nota: Tildes omitidas para evitar incompatibilidades. :wq
