Handmade Hero»Forums»Code
Oliver Marsh
193 posts / 1 project
Olster1.github.io
Why don't use discriminated union rather than Sparse System for entity system?
Edited by Oliver Marsh on

Don't want to answer for Ryan but following Ryan's example would be thinking in code paths/behaviours first.

So the behaviour would be 'able to hurt things in game world', so maybe the code path that corresponds to this is a collider that checks if it has hit other things and decrements the health of that entity.

The data that accompanies this behaviour is: collider, damage power. The fat struct might already have a collider component so we wouldn't have to define a second one.

So a weapon would have the behaviours Weapon = { hurtEnemies, followPlayer, renderSprite }

It would get alot more complicated than this but I think avoid thinking in discrete types which will cause the number of types to explode, instead thinking of entities as collection of behaviours(collection of code paths that run)

Please let me know if I've totally missed it 😅

140 posts
Why don't use discriminated union rather than Sparse System for entity system?
Edited by longtran2904 on
Replying to OliverMarsh (#25878)

Yeah, I'm kind of thinking the same thing. The whole point of a fat struct is that:

Because there's only one way to interpret the type, you can write codepaths that are actually not specific to any entity "kind" at all, but still work with all of the data of an entity. The entity "kind" just doesn't really matter in many codepaths, while the data often still does. This is where the code savings comes from, as well as the fact that the work you have to do managing these "bundles" doesn't scale like O(2^N), and instead scales like O(N).

One of the most important slides in the talk was the side-by-side comparison of the two approaches. Even though the union is smaller in memory size, it's greater in code size and writing code for it is more cumbersome and annoying.

The weapon system is just a random example of whether to make a behavior works by splitting it into different entities or by adding a completely new component. But if I have to, I'd probably just make it the same as an enemy (sprite, animation, trigger, attack, etc), be a child of the player (so it will follow and rotate with the player), and its health can be used in some kind of durability system.

Oliver Marsh
193 posts / 1 project
Olster1.github.io
Why don't use discriminated union rather than Sparse System for entity system?
Edited by Oliver Marsh on

I'll have to check out the talk, sounds good 👍

You've probably have come across Ryan's dungoneer repo, but if you havent he uses the component system there with weapons https://github.com/ryanfleury/dungeoneer/blob/c502116401bddaade8f73ac086726aea32ef8826/game/source/component.c#L250

One thing I came across in a game I was making - I followed the 'fat struct' pretty liberally for all the entity and physics stuff, also storing big static arrays in the entity struct instead of using dynamic arrays. And my memory footprint was pretty big like 3gb in task manager. Although other things probably contributed to it (like my coding style?), if you are using the fat struct approach, keeping task manager open to see your apps memory usage has been handy.

65 posts
Why don't use discriminated union rather than Sparse System for entity system?
Edited by Shastic on
Replying to OliverMarsh (#25881)

"And my memory footprint was pretty big like 3gb in task manager."

Ouch! Lucky memory is cheap.

@ longtran2904

"Let's imagine that I want to add a weapon system to my game. There are two ways that I can do it: either I just add a new entity called weapon which is the player's child entity (using existing members in the struct like position, sprite, animation, etc but also adding new members like weaponDamage or weaponRange), or make a new struct Weapon { ... } and add it into the flat struct."

As I understand it:

If the player is a weapon, meaning if he bumps into something else he damages it, turn on the weapon code in the player.

If the player is carrying a weapon, and it can be dropped, then make it a child entity of the player.

Both the weapon and the player use the same entity struct type, so you keep stuffing variables into the entity struct.

I like this explanation and the name.

https://www.philhassey.com/blog/2012/04/20/dynamite-jack-component-object-model/

140 posts
Why don't use discriminated union rather than Sparse System for entity system?
Replying to OliverMarsh (#25881)

Just curious, how many active entities do you have? How large is a single entity?

Also, does anyone know any shipped game that uses a fat struct for the entity system?

Oliver Marsh
193 posts / 1 project
Olster1.github.io
Why don't use discriminated union rather than Sparse System for entity system?
Edited by Oliver Marsh on
Replying to longtran2904 (#25884)

Probably should have given more info on that number before throwing it out there 😅. I’ll have a look and show what my struct looks like and how many entities were active (hopefully today or tomorrow). This 3gb was in a worst case scenario where I shot a lot of arrows, each one with a physics body which had a lot of data aswell because of static arrays.

Nirion on handmade.network I believe uses the flat struct approach.

EDIT: Looking at it now, it's probably a memory bug in something else, it seems like too much memory is being allocated :( from something else.

This is my sizes

sizeof(Entity) = 512 
sizeof(EasyRigidBody) = 100 
sizeof(EasyCollider) = 88

This is what my Entity struct looks like

struct Entity { 

	EntityType type;

	u64 flags;

	EntityDirection direction;

	//NOTE: This is for the redo undo system, and to save entities that shouldn't be deleted like the sword and shield
	bool isDeleted;

	//NOTE: If the entity is flipped on the x-Axis
	bool isFlipped; 

	bool isDead;

	bool isSwimming;
	bool isFalling; //For player falling through the floor

	float animationRate;

	EntityEnemyType enemyType; 

	//FOr empty triggers that do stuff
	EntityTriggerType triggerType;
	char *levelToLoad; //for triggers that load levels

	//Location Sound type to retrieve string
	EntityLocationSoundType locationSoundType;

	///NOTE: CHest information
	bool chestIsOpen;
	ChestType chestType;
	/////

	//NOTE: For things that are have a switch that gets turns on and stay on. Using for a door when you exit it it closes.
	bool isActivated;

	//For entity creator
	float rateOfCreation;
	float timeSinceLastCreation;
	EntityType typeToCreate;
	/////////////////////////////


	int subEntityType;

	//NOTE: If no animation, use this sprite
	Texture *sprite;

	V4 colorTint;

	EasyTransform T;
	EasyAnimation_Controller animationController;

	//For the ai stuff
	EasyAiController *aiController;
	V3 lastSetPos; //the position the A* path find is travelling to
	V3 beginSetPos;
	float travelTimer; //timer to lerp between A* positions
	V3 lastGoalPos;
	///

	//NOTE: For loading to other scenes through a door
	int partnerId;
	V2 moveDirection;
	//////////////////////


	EasyRigidBody *rb;
	EasyCollider *collider;
	//Four colliders for the rock
	EasyCollider *collider1;
	EasyCollider *collider2;
	EasyCollider *collider3;
	EasyCollider *collider4;

	bool shieldInUse;
	bool staminaMaxedOut;

	float flashHurtTimer;

	int animationIndexOn; //for ai state machines

	float layer; //NOTE: zero for infront, +ve for more behind

	////////////////  Different entity sub types ////////////////
	float lifeSpanLeft;
	float maxLifeSpan;

	bool isDying;
	int health;
	int maxHealth;

	bool wearingGloves;

	
	/////
	int footstepAt;
	float footStepTimer;

	//////////////////

	float lightIntensity;
	V3 lightColor;

	float innerRadius;
	float outerRadius;

	bool renderFirstPass; //Render before entities like terrain so the doesn't affect the depth buffer ordering 

	PlayingSound *currentSound;

	//NOTE: For the button that needs to know things are on top of it
	int refCount;


	//Player stamina
	float stamina;
	float maxStamina;
	float staminaTimer;

	//For NPCs and signs
	DialogInfoType dialogType;

	//For key prompts
	float tBob;

	EasyModel *model;

	float rotation;

	float healthBarTimer; 

	//For the audio checklist
	char *audioFile;

	//For the push block
	float moveTimer;
	V3 startMovePos;
	V3 endMovePos;
	////////////////////

	int particleSystemIndexToEndOnDelete;
	float enemyMoveSpeed;


} ;

This is the rigid body

struct EasyRigidBody {
	int arrayIndex;
	
	V3 dP;
	V3 accumForce; //perFrame
	V3 accumForceOnce; //Gets cleared after one phsyics click
	V3 accumTorque;
	V3 accumTorqueOnce;

	union {
		struct { //2d
			float inverse_I;
		};
		struct { //3d
			V3 dA;
			// Matrix4 inverse_I;
		};
	};
	
	float inverseWeight;
	float reboundFactor;

	float dragFactor;
	float gravityFactor;

	bool updated;
	bool hasRigidCollider;

	u32 isGrounded; //flag where grounded is 1 << 0 & done this frame is 1 << 1 

};

This is the collider

struct EasyCollider {
	int arrayIndex;

	EasyTransform *T;
	EasyRigidBody *rb;

	EasyColliderType type;
	V3 offset;

	bool isActive;

	bool isTrigger;

	EasyCollisionLayer layer;


	InfiniteAlloc collisions;

	bool canCollide; //this is since rigid bodies have to have a collider to update their position

	union {
		struct {
			float radius;
		};
		struct {
			float capsuleRadius;
			float capsuleLength;
		};
		struct {
			V3 dim3f;
		};
		struct {
			V2 dim2f;
		};
	};
};
140 posts
Why don't use discriminated union rather than Sparse System for entity system?
Replying to OliverMarsh (#25886)

If you have a static array of entities that were allocated at the start then how can the memory usage go up? Am I missing something? Or is the EasyRigidBody and EasyCollider get allocated every time you shoot an arrow? Also, why do you need four colliders for the rock?

Regarding the data format talk, here's the slide that I was talking about.

Oliver Marsh
193 posts / 1 project
Olster1.github.io
Why don't use discriminated union rather than Sparse System for entity system?
Edited by Oliver Marsh on

The entities are in a pool array (not sure the right terminology - fixed sized arrays joined by a linked list) so it allocates memory there. Also the InfiniteAlloc type on the collider is a dynamic array that allocates memory ( it used to be static arrays as I thought this was hogging memory).

Each time an entity gets allocated it also allocates a rigid body & collider if it needs one. These are on a seperate pool array. I did this to save memory, lol, and because the physics system doesn't know about entities and just loops through the collider & rigid body arrays. The ai_controller is also the same: only allocated if needed and into a seperate pool array (but the arrows aren't using this).

The block has four colliders, one for each side as a trigger for pushing it. I did it this way as it was easier on game code to know which direction the player pushed the block.

This memory issue prompted me to try a simplify the way I was using memory and 'go back to basics' on another project 😥

I feel at this point my trouble has more to do with my memory management and not the fat struct approach 😝. If in worst case scenario each entity total used 1kilobyte then 1000 entities would use 1megabyte which seems reasonable.

Thanks for the link 🙂

65 posts
Why don't use discriminated union rather than Sparse System for entity system?
Edited by Shastic on
Replying to longtran2904 (#25884)

"Also, does anyone know any shipped game that uses a fat struct for the entity system?"

Not that I know of. Casey is the only one I have heard of, other than the link I posted.

Casey makes it work for his game that has lots of entities, by compressing the entity structs of objects that are far away from the player, and writes them out to the drive. Zero is initialization would help there. Also, he decompresses and updates far away objects in a different thread, one game grid area at a time.

I haven't seen those videos in quite a while, must watch them again soon.

140 posts
Why don't use discriminated union rather than Sparse System for entity system?
Edited by longtran2904 on

The more I use fat struct for my entity system, the more I love it. Just saying each flag corresponds to a feature reducing a lot of invariants for most gameplay code. But something that I still kink of figuring out is how to make a system whose job is to manage and change these flags.

Most of these flags are just set-up-and-run types that get initialized when you first create an entity (e.g ControlledByPlayer, GameOverWhenDied, AttackWhenCollide, etc). These kinds of flags can also get changed by other data transformations at runtime and are usually responsible for simple, single, independent behaviors. For example, when the player gets hit he can't attack other entities so we disable his AttackWhenCollide flag for a while. Or we can set the GameOverWhenDied flag for entities that would resolve to a game over when died like the player, NPCs in escorted mission, final boss, etc.

But great games are formed by interesting interactions between combinations of features. Oh, when the player moves to this spring it springs the player toward this direction passes these turret's sensors which make them shoot some other enemies which make those explode and burn the wooden bridge that the player landed on. We can think of this example as a series of data transformations that happen to all the entities which get started when the player touches the spring. Specifically, each interaction sets up some flags and changes some values of some entities.

The main problem that I'm currently facing is how to make complicated behaviors that work across multiple entities and consist of multiple smaller behaviors each with a different set of invariants. This has been a really tough challenge since I started working on my enemy's AIs.

The first idea that I had is to have some kind of EntityBrain and delegate all the decision-making to it (like in handmade hero). The brain would run every frame to check for a set of conditions, manage the flags and states correctly, and later execute the behaviors based on some enums. Each entity has an EntityStateEnum and an EntityMoveTypeEnum. These will get changed by the brain and at the end of the frame, the entity has a switch statement to handle movement. This quickly falls apart because there were a lot of repeatable patterns. A lot of brains started to have the same conditions to check but different enough so I couldn't use goto. The movement also started to get samey, a lot of entities move closely like each other but with different orders or operations. I also should say that these brains are pretty specific about an entity "kind" (e.g PLAYER_BRAIN, SNAKE_BRAIN, ZOMBIE_BRAIN, etc) so maybe this is why it failed.

The second idea that I'm currently trying is to make is having a big MoveData struct that contains all of the necessary data. It has a bunch of flags saying how and when should you move it. But then you get into interesting questions like I want the player to move and jump so should I have a single MoveData struct that can both move and jump at the same time or I should have 2 MoveData structs, one for each. How many instances should an entity hold? Does MoveData have something like a pointer to the next MoveData or should every entity just hold an array of these, loop through, and execute the first one that met its condition.

I'm very curious to see your solution to this problem!