Day 4: Fantastic Bits

I have started day 4 of 100 days of code with a CodinGame code clash and there a user (namely twilk) mentioned, that I am at the top of the silver league.

I thought it would be a good thing to leave the Mars Lander for a day and moving up to the gold league.

So I have spent a bit more than one hour with Fantastic Bits and my code.

Prior to this I have had a very basic logic without simulation. So I thought it would be great to add a simulation “engine” to calculate the next position of objects based on their speed — without collisions.

My calculations look like this in “pseudo code”:

  • calculate the difference between the current position and the target position
  • calculate the distance between the current position and the target position
  • calculate the angle between the current position and the target position
  • calculate a speed vector based on the angle
  • based on the speed vector calculate the next position after the step
  • calculate the velocity after the step

Fairly simple and there is no collision calculation — but it took me quite some hours to figure out this calculations. Here is my code of the steps above:

def distance2(a, b):
    return (a[0] - b[0])**2 + (a[1] - b[1])**2

def distance(a, b):
    return math.sqrt(distance2(a,b))

def predict_next_round(unit, target, thrust, mass=1, friction=0.75):
    dist = distance(unit, target)
    diff_x, diff_y = target[0]-unit[0], target[1]-unit[1]
    angle = math.atan2(diff_y, diff_x)
    speed_x = math.cos(angle) * (thrust/mass) + unit[2]
    speed_y = math.sin(angle) * (thrust/mass) + unit[3]
    next_x = round(unit[0] + speed_x)
    next_y = round(unit[1] + speed_y)
    next_vx = round(speed_x * friction)
    next_vy = round(speed_y * friction)

    return next_x, next_y, next_vx, next_vy

The two distance methods are differentiated because calculating the square root is slow and sometimes you do not need the distance but can work with the squared distance.

The function predict_next_round takes 3 mandatory and 2 optional parameters:

  • unit is the object which we will calculate the next position (wizard, snaffle or bludger)
  • target is a pair with x and y coordinates of the target position
  • thrust is the thrusting power into the direction
  • mass is the mass of the unit, it defaults to 1 which is the mass of a wizard
  • friction is the friction of the unit, it defaults to 0.75 which is the friction of both wizards and snaffles

And the calculation works — at least with wizards. For other types I did not try it. This will be the next step: calculate the movement of the snaffle after thrown by me, then for the opponents.

After this is done I will add a calculation based on applying magic like Flipendo or Accio.

One more point is missing: simulate the next round without knowing the target based only on the parameters like current position and velocity…

Alternatively it is possible to model the information of units in classes. In this case I always have to know which parameter in a tuple represents what value — and with the usage of classes I could align my solution to those of great players with C++ solutions like Magus. But I think I will create named tuples for units, that is somewhere between the current state and OOP.

However I do not have any idea currently how to utilize this simulation to get better results in the competition. I am thinking about the following:

  • see if fired snaffle is heading into the right direction and will arrive in the goal
  • see if the snaffle encounters an opponent wizard

Feel free to share your thoughts / ideas with me!

And I reached gold league without any code change. Patience pays off.

Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s