How to calculate positions of holes in a game board?

I'm making a game with Python->PyGame->Albow and ran into a problem with board generation. However I'll try to explain the problem in a language agnostic way. I believe it's not related to python.

I've split the game board generation into several parts.

Part one generates the board holes.

Holes are contained in a list/array. Each hole object has a mapping of angles relating to other holes which are surrounding it, each of those holes also links back to it. (Sort of like HTML DOM siblings, the difference being any angle is possible)

A hole is something like:

hole = {
    empty: True,
    links: {
        90: <other hole>,
        270: <another hole>,
        etc...
    }
}

Part two, calculate hole positions. The code is something like this.

def calculate_position(hole):
    for linked_hole in hole.links:
        if linked_hole.position == None:
            #calculate linked hole's position relative to this hole
            linked_hole.position = [position relative to first hole]
            calculate_position(linked_hole)

first_hole.position = (0, 0) #x, y
calculate_position( first_hole )

Part three, draw board.

Find the window height, expand the positions of holes (calculated in step two) to fit the window. Draw everything.

I believe that the problem is in step two I am calculating every hole relative to a previous hole. Rounding errors add up and the board goes squint shaped the further away from the starting hole the holes are and the bigger the board is. This only happens when making boards that aren't rectangular because otherwise there aren't rounding errors.

I am using simple trigonometry to calculate the relative positions of holes by converting the angle into radians and using built in sin/cos functions.

Any idea as to a solution or if I'm mistaken as to the problem is useful :)

PS: I will post the source code if it would help however feel it will clutter things up

Thanks for all the answers.

The people who said rounding probably wasn't going to be an issue were spot on. I had another look through the code with that in mind. I'm embarrassed to say I was generating the wrong angles in the first part of the board generation, the rendering part was correct.

I've marked Norman's answer as correct because it explains how to use a linear combination of vectors to solve the problem.


Asked by: John222 | Posted: 06-12-2021






Answer 1

If hole positions are stored as integers, I don't doubt rounding error accumulates quickly enough to kill you. If hole positions are stored as floating point, and if you have an error of one unit in the last place (ULP) at each computation, I'm not quite sure how quickly error accumulates—but if error doubles at each step, then you have at most 53 links before even double-precision floating point would go wrong.

If you want to be rock-solid accurate, I would represent each position as a linear combination of vectors. You can represent each vector by its angle, and you have just a few angles, so you can represent the position of a hole as something like

Take six 30-degree steps and two 90-degree steps and four 180-degree steps

The numbers six, two, and four will be exact, and once you've computed all positions as vectors, you can then do the trig to convert to (x, y) coordinates all at one go. If you're worried about speed you can cache the arctangent of each angle and it will even be fast.

If this description is too terse, let me know.

Answered by: Sydney842 | Posted: 07-01-2022



Answer 2

The bit about accuracy becomes relatively important as soon as we realize these points are going to be converted to pixel coordinates, a.k.a. integers. Accumulate an error of 0.5 and bam! You're one pixel off.

So, either there is a huge problem with accuracy and rounding errors are climbing very very fast, or the source of the issue is elsewhere. I'm looking at this in step in particular:

expand the positions of holes (calculated in step two) to fit the window

Until I see a screenie, I'll assume "squint" means 'oval-kinda-sorta-thing'; sounds exactly what a bug in this step could produce.

Answered by: Madaline376 | Posted: 07-01-2022



Answer 3

I hate to be the one to suggest this, but, start in the the center. Also, you should look at your code and double check for an unfortunate conversion. The is, if a hole ends up at "138.2, 150.8", you need to keep the fractional parts until you have computed the next hole.

Answered by: Darcy473 | Posted: 07-01-2022



Similar questions

python - How to calculate positions of new points after image rotation

I am trying to get a positions of new points P1_r(x1_new, y1_new) and P2_r(x2_new, y2_new) after image rotation using imutils.rotate_bound(). Original image contain line defined by points P1(x1, y2) and P2(x2, y2). import imutils import numpy as np P1 = np.array([x1, y1]) P2 = np.array([x2, y2]) The starting position is as f...


python - How can I calculate the positions of Jupiter and Saturn?

Jupiter and Saturn have just met up in the sky. Where can I look for them? When will they do it again? PyEphem seems to be a standard programming tool for performing this kind of calculation, but how can it be employed in this instance?


python - How to calculate the positions of new points after rotating the image around arbitrary axis

Having a dataset of aligned objects, I would like to augment it by applying random rotations with the axis at the center of the object. Below is the rotation representation (left original, right image rotated around the point (xc, yc). for rotation, I have used the following logic: import cv2 import random image_source = cv2.imread('sample.png') height, width = image_source.shape[:2] random_angle = random.un...


python - Calculate position on 1 dimension axis with start and stop positions, time to travel and elapsed time

I'm struggling a bit with this simple math. Given one dimensional plane and: start position (can be positive and negative) end position (can be positive and negative) time to travel (always positive) calculate position after a defined time What I came out with is the following code, but something makes me think I should not calculate negative speed and somehow do i...


python - What's the best way to calculate a 3D (or n-D) centroid?

As part of a project at work I have to calculate the centroid of a set of points in 3D space. Right now I'm doing it in a way that seems simple but naive -- by taking the average of each set of points, as in: centroid = average(x), average(y), average(z) where x, y and z are arrays of floating-point numbers. I seem to recall that there is a way to get...


How Python calculate number?

This question already has answers here:


python - Calculate score in a pyramid score system

I am trying to calculate gamescores for a bunch over users and I haven't really got it yet. It is a pyramid game where you can invite people, and the people you invite is placed beneth you in the relations tree. So if i invite X and X invites Y i get kickback from both of them. Let's say 10%^steps... So from X i get 10% of his score and 1% from Y, and X get 10% from Y. So to calculate this i was thi...


How to calculate a mod b in Python?

Is there a modulo function in the Python math library? Isn't 15 % 4, 3? But 15 mod 4 is 1, right?


To calculate the sum of numbers in a list by Python

My data 466.67 465.56 464.44 463.33 462.22 461.11 460.00 458.89 ... I run in Python sum(/tmp/1,0) I get an error. How can you calculate the sum of the values by Python?


python - How to calculate a date back from another date with a given number of work days

I need to calculate date (year, month, day) which is (for example) 18 working days back from another date. It would be enough to eliminate just weekends. Example: I've got a date 2009-08-21 and a number of 18 workdays as a parameter, and correct answer should be 2009-07-27. thanks for any help


python - How to calculate the scrape URL for a torrent

I've read the Bit-torrent specification and done a number of searches, trying to find out how I can get the seeds/peers/downloaded data from a torrent tracker (using Python). I can calculate the info hash from a Torrent no problem, which matches up with the info hash given by various working torrent applications. However, when I try to get the information from the tracker I either timeout (the tracker is working) o...


datetime - How to use Python to calculate time

I want to write python script that acts as a time calculator. For example: Suppose the time is now 13:05:00 I want to add 1 hour, 23 minutes, and 10 seconds to it. and I want to print the answer out. How do I do this in Python? What if date is also involved?


c# - Calculate percent at runtime

I have this problem where I have to "audit" a percent of my transtactions. If percent is 100 I have to audit them all, if is 0 I have to skip them all and if 50% I have to review the half etc. The problem ( or the opportunity ) is that I have to perform the check at runtime. What I tried was: audit = 100/percent So if percent is 50 audit = 100 /...


python - Calculate time between time-1 to time-2?

enter time-1 // eg 01:12 enter time-2 // eg 18:59 calculate: time-1 to time-2 / 12 // i.e time between 01:12 to 18:59 divided by 12 How can it be done in Python. I'm a beginner so I really have no clue where to start. Edited to add: I don't want a timer. Both time-1 and time-2 are entered by the user manually. Thanks in advance for your help.






Still can't find your answer? Check out these communities...



PySlackers | Full Stack Python | NHS Python | Pythonist Cafe | Hacker Earth | Discord Python



top