Take the 2-minute tour ×

I'm working on an iOS game where players villages are displayed on a large kingdom map. Each village has a x,y location on that map, and each village is stored as an object in a database on a server (Parse.com).

What I want to be able to do is pull down all the villages around the current players village. Usually this would be straightforward as you would just use the shortest distance algorithm, but to use that I would need to download all of the villages in the database, and then run the algorithm on each one, then sort them according to distance from player, which is not exactly a quick/efficient way of doing it. So does anyone know of a more refined/efficient way of doing the above? what would be great would be to be able to pull down the villages around the current player actually in the query to the database, kill 2 birds with one stone so to speak, but I can't see any way to do that. I suspect the answer lies in perhaps storing more information about the location of the village in the database, so a query could pull the closest ones down without having to run an algorithm to make it happen.

Any ideas?

I'll leave this question up as I'm still interested in how to do it with basic math, the Manhatten distance approach should be ok, but for anyone using Parse.com it might be possible to use geoPoints maybe? It's a nutty idea, but I'm going to try it.

share|improve this question
Surely the x and y values are in the DB so you can query them (and use > and < in the query) ? –  Wain Sep 17 '13 at 15:50
You could do a query, to see if a number is greater or less then another number, and perhaps do that with one query on both the x and y int's, but that just gives you an absolute value, that's not the distance between points. –  Phil Sep 17 '13 at 15:53
add comment

1 Answer

up vote 1 down vote accepted

You can easily get all villages within D units of Manhattan distance away from point (X,Y) by querying for all villages matching the constraints X - D < x and x < X + D and Y - D < y and y < Y + D.

You can then do further filtering based on Euclidean distance on the client if you want to.

share|improve this answer
Thanks, Any chance of putting that into some pseudo code? Obj-c ideally :) –  Phil Sep 17 '13 at 16:04
@Phil: any specific area where you're having difficulty? IMO, the description I gave is pretty clear and should be fairly easy to implement. –  Lie Ryan Sep 17 '13 at 16:12
Thanks, I'm going to have a go at using Parse.com's geoPoints see if that works out. –  Phil Sep 17 '13 at 16:14
Try using the whereKey:nearGeoPoint types of query constraints - you'll get exactly what you're looking for. –  Hector Ramos Sep 17 '13 at 16:19
@Phil be aware that GeoPoints are proper latitude/longitude values. Representing numbers as (lat,long). The distance between (0,0) and (0,+1) is 111.312km (going from east to west along the equator). The distance between (+90,0) and (+90,+1) is 0km (North pole). If your villages are based on real world Earth coordinates, this is fine, if your villages are based on a normal "grid", you will run into problems. –  ahar083 Sep 17 '13 at 16:37
show 6 more comments

Your Answer


