Ruby Performance Question...

[Heretic86]

One thing always leads to another...

So I was thinking to myself that the way that XP at least handles certain things is completely inefficient.  Duh.

What I didnt like was how many times "for event in $game_map.events.values" is called.  And I thought it might be way faster to only grab events at matching XY coordinates.  Accordingly, hashes are WAY faster for lookups than Arrays.  So what Im trying (successfully) is to create a default replacement method for iterating through every event and only iterating through a unique merger of two arrays.  When the map is intialized, I also created two hashes (for performance) @events_at_x = {} and one for y also.  Well, not exactly how I did it.  Default hash object is based on XY coordinates and value is an array.

So youd see something like this: @events_at_x.inspect returns { 4 => [event, event, event] }, and to call @events_at_x[4] returns the array, nil if there are no events in it.

End result is that instead of iterating every single event then comparing their xy coordinates, it only grabs all events in the X column and all events in that Y column.  Im just thinking this MAY be a more efficient way to do it, despite the slight performance hit from merging the two arrays.  I am thinking it should also allow for much faster performance for other scripts if those need to do event iterations.
[script]  #--------------------------------------------------------------------------
 # * Events At XY (x, y)
 #--------------------------------------------------------------------------
 def events_at_xy(x, y)
   # Return Array of Unique Events
   return (@events_at_x

• & @events_at_y[y]).uniq
   end[/script]
  
  Im just wondering if this would be useful to anyone that might be concerned about performance with their scripts because of too much iterating through ALL events...
  
  Thoughts?

[Blizzard]

Zeriab implemented an anti-lag system with that kind of approach and I used a different system in CP than the default and it turns out that using something like this decreases performance. The expected increase in performance (when comparing to iterating through an array) doesn't happen until a larger number of events on the map.

[winkio]

The best approach would probably be a hybrid system where stationary events are kept in a 2D array, while events that move/teleport are in the current system.

[Heretic86]

Well, this is what I came up with.  I didnt seem to have much luck getting any better performance, but I figure someone that does a lot of collision checking might have use for it.

Spoiler: ShowHide

#==============================================================================
# ** Game_Map
#------------------------------------------------------------------------------
#  This class handles the map. It includes scrolling and passable determining
#  functions. Refer to "$game_map" for the instance of this class.
#==============================================================================

class Game_Map
  #--------------------------------------------------------------------------
  # * Public Instance Variables
  #
  #   Event Hashes (events_at_x and events_at_y) are updated by Event Methods
  #--------------------------------------------------------------------------
  attr_accessor :events_at_x             # Has of All Events sorted by X
  attr_accessor :events_at_y             # Has of All Events sorted by Y   
  #--------------------------------------------------------------------------
  # * Setup
  #     map_id : map ID
  #--------------------------------------------------------------------------
  def setup(map_id)
    # Put map ID in @map_id memory
    @map_id = map_id
    # Load map from file and set @map
    @map = load_data(sprintf("Data/Map%03d.rxdata", @map_id))
    # set tile set information in opening instance variables
    tileset = $data_tilesets[@map.tileset_id]
    @tileset_name = tileset.tileset_name
    @autotile_names = tileset.autotile_names
    @panorama_name = tileset.panorama_name
    @panorama_hue = tileset.panorama_hue
    @fog_name = tileset.fog_name
    @fog_hue = tileset.fog_hue
    @fog_opacity = tileset.fog_opacity
    @fog_blend_type = tileset.fog_blend_type
    @fog_zoom = tileset.fog_zoom
    @fog_sx = tileset.fog_sx
    @fog_sy = tileset.fog_sy
    @battleback_name = tileset.battleback_name
    @passages = tileset.passages
    @priorities = tileset.priorities
    @terrain_tags = tileset.terrain_tags
    # Initialize displayed coordinates
    @display_x = 0
    @display_y = 0
    # Clear refresh request flag
    @need_refresh = false
    # Set map event data
    @events = {}
    # Hashes to hold coordinates, Default Hash for each Coordinate Value
    @events_at_x = Hash.new { |hash, key| hash[key] = {} }
    @events_at_y = Hash.new { |hash, key| hash[key] = {} }
    for i in @map.events.keys
      # Create Event
      event = Game_Event.new(@map_id, @map.events[i])
      # Add to Events Hash
      @events[i] = event
      # Events indexed by X coordinates as Key, then Id as Key in Sub Hash
      @events_at_x[@events[i].x][event.id] = event
      # Events indexed by Y coordinates as Key, then Id as Key in Sub Hash
      @events_at_y[@events[i].y][event.id] = event
      # Update Map Coordinates for Event
      @events[i].map_stored_x = @events[i].x
      @events[i].map_stored_y = @events[i].y      
    end
    # Set common event data
    @common_events = {}
    for i in 1...$data_common_events.size
      @common_events[i] = Game_CommonEvent.new(i)
    end
    # Initialize all fog information
    @fog_ox = 0
    @fog_oy = 0
    @fog_tone = Tone.new(0, 0, 0, 0)
    @fog_tone_target = Tone.new(0, 0, 0, 0)
    @fog_tone_duration = 0
    @fog_opacity_duration = 0
    @fog_opacity_target = 0
    # Initialize scroll information
    @scroll_direction = 2
    @scroll_rest = 0
    @scroll_speed = 4
  end
  #--------------------------------------------------------------------------
  # * Events At XY (x, y)
  #
  #   http://stackoverflow.com/questions/5551168/performance-of-arrays-and-hashes-in-ruby
  #
  #   This is designed as a replacement for iterating through every single
  #   event in a $game_map.  Events exist in both the x and y hashes so to
  #   speed things up, the smaller hash is returned.
  #
  #   This is much faster than doing an intersection of two arrays.
  #
  #   Call by using $game_map.events_at_xy(x, y).values cuz keys (id's) are
  #   also returned.
  #--------------------------------------------------------------------------
  def events_at_xy(x, y)
    # Event is in both Hashes, return the smaller one for speed
    if @events_at_x[x].size > @events_at_y[y].size
      # Y array is Smaller so return it for less iteration
      return @events_at_y[y]
    else
      # X array is Smaller so return it for less iteration
      return @events_at_x[x]
    end
  end  
  #--------------------------------------------------------------------------
  # * Get Designated Position Event ID
  #     x          : x-coordinate
  #     y          : y-coordinate
  #--------------------------------------------------------------------------
  def check_event(x, y)
    #for event in $game_map.events.values
    for event in $game_map.events_at_xy(x, y).values
      if event.x == x and event.y == y
        return event.id
      end
    end
  end
end
#==============================================================================
# ** Game_Event
#------------------------------------------------------------------------------
#  This class deals with events. It handles functions including event page 
#  switching via condition determinants, and running parallel process events.
#  It's used within the Game_Map class.
#==============================================================================

class Game_Event < Game_Character
  #--------------------------------------------------------------------------
  # * Public Instance Variables
  #--------------------------------------------------------------------------
  attr_accessor :map_stored_x            # Position for @events_at_x
  attr_accessor :map_stored_y            # Position for @events_at_x
  #--------------------------------------------------------------------------
  # * Object Initialization
  #     map_id : map ID
  #     event  : event (RPG::Event)
  #--------------------------------------------------------------------------
  alias events_at_xy_initialize initialize
  def initialize(map_id, event)
    # Call Original or other Alias
    events_at_xy_initialize(map_id, event)
    # New Properties
    @map_stored_x = 0
    @map_stored_y = 0
  end
  #--------------------------------------------------------------------------
  # * Updates Events Location in Map Coordinates
  #--------------------------------------------------------------------------
  def update_map_x_hashes
    # Delete Old Hash Key Value Pair
    $game_map.events_at_x[@map_stored_x].delete(id)
    # Push Id into current Hash
    $game_map.events_at_x[@x][@id] = self
    # Update Map Position
    @map_stored_x = @x
  end
  #--------------------------------------------------------------------------
  # * Updates Events Location in Map Coordinates
  #--------------------------------------------------------------------------
  def update_map_y_hashes
    # Delete Old Hash Key Value Pair
    $game_map.events_at_y[@map_stored_y].delete(@id)
    # Push Id into current Hash
    $game_map.events_at_y[@y][@id] = self
    # Update Map Position
    @map_stored_y = @y
  end  
  #--------------------------------------------------------------------------
  # * Frame Update for Event
  #--------------------------------------------------------------------------
  alias events_at_xy_update update
  def update
    # Update Map X Location if stored coordinates do not match
    update_map_x_hashes if @x != @map_stored_x 
    # Update Map Y Location if stored coordinates do not match
    update_map_y_hashes if @y != @map_stored_y 
    # Call Original or other Alias
    events_at_xy_update
  end
end

#==============================================================================
# ** Game_Character
#------------------------------------------------------------------------------
#  This class deals with characters. It's used as a superclass for the
#  Game_Player and Game_Event classes.
#==============================================================================

class Game_Character
  #--------------------------------------------------------------------------
  # * Determine if Passable - Redefinition
  #     x : x-coordinate
  #     y : y-coordinate
  #     d : direction (0,2,4,6,8)
  #         * 0 = Determines if all directions are impassable (for jumping)
  #--------------------------------------------------------------------------
  def passable?(x, y, d)
    # Get new coordinates
    new_x = x + (d == 6 ? 1 : d == 4 ? -1 : 0)
    new_y = y + (d == 2 ? 1 : d == 8 ? -1 : 0)
    # If coordinates are outside of map
    unless $game_map.valid?(new_x, new_y)
      # impassable
      return false
    end
    # If through is ON
    if @through
      # passable
      return true
    end
    # If unable to leave first move tile in designated direction
    unless $game_map.passable?(x, y, d, self)
      # impassable
      return false
    end
    # If unable to enter move tile in designated direction
    unless $game_map.passable?(new_x, new_y, 10 - d)
      # impassable
      return false
    end
    # Loop all events
    #for event in $game_map.events.values
    for event in $game_map.events_at_xy(new_x, new_y).values
      # If event coordinates are consistent with move destination
      if event.x == new_x and event.y == new_y
        # If through is OFF
        unless event.through
          # If self is event
          if self != $game_player
            # impassable
            return false
          end
          # With self as the player and partner graphic as character
          if event.character_name != ""
            # impassable
            return false
          end
        end
      end
    end
    # If player coordinates are consistent with move destination
    if $game_player.x == new_x and $game_player.y == new_y
      # If through is OFF
      unless $game_player.through
        # If your own graphic is the character
        if @character_name != ""
          # impassable
          return false
        end
      end
    end
    # passable
    return true
  end
end

#==============================================================================
# ** Game_Player
#------------------------------------------------------------------------------
#  This class handles the player. Its functions include event starting
#  determinants and map scrolling. Refer to "$game_player" for the one
#  instance of this class.
#==============================================================================

class Game_Player < Game_Character
  #--------------------------------------------------------------------------
  # * Same Position Starting Determinant
  #--------------------------------------------------------------------------
  def check_event_trigger_here(triggers)
    result = false
    # If event is running
    if $game_system.map_interpreter.running?
      return result
    end
    # All event loops
    #for event in $game_map.events.values
    for event in $game_map.events_at_xy(@x, @y).values
      # If event coordinates and triggers are consistent
      if event.x == @x and event.y == @y and triggers.include?(event.trigger)
        # If starting determinant is same position event (other than jumping)
        if not event.jumping? and event.over_trigger?
          event.start
          result = true
        end
      end
    end
    return result
  end
  #--------------------------------------------------------------------------
  # * Front Envent Starting Determinant
  #--------------------------------------------------------------------------
  def check_event_trigger_there(triggers)
    result = false
    # If event is running
    if $game_system.map_interpreter.running?
      return result
    end
    # Calculate front event coordinates
    new_x = @x + (@direction == 6 ? 1 : @direction == 4 ? -1 : 0)
    new_y = @y + (@direction == 2 ? 1 : @direction == 8 ? -1 : 0)
    # All event loops
    #for event in $game_map.events.values
    for event in $game_map.events_at_xy(new_x, new_y).values
      # If event coordinates and triggers are consistent
      if event.x == new_x and event.y == new_y and
         triggers.include?(event.trigger)
        # If starting determinant is front event (other than jumping)
        if not event.jumping? and not event.over_trigger?
          event.start
          result = true
        end
      end
    end
    # If fitting event is not found
    if result == false
      # If front tile is a counter
      if $game_map.counter?(new_x, new_y)
        # Calculate 1 tile inside coordinates
        new_x += (@direction == 6 ? 1 : @direction == 4 ? -1 : 0)
        new_y += (@direction == 2 ? 1 : @direction == 8 ? -1 : 0)
        # All event loops
        #for event in $game_map.events.values
        for event in $game_map.events_at_xy(new_x, new_y).values
          # If event coordinates and triggers are consistent
          if event.x == new_x and event.y == new_y and
             triggers.include?(event.trigger)
            # If starting determinant is front event (other than jumping)
            if not event.jumping? and not event.over_trigger?
              event.start
              result = true
            end
          end
        end
      end
    end
    return result
  end
  #--------------------------------------------------------------------------
  # * Touch Event Starting Determinant
  #--------------------------------------------------------------------------
  def check_event_trigger_touch(x, y)
    result = false
    # If event is running
    if $game_system.map_interpreter.running?
      return result
    end
    # All event loops
    #for event in $game_map.events.values
    for event in $game_map.events_at_xy(x, y).values
      # If event coordinates and triggers are consistent
      if event.x == x and event.y == y and [1,2].include?(event.trigger)
        # If starting determinant is front event (other than jumping)
        if not event.jumping? and not event.over_trigger?
          event.start
          result = true
        end
      end
    end
    return result
  end  
end

Most of it is just copy and paste of existing definitions to change $game_map.events.values to $game_map.events_at_xy(x,y).values

[Blizzard]

Why aren't you just using a 2D array of arrays that contain events on their given coordinates?

@events_grid = []
(0...$game_map.width).each {|i|
    @events_grid.push([])
    (0...$game_map.height).each {|j|
        @events_grid[i].push([])
    }
}

# later, somewhere else
return @events_grid[x][y] # returns array of events on coordinate x,y

[Heretic86]

http://stackoverflow.com/questions/5551168/performance-of-arrays-and-hashes-in-ruby

The link is sort of what started this all for me.

require 'benchmark'
Document = Struct.new(:id,:a,:b,:c)
documents_a = []
documents_h = {}
1.upto(10_000) do |n|
  d = Document.new(n)
  documents_a << d
  documents_h[d.id] = d
end
searchlist = Array.new(1000){ rand(10_000)+1 }

Benchmark.bm(10) do |x|
  x.report('array'){searchlist.each{|el| documents_a.any?{|d| d.id == el}} }
  x.report('hash'){searchlist.each{|el| documents_h.has_key?(el)} }
end

#                user     system      total        real
#array       2.240000   0.020000   2.260000 (  2.370452)
#hash        0.000000   0.000000   0.000000 (  0.000695)

Hashes are much faster for lookups than arrays according to this.  Apparently not as fast as all the needed updates, and event.x == x checks.

[KK20]

I know I had to do something like this in Advance Wars. I used a 2D array instead of a hash though.

Suggestion, you can do this:

@events_grid = {}
(0...$game_map.width).each {|i|
    (0...$game_map.height).each {|j|
        @events_grid[$game_map.width * j + i] = #Whatever you want
    }
}

and

def event_at(x,y)
  return @events_grid[$game_map.width * y + x]
end

Now it's a hash that functions like a 2D array.

[Blizzard]

A hash definitely improves the speed of access, but you have to take into account that if you are using a combination of hashes and arrays like you did, you're not gaining performance. What makes arrays slower is the iteration process, not access of data. The example code I gave earlier (and the one KK20 gave) are fast because they access data directly through an index. When data is accessed like that, arrays are faster because hashes requires key hash calculation and "finding" the container (if this is a classic hash map implementation as I assume).

[LiTTleDRAgo]

how about using select / find_all ?

  def event_at(x, y)
    @events.values.select {|event| event.x == x && event.y == y }
  end

edit : changed [event.x,event.y] == [x,y] to event.x == x && event.y == y

[Blizzard]

At least use

event.x == x && event.y == y

because creating arrays is costly.

[Heretic86]

I see what you are saying about the 2d array and not hashing by index, but I dont seem to be able to get any noticable performance increases.  I am also guessing the 2d array needs to be updated when an event moves.  So maybe this idea isnt worth while after all.

[Blizzard]

The hash would need to be updated as well. This is the drawback in this technique. It will improve performance when there are a lot of events around, but it might reduce performance when a lot of events are moving at the same time because of the update overhead.