Keith
The Kaioru Blog

The Kaioru Blog

Finding the Perfect Spatial Data Structure for a 2D Platforming Game Server

Finding the Perfect Spatial Data Structure for a 2D Platforming Game Server

All roads lead to RTree

Keith's photo
Keith
·Sep 2, 2022·

7 min read

Table of contents

  • The Problems
  • Solutions
  • Benchmarks
  • Conclusion
  • Resources

One of my favourite passion projects I'm working on is a re-implementation of the server of a specific 2D mushroom game which shall not be named. And one of the things I've hit a roadblock on was spatial data.

See, in the game, there are maps full of collision data such as floors, walls, and even slopes (which I guess you might consider floors). And as a server that has to verify potentially thousands of movement data, my current implementation of iterating through every single floor object and finding the one the player was standing on was not going to cut it.

Here, I'll be sharing some ways I've experimented with, benchmarked on, and some musings on the entire process.

The Problems

Well the first step to finding a data structure is to know what problems we are trying to solve in the first place. And I've narrowed it down to these 2:

  1. Finding the floor the player is standing on
  2. Finding the floor the player is above

The second point sounds a little redundant but I promise its different! Imagine this: A player is falling from the sky onto the ground. While in the sky, the player drops an item (that would fall straight down to the ground). The server needs to know the floor object that item will fall onto, and thus: we need to find the floor object the player is above.

Also, as an added limitation, floor objects were basically line segments like so:

struct Floor {
  Point2D Start;
  Point2D End;
}

Point2D being a struct with just integer X, Y values.

Solutions

.. an Array?

Okay so, with no prior knowledge to any spatial data structures, my first thought was to break down the gigantic list of floor objects into smaller sized chunks.

Well how do we break them into smaller sized chunks? We use the positional property of the floor objects! Because floor objects would exist on a 2D plane, we could get the bounds of that plane and then chop em' up into smaller chunks. Kinda like those flat square Classified Chicken Pizza from Dominoes.

To first get the boundaries of the plane, I would iterate through all the floor objects (during load) and get the leftmost X, topmost Y, rightmost X, and bottommost Y values. And with the boundaries, I set the 'pizza slice size' to be 50x50.

Then, I would create a nested array kinda like so:

floors = new Floor[(top - bottom) / 50, (right - left) / 50];

And then sort all the existing floor objects into their respective arrays.

So what does this solve? Given a player object at a specific location, what the server now computes is which 'pizza slice' the player is on -- this is computationally cheap like so:

var nested = floors[(player.y - bottom) / 50, (player.x - left) / 50];

And from there, we can iterate through the nested array and find what we need to find!

Analysis

Okay okay, yes I know probably still not the greatest. But in one of my projects, I've actually ran with this solution for awhile and it ran pretty OK.

Although there was definitely lesser iterations versus iterating the entire list of floor objects, one thing I realised was that the amount of floor objects in each nested array could vary drastically. For example when many floor objects are condensed into a small area.

This made me extremely uneasy. One of the main goals of the project was efficiency, and this was not quite it.

RTree

You see, reading this blog post and seeing the jump from an array to an RTree might seem pretty normal to you but in reality, it took me weeks of research and exploration into the various different types of spatial data structures but I digress.

Without going into to much detail into how RTrees work, RTrees can search with a given bound and return all floor objects in that bound (if any).

So how will this solve our 2 problems?

  1. When looking for floor objects the player is standing on, we could just search the RTree with the player's current position.
  2. When looking for floor objects the player is above, we could search the RTree with the player's current position all the way to the bottom bound of the map.

Challenges

Okay, now that we got that out of the way, one tiny teensy issue still stands: elements in the RTree are indexed with a rectangular box. So when our floor object is a slope, it will look kind of like so:

IMG_60A6094EA22F-1.jpeg

Imagine the red part of the drawing being the floor object and the bounding box being black. So as long as our search includes the positions in that bounding box, it would return it as a result.

I'm pretty sure the answer has already came to your minds but to just give some perspective, my formal education in mathematics stopped at quadratic equations about 7 years ago now in secondary school. I wasn't the brightest kid.

So after my short fling with Khan Academy for about 3 months, I have gained more intuition on segments and realised I could verify if a point falls on a line by ensuring the total distance of the point and the start of the floor and the point and the end of the floor is the the same as the length of the floor object.

Anyway, with that information, I just simply added a check after the search and voila! It works and solves our problems.

Benchmarks

Okay look, I'm not just gonna implement something new that's theoretically faster and call it a day. I need to benchmark it, to quantify it (as they say), to bask in all the glory of the numbers I've cut.

By comparing a plain ol' array to RBush (C# implementation of RTree) these were the results:

  1. Finding floor object player is on
MethodPointMeanErrorStdDevRank
RBushPoint (9000, 9000)95.84 ns0.287 ns0.269 ns1
RBushPoint (0, 0)721.77 ns8.947 ns7.471 ns2
RBushPoint (429, 290)931.71 ns2.262 ns1.889 ns3
ArrayPoint (9000, 9000)19,159.15 ns17.328 ns15.361 ns4
ArrayPoint (429, 290)34,256.11 ns102.668 ns91.013 ns5
ArrayPoint (0, 0)40,552.03 ns798.794 ns784.523 ns6
  1. Finding floor object player is above
MethodPointMeanErrorStdDevRank
RBushPoint (9000, 9000)105.6 ns0.37 ns0.32 ns1
RBushPoint (0, 0)276.6 ns0.13 ns0.13 ns2
RBushPoint (429, 298)366.1 ns0.38 ns0.32 ns3
ArrayPoint (9000, 9000)76,319.4 ns48.41 ns40.42 ns4
ArrayPoint (429, 298)78,222.4 ns48.99 ns45.82 ns5
ArrayPoint (0, 0)78,715.4 ns28.76 ns26.90 ns5

Conclusion

I think it is quite evident in my case to work with RTree.. But let me put my motivational speaker hat on for a moment and say: don't let problems scare you, even if you don't currently have the knowledge to solve them, more often than not you will find a solution through exploration and research.

But who am I to say? I am but just a student struggling through university.

Resources

All my work and benchmarks are found on my repo: Foothold

Also, all this work is actually being used here! check it out: Edelstein

  • Note when looking through is that the Y-axis in the projects are flipped. (Lower Y value signifies up, vice versa)
 
Share this