Irregular perimeter in Ruby code

Question

I came across a situation where I'd like to improve my code, but don't really have a clue about what I could do... It's for a game I'm making, I want to get a perimeter surrounding a unit, but I don't want tiles inside the perimeter. I'm pretty sure there is a better way to do this. (@x and @y are the unit's coordinates)

r = 4
radius = []
for x in @x-r..@x+r
 for y in @y-r..@y+r
 radius.push([x, y]) if $game_map.passable?(x, y) 
 end
end
radius.delete_if {|a|
 radius.include?([a[0] + 1, a[1]]) &&
 radius.include?([a[0] - 1, a[1]]) &&
 radius.include?([a[0], a[1] + 1]) &&
 radius.include?([a[0], a[1] - 1])
}

There are some things that I simplified here to focus on the problem, like the local variable 'r' that would not be constantly 4. What matters is how to handle radius so it gives the same result without having to add the coordinates that will be removed.

Performance is important as this function is called frequently by many units.

• tokland: Please a give some assert test (or a couple) in the form "If I have this @x, @y and r, I want this value in radius"
• Alex: The thing is that the perimeter is irregular, I need at least two couples of coordinates by row and by column. r is there as a limit, a range. If the perimeter was a rectangle, then I could easily add something in my loop like: next if ! ([@x-r, @x+r].include?(x) || [@y-r, @y+r].include?(y))
• Eric Walker: Is this for a homework problem?
• Eric Walker: Also, have you seen any performance penalty with the current approach?
• Alex: No, it's for a personal project. And well, it's not particularly good since the program adds useless values and then evaluates them all. I wonder if there would be some kind of algorithm which can simply add the necessary values so I don't have to use delete_if. Also, as you may have noticed, with my current solution I need to get all the values I normally wouldn't want in order to make the evaluations. This function is quite frequently, so improving this part of the code will make a difference.

Answer 1

Better late than never - Anon

first make it work, then make it right, and, finally, make it fast. - Kernighan & Johnson

Rules of optimization: (1) Don't. (2) (for experts only) Don't yet. (3) Profile before optimizing

First make it work, then make it right

There's a bug. If $game_map#passable? always returns true, the coordinates returned by this code are in this pattern:

XXXXXXXXX
X-X-X-X-X
XX-X-X-XX
X-X-X-X-X
XX-X-X-XX
X-X-X-X-X
XX-X-X-XX
X-X-X-X-X
XXXXXXXXX

Based on your description, you are (or were) looking for this pattern:

XXXXXXXXX
XXXXXXXXX
XXXXXXXXX
XXX---XXX
XXX---XXX
XXX---XXX
XXXXXXXXX
XXXXXXXXX
XXXXXXXXX

The trouble is here:

 radius.delete_if {|a|
 radius.include?([a[0] + 1, a[1]]) &&
 radius.include?([a[0] - 1, a[1]]) &&
 radius.include?([a[0], a[1] + 1]) &&
 radius.include?([a[0], a[1] - 1])
 }
 radius

One fix is to replace those lines with:

 radius.reject do |x, y|
 x.between?(@x - 1, @x + 1) && y.between?(@y - 1, @y + 1)
 end

and finally, make it fast

With the above fix, the code works, so let's benchmark it. 10,000 iterations of it take 0.600 seconds on my box.

We can do better. Instead of adding coordinates just to remove them later, how about not adding them in the first place?

 r = 4
 radius = []
 for x in @x-r..@x+r
 for y in @y-r..@y+r
 next if x.between?(@x - 1, @x + 1) && y.between?(@y - 1, @y + 1)
 radius.push([x, y]) if $game_map.passable?(x, y)
 end
 end
 radius

This is simpler, but is it faster? Just a bit. 10,000 iterations now take 0.500 seconds instead of 0.600. More important, though, it's simpler.

There doesn't seem to be much room for optimization here, which leads to these questions:

• Is the program fast enough?
• If not, which part of the program is the bottleneck?

You can't answer those questions without profiling. That's why the first code you write should be clear and correct. Then, only if it isn't fast enough, profile to learn where it's too slow, and optimize that part. Repeat until it's fast enough, then stop.

The reason to optimize later rather than earlier is because optimization has a cost. It increases the complexity of the code, often leading to code that's harder to read and maintain. It's no good to pay that cost unless you're getting actual benefit from it.

An OOP issue

This code should probably be in GameMap:

class GameMap
 ...
 def passable_coords_near(x, y)
 r = 4
 radius = []
 for x in (x - r)..(x + r)
 for y in (y - r)..(y + r)
 next if x.between?(x - 1, x + 1) && y.between?(y - 1, y + 1)
 radius.push([x, y]) if passable?(x, y)
 end
 end
 radius
 end
 ...
end