Retrieve all events on a particular tile

[Tsukihime]

So here's the problem: given an (x, y) position (on the map), return all events on that position

Currently, the way the game does it is to simply loop over every event on the map and select all of the events whose x and y values match the specified position.

def events_xy(x, y) @events.values.select {|event| event.pos?(x, y) }endIs it necessary to find ways to improve this?How much of a bottleneck does this approach really have, given that on average maps do not have more than 1000 events anyways?

I mean, it's only called every step you take so realistically it's not too bad, since the default engine assumes that only the player will need to actually check every event on the map at every step.

 

[Galv]

I believe events also do that check each step they take. So each of those 1000 events would check 1000 times each step they take to make sure no other event is blocking their step.


I've been playing around with that recently and instead of checking each event for x,y positioning, I set it up to store event id's in a hash instead (using [x,y] as the key with array of id's as vlue) each time they take a step. This was just a test to see improvement and on a map with 999 events on it, I got an improvement of 15-25 FPS.


Perhaps there is a faster way to store data in a grid?

 

[Zeriab]

That is a known bottleneck in XP and VX.

From Galv's test the same seems to hold true for Ace.

I used that principle in my RMXP Antilag script which significantly increases the collision detection algorithm.

On top of this I build a positive list of events. Those that needs to be updated each frame, that is visible and special events. Note that this is an actual functional change.

Additionally I use the map for creating/disposing sprites on the fly as the move in and out of the visible area.

All these elements combine to typically give quite a significant performance increase for XP games.

*hugs*

 - Zeriab

 

[Tsukihime]

I had done a tutorial on collision detection and passage settings just a few weeks ago and already forgot that the check involves looping over all events lol


I was just randomly looking at this method and thought "well, this seems kind of silly" but it's good to see that work has been done on this.

 

[Kaelan]

I believe events also do that check each step they take. So each of those 1000 events would check 1000 times each step they take to make sure no other event is blocking their step.

I've been playing around with that recently and instead of checking each event for x,y positioning, I set it up to store event id's in a hash instead (using [x,y] as the key with array of id's as vlue) each time they take a step. This was just a test to see improvement and on a map with 999 events on it, I got an improvement of 15-25 FPS.

Perhaps there is a faster way to store data in a grid?

Storing them in a 3D array (map width x map height x event array size) is more efficient than storing them in a hash. I'm using that in my game to do fast collision between players, events & the mouse, it works pretty well.

Edit: It's generally also more efficient to update it once per frame (on map update) instead of once every time someone or something takes a step. If you had 1000 events walking simultaneously, you'd be updating 1000 times per frame.

 

[Tsukihime]

Wouldn't it be possible for two people to completely walk through each other without the game noticing because one happens to walk very fast?

 

[Kaelan]

Yeah, that's a classic problem in collision detection, which you usually solve with continuous collision detection (CCD). But it's only one you should try to solve if you know you actually have a use case for it, since it increases the cost of collision checks by a lot (and even then, personally I'd only run it specifically for fast-moving objects and turn it off for everything else).

 

[Tsukihime]

There's the bug where if an event and a player that are facing each other move at the same time, they can literally swap positions without triggering anything.


While it is rather difficult to come across (or maybe not, I don't know my timing isn't that great), I guess it's not as important.

 

[Kaelan]

They would have to move on exactly the same frame, which should be pretty rare. If you're really worried about that, an alternative is to have events update the tile they were in and the tile they moved to in the grid whenever they move. You mainly want to avoid updating the whole grid when a single event moves.

 

[Tsukihime]

Oh that's what you meant by updating it once per frame.


I interpreted that as queuing up all of the moves that are made and then updating the grid once per frame, even if someone may have moved several times in one frame.