# Find X,Y Spiral positions by given ID. Hard formula.

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]


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.

• Why do you store the grid in a spiral? Feb 22, 2017 at 11:00
• How else? I dont know the limit of players and i want to place them equally each form another Feb 22, 2017 at 11:00
• From left to right? Feb 22, 2017 at 11:01
• 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 Feb 22, 2017 at 11:02
• And why does a regular grid stop you from doing that? Feb 22, 2017 at 11:03

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)

• 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!
– user35344
Feb 22, 2017 at 12:30
• Thanks! It works really good :) Just now had to implement this :) Apr 28, 2017 at 19:54

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))

• 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. Feb 22, 2017 at 11:32
• @lozzajp You mean like caching system Feb 22, 2017 at 11:34
• Brilliant idea, lozzajp :) Feb 22, 2017 at 11:36
• Yeah caching is definitely a good idea.
– user35344
Feb 22, 2017 at 11:39
• Is the player constantly connected? A cache on the server could still work and just ask for a request. Feb 22, 2017 at 11:49