Game Engine Programming 009 - Identifiers with index and generation parts | C Game Engine

hello everyone and welcome to the game engine programming series where i write a game engine from scratch today is the day we finally start working on the game engine itself the engine project in our solution so far we only have been programming for the editor part which has been fun but i i'm really looking forward to start programming for the game engine itself because it's a game engine programming series so without further ado let's get started [Music] all right let's get rid of all these files at least i just closed them we don't need them

anymore the first thing i would like to do is to go through the properties of this project and see if there are any options that i need or want to change for this project to be optimally configured so in debug build these seem to be okay it's a library it's using the latest uh installed version of the windows sdk and the tool set is okay and the advanced settings in the cc plus plus options i'll just view all options i don't want to go through all of these subcategories i can view them in one go

that is easier so let's see there are no additional include directories yet i'll probably have to add one later on to have like a central location for the include files these are all okay the language standard that i'm going to use is c 17. i'm not going to use the latest because some of those have some kind of breaking changes that they could change later on and then yeah then we have to go back to our code and adjust that again or modify it so i'm just using the latest stable version of the language that

is implemented in visual studio the calling convention uh i'm going to choose fast call the difference being that in the cdec [Music] deco option you push all the parameters of the uh of the function that you are going to call you push them on the stack so into memory and then the function when it starts pull pop the parameters from the stack and use them and the fast call is is going to put as much as possible of those parameters on the registers and pass them through registers to the function that we are going to

call and using the registers is of course faster than using memory so that's why it's called fast call i'm not sure what's the difference is between standard call and c uh vector call you use for whenever you have uh cmd instructions and you want to pass the cmd registers like mmx and those kind of data types then the compiler will put those in the cmd registers but in general i'm just using fastcall i'm not going to use exceptions at all in the engine so i'm going to turn them off the enhanced instruction said i'll let

the compiler decide for now which one it will use normally i think on default it will just pick the ss2 sse2 instruction set that's fine for now uh i have no idea what these this is jccc return mitigation no i think that's one of those intel defects i don't know i'm just leaving it like this uh the intrinsic functions in the debug build i'm not bothered with these optimization things i don't need runtime type information ever so that's a no i'm not going to use a lot of strings if any at all in this engine

so i don't really care i have no idea what this means no i guess no um okay floating point model we are not going to do any scientific precise calculations in a game engine so i'll just use fast i hope that this will also do some denormal prevention uh stuff but i'm not sure i have to look it up if what i mean by the normal prevention is that whenever the floating point numbers get really close to zero then the processor is going to treat them differently than when they are in a normal range so

the processing of those kind of really small numbers is slower and with this i hope to say that whenever that happens just treat those numbers as zeros because they are really small anyway and then just calculate as if they were zeros and uh we have like not this high kind of precision calculations but we are fast force conformance for loop scope i guess so i don't care no xml documentation files no don't ignore include paths no inline function expansions multi-processor compilation yeah sure why not i mean visual studio is kind of slow anyway so why

not use multiple cores to compile our programs with i remember i removed these these extra platforms so let me quickly check if it's still the case so here in configuration manager it's curious because i still have the option in in the in the project properties i can i can still select this win32 platform oh here it is again [Music] why you still have that it's so annoying visual studio is just annoying of course the human kind still has to find out how to properly outline the ui elements in like a professional software package that we

have here oh my god okay how am i going to okay let's try again go to all options and then let's see if i okay i got i managed to get rid of that vin32 platform finally thank god multiprocessor compilation yes optimization is disabled for debug build that's okay i'm not going to use pre-compiled headers yet so not using those and this should then go away not having a pre-compiled header file i don't think i need stl checks we are not going to develop any security sensitive software anyways so i'm just going to get rid

of this and disable security checks and if we get hacked while we are playing a game that was made by this engine then too bad i deny any responsibility for that spectre mitigation not needed okay i don't care for these uh unicorn unicorn no unicode for assembler listing so this is okay for the debug build let's apply that and then go to release uh here's the same story with those additional include like include directories uh no no assembler output again using fast call language sum standard is 17 i don't think we need this no no

security needed there's no security checks needed at least no exceptions uh function levels linking i guess that's that should be yes uh intrinsic functions well it depends if it makes your code very large then you'll have a lot of cache misses in this instruction cache and then your code will become slow but on the other hand if uh you you do you do a lot of calls to these intrinsic functions in tight loops then this should improve the performance so i'm going to leave it yes for now yeah parallel code generation yes please runtime type

information again no the floating point model should be fast again yes multi-processor compilation is good i hope at least with visual studio you never know no pre-compiled headers no security checks i'm going to have a higher level of warnings which is four obviously it would give me more kinds of warnings so apply this and go back to debug because i think i have the level yeah here i should set the level warning level to level four as well and i think i'll leave it there for now here there aren't things that i want to set

so that's good okay let's see what happens when i build the project now it builds fine okay the next thing i'd like to do is to get rid of these files that i'm not going to use show all files select them all and delete them and i don't need these filters anymore so delete them as well save all and we are set to start writing code for the engine so um the first the first file i want to create is a common header for everything basically in the engine uh oh i created the filter accidentally

let's delete this go into file mode and add a folder okay so the difference between filters and folders is that whenever i create a folder it well it creates a folder but the filters are not created anywhere in this in the folder of the engine so all the files that we then would create would be here in the root folder which is not good because well then they wouldn't be ordered in any way so i'll just create folders and put them in there so as i said i want to create a new header file actually

i want to have it as common headers and here i include all the headers that i need in the project so the c plus plus cc plus headers the ones i want to start with are the standard int integer and the asset assertion header next i want to create my own types of integers i'll at least i'll give the different size integers their own names so i'll create a file for primitive types and here i again include this standard int header so c plus plus has these kinds of integers uh like a unsigned integer 16

bit type and those are based on the native types of c plus so we know what size exactly they are which is very handy if you need integers of 32 bit length of or any other kind of integers that you really need to know what size they are because if you use these uh these kind of integers like a long long and unsigned char or whatever c plus plus originally included are actually these are c types right their size can be different on different platforms so that's why we have this now uh which is fine

but i think these names are a bit too long to type all the time that's why i'm going to rename them for for use in my own engine so for example i'll have the u8 the 8-bit unsigned integer to be like this so we have 64 bits 32 bits and 8 and 16 bit unsigned integers and i'm going to do the same for signed integers i'm going to use s instead of u to indicate on signed and here we can just delete the u and we have signed integers and i want to have one for

a floating point value because i'm going to use these kind of integers for indices a lot of times actually i need a value to be reserved to indicate an invalid index well indices start at 0 normally and i would like to reserve the biggest value that you could fit in to an integer to be an invalid value so for example if you look at the 8-bit unsigned integer it's in the range 0 and 255 and i want to have this value of 255 to be the invalid index so any index that has this value is

invalid that means that we can use 0 to 254 and if you look at the binary representation of the invalid value is the eight bits are well eight zeros of course so we have one and then two and then three and then four etc and all the way to 255 which is just all once eight ones and this also represents the value minus one so i'm going to use minus one for all of these integers to represent the invalid index value so what i just did is that i use the hexadecimal representation of the value

-1 so this is again all the bits set to run okay um so yeah we are done with the primitive types i have everything i need here now i can also include this header to our common headers next i want to start like we did for the level editor with entities and their components but before i start working on those i am going to explain how i'm going to implement those in the engine because they are rather different from how we implemented them in the level editor okay going to my drawing here it depicts the

way we implemented the entities and components in the editor which is the object-oriented way of implementing it so here we have a list of entities and each entity has a list of components so for example this one the first one has a transform which all entities have to have so that one is in all entities and it has a geometric component same as the second entity but the third entity has only a transform and a script and this one the middle one has all four of these entities well of course there are probably going to

be more kinds of components than these four but this is just for the illustration purposes for the explanation uh and the way we retrieve any information about these components is that we just go through the list and see if it has a component of this type for example if you're looking for a geometry component in an entity then we go through its component list and check if it has a geometry component and if not then we return no it works fine as long as you are not going to do a lot of calculations on thousands

of entities every frame of your game like in the editor of course we don't do that we just do it whenever i select an entity and it's retrieved once and that's basically it but in the game engine we have to process a lot of these this information every frame so that means at least 30 or 60 times per second for possibly hundreds or thousands of entities and that kind of just makes your cpu very sad because cpu is just sitting there waiting for the for all these memory fetches to come in and do something with

one of them and then wait again for the next piece of information and then yeah it kind of gets boring for the cpu this way very fast the way i'm going to implement these entities and their components in the engine is a bit more data oriented so i'm going to use indices instead of instances so i'll have an array for example for the transform component i'll have an array for that in a separate file that has all the positions and orientations and skills in the same array and then i just have an index to that

array in my entity list so that means that these indices by the way start at zero so to be more precise but here they start at one one two three four uh that means that whenever we have an entity that doesn't have a particular component that we then use one of those invalid indices to indicate that this entity doesn't have that component and the way we can look up components is then very easy we just know that for every component there is an entry in the list of components for entities so for example for geometry

we know that its index is in the third slot one two three and if this third slot is minus one that means that the entity doesn't have a geometry component so these are also all 32-bit unsigned integers and yeah this is a bit or actually quite faster to process than the object oriented method but there is still room for improvement uh right now if you would implement it like this then we would have a list of components like transform and then script id and then geometry id and rigidbody and then we would repeat that in

the next entity so that then the transform ids would be alternated by three other indices or at least three other indices and that introduces a lot of cache misses as well so to make a further improvement i would do the following uh here was the first idea of data oriented design and i could do the same but then give each kind of in each type of index their own array so if i i'm only looking for geometry ids i can just go through this array of geometries and without involving any other element in between two

indices so that would be even faster and yeah that's how i'm going to uh implement the entity and components here and the entity basically is just a list of indices now it's not even a class or anything like that and that makes your cpu go super saiyan and before i start implementing the entity and components i would like to explain something more about the indices that i'm going to use imagine that we have this list of entities entity information in some kind of array and and each slot has an index so here in the second

slot we have entity number two it's sitting here being happy and there is an object somewhere in our game engine or in the game code that refers to this element but at some point we are going to delete this entity and later on we'll add another entity that will sit in the same slot because we are of course reusing these slots to save space on the memory and now this reference to this entity isn't valid anymore because if this object would ask for the information of this entity it will get the information from the new

entity and not the old one so it will have for example if you would ask for an for a geometry component it will it would get the geometry of the new entity which could be a mountain instead of an apple which would have been the the old entity so that's a problem and to solve this i'm going to slice each index into two parts a small part of it for example 8 bits of it or maybe 10 bits depending on how often we are going to remove and add new entities that part i'm going to

use as a generation part and the rest of the index is the index into this array and each time we put another entity here i'll just increment the generation so for example for this new entity i'll have the generation one because it was zero first and now it's a new generation and if you would remove this one and add another one then the generation would become two but the index would uh stay the same because it's still in the second uh in the second slot of the array right this way if we now if our

object would request information about uh about the entity in this index then we could compare their generations to each other and determine if we are talking about the same entity now because of this mismatch we can infer that this object has an old has a reference to an old entity and we can tell it that it doesn't exist anymore and then it can't handle that case so yeah this is the first thing i'm going to write because the indices are rather important in the entity component system that i'm going to implement and it is basically

roughly based on something i read a long time ago in a block of stingray engine and let's see they are talking about this index bits and index mask and generation bits etc so the way i'm going to implement this index system is roughly based on their block i'll include a link to this one in the description of the video so you can read it yourself actually there is a lot of very useful interesting articles in this blog that could be really interesting to anyone who wants to learn more about game engine programming like me anyway

going back to visual studio now i can here again add a folder in this folder i'll put anything again like we did for the primal editor anything that has to do with the components and entities but before that i'll just add a header file for the id ids system index system that i just told you about here i'm going to include this common header again common headers first of all i'll just have a type name for our id that we can change whenever we want so what i mean by that is i have an id

type and that's a 32-bit unsigned integer so later on maybe like in 20 years when we have a need for more than 4 billion entities we can change that to like 64 or 64 bit so that would work or maybe some people would like even 16 bit to preserve memory that is also good so we can change the type of our indices like this and then i am going to say okay how much how many bits of this index i want to reserve for that generation part so right now i'm going to reserve eight bits

for it but we could also use six or 10 depending on what you're comfortable with because this generation if it's at 8 bit that means that if we would do this removing an addition of new entities like 255 times then this would wrap around and become zero again and then in that case if at that moment someone would ask for this index of zero zero zero two then they would still get an invalid or the wrong entity so that's extremely unlikely to happen but if you are not comfortable with that you could use more than

eight bits and for example if you would use 10 bits then this chance of a bug happening would happen every thousand to 24 refreshments of this slot if you understand what i mean i hope so yeah that's why i want to make that configurable as well okay next is the index bits and that's just how many bits the id type has minus the bits that we reserved for generation bits and then i'll have a mask for these parts so we can't we can for example get rid of the generation part and then have only the

index so we can go into our arrays for that index and retrieve information therefore we need these masks and if i only need the generation bits then i'll have a mask for index bits that would get rid of the index and the other way around is as i have an index for generation bits that would get off the generation part and leave me with the index well i am really sorry i was i forgot to zoom in the code all this time so it might have been a bit difficult to read up until now but

now it should be okay i apologize for that i um the visual studio sometimes has difficulty remembering my settings but that doesn't mean that i can be less careful so okay let's see everything is okay now all right so what i did here was to shift one bit to the right so for example if we would have we had a for a four bit type id it should be like this we have four bits and maybe one bit of generation type so we would have an index bits bits of three so if you would shift

one one one two three like this and then subtract one from it this binary value would become 0 1 1 1. and this gives us exactly the mask that we need to isolate the index so we can have an index id and this value and the generation part whatever it is will because it's ended by zero it will become zero and then we are just left with the index part and i can do the same for the generation mask and i need to know what indicates an invalid id type remember we have this these types

of invalid indices i could use something like because we are using a 32-bit type id i could use these oh i need to change this i could use this 32-bit invalid id but beforehand of course we don't know how big our id type is right so i still can use minus one for this and this gives me like an invalid id for any any type of type id type so you can see here now that's for four billion something and that means that all the bits are set and if i would change this to 64-bit

for example then this also would change to some big number and for 16 bits it would become 64k basically and for eight bits it is a char hell okay now i also need to to have a generation type because i'm going to remember the generation in the generation indices sometimes in an in a separate array as well and then i need to know in what integer type i can save generation okay so to determine what is the smallest integer type that i can use to fit this amount of generation bits in it i'm using something

called a conditional and a conditional is very simple actually there is nothing magic about it first i'm going to look up in which header it is defined so i can include that so i think i can use type info for that for now so what this actually is is just two structures a template type okay this is basically what it does this is a template with three template arguments a condition and two types and if the condition is uh true well for any condition that's not false then the compiler will pick this one and since

it's a boolean it's only it's it will only pick this one if it's true because we have a template specialization for whenever it's false and then it will pick the second implementation which returns this second type and then what this conditional t does is that it just takes the type so we can i actually look at the code here and it's these three things so again there is like a test and if the test is not false then the compiler will pick this one which returns the first type and the second type is returned only

when this test is false and the conditional t will give you this part so we don't have to type this every time so now i can remove this and then we have the generation type u8 because eight bits fit in a 8-bit unsigned integer if you would reserve 10 bits for generation bits then we see that generation type is now a u16 so that's good and then i would like to check a couple of things before [Music] we start working on the rest of this id system first of all if uh the generation type requires

more bits than its in generation bits then that's good uh it shouldn't have less bits than generation bits of course and that can happen if we increase generation bits to above 32 bits uh because then we will require a more a bigger integer but since our biggest integer is 64 bit that means that we can't have like every time if we go to more bits than our size of the generation type doubles so it goes from u8 to 8 u16 to u32 and the next one is u64 but the biggest index type that we can

have is u64 and if 64 bit of that is only generation bits then we can't use it right um so yeah the biggest generation part that we can have is 32 bits are actually 31 bits so that's why i use this assertion the next assertion that i want to use is whether the generation type is not the same size as the index type because it uh it needs to be smaller obviously otherwise it would uh it would be the whole index okay now i can go ahead and write the methods that i need for this

to work the first method that i want to write is want to check if my id is valid so this id is valid if it's not -1 and the next method is to get the index part of the the id so this masks the [Music] the id and gives only the index part of it the next one is to get the generation for for this to work we first need to shift the id to the left so we are only only left with the generation bits and then mask them okay and uh whenever i want

to inc increment the generation part i can write a method to do just that so here i get the generation of the id and add one to it and then i assert that it's smaller than 255 because otherwise we'll drop around and then well we could if someone asks for this id again then it wouldn't be correct like i explained before and then now we have the new generation and we shift it back to its place in the in the whole id and are that together to have a new id so for example we have

the generation one and then id index part is one this first line will well this function here the generation will shift this uh this first one all the way to the right so we have three index bits in this example so it will be here this is what it's this part gives back and then we add one to it so it will become two and now uh this part will shift it back with three index bits so this digit two will go back to its place and the index of the original id um will be

art with that so we are left with this id now i hope that's a bit clear with my explanation okay now i am ready to start working on entities and components so first i'm going to add a new header for the entity okay here instead of adding these common headers i'll have a shared header in the components folder because i'll need this id header in in the components and entities but i don't need it to be in the common headers because not everything in the engine will use this id part so here i'm going to

add a new item and this will include the common headers and the id as you can see it can't find those folders because well obviously they are in a different folder and so what i can do is to add this folder to additional include directories in the properties and i can't see my c plus plus options anymore because i don't have a c plus plus file visual studio can't figure out that this is a c plus plus project if i don't have a c plus plus file in it although i created this project as a

c plus plus library so uh anyway i can add to solve that problem i can add a new cpp file for our entities and now if i go back to my properties i can see the properties for c plus plus and in additional include directories i can set the project directory so this is a project directory and here is the common folder so that folder will be an include directory that all cpp files or header files can refer to apply and i should do that for the release as well i know you can see that

these files can be found and are included here so now i can go ahead and in entity header include components common this is the header for entity and i want to have two methods to create entities and remove game entities so this um is the initialization information for my game entity and for that i'll have an instruct and hearing i'll have all the information that we need to create a game entity and for removing a game entity i'll have a remove game entity method so this first one the create game entity will give me an

index to the array of game entities and because i'll have all kinds of indices for different kinds of components as well for entities i want some kind of differentiation between these indices otherwise i can mistakenly give an index for a component to this remove function and for that i can create a typed index so going back to this id header i want to have something that differentiates between ids in a debug build and reduced to u32 type or the id type in the release build so if we are in debug build i'll have a base

class or yeah base structure for our id types okay so here i have an id base and its constructor just accepts an id of type id type in our case is that 32-bit unsigned integer and it puts it in its private field to remember it and whenever i want to have it back in the form of id type then i can have an implicit conversion operator for that so whenever i have something like okay some type of id that's in that inherits from this id base for example an entity id and i have a u32

i can just do this and then it this would use this operator to give me back the id type now i'm going to create a macro that we can use to inherit from this base id type but first in case we are just building in release mode i can define it for that case so if we use this macro to create a entity id then this entity id type will be the same as id type in release mode in debug mode however i'm going to define that differently i'm going to define it to inherit from

this id base okay so here in my macro i'll inherit from this id base and i have two constructors one with an argument that will uh pass to the base and the second one is one without a parameter and that one just initiates its member variable with an invalid index now i can go here in components common then here i can define my id for the entities and i'm putting it here instead of in the entity header because i know that my components will need the id of their owner to know to whom they belong

so they need to know what kind of id the entities are using okay now we have a type of id that's specific for our game entities so now i can see that it's in the wrong namespace it's in primal id so that this is not correct that's because i forgot to end this internal namespace here so i can do this and now it should be correct yeah so it's now in primal game entity namespace so i can put this in their own namespace of game entity and now instead of having u32 i can have it

return an entity id and likewise i can use an entity id here and i can have one more method to tell if an entity is alive and that's basically the comparison of generations that i was talking about before so if this id has the same generation as the slot where this entity is in then it's alive before i implement these methods i also need to know what is in this entity info that i can use to create an entity and therefore i'm going to also add a transform component so we have something some example of

a component to work with so again here i'm going to have two methods to create and remove transform components again because the creation function will return an id i need to define a typed id for my transform component so here i use an initialization information structure for this transform and i'll tell this function what entity this transform component belongs to and this initialization information is another structure that contains the information for the transform component so this structure contains uh three floating point numbers for position a rotation quaternion that's why it's uh four components because quaternions

have four components and three components for the scale with a default value of one and well i also need another method to remove a transform component so the way i would like to to structure this creation of components is through the entity so i can include the information for all types of components in the entity info structure so i can for example do something like transform init info whenever i get this information in this method i can call also the creation function for the transform and then give it the pointer to that init info but

as we see this file doesn't know what this transform name space is yet or actually it doesn't know anything about this init info and one way i could solve this is just to include the transform header in here but i don't want to include all headers in all the other headers and then it will become like a cyclic soup of headers that we don't want to have a better solution would be to forward declare this structure i could i know that this is in a transform namespace like here transform and then it's defined here so

i can't forward declare it like so now we see that there is no problem anymore but i don't want to type this every time i have a new component so i'll define a macro for that as well okay so here i have a new macro that is basically this uh the forward declaration so whenever i call it with for example transform then it will substitute transform in here and then we end up with the code that i just had and after i have done this forward initialization i don't need this macro anymore so i undefined

it again so it couldn't pollute anything that would include this header file that's a good i think that's a good practice and yeah now i am ready to go and implement these methods but that's something for the next video thanks for watching if you like this video please feel free to like and subscribe if you join me on patreon you'll get access to the code on github so you don't have to type everything over from the video plus there are also other nice goodies and rewards exclusive to my patreon supporters please use the link in

the video description to check them out i hope to see you next time until then take care and happy game engineering [Music] you