Hàng xóm gần nhất

Lưới hoặc quadtree cho hàng nghìn hình tròn: k vật gần nhất, đẩy các vật chồng nhau ra. Tiếp...

Classes
struct	njin::spatial_item
	Một vật trong index: hình tròn tâm pos. Tiếp...
struct	njin::spatial_desc
	Cách dựng một njin::spatial_index. Tiếp...
struct	njin::spatial_index
	Index không gian cho hàng nghìn hình tròn: tìm k vật gần nhất và đẩy các vật chồng nhau ra, không cần collider, không sinh event. Tiếp...
struct	njin::spatial_query
	Một câu hỏi cho spatial_nearest(). Tiếp...
struct	njin::spatial_hit
	Một vật tìm thấy. Tiếp...

Enumerations
enum	njin::spatial_kind : u8 { njin::spatial_grid , njin::spatial_quadtree }
	Cấu trúc bên dưới một njin::spatial_index. Tiếp...

Các hàm
void	njin::spatial_build (spatial_index &index, const spatial_desc &desc, const spatial_item *items, u32 count)
	Dựng (lại) index từ count vật.
void	njin::spatial_build (spatial_index &index, const spatial_desc &desc, const std::vector< spatial_item > &items)
	Như bản trên, từ một vector.
u32	njin::spatial_size (const spatial_index &index)
	Số vật trong index.
u32	njin::spatial_nearest (const spatial_index &index, const spatial_query &q, spatial_hit *out, u32 k)
	Tìm tối đa k vật gần q.at nhất thỏa q, gần nhất trước.
u32	njin::spatial_nearest (const spatial_index &index, const spatial_query &q, std::vector< spatial_hit > &out, u32 k)
	Như bản trên; out được xóa rồi nhận kết quả.
u32	njin::spatial_separate (const spatial_index &index, std::vector< vec2 > &push, u32 k=6)
	Tính độ đẩy để các vật chồng nhau tách ra: va chạm mềm cho đám đông.

Mô tả chi tiết

Lưới hoặc quadtree cho hàng nghìn hình tròn: k vật gần nhất, đẩy các vật chồng nhau ra.

Thông tin về Enumeration Type

spatial_kind

enum njin::spatial_kind : u8

Cấu trúc bên dưới một njin::spatial_index.

Cả hai trả cùng kết quả, chỉ khác tốc độ: đo trong game của bạn rồi chọn.

Enumerator
spatial_grid	Lưới đều. Dựng lại rất rẻ; nhanh nhất khi các vật cùng cỡ và rải khá đều trong một vùng có giới hạn (đám đông, đàn quái, đạn).
spatial_quadtree	Quadtree: chia nhỏ chỗ đông, bỏ qua chỗ trống. Hợp khi vật dồn cục, map rộng mà thưa, hoặc truy vấn bán kính lớn.

Thông tin về hàm

spatial_build() [1/2]

void njin::spatial_build	(	spatial_index &	index,
		const spatial_desc &	desc,
		const spatial_item *	items,
		u32	count )

Dựng (lại) index từ count vật.

Các tham số

index	Index, dựng lại từ đầu.
desc	Lưới hay quadtree và các thông số.
items	Các vật. Vật thứ i có tên i trong kết quả.
count	Số vật.

spatial_build() [2/2]

void njin::spatial_build ( spatial_index & index, const spatial_desc & desc, const std::vector< spatial_item > & items )

inline

Như bản trên, từ một vector.

Các tham số

index	Index.
desc	Cách dựng.
items	Các vật.

spatial_size()

u32 njin::spatial_size

(

const spatial_index &

index

)

Số vật trong index.

Các tham số

index

Index.

Giá trị trả về

Số vật của lần dựng gần nhất, 0 nếu chưa dựng.

spatial_nearest() [1/2]

u32 njin::spatial_nearest	(	const spatial_index &	index,
		const spatial_query &	q,
		spatial_hit *	out,
		u32	k )

Tìm tối đa k vật gần q.at nhất thỏa q, gần nhất trước.

njin::spatial_hit near[4];
const njin::u32 n = njin::spatial_nearest(index, {.at = pos, .radius = 120.0f, .skip = self}, near, 4);

Các tham số

index	Index đã dựng.
q	Câu hỏi.
out	Nhận kết quả, đủ chỗ cho k.
k	Số vật tối đa.

Giá trị trả về

Số vật tìm thấy, từ 0 đến k.

spatial_nearest() [2/2]

u32 njin::spatial_nearest ( const spatial_index & index, const spatial_query & q, std::vector< spatial_hit > & out, u32 k )

inline

Như bản trên; out được xóa rồi nhận kết quả.

Các tham số

index	Index đã dựng.
q	Câu hỏi.
out	Nhận kết quả, gần nhất trước.
k	Số vật tối đa.

Giá trị trả về

Số vật tìm thấy.

spatial_separate()

u32 njin::spatial_separate	(	const spatial_index &	index,
		std::vector< vec2 > &	push,
		u32	k = 6 )

Tính độ đẩy để các vật chồng nhau tách ra: va chạm mềm cho đám đông.

Mỗi vật không fixed bị đẩy bởi k vật chồng lên nó gần nhất: hai vật đều di chuyển được thì mỗi bên lùi một nửa phần chồng, vật fixed thì bên kia lùi hết. Vật cùng nhóm (khác 0) không đẩy nhau. Chỉ cộng lực của k vật gần nhất, nên giữa một cụm dày một vật không bị hàng chục vật cùng hất ra; phần chồng còn lại tan dần qua các frame. Độ đẩy tính từ vị trí lúc dựng, nên không phụ thuộc thứ tự, và không quá bán kính của vật.

Gọi mỗi frame sau khi dựng lại index, rồi cộng push[i] vào vị trí vật i.

Các tham số

index	Index đã dựng.
push	Nhận độ đẩy của từng vật, cùng số thứ tự với mảng đã dựng (0 với vật fixed và vật không chạm ai).
k	Số vật chồng gần nhất được xét cho mỗi vật.

Giá trị trả về

Tổng số lần đẩy (một cặp hai vật di chuyển được tính hai lần).