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.

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