Fast World Query

[Kuba663]

Summary

Easy way for modders to check for entities/blocks efficiently.

Goals

• Implementing an API for easy checking for presence of blocks and entities (including players).

Non Goals

• Rewriting the collision system
• changing how World works

Motivation

I was working on a mod and the netities checking for blocks and players in their surroundings caused huge lag.

Description

An API for querying things in the game World fast.

Implementation

Entities and blocks of interest are tracked. When something checks for the presence of a block or entity, the game checks for presences of such things and the found objects are returned. A spatial data structure like an octree (R-Trees are also an option, although they are hard to implement) or a fast collision detection algorithm (stream and scan) can be used to store the tracked entities (and blocks). Blocks could also be stored as ids in an in-memory only array for lookup.
This should prevent lag spikes drastically, as querying blocks now takes a huge amount of time, especially if it's done multiple times a second by entities.

Dependencies

No

References

• Original Stream and Scan paper
• Sample implementation of Stream and Scan
• Octree

Guidelines

• I have and will continue to adhere to the guidelines

[Rongmario]

What could "blocks of interest" be defined as?

[Kuba663]

Any block that an entity might query. MCA villagers will search for beds, etc.

[tttsaurus]

Any block that an entity might query. MCA villagers will search for beds, etc.

Guess you'll have to think more carefully about the capabilities of block-of-interest queries

Like, is your proposed system supposed to be capable of these queries

• Does a certain region contain a certain block?
• Where is the nearest block from a certain coordinate?
• (could be more)

Or would it be possible to generalize the concept of queries and allow devs to register their own type of queries? (but still benefiting from the space segmentation algorithms regardless the form of the query)

Just to clarify, I mean allowing devs to register their own "query paradigm" here, instead of registering certain blocks etc

It also raises more questions about the caching system cuz the cached result relies on the query input (e.g. where is the nearest bed from 0,0,0? the coordinate can be seen as the input)
And it obviously doesn't make sense to cache the result for every coordinate. Maybe octrees should be cached instead.

Moreover, when the form of queries varies, the info that we want to cache might change as well (e.g. an octree this time but a hash map next time)
I wonder if there exists a certain info that would accelerate any forms of queries. It sounds plausible cuz the whole thing is revolving around the concept of distance.