Efficient way to return all events around a position

[Tsukihime]

Suppose you have a 500x500 map with 10000 events scattered fairly uniformly throughout the map so that for any given tile, there are at most only a few events around you.


Suppose you are standing at (10, 10) and there is one event at (13, 13)


You then unleash a spell that affects all enemies within a square around the origin of the spell.


So for example if the size of the square is 5x5, then any events within the 25 tiles around the target position will be triggered.


What is an efficient way to check for this (with respect to the size of the square).


Basically, a naive solution would have it such that given a square of length n, the number of tiles to check is n^2.


How can this be improved?

 

[Quxios]

Well I haven't been programming long enough to know what methods are more efficient.  But in my opinion I would prefer using a system of inequalities instead of checking tiles inside a box.  With system of inequalities you could also check for different shapes by plugging in different math equations.

For a box you would use 4 equations, Where (x1, y1) would be top right of box and (x2, y2) would be bottom left.

event x >= box x1, event x <= box x2, event y >= box y1, event y <= box y2if they all come out to be true then the event is inside the box. (which is what by collision check does instead of checking every pixel in the box area or parameter)

What would slow this method down would be the number of events that run through this check but you would only need to run it once.  But I'm guessing that would be a problem in every other method as well since if you did tiles you would have to run through every event for every tile to see if the x,y match the tile x,y which would come out to be a lot more iterations.

 

[Heretic86]

Almost sounds like there is an Anti Lag Script available.  If that is the case, the Events will probably be stored differently so that they can be accessed more easily, usually a Hash with Key Value Pairs.  So we have to ask the OP about any Anti Lag scripts.

With an Anti Lag script, this might work:

for event in $game_map.events_hash(@x, @y)

  # Do something

end

Efficiency is not just about how to iterate every element in an Array or Hash, the way these things are stored is also exceptionally important.  For example, Self Switches.  Self Switches are stored in a global Hash, and accessed by a Key.  The Key to the Hash is the ABCD Self Switch and Map ID and is typically oodles faster than iterating through every element of an Array.  I have seen a couple of Anti Lag scripts that use a Hash to store Events instead of an Array, which requires iterating.  So something like foo = $game_map.get_events_at_xy(@x, @y) would return an Array only containing Events instead of all Events.

More info from the OP is needed.

 

[sokita]

mimic the method near_the_player, maybe? 

 

[Tsukihime]

Well I haven't been programming long enough to know what methods are more efficient.  But in my opinion I would prefer using a system of inequalities instead of checking tiles inside a box.  With system of inequalities you could also check for different shapes by plugging in different math equations.

Box check is what I would do as well, since if my box was sufficiently large, I don't want to have to iterate over every tile.

Almost sounds like there is an Anti Lag Script available.  If that is the case, the Events will probably be stored differently so that they can be accessed more easily, usually a Hash with Key Value Pairs.  So we have to ask the OP about any Anti Lag scripts.


More info from the OP is needed.

Consider three different scenarios separately. Would the implementation be different?


1. No optimizations are made. You have the default project, where returning an array of events at (x,y) requires you to iterate over every event.


2. Optimizations are made so that $game_map.events_xy(x, y) will return a collection of events whose position equals (x, y), but prioritizes compatibility with existing scripts so maintains the same interface. This means that it will return an array of events.


How the optimization is implemented is not too important; assume it is implemented efficiently and can perform in constant time somehow (index on [x, y], hashes, etc)


There might be some other useful methods provided that wouldn't cause compatibility issues, but I don't know what they might be.


3. You are free to change how events are stored and accessed. Basically, assume compatibility is not important and that if people want better performance, they will change their scripts to use your interface.


Not sure if that is the info you expected.

 

[Shaz]

If you were talking about that large a map and that many events, I'd be looking at setting up a table on the map class that contains a list of events at each grid location (events, when moving, would "remove" themselves from the current grid location and "add" themselves to the new one).


Then you just need to iterate between x1 and x2, and between y1 and y2, to find them all. Don't even need to look at other events to see where they are.


This approach was discussed in another topic a while ago about improving performance when you have lots of events.

 

[Zeriab]

So, to sum up I would suggest you consider the following three approaches.

Iterate through each event

The easiest and most compatible solution. Likely also the slowest.

Could be worth implemented to checking the performance, and for having something for testing more complex solutions against.

Iterate through events on each tile

Here you can likely leverage existing antilag scripts that surely have optimized that method to a fast hash-lookup.

Time is dependent on the size of the affected area and amount of events on each tile. If the square size really only is 5x5 then it's only 25 squares. Not really a lot.

Maybe the factor is low enough that the growth does not become an issue. Performance testing is required for answering that question.

Keep track of player-event distance

Maintain a datastructure where you map distance to events. Whenever a player or event moves an update is needed, so additional cost added there. The actual lookup will be fast. Just go through each event up to the spell distance.

You can follow a concept from most antilag scripts where you only update events coming within the relevant area. I.e. whatever the max square size is possible plus one or two.

This concept does follow the idea that it is player vs. enemy only. Should also want enemy vs. enemy then maintaining multiple distance maps can be necessary making this design a bad idea.

*hugs*

 - Zeriab

 

[Lemur]

Keep a grid going of positions, then you can easily get a 2D array range of 5 in all directions, just iterating that for events.

class Point  attr_accessor :x, :y  def initialize(x,y)    @x, @y = x, y  end  def within(n, grid)    x_range = ((@x - n)..(@x + n))    y_range = ((@y - n)..(@y + n))    x_range.flat_map { |x|      y_range.map { |y| grid[x][y] }.compact    }.compact  endend# Being lazy, I know$positions = []def make_grid(rows, columns)  Array.new(rows) { [nil] * columns }endmy_grid = make_grid(25, 25)# Keep it bi-directional for easier accessplayer = Point.new(10, 10)my_grid[10][10] = player$positions << player# Get us 50 random events50.times { |i|  found_blank = false  until found_blank do    x, y = (0..24).to_a.sample, (0..24).to_a.sample        unless my_grid[x][y]      event = Point.new(x,y)      $positions << event      my_grid[x][y] = event      found_blank = true    end  end}def where_they_be?  $positions.each { |pos| puts "#{pos.x} #{pos.y}" }end

Yes, somewhat lazy implementation, but it works. The point is only to check areas you actually need to, and that grid allows you that luxury.

 

[Lemur]

Also, this looks insanely useful on that subject: https://www.coursera.org/course/matrix

 

[Wavelength]

This is a really interesting topic!  The ABS system that I started for one of my own games used almost no optimization, and it would simply iterate through every event that could be affected by a given action to ascertain its location and calculate whether it was in the circle/cone/line/shape of the action's area of effect.  With about 100 events it's nearly lagless, but I had a feeling there was a better way, so I'm gonna follow this topic closely.

What I don't really understand, though, is why it would be more efficient to keep updating the location of every moving event every time it moves, rather than simply checking through every event at the time it's needed (e.g. when a spell is cast)?  Does this simply "distribute" the processing time that's needed in a more even manner, or does it actually reduce the total number of calculations the engine will need to make over time?

 

[Lemur]

Though if you *really* want to milk efficiency, you can use the Voxel algorithm: http://www.flipcode.com/archives/A%20faster%20voxel%20traversal%20algorithm%20for%20ray%20tracing.pdf

 

[Zeriab]

Doesn't voxels imply a 3D space? What would you plan to put in the third dimension before doing the raytracing?

*hugs*

 - Zeriab