# 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? – Bálint Feb 22 '17 at 11:00
• How else? I dont know the limit of players and i want to place them equally each form another – mansim Feb 22 '17 at 11:00
• From left to right? – Bálint Feb 22 '17 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 – mansim Feb 22 '17 at 11:02
• And why does a regular grid stop you from doing that? – Bálint Feb 22 '17 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! – Tyyppi_77 Feb 22 '17 at 12:30
• Thanks! It works really good :) Just now had to implement this :) – mansim Apr 28 '17 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 * DISTANCE, coords * 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 * SIZE, coord * 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. – lozzajp Feb 22 '17 at 11:32
• @lozzajp You mean like caching system – Bálint Feb 22 '17 at 11:34
• Brilliant idea, lozzajp :) – mansim Feb 22 '17 at 11:36
• Yeah caching is definitely a good idea. – Tyyppi_77 Feb 22 '17 at 11:39
• Is the player constantly connected? A cache on the server could still work and just ask for a request. – lozzajp Feb 22 '17 at 11:49