by baggers
It's nanowrimo this month and I usually take this month to try implement some entire feature. It's not started great as I've been ill and utterly unable to get started.
I'm still trying to nail down exactly what I want this thing to be but in short it is a datastructure. Im going to ramble about it now and hopefully get some ideas in order in the process.
Common Lisp (CL) is a dynamic language, a particularly good one which allows iterative/live development but still a dynamic language with all the trappings, including a GC.
I want to make largish games in this language and, given that all these projects are for my own enjoyment, I want to really think about a lot of the componenets I'm using. If I wanted to just get something done I could use Unity #[0]
I have been looking into Jai and some of the data-oriented programming talks and decided I wanted to play with something in this space.
The thing that keeps coming back into my head is the following:
Let's say we have a game-object for an NPC in our game. Let's also assume we do want the GC to clean it up when we are done.
Now we make our NPC and we need to draw it each frame so we have some array of game-objects that are currently being rendered, then NPC is in there.
AI for NPC's generally cheat, we don't have a totally segregated brain for each one, we probably want some kind of group behaviour so the NPC is in the AI manager.
The NPC can collide with things and so we may have it in a spatial hashing system so we can query what objects are in a particular region in the game.
Very quickly we get a bunch of references to the game-object, so naturally we ask 'when will our game object be GCd?' and the answer is 'not until we remove it from all the systems'
So at this point we have to have some dispose method that explitly removes the object from all these places. We are part of the way back to manual memory management with one other disadvantage, we still don't know when the GC will actuall free this thing. Games are know to be sensitive to intermittent pauses, and there is no way to tell the lisp GC (or most gc's) when it is ok to go look for objects to free.
GC's naturaly have optimization strategies but eventually it has to walk through all your references looking for what to free. If we KNOW there is a bunch of stuff that can't be freed then why are we wasting the GC's time in the first place #[1]
We should lighten the load on the GC so that it can be used on the more interesting parts of the system we may be experimenting on #[2]
I want a datastructure that:
Let's dive in a little
I'm calling it Tables and may refer to map and reduce as queries as I am finding that treating this think like a table in a database is helping me design it.
Properties like not having explit control over things like order feel natural in the database world, but less so in arrays.
Also as I intend to allow you to control the memory layout of a table (for example picking AOS -v- SOA -v- AOSOA) it felt wrong to call it a 'flat-struct-array' or something that implies some direct dictation over the structure.
We are going to use the FFI to make allocators over static data. We will have to be careful here. One thing that garbage collected languages do REEEALLY fast is allocation so we need to make sure we don't shoot ourselves in the foot here. The reason GC'd languages do this well is that internally they manage the allocations and will often preallocate chunks of memory to allocate into too.
The data for our tables may be in static data but we are going to make it feel as 'native' as possible.
Often you don't want your data all packed together as increase chances of a cache miss. Usually there isnt much we can do in a dynamic language to know how our data is laid out. With tables we will and it should be easy to tweak.
This datastructure may use static memory, but I sure as hell don't want my programs to become a pointer-fest. 95% of the time you should never have to deal with the reality of the data relationships (just as you don't in the language now).
The exception of course is with foreign libraries. I have been working with a few libraries recently and they all very helpfully let you provide a pointer to you data so that, when you are in a callback for that system, you can refer to your objects. Sadly in lisp this has meant storing an index into a lisp array or worse.. a key to a hashmap.. blech.
I want to be able to hand off a 'safe' pointer for these cases.
I need to have an easy way to take a table, test data and functions and profile the datastructure. Bonus points for the system being able to optimize itself for a certain task.
Moving data between threads will be important. Look into safe ways we can do this.
This is all pointless if it can't be used live. Make sure we can redefine the columns/types of the table on the fly and have it keep working. It may not be able to maintain the size/locatity when doing this, but in those cases the system must communicate this to the user in a sane way. Basically, anywhere this is something going one behind the scenes the user should be able to hook a listener into it to 'hear' what choices the system in making.
Well fuck that got big. I don't think I'll get it all done, but there is the goal. I'll have a bash at it and see what happens.
Peace
#[0] clearly this is me arse covering here as I'm about to overanalyze a problem :p
Unity is a actually a very interesting case as it is static, but it is also garbage collected. You can easily find people have struggled when making larger games in it dur to performance expecially around the GC. One thing that makes me sad is when you have a cool selling point, but you end up avoiding that feature as time goes by because you learn that feature bite you later on in the development process.
When I experimented with making a simple entity component system (ECS) I watched this great talk by the folks who made Entitas which is an alternate ECS for Unity. They showed how their compile time code generation for c#, combined with smart caching gave them big performance boosts. The benefits of the feature remained but the cost was lower, this was pretty cool.
In the end I didnt feel at home in entity component systems. It felt hard to layout my game in my head in terms of an ECS. I want something which has some of the benefits (locality, working with the aggregate not single entities) but with a less restrictive interface.
#[1] of course GC is still helpful when you have references to the object you didnt know about.
#[2] Limited GC is a cool idea. I will now reference Carkmack to give my viewpoint some credence :p https://youtu.be/1PhArSujR_A?t=23m59s
Last Edited on Mon Nov 07 2016 15:29:56 GMT-0500 (EST)