0
\$\begingroup\$

I need to spawn new villages in my grid-based game map. But i am weak in advanced math.. I need to fetch coordinates by id. These 2 constants can be other numbers. Please help with the function in javascript :)

const DISTANCE = 3;
const FIRST_VILLAGE = [0,0];

function get_coordinates_by_id (id) {
  ..
}

get_coordinates_by_id(6) // returns [0, -3]
get_coordinates_by_id(11) // returns [0, 6]
get_coordinates_by_id(2) // returns [0, 3]

enter image description here

And in addition - i want it to return the coordinates without iteration of all the previous positions. I need a formula which just simply does many calculations and without iterations. If i have billion villages, i don't want it to iterate billion times until it finds the position.

\$\endgroup\$
9
  • \$\begingroup\$ Why do you store the grid in a spiral? \$\endgroup\$
    – Bálint
    Feb 22, 2017 at 11:00
  • \$\begingroup\$ How else? I dont know the limit of players and i want to place them equally each form another \$\endgroup\$
    – mansim
    Feb 22, 2017 at 11:00
  • \$\begingroup\$ From left to right? \$\endgroup\$
    – Bálint
    Feb 22, 2017 at 11:01
  • \$\begingroup\$ What? that would be bad. I am making a game when every player can occupy grid tiles and spread their territory by occupying other player having grids \$\endgroup\$
    – mansim
    Feb 22, 2017 at 11:02
  • \$\begingroup\$ And why does a regular grid stop you from doing that? \$\endgroup\$
    – Bálint
    Feb 22, 2017 at 11:03

2 Answers 2

3
\$\begingroup\$

Sorry for the Python implementation, but according to this answer the code can be implemented like this:

from math import ceil, sqrt 
def spiral_strange(n):    
    k = ceil((sqrt(n) - 1) / 2)
    t = 2 * k + 1
    m = t**2
    t = t - 1
    if n >= m - t:
        return 3*(-k),  3*(k-(m-n))
    else:
        m=m-t
    if n >= m - t:
        return 3*(-k+(m-n)), 3*(-k)
    else:
        m=m-t
    if n >= m - t:
        return 3*(k), 3*(-k+(m-n))
    else:
        return 3*(k-(m-n-t)), 3*(k)
\$\endgroup\$
2
  • \$\begingroup\$ Your implementation of this is a lot cleaner than mine, but I decided to post my version as well to my answer, which is based on the other answer over at the Math.SE question. Anyways, this is a really clean way to do it, +1! \$\endgroup\$
    – user35344
    Feb 22, 2017 at 12:30
  • \$\begingroup\$ Thanks! It works really good :) Just now had to implement this :) \$\endgroup\$
    – mansim
    Apr 28, 2017 at 19:54
1
\$\begingroup\$

Here's a solution that doesn't involve a very tricky formula: You just iterate and calculate coordinates until you find one. The solution is in Python and could probably use some improving, but it does get the job done.

The spiral iteration code is directly ripped from this SO answer.

DISTANCE = 3
FIRST_VILLAGE = (0, 0)

def get_coordinate(id):
    if id == 1:
        return FIRST_VILLAGE
    count = 0
    for coords in spiral(id, id):
        count += 1
        if count == id:
            return (coords[0] * DISTANCE, coords[1] * DISTANCE)

    return (0, 0)

def spiral(X, Y):
    x = y = 0
    dx = 0
    dy = -1
    for i in range(max(X, Y)**2):
        if (-X/2 < x <= X/2) and (-Y/2 < y <= Y/2):
            yield(x, y)
        if x == y or (x < 0 and x == -y) or (x > 0 and x == 1-y):
            dx, dy = -dy, dx
        x, y = x+dx, y+dy

print(get_coordinate(6))
print(get_coordinate(11))
print(get_coordinate(2))

EDIT: Another alternative, which is messy but potentially faster would be based on this answer:

import math

SIZE = 3

def coordinate(n):
    coord = get_coordinate(n - 1)
    return (coord[0] * SIZE, coord[1] * SIZE)

def get_coordinate(n):
    m = math.floor(math.sqrt(n))
    if m % 2 == 1:
        k = 0.5 * (m - 1)
    else:
        if n >= m * (m + 1):
            k = m / 2
        else:
            k = m / 2 - 1

    if 2 * k * (2 * k + 1) < n <= pow(2 * k + 1, 2):
        return (n - 4*k**2-3*k, k)
    elif pow(2 * k + 1, 2) < n <= 2 * (k + 1) * (2*k + 1):
        return (k+1, 4*k**2+5*k+1-n)
    elif 2 * (k + 1) * (2*k + 1) <= n <= 4 * pow(k+1, 2):
        return(4*k**2+7*k+3-n, -k + 1)
    elif 4 * pow(k+1, 2) < n <= 2*(k + 1)*(2*k+3):
        return (-k-1, n - 4*k**2-9*k-5)

print(coordinate(6))
print(coordinate(11))
print(coordinate(2))
\$\endgroup\$
8
  • 1
    \$\begingroup\$ Nice. Since this could be run to the end of spiral many times, wonder if it is worth running once and storing a list of items {id, x, y} then doing a lookup. \$\endgroup\$
    – lozzajp
    Feb 22, 2017 at 11:32
  • \$\begingroup\$ @lozzajp You mean like caching system \$\endgroup\$
    – Bálint
    Feb 22, 2017 at 11:34
  • \$\begingroup\$ Brilliant idea, lozzajp :) \$\endgroup\$
    – mansim
    Feb 22, 2017 at 11:36
  • \$\begingroup\$ Yeah caching is definitely a good idea. \$\endgroup\$
    – user35344
    Feb 22, 2017 at 11:39
  • 1
    \$\begingroup\$ Is the player constantly connected? A cache on the server could still work and just ask for a request. \$\endgroup\$
    – lozzajp
    Feb 22, 2017 at 11:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .