LINUX.ORG.RU

Воксельный движок на Rust

 ,


0

4

Как вы бы реализовали хранение вокселей «а-ля Minecraft» на Rust?

- Каждый воксель имеет тип, который задаёт его поведение (начиная от построения меша для рендеринга и заканчивая реакцией на действия игрока и т. д.)

- Помимо типа у каждого вокселя может быть некоторое состояние. Структура состояния зависит от типа (не всем типам вокселей вообще оно нужно). Реализация каждого поведения от типа должна иметь доступ к состоянию конкретного вокселя.

- Воксели хранятся в массиве, поэтому структура вокселя должна иметь константный размер (ну и да, мы не хотим дёргать аллокатор отдельно на каждый из миллионов вокселей). Так что звучит разумно ограничить размер состояния некоей небольшой величиной, а сколько реально байт в нём будут использоваться пусть решает конкретный тип.

- У небольшого количества вокселей может быть большое состояние, которое не влезет в фиксированный размер. В этом случае в состоянии вокселя помещается указатель на динамически выделяемую структуру и нужно в какой-то момент (либо при уничтожении мира, либо при смене типа этого вокселя) освободить память.

На Си это могло бы выглядеть как-то так:

typedef struct voxel_type voxel_type;

struct voxel {
    voxel_type *type;
    char data[16]; // Мы уверены, что на целевой платформе сюда влезет хотя бы один указатель
};

struct voxel_type {
    void (*init)(voxel_type *type, voxel *v);
    void (*destroy)(voxel_type *type, voxel *v);
    void (*to_string)(voxel_type *type, voxel *v, char *buffer, size_t buffer_size);
    texture_t *(*get_texture)(voxel_type *type, voxel *v);
    void (*build_vertex_data)(voxel_type *type, voxel *v, char *buffer, size_t buffer_size);
    void (*on_click)(voxel_type *type, voxel *v);
    ...
};

void set_voxel_type(voxel *v, voxel_type *t) {
    v->type->destroy(v->type, v); // Подразумевается, что изначально все воксели инициализированы каким-нибудь "пустым" типом при создании их массива
    v->type = t;
    t->init(t, v);
}

void voxel_to_string(voxel *v, char *buffer, size_t buffer_size) {
    v->type->to_string(v->type, v, buffer, size);
}

Соответственно, каждая функция из структуры voxel_type внутри себя кастует data в конкретную для данного типа вокселя структуру состояния (которая обязана быть не больше 16 байт размером, однако может содержать указатель на что-то большее), при этом init производит начальную инициализацию и не должен делать никаких допущений о том, что лежало в data до него (там может быть неинициализированная память или данные от предыдущего типа вокселя), а destroy может либо ничего не делать, либо освобождать память (если мы клали в data указатель).

Это похоже на класс с vtable из C++ (который создаётся через placement new на буфере), однако является более гибким механизмом: своё состояние имеет не только сам воксель, но и его тип (то есть можно в рантайме инстанцировать несколько типов вокселей с одинаковым поведением, но разными параметрами типа, например, текстурой, при этом каждый воксель не будет нести в себе эти параметры, а только указатель на «шаблон»).

Как это можно уложить на синтаксис и парадигму Rust? Разумеется, жалательно поменьше unsafe и побольше compile-time гарантий (например, было бы неплохо, если бы реализации типов вокселей сразу получали скастованное в нужный тип состояние, возможно, с помощью какой-нибудь магии на макросах).

Первая мысль - тип вокселя должен быть трейтом (соответственно, в нём оказываются все нужные методы, но без реализации), а конкретный воксель имеет в себе поле вроде kind: &'static dyn VoxelType. Преобразования типов можно сделать на макросах (чтобы был макрос для описания типа вокселя, который под капотом перенаправляет вызовы методов, принимающих &Voxel, в методы, принимающие конкретный тип состояния, а также берёт на себя реализацию методов создания и удаления состояния). Однако встаёт вопрос собственно инициализации и деинициализации состояния. Rust гораздо стороже относится к этому вопросу.

★★★★★

Ответ на: комментарий от intelfx

В этом случае придётся в одном месте описывать все типы вокселей, а хочется, чтобы их можно было создавать в рантайме (например, чтобы можно было сделать тип «простой текстурированный воксель», а потом наплодить его экземпляров, передавая разные параметры текстуры, светимости и т. д. при создании типа, но при этом не хранить это всё в самом вокселе, а только ссылку на тип). А ещё при работе с tagged-union придётся делать огромный match на каждый вызов метода-поведения.

KivApple ★★★★★ ()
Ответ на: комментарий от MOPKOBKA

Беглое гугление дало, что в Minecraft раньше был один int (ну и ссылка на тип блока само собой, кстати, как и у меня один разные экзмепляры одного класса могут задавать разные типы блоков и их можно создавать в рантайме), значение которого каждый блок трактовал по-своему. Затем сделали генерацию этого int из набора преопределённых флагов и enum-в (частный случай - жёстко ограниченное по диапазону число), чтобы код выглядел чище.

С одной стороны это очень просто в реализации, с другой из-за этого всё хоть чуть-чуть сложное вынуждает создавать сущность вместо блока.

KivApple ★★★★★ ()
Последнее исправление: KivApple (всего исправлений: 1)
Ответ на: комментарий от MOPKOBKA

Я не против сущностей. Как минимум они нужны для вещей не привязанных к сетке вокселей - например, мобам и игрокам.

Но без сложной обработки (той же возможности сделать update по тикам) для простых блоков не обойтись - как минимум же же жидкости на сущностях делать слишком накладно (ведь жидкостей могут быть целые океаны), не?

Я пока себе представляю, что у каждого типа вокселя есть update, который вызывается для каждого блока после загрузки/генерации чанка + при изменении (не важно игроком или из update другого блока) любого соседнего (в кубе 3х3х3) блока. update может вернуть true и тогда он будет вызван на следующем тике и т. д. (пока не вернёт false). Или лучше создавать в этот момент временную сущность, которая исчезнет, когда жидкость перестанет растекаться?

KivApple ★★★★★ ()
Последнее исправление: KivApple (всего исправлений: 3)
Ответ на: комментарий от KivApple

(ведь жидкостей могут быть целые океаны), не?

Это же статичные блоки, зачем их обновлять? Жидкость которая должна потечь это уже другое дело.

Я пока себе представляю, что у каждого типа вокселя есть update

Тормоза, хотя в принципе пойдет если ограничишь обновляемые блоки.

MOPKOBKA ()
Последнее исправление: MOPKOBKA (всего исправлений: 2)
Ответ на: комментарий от MOPKOBKA

который вызывается для каждого блока после загрузки/генерации чанка + при изменении (не важно игроком или из update другого блока) любого соседнего (в кубе 3х3х3) блока. update может вернуть true и тогда он будет вызван на следующем тике и т. д. (пока не вернёт false).

То есть большинство блоков обновляются только один раз, при загрузке, а каждый такт только избранные.

KivApple ★★★★★ ()
Последнее исправление: KivApple (всего исправлений: 1)
Ответ на: комментарий от Harald

Отсутствие метапрограммирования. В плюсах есть темплейты, в rust макросы (нормальные). Также в C++ есть RAII, в rust borrowing. Без всего этого многопоточную работу с миром сложно корректно запрограммировать.

KivApple ★★★★★ ()
Ответ на: комментарий от Harald

Я уже написал на плюсах: https://eternal-search.com/voxel-game/ (если что там мультиплеер). Дошел до сущностей (воксельный мир достаточно функционален, даже жидкости работают), но не реализовал их пока.

Но меня удручает скорость компиляции + ключевой код (класс типа блока) представляет из себя огромную лапшу шаблонов (а мне теперь то же самое делать для сущностей). Плюс rust должен давать больше гарантий на корректную работу с памятью.

KivApple ★★★★★ ()
Последнее исправление: KivApple (всего исправлений: 3)
Ответ на: комментарий от KivApple

Да, я понял. Подумай как именно они будут обновляться, типы то у тебя динамические, надо будет комбинировать функции, и 1 свойство может снятся, а функция апдейта от другого свойства еще не завершиться итд...

MOPKOBKA ()
Ответ на: комментарий от Harald

И сервер, и клиент на плюсах (часть кода общая). Клиент скомпилен через wasm. Также его можно скомпилить нативно (используется SDL2 и OpenGL ES). Связь с сервером в обоих случаях через вебсокеты. Мир хранится на сервере в SQLite.

KivApple ★★★★★ ()
Последнее исправление: KivApple (всего исправлений: 1)
Ответ на: комментарий от MOPKOBKA

У меня все апдейты происходят в рамках одного тика мира. Если блок за это время изменит свой тип (например, его модифицирует соседний блок), то да, потенциально может потеряться последний апдейт (или первый апдейт изменённого блока случится только в следующий тик), но, мне кажется, это вряд ли проблема. За исключением тика воксели не обновляются (только шедулятся для обновления в специальный список локаций вокселей внутри чанка, которые надо обновить в следующий раз, когда наступит время обновлять чанк). При любой модификации чанк (или куб чанков 3х3х3) блокируется R/W mutex, так что race condition для отдельного вокселя исключён (но при этом можно иметь параллельный доступ к чанкам из разных потоков, если они достаточно далеки друг от друга).

Помимо обычного update есть slowUpdate (как такт блока в Minecraft) - вызывается для 4 случайных блоков в чанке перед тем как обновить блоки, которые были зашедулены для обновления с прошлого обновления чанка (сейчас таким образом растёт и умирает трава).

Вообще вот кусок кода С++ отвечающий за один воксель: https://pastebin.com/cZWreksU

Мне интересно как его переписать не таким страшным на Rust.

KivApple ★★★★★ ()
Последнее исправление: KivApple (всего исправлений: 8)
Ответ на: комментарий от Harald

На плюсах сейчас воксель представляет из себя вот что: https://pastebin.com/cZWreksU

И меня удручает, что такое же придётся писать для сущностей. А Rust пока показывает просто чудеса скорости при компиляции проекта (но там пока гораздо меньше всего реализовано) и у него нормальные макросы должны быть.

Эх... Были бы в плюсах работающие модули... Но, кажется, они нормально работают только в MSVC (особенно с CMake и CLion) пока.

KivApple ★★★★★ ()
Последнее исправление: KivApple (всего исправлений: 6)
Ответ на: комментарий от KivApple

На плюсах сейчас

На плюсах чуть меньше 10 лет назад. Портянка твоя уже банально с fold expressions в 1.5 раза схлопнется, не говоря уже о концептах.

Цифра, кстати, не от балды. Вот два эквивалентных куска кода. Это «экстремальный» пример и в среднем так хорошо не получится, но все и так понятно.

template<typename ...Traits> struct traitsHaveVoxelInterface {
	template<typename Trait, typename ...RestTraits> constexpr static bool performCheck(
			Trait *trait,
			RestTraits... restTraits
	) {
		if constexpr (std::is_base_of<VoxelTypeInterface, Trait>::value) {
			return true;
		}
		return performCheck(restTraits...);
	}
	constexpr static bool performCheck() {
		return false;
	}
	
	static constexpr bool value = performCheck(static_cast<Traits*>(0)...);
	
};
template <typename ... Traits>
constexpr auto traitsHaveVoxelInterface = false || (std::is_base_of_v<VoxelTypeInterface, Traits> || ...);

А Rust пока показывает просто чудеса скорости при компиляции проекта (но там пока гораздо меньше всего реализовано)

Меньше всего реализовано, но раст показывает чудеса скорости. С чем же это связано?

Siborgium ★★★ ()
Последнее исправление: Siborgium (всего исправлений: 1)

Ты не можешь использовать конструктор у трейта, да. Но ты можешь сделать где-нибудь мап типа HashMap<VoxelType, Box<Fn(Vec<Param>) -> Box<VoxelTrait> и дергать конструктор отттуда. Ну и динамически модифицировать этот мап, если оно тебе требуется

Aswed ★★★★★ ()
Ответ на: комментарий от Siborgium
template<typename Trait> static constexpr auto traitHasToString(
		Trait*,
		const State* voxel
) -> decltype(std::declval<Trait>().toString(*voxel), true) {
	return true;
}
template<typename Trait> static constexpr auto traitHasToString(...) {
	return false;
}

template<typename Trait, typename ...RestTraits> void traitsToString(
		const State &voxel,
		std::string &result,
		Trait *trait,
		RestTraits... restTraits
) {
	if constexpr (traitHasToString<Trait>((Trait*) 0, (const State*) 0)) {
		result += trait->toString(voxel);
	}
	traitsToString(voxel, result, restTraits...);
}
void traitsToString(const State &voxel, std::string &result) {
}

void toString(const State &voxel, std::string &result) {
	traitsToString(voxel, result, static_cast<Traits*>(this)...);
}
	
std::string toString(const State &voxel) {
	std::string result;
	toString(voxel, result);
	return result;
}
	
std::string invokeToString(const Voxel &voxel) override {
	return static_cast<T*>(this)->T::toString(static_cast<const Data&>(voxel));
}

А такие фрагменты как можно оптимизировать? С is_base_of_v случай относительно тривиальный (я не знал, что || совместим с ...), а для определения наличия методов в std вроде нет утилит.

KivApple ★★★★★ ()
Ответ на: комментарий от KivApple

Кратко: https://godbolt.org/z/K96z6onrb

Для Ъ:

/* Визитор, пишется один раз в хэдере */
template <typename ... Ts> struct Overloaded: Ts... { using Ts::operator()...; };
template <typename ... Ts> Overloaded(Ts...) -> Overloaded<Ts...>;

/* Актуальный код */
template <typename T>
concept HasToString = requires (T trait, std::string& result, const State & state) {
    result += trait.toString(state);
};

template <typename ... Traits>
void traitsToString(const State& voxel, std::string& result, Traits&& ... traits) {
    Overloaded impl {
        [&](HasToString auto&& trait){ result += trait.toString(voxel); },
        [](auto&&){ /* noop */ }
    };
    (impl(traits), ...);
}

Можно, конечно, и без визитора, а просто через if constexpr, но там нужно будет remove_cvref_t делать.

Кстати, делать string += toString так себе идея. Лучше уж тогда stringstream и передавать по ссылке в toString, чтобы строки лишний раз не создавать.

Siborgium ★★★ ()
Последнее исправление: Siborgium (всего исправлений: 1)
Ответ на: комментарий от KivApple

А лучше даже так:

template <typename ... Traits>
void traitsToString(const State& voxel, std::string& result, Traits&& ... traits) {
    auto impl = [&]<typename T>(T && trait) {
        if constexpr (requires { result += trait.toString(voxel); }) {
            result += trait.toString(voxel);
        }
    };
    (impl(traits), ...);
}

если toString больше нигде не нужно будет делать.

Siborgium ★★★ ()
Последнее исправление: Siborgium (всего исправлений: 1)