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?
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.
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.
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.
#==============================================================================
# ** 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
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
http://stackoverflow.com/questions/5551168/performance-of-arrays-and-hashes-in-ruby
The link is sort of what started this all for me.
Quoterequire '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.
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.
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).
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
At least use
event.x == x && event.y == y
because creating arrays is costly.
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.
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.