Movement code for a game that should be able to handle almost infinite coordinates

Now I've grasped the very basics of Pygame, I thought it'd be useful to make a few classes that I could use later on if I try make a simple RPG style game. I've done this to handle the coordinates for the player movement (and possibly for other things too), and tried to do it in a way where you wouldn't get the floating point precision errors that Minecraft and similar games get when you travel out very far.

I tested it against the decimal module, and mine appeared to up to 10x faster for small movements, though the speeds evened out when using super large movements like +- 10000000000000.

It's only half a days worth of work so it's not perfect, I can't find any more bugs though. It's recommended you input the coordinates as strings though if you're using large ones to start with, especially if you're using floats.

class Movement(object):
"""This was built to allow large coordinates to be stored without
causing any floating point precision errors.
It is faster than the decimal module, especially with processing
large amounts of small movements.

It works by breaking down the coordinates into 'blocks', where each
new block is the squared amount of the previous one.
The method is very similar to the base number system, in which a
block size of 10 will split 235.9 into [5.9, 3, 2].

A large block size is faster than a small one, though the precision
will be worse. At 16 digits, Python can't store any more decimals,
so definitely keep it under that.
"""

BLOCK_SIZE = 65535
COORDINATES = range(3)

def __init__(self, x=0, y=0, z=0, block_size=None):
"""Convert the starting coordinates into the format accepted
by the class.

>>> m = Movement('15',
...              '-31564.99933425584842',
...              '1699446367870005.2')
>>> m.player_loc
[[15.0], [-31564.99933425585], [38640.2, 17514, 2485, 6]]

>>> print m
(15.0, -31564.9993343, 1699446367870005.2)
"""

#Set a new block size if needed
if block_size is not None:
self.BLOCK_SIZE = block_size

#Store the initial coordinates
self.player_loc = [self.calculate(self._get_integer(i),
self._get_decimal(i))
for i in map(str, (x, y, z))]

def __repr__(self):
"""This needs improving, currently it just converts back to
the absolute coordinates."""
return 'Movement({}, {}, {})'.format(*self._convert_to_world())

def __str__(self):
"""Print the absolute coordinates."""
return str(tuple(self._convert_to_world())).replace("'", "")

def __getitem__(self, i):
"""Return an absolute value for X, Y or Z.

Parameters:
i (int): Index of coordinate.
"""
try:
return self._convert_to_world()[i]
except IndexError:
MovementError.index_error_coordinate()

def __setitem__(self, i, n):
"""Set an absolute value for X, Y or Z.

Parameters:
i (int): Index of coordinate.

n (int/float): New value to set.
"""
n = str(n)
try:
self.player_loc[i] = self.calculate(self._get_integer(n),
self._get_decimal(n))
except IndexError:
MovementError.index_error_coordinate()

@classmethod
def _get_integer(self, n):
"""Convert the input to an integer.

Parameters:
n (str): Integer to convert.

>>> Movement._get_integer('15.35321')
15
"""
return int(n) if '.' not in n else int(n.split('.'))

@classmethod
def _get_decimal(self, n):
"""Get the decimal number from the input.

Parameters:
n (str): Decimal to convert.

>>> Movement._get_decimal('15.35321')
35321
"""
return 0 if '.' not in n else int(n.split('.'))

def calculate(self, amount, decimal=0):
"""Convert the coordinate into a block.

Parameters:
amount (int/str): Total value without any decimals.

decimal (int, optional): The decimal value as an integer
without the leading '0.'.

>>> Movement().calculate(128)
[128.0]
>>> Movement().calculate(128, 5176)
[128.5176]
>>> Movement().calculate(4294836224)
[65534.0, 65534]
>>> Movement().calculate(4294836225)
[0.0, 0, 1]
"""
coordinate = []
amount = int(amount)
negative = amount < 0
multiplier = int('-1'[not negative:])

if negative:
amount *= -1

while amount > self.BLOCK_SIZE - 1:
remainder = amount % self.BLOCK_SIZE
amount = (amount - remainder) / self.BLOCK_SIZE
coordinate.append(int(remainder * multiplier))
coordinate.append(int(amount * multiplier))

decimal = float('0.' + str(int(decimal)))
coordinate += decimal * int('-1'[not coordinate < 0:])

return coordinate

def _move(self, direction, amount, final_run=False):
"""Add the coordinate to a block.

Parameters:
direction (int): Represents X, Y, or Z as a number.

amount (int/float): Amount to add or subtract from the
coordinate.

>>> m = Movement(135, 426.42, -1499941.5002)
>>> print m
(135.0, 426.42, -1499941.5002)

>>> m.move(100, -5133.100532, 5)
>>> print m
(235.0, -4706.680532, -1499936.5002)
"""

#Fix to keep decimals on large numbers
if not final_run and amount > self.BLOCK_SIZE:
decimal = self.player_loc[direction] % 1
if '.' in str(amount):
decimal += float('0.' + str(amount).split('.'))
self.player_loc[direction] += int(amount)
else:
self.player_loc[direction] += amount

#Recalculate and add blocks if needed
i = 0
while i < len(self.player_loc[direction]):

stop = True
current_block = self.player_loc[direction][i]
while not -self.BLOCK_SIZE < current_block < self.BLOCK_SIZE:
stop = False

remainder = current_block % self.BLOCK_SIZE
new_addition = int(current_block - remainder) / self.BLOCK_SIZE
if i:
remainder = int(remainder)
self.player_loc[direction][i] = remainder

try:
self.player_loc[direction][i + 1] += new_addition
except IndexError:

#Break execution if higher blocks are not edited
if stop:
break

i += 1

#Add the final decimals if a large number was input
try:
self._move(direction, decimal, final_run=True)
except UnboundLocalError:
pass

def move(self, x, y, z):
"""Update the coordinates with a new relative location."""
for i, amount in enumerate((x, y, z)):
if amount:
self._move(i, amount)

def _convert_to_world(self):
"""Convert the blocks into absolute coordinates as a string."""

#Convert coordinates back to numbers, without using floats
coordinates = [sum(int(amount) * pow(self.BLOCK_SIZE, i)
for i, amount in enumerate(coordinate))
for coordinate in self.player_loc]

#Add the decimal points as strings
coordinates = [(str(coordinates[i])
+ '.'
+ str(float(self.player_loc[i])).split('.'))
for i in self.COORDINATES]

#Fix for numbers between -1 and 0
for i in self.COORDINATES:
if (len(self.player_loc[i]) == 1
and str(self.player_loc[i]).startswith('-0.')):
coordinates[i] = '-' + coordinates[i]
return coordinates

class MovementError(Exception):
"""Custom movement exceptions."""
@classmethod
def index_error_coordinate(self):
raise MovementError('coordinate index out of range')

if __name__ == '__main__':
import doctest
doctest.testmod()

In response to the comment by holroy, I decided to keep with float (as opposed to store the decimal value as a separate int) because I've still got to think about conversion to and from the game world. With the current way, unless the float value goes above the block size, it's literally just a single addition, whereas the other way would be a lot slower, and the precision to that level isn't really needed.

I did the block method in a previous project which was about octrees, where the coordinates were stored relative to each 3D block, which was split into 8 smaller blocks (so a coordinate would be [(1, 1, 1), (-1, 1, 1), (1, 1, -1), (-1, -1, 1)] for 4 nested blocks, which results in (5, 13, 11). The problem with this approach is if a coordinate was at 16, that's too high to store, so you'd need to recalculate everything for 5 blocks instead of 4 (which upon writing this, I've realised it may be as simple as multiplying all of block 4 by -1, though I'm not sure).

The boundaries can also be a bit confusing, as the size of the block is -(2^x)+1 to 2^x, like -255 to 256.

I wanted this to be able to scale as much as needed, without getting overly complicated, and the current way seems to accomplish this fine.

• Since python supports seemingly arbitrarily large integers, why do you use decimals with limited precision at all? If you want to have block coordinates and coordinates with in the block, then why not make the coordinate a tuple of (block, sub-block coordinate), where both values are integers? – holroy Nov 8 '15 at 19:30
• What I really are aiming at, is could you explain a little more why you have chosen this design on how to handle the coordinates? – holroy Nov 8 '15 at 19:33
• Updated the question with some of the points you mentioned, I'm never great at wording stuff so let me know if some parts need to be clearer – Peter Nov 9 '15 at 0:58

_get_integer and _get_decimal

A lot to say here. First, you’ve got a bug. Consider float('.0') and float('3.') which are valid calls that anyone may expect to work alike with your Movement class. Unfortunately, both Movement('.0') and Movement('3.') fails. This is due to an empty string being returned as one part or the other of the split('.'). And int('') is not valid.

An other thing to note, here, is that both functions will always be called together. And that they both convert the same argument into a string to split it right after. It’s redundant. Better have only one function that will split the string and return both the integral and the decimal part as a tuple. Moreover, it’ll be easier to fix the bug stated above:

def split_decimal_part(number):
n = str(number)
try:
integral, decimal = n.split('.')
except ValueError: # no '.' in n
return int(n), 0
else:
# Account for either integral or decimal being ''
return int(integral) if integral else 0, int(decimal) if decimal else 0

Last and not least: do not confuse yourself between @classmethod and @staticmethod. Class methods are implicitly passed the class instance as first parameter (usualy named cls) and not self which is an instance of the class. Static methods does not have implicit parameters at all. They just use the class or the instance type as a namespace. Since you make no use of the class parameter of your @classmethods, they should be @staticmethods instead.

On @classmethod again

The usual way to define custom exceptions is just:

class MyCustomException(Exception):
pass

you then raise it with any custom message you want. What is important to note, is that you raise it explicitly wherever you need to. Using a static method (instead of the class method you used) to do it for you is not common and impairs readability. If you really need to save on typing predifined error messages you can either:

• store them as constants/class attributes;
• define them as default value for the constructor.

On reinventing the wheel

There is a bunch of built-ins that you could use to simplify the reading of your code. For insance divmod, math.copysign or zip. You’re also using two methods for building your string outputs where they very much look alike.

Lastly, _move is very unintuitive with its two passes, its decimal flag (yes it takes a while to figure out it is both some kind of flag and some values stored) and its stop one. The least intuitive thing, however, is how you differentiate things whether you’re adding more or less than a block size on a given axis. That lead to all issues stated above. You should add the decimal parts and then take care of the integral ones using your block approach.

And since you access self.player_loc[direction] a lot, you should make it a local variable.

Proposed improvements

from math import copysign
from itertools import count, repeat, izip, chain

class Movement(object):
"""This was built to allow large coordinates to be stored without
causing any floating point precision errors.
It is faster than the decimal module, especially with processing
large amounts of small movements.

It works by breaking down the coordinates into 'blocks', where each
new block is the squared amount of the previous one.
The method is very similar to the base number system, in which a
block size of 10 will split 235.9 into [5.9, 3, 2].

A large block size is faster than a small one, though the precision
will be worse. At 16 digits, Python can't store any more decimals,
so definitely keep it under that.
"""

BLOCK_SIZE = 65535

def __init__(self, x=0, y=0, z=0, block_size=None):
"""Convert the starting coordinates into the format accepted
by the class.

>>> m = Movement('15',
...              '-31564.99933425584842',
...              '1699446367870005.2')
>>> m.player_loc
[[15.0], [-31564.99933425585], [38640.2, 17514, 2485, 6]]

>>> print m
(15.0, -31564.9993343, 1699446367870005.2)
"""

#Set a new block size if needed
if block_size is not None:
self.BLOCK_SIZE = block_size

#Store the initial coordinates
self.player_loc = [self.calculate(*self._split_decimal_part(i))
for i in (x, y, z)]

def __repr__(self):
"""This needs improving, currently it just converts back to
the absolute coordinates."""
return 'Movement{}'.format(self)

def __str__(self):
"""Return the absolute coordinates."""
return '({}, {}, {})'.format(*self._convert_to_world())

def __getitem__(self, i):
"""Return an absolute value for X, Y or Z.

Parameters:
i (int): Index of coordinate.
"""
try:
return self._convert_to_world()[i]
except IndexError:
raise MovementError(MovementError.COORDINATE_INDEX_ERROR)

def __setitem__(self, i, n):
"""Set an absolute value for X, Y or Z.

Parameters:
i (int): Index of coordinate.

n (int/float/str): New value to set.
"""
try:
self.player_loc[i] = self.calculate(*self._split_decimal_part(n))
except IndexError:
raise MovementError(MovementError.COORDINATE_INDEX_ERROR)

@staticmethod
def _split_decimal_part(n):
"""Split the input into its integral part and its decimal part.

Parameters:
n (str/int/float): Integer to convert.

>>> Movement._split_decimal_part('15.35321')
(15, 35321)
"""
n = str(n)
try:
integral, decimal = n.split('.')
except ValueError:
return int(n), 0
else:
return int(integral) if integral else 0, int(decimal) if decimal else 0

def calculate(self, amount, decimal=0):
"""Convert the coordinate into a block.

Parameters:
amount (int/str): Total value without any decimals.

decimal (int, optional): The decimal value as an integer
without the leading '0.'.

>>> Movement().calculate(128)
[128.0]
>>> Movement().calculate(128, 5176)
[128.5176]
>>> Movement().calculate(4294836224)
[65534.0, 65534]
>>> Movement().calculate(4294836225)
[0.0, 0, 1]
"""
amount = int(amount)
multiplier = int(copysign(1, amount))
amount *= multiplier

coordinate = []
while amount >= self.BLOCK_SIZE:
amount, remainder = divmod(amount, self.BLOCK_SIZE)
coordinate.append(remainder * multiplier)
coordinate.append(amount * multiplier)

decimal = float('0.{}'.format(decimal))
coordinate += decimal * multiplier

return coordinate

def _move(self, direction, amount):
"""Add the coordinate to a block.

Parameters:
direction (int): Represents X, Y, or Z as a number.

amount (int/float): Amount to add or subtract from the
coordinate.

>>> m = Movement(135, 426.42, -1499941.5002)
>>> print m
(135.0, 426.42, -1499941.5002)

>>> m.move(100, -5133.100532, 5)
>>> print m
(235.0, -4706.680532, -1499936.5002)
"""
axis = self.player_loc[direction]
amount_blocks = self.calculate(*self._split_decimal_part(amount))
overflow = 0

for amount, base, i in izip(axis, chain(amount_blocks,repeat(0)), count(0)):
total = amount + base + overflow
negatif = total < 0
overflow, remainder = divmod(-total if negatif else total, self.BLOCK_SIZE)
axis[i] = -remainder if negatif else remainder
overflow = int(-overflow if negatif else overflow)

for amount in amount_blocks[i+1:]:
total = amount + overflow
negatif = total < 0
overflow, remainder = divmod(-total if negatif else total, self.BLOCK_SIZE)
axis.append(-remainder if negatif else remainder)
overflow = -overflow if negatif else overflow

negatif = overflow < 0
overflow = -overflow if negatif else overflow
while overflow > 0:
overflow, remainder = divmod(overflow, self.BLOCK_SIZE)
axis.append(-remainder if negatif else remainder)

def move(self, x, y, z):
"""Update the coordinates with a new relative location."""
for i, amount in enumerate((x, y, z)):
if amount:
self._move(i, amount)

def _convert_to_world(self):
"""Convert the blocks into absolute coordinates as a string."""

#Convert coordinates back to numbers, without using floats
coordinates = [sum(int(amount) * self.BLOCK_SIZE**i
for i, amount in enumerate(coordinate))
for coordinate in self.player_loc]

#Add the decimal points as strings
coordinates = ['{}.{}'.format(coord, str(location).split('.'))
for coord, location in zip(coordinates, self.player_loc)]

#Fix for numbers between -1 and 0
for i, location in enumerate(self.player_loc):
if len(location) == 1 and (-1 < location < 0):
coordinates[i] = '-' + coordinates[i]
return coordinates

class MovementError(Exception):
"""Custom movement exceptions."""
COORDINATE_INDEX_ERROR = 'coordinate index out of range'

if __name__ == '__main__':
import doctest
doctest.testmod()

A word on accuracy and speed

Since you have specific needs as regard to speed and accuracy, you may find that writing functions to factorize some code may be slower than explicitly writing the same kind of call. That's why I didn't try to remove redundancy in _move.

You may still have room for improvement though: __getitem__ does not need to compute all 3 axis before returning the required one; _convert_to_world can iterate over self.player_loc one less time using:

coordinates = [str(sum(int(amount) * self.BLOCK_SIZE**i
for i, amount in enumerate(coordinate)))
+ '.' + str(coordinate).split('.')
for coordinate in self.player_loc]

In the end it's up to your requirements that you can consider readability and maintenance improvements.

• Thanks for the feedback, I'll reply to a few of the more basic points. Good idea with the decimals, I hadn't noticed I only used them together haha. And with '@classmethod', I tend to throw it in if __init__ isn't needed, but it's usually an afterthought, so at least now I have a better idea of how/when to use it. I've never used divmod or math.copysign but looking at your code they seem so much nicer than my version, and I was thinking zip would run a lot slower. As to '{}.{}'.format(), I'd done a quick test and found that x+'.'+x ran so much faster, even if it does look worse. – Peter Nov 10 '15 at 14:32
• @Peter found some time to edit in the changes for _move. As far as performances are concerned, I didn't test anything. Neither speed, nor float accuracy. So some advices might not suit you, indeed. – Mathias Ettinger Nov 10 '15 at 15:15
• Thanks a lot for the help, I'll go over everything you've done tonight or tomorrow when I get time. Like I'd mentioned in the post, as long as there's enough precision for smooth movement, accuracy isn't really important, since you wouldn't notice slight errors anyway. As long as something is relatively similar speed wise, that's fine (like a couple of function calls in _move is ok, just not hundreds), I'm mainly just being overly cautious based on previous experience aha. – Peter Nov 10 '15 at 18:19
• Hey, sorry for the wait, I'm currently trying out the code and attempting to fix a bug with your overflow part. For example, Movement('124151.4',0,0).move('11286.45',0,0) comes out with Movement(4294906127.85, 0.0, 0.0), It should be [4367.85, 2] but your code results in [4367.85, 1, 1], I know why it's doing that part, just need to figure out why it's happening when it shouldn't be :P – Peter Nov 14 '15 at 12:54
• I couldn't figure out the fix, so I turned it into a very simple version based on yours that works correctly as far as I can tell - pastebin.com/s0Zh0LJ0 – Peter Nov 14 '15 at 13:24