# Detecting Units on a Grid

I am making a little turn based strategy game in pygame, that uses a grid system as the main map to hold all the characters and the map layout. (Similar to Fire Emblem, or Advance Wars)

I am trying to determine a way to quickly and efficiently (i.e. without too much of a slow down) check if there are any characters within a given range of the currently selected character.

So to illustrate:

O = currently selected character
X = squares within range

Range of 1:

X
X O X
X

Range of 2:

X
X X X
X X O X X
X X X
X

Range of 3:

X
X X X
X X X X X
X X X O X X X
X X X X X
X X X
X

Now I have to tell the user who is in range, and I have to let the user choose who to attack if there are multiple enemies in range.

If I have a 5x5 grid, filled with " " for empty and numbers for the characters:

[ ][ ][ ][ ][4]
[ ][1][ ][ ][ ]
[ ][ ][ ][ ][ ]
[ ][ ][2][3][ ]
[ ][ ][ ][ ][ ]

Depending on which character the user selects, I would like to show the user which other characters are in range. So if they all had a range of 3:

• 1 can hit 2
• 2 can hit 1 or 3
• 3 can hit 2
• 4 cannot hit anyone.

So, How do I quickly and/or efficiently run though my grid and tell the user where the enemies are?

PS- As a bonus, if someone could give an answer that could also work for a minimum distance type range, I would give them a pat on the back and a high five, should they ever travel to Canada and we ever meet in life.

For example: Range of 3 to 5: (- is out of range)

X
X X X
X X X X X
X X X - X X X
X X X - - - X X X
X X X - - O - - X X X
X X X - - - X X X
X X X - X X X
X X X X X
X X X
X
• What have you tried so far? Have you tried a naive solution that turns out to be too slow? Jun 20, 2012 at 19:29
• I believe hammy is waiting until he can answer his own question to supply that information. He said he was going to answer it but I removed that as irrelevant to the question. Perhaps it wasn't... Jun 20, 2012 at 19:32
• I have to wait 8 hours to post the full version of what I've tried, as Byte said, but I basically started to check all the squares in cross pattern. So it would not check diagonally from the origin. It only checked the squares within the range vertically and horizontally. It worked for a range of 1 since there is no diagonals then, but a range of 2+ does not work Jun 20, 2012 at 19:36
• Also, why isn't the range a circle? There are directions where the characters does not see as far? Jun 20, 2012 at 19:39
• @Apoc Well its on a grid, so that kind of is a circle. The range is the same thing as a radius. The units can 'see' 3 grid squares away Jun 20, 2012 at 19:41

Iterate through all the enemies in the map and calculate the distance between each enemy and the player. If the distance is equal to 1, they are within range 1, equal to 2, within range 2.

If you have too many units and it is slowing you down. You need to divide your map into sections. And have your enemies/player be part of a section. Then you only iterate through all the enemies within the same section of the map as your player. If you happen to do the implementation, check out Wackidev's comment, he is pointing out a problem that you could probably run into.

• What if the player is on the edge of a section? You also need to check all 8 surrounding sections. +1 this is definitely the first thing to try. Jun 20, 2012 at 20:19
• You are right. But at first I'd leave the map division solution out unless it is really necessary. But I doubt that OP's game is that big that it will slow down the game. Jun 20, 2012 at 20:28
• hmmm, the only problem with this is, I'd have to check all surrounding sections not just if on the edge, but also if the range goes beyond the edge. So even if 4 squares away and the range is 5, I would then have to check 9 of the sections, and if each of those sections where say 10x10, thats 900 checks. I think that might be a bit slow. Jun 20, 2012 at 20:36
• I think you misunderstood the solution. You don't check all the squares in each sections, you simply check all the ennemies, within that section. Or simply all the ennemies in the map. I'm sure you have some sort of container with all the units in your map. ANd again the section solution is not necessary. Jun 20, 2012 at 20:39

you have three options:

1. iterate through all characters and filter on weather they are in range or not (most stupid but simple to implement)
2. search on the grid everything that is within range. requires links from the map to characters
3. put every character in a search tree (eg kd-tree) to quickly find everything that is within range. This requires knowledge about search trees, but they are not too difficult to understand
int minRange = 2;
int maxRange = 4;
for(int x = playerLoc.x - maxRange; x <= maxRange + playerLoc.x; ++x) {
for(int y = playerLoc.y - maxRange; y <= maxRange + playerLoc.y; ++y) {
int range = Math.abs(playerLoc.x - x) + Math.abs(playerLoc.y - y);
if(range >= minRange && range <= maxRange) {
}
}
}

If you decide to allow diagonal movement someday, you can just change the range variable's calculation.

• That code doesn't work, the logic is correct, but no matter the playerLoc, it would only grab the range from the origin. Changing the addUnitToTargetList(mapgrid.getCharacterAt(x, y)); to: addUnitToTargetList(mapgrid.getCharacterAt((x+playerLoc.x), (y+playerLoc.y))); addUnitToTargetList(mapgrid.getCharacterAt((-x+playerLoc.x), (y+playerLoc.y))); addUnitToTargetList(mapgrid.getCharacterAt((x+playerLoc.x), (-y+playerLoc.y))); addUnitToTargetList(mapgrid.getCharacterAt((-x+playerLoc.x), (-y+playerLoc.y))); fixes it however. Aug 3, 2012 at 14:36
• You are correct, there was a small bug. I have edited my post to fix the loop condition because I felt it was cleaner.
– Jim
Aug 3, 2012 at 14:57
• Hmmm, it's still not quite working for me. I got it to work when the player location is (3,3), but when trying (5,5) it didn't work. Havn't even tried different x-y's such as (2,6) yet. Aug 3, 2012 at 17:02
• Are you correctly handling cases of mapgrid.getCharacterAt(x,y) looking at invalid grid positions?
– Jim
Aug 4, 2012 at 15:09
• Sorry for the late response. Oh I got it, thanks! I had and error in changing the code from your language (Java?) to Python, but I got it fixed and its the algorithm is working beautifully, thanks a lot! Aug 7, 2012 at 15:00