Find objects near a point in the world *fast*!

[ataulien]

Right now we don't have any kind of acceleration structure to find stuff being near a character. We would have to query all the objects every time and that's just too slow to do for so many characters.

Usecase

Imagine figuring out which items are close to the character so we can take on into focus (Draw it's name on top of it).

Also monsters will later need to check whether a character is within a certain range for them to get angry.

Some ideas on how this could be implemented

I think we can get away with only taking objects into account which have the Focusable-component attached to them.

The class GameWorld has a list of all important objects in the scene. To keep the GameWorld-class clean, I would propose creating a small class which is then instantiated inside GameWorld, for example (pseudo code):

class FocusablesInRange
{
    HFocusable findClosestFocusableWithinRadius(position, radius);
    bs::Vector<HFocusable> findFocusablesWithinRadius(position, radius);

    // ...
};

For the actually searching, the original game uses a BSP-Tree. We don't have that at hand here and we actually don't want one. Spatial Hashing is much easier to implement! A Quad-tree should work too (I don't think we would benefit much from taking the Y-axis into account since gothics worlds are mostly flat).

Spatial Hashing

Spatial hashing is really simple: It divides the world into cells, which can be looked up easily. To figure out the cell of an object, one can divide the position by the cell-size and cut the fractional part:

cellX = (bs::INT32)(position.x / CELL_SIZE)
cellY = (bs::INT32)(position.y / CELL_SIZE)

The two resulting coordinates can then be used as keys into a hashmap. This could be a standard hash map like

bs::Map<std::pair<bs::INT32, bs::INT32>, bs::Vector<HFocusable>>

or maybe a MultiMap is worth looking at.

Adding, removing and updating objects

A possible solution is to add

• GameWorld::onMoveFocusable(HFocusable focusable, ... previousPosition)
• GameWorld::onDestroyFocusable(HFocusable focusable)

methods, which get called from the Focusable::onInitialized(), Focusable::onTransformChangedorFocusable::onDestroyed()`.

When a Focusable was moved into a new cell, the hash-map entry of the previous cell needs to be removed, and added into the new cell.

Of course, if you have better ideas on how to solve this, go ahead and implement them! This is only what came to my mind so far.

[ataulien]

A simple search has been implemented in #92 (Simple brute-force)