Porting Spatial Hash

[Cleptomania]

Some of the first work that been completed in this project is improving collision detection performance. This has largely so far been centered around hitboxes and direct brute force polygonal collision detection. While there are still improvements to be made to that system, another desire for collision detection is to see if we can improve the spatial hashing system in Arcade.

Spatial Hashing is a technique by which objects are placed into a sort of "grid" of cells, and when performing collision checks, we need only check items which are in the cells that could possibly collide with an object in a given cell. This significantly reduces the amount of brute force collision checks which are needed, and means the algorithm can in practice support a nearly infinite number of objects.

The downside to this system, is that moving or inserting new objects has a significant cost, making it in most scenarios not suitable for objects which might move, so it is only generally used for things like walls. If by porting this system to Rust we can significantly reduce the cost of this operation, then it may open this algorithm up to be a viable path for many more scenarios.

In terms of the actual implementation of this, this may require starting to port some of SpriteList, but I am unsure to what extent or even if at all that will need done, there is a non-zero amount of coupling between SpriteList and SpatialHash in the pure python version, and having to back and forth between Rust and Python for that could cause a scenario where we don't get any improvement or even make it worse. This will need more investigation and probably won't fully be determined until we get some kind of initial implementation built out.

[codeguru42]

I'm starting on this. My branch is here: https://github.com/codeguru42/arcade-accelerate/tree/spatial-hash. I will continue to work on it through PyCon sprints at the least.

[codeguru42]

@Cleptomania I have some time today to pick back up on this and have some plans to continue in the near future. One detail I found is that BasicSprite needs to implement some traites in order to use it with SpatialHash. These include the following: Eq, PartialEq, and Hash. When I add #[derive(Eq, Hash, PartialEq)] to BasicSprite, I get the following error:

error[E0277]: the trait bound `pyo3::Py<pyo3::PyAny>: std::cmp::Eq` is not satisfied
   --> src/sprite.rs:10:5
    |
7   | #[derive(Eq, Hash, PartialEq)]
    |          -- in this derive macro expansion
...
10  |     texture: PyObject,
    |     ^^^^^^^^^^^^^^^^^ the trait `std::cmp::Eq` is not implemented for `pyo3::Py<pyo3::PyAny>`
    |
note: required by a bound in `AssertParamIsEq`
   --> /Users/l/.rustup/toolchains/stable-aarch64-apple-darwin/lib/rustlib/src/rust/library/core/src/cmp.rs:315:31
    |
315 | pub struct AssertParamIsEq<T: Eq + ?Sized> {
    |                               ^^ required by this bound in `AssertParamIsEq`
    = note: this error originates in the derive macro `Eq` (in Nightly builds, run with -Z macro-backtrace for more info)

I believe this is because the default implementation of Eq just applies (is there a more precise term here?) Eq on each field of the struct. Since we have texture: PyObject, it tries to use Eq on the texture member which doesn't implement the Eq trait.

My first instinct here is that we will need to implement our own version of the functions needed for Eq. So my question is which fields do we want to use to define that two sprite objects are "equal"?

[Cleptomania]

That’s a good question, I’m actually not sure what the answer is, because two different Sprites could have exactly the same values(texture, position, scale, rotation, etc etc) and still be completely separate objects.

I would guess they would need some kind of unique hash or something which can be evaluated?

We could also investigate starting work on Texture, however that’s gonna be quite the undertaking I think

[codeguru42]

@Cleptomania so do we implement object equality rather than structural equality?

[codeguru42]

meaning that two sprites are equal if and only if they are the exact same object in memory rather than having fields with the same values

[Cleptomania]

That would be my thinking, we could maybe implement both somehow but in general I would think we would be wanting to evaluate if it’s the exact object. @einarf might have some input on this well.

[codeguru42]

Or alternatively, we add a uuid field that we can use to identify distinct sprite objects.

[codeguru42]

That way if we clone a sprite, it could still be considered "equal" to the original because they would both have the same uuid.

[codeguru42]

I'm running into another issue while testing SpatialHash. I'm working on the add() method and have started a test like this:

    #[test]
    fn test_add() {
        let spatial_hash = SpatialHash::new(10).unwrap();
        let sprite = BasicSprite::new();
        spatial_hash.add(sprite)
    }

The problem is that the first parameter to BasicSprite::new() is a Python<'_> for the pyo3 binding. I don't know how to create one of these for testing, and this doesn't seem like a good path to go down anyway. We previously talked about creating a "pure Rust" version of classes like this and then add a pyo3 wrapper around that class. Does this still sound like a good direction to go? If so, we probably need to finish that before working any further on SpatialHash.

[codeguru42]

Additionally, the texture parameter for BasicSprite::new() is a PyObject. Maybe we need to port this to Rust as well. I see that the python version of Texture uses PIL. So I assume replacing this library is one of the biggest pieces to solve in order to port Texture to Rust. Is that a valid assumption?