Thrive Game Development

Development of the evolution game Thrive.
 
HomeHome  PortalPortal  CalendarCalendar  FAQFAQ  SearchSearch  MemberlistMemberlist  UsergroupsUsergroups  RegisterRegister  Log inLog in  
Welcome new and returning members!
If you're new, read around a bit before you post: the odds are we've already covered your suggestion.
If you want to join the development team, sign up and tell us why.
ADMIN is pleased to note that this marquee has finally been updated.
ADMIN reminds you that the Devblog is REQUIRED reading.
Currently: The Microbe Stage GUI is under heavy development
Log in
Username:
Password:
Log in automatically: 
:: I forgot my password
Quick Links
Website
/r/thrive
GitHub
FAQs
Wiki
New Posts
Search
 
 

Display results as :
 
Rechercher Advanced Search
Statistics
We have 1675 registered users
The newest registered user is dejo123

Our users have posted a total of 30851 messages in 1411 subjects
Who is online?
In total there is 1 user online :: 0 Registered, 0 Hidden and 1 Guest

None

Most users ever online was 443 on Sun Mar 17, 2013 5:41 pm
Latest topics
» THIS FORUM IS NOW OBSOLETE
by NickTheNick Sat Sep 26, 2015 10:26 pm

» To all the people who come here looking for thrive.
by NickTheNick Sat Sep 26, 2015 10:22 pm

» Build Error Code::Blocks / CMake
by crovea Tue Jul 28, 2015 5:28 pm

» Hello! I can translate in japanese
by tjwhale Thu Jul 02, 2015 7:23 pm

» On Leave (Offline thread)
by NickTheNick Wed Jul 01, 2015 12:20 am

» Devblog #14: A Brave New Forum
by NickTheNick Mon Jun 29, 2015 4:49 am

» Application for Programmer
by crovea Fri Jun 26, 2015 11:14 am

» Re-Reapplication
by The Creator Thu Jun 25, 2015 10:57 pm

» Application (programming)
by crovea Tue Jun 23, 2015 8:00 am

» Achieving Sapience
by MitochondriaBox Sun Jun 21, 2015 7:03 pm

» Microbe Stage GDD
by tjwhale Sat Jun 20, 2015 3:44 pm

» Application for Programmer/ Theorist
by tjwhale Wed Jun 17, 2015 9:56 am

» Application for a 3D Modeler.
by Kaiju4u Wed Jun 10, 2015 11:16 am

» Translator to Serbian here
by Simeartherist Sun Jun 07, 2015 6:36 am

» Presentation
by Othithu Tue Jun 02, 2015 10:38 am

» Application of Sorts
by crovea Sun May 31, 2015 5:06 pm

» want to contribute
by Renzope Sun May 31, 2015 12:58 pm

» Music List Thread (Post New Themes Here)
by Oliveriver Thu May 28, 2015 1:06 pm

» Application: English-Spanish translator
by Renzope Tue May 26, 2015 1:53 pm

» Want to be promoter or project manager
by TheBudderBros Sun May 24, 2015 9:00 pm


Share | 
 

 Engine Architecture

View previous topic View next topic Go down 
Go to page : 1, 2  Next
AuthorMessage
Nimbal
Programming Team lead


Posts : 258
Reputation : 24
Join date : 2013-03-17
Age : 32
Location : Ratingen, Germany

PostSubject: Engine Architecture   Sun Mar 31, 2013 4:29 pm

Hi everyone,
this thread is for discussing the basic structure of our engine.

Basics

We'll use the entity / component approach. Excellent introductions to this topic can be found at any of the following links:

  • Entity / Component Primer
  • Game Engines 101 : The Entity / Component Model
  • What is an Entity Framework?

Daniferrito also posted an overview in another thread.


Design Notes

To be filled out soon...

I'll update this post as the final design crystallizes.

Back to top Go down
View user profile
Nimbal
Programming Team lead


Posts : 258
Reputation : 24
Join date : 2013-03-17
Age : 32
Location : Ratingen, Germany

PostSubject: Re: Engine Architecture   Sun Mar 31, 2013 4:58 pm

At the risk of sounding negative (first rule of discussing programming: you are not your code), I'd like to discuss some problems I have with the current state.

Concerning Nodes

First, I'm not entirely sure about the actual purpose of "Nodes". As far as I can tell, they are just a form of optimization, basically gathering direct pointers to components that could be retrieved on the fly. If that's their only purpose, I wouldn't "waste" an important sounding name like "Node" for something that simple. Especially since some systems can make do with a single component just fine, only the more complex ones need several components all the time.

As an alternative, I propose the following plan:

Plan A: We remove "Nodes" as a concept from the design. Systems that need several components should retrieve them on-the-fly by querying the entity (or whatever holds the components) for each update. If, and only if, that turns out to be a measurable performance bottle neck, we can pick out critical systems and implement Plan B for them.

Plan B: We add internal caching to a system. The system holds a map with entities' ids as keys and a suitable data structure containing (shared?) pointers to the entities' relevant components. When an entity is added / removed or an existing entity's component makeup changes, all systems are notified. The systems performing internal caching can then invalidate their cache for the changed entity and rebuild the cache entry before their next update.

Who keeps the data?
Ideally, each piece of data is only present once in the whole system. If a system or other part of the engine needs frequent, direct access to some component for whatever reason, it should only store it as a pointer or reference.

I would suggest using std::shared_ptr for that. They carry a performance penalty, but play well with multi-threading and a simple (but easy to abuse) safeguard against accessing destroyed objects. As an alternative, we could store an std::weak_ptr, but we will have to be very careful about checking for a successful call to lock

To notify interested parties about data changes (so they don't have to poll), we can use the signalling system I described in the Scripting thread.

I'll continue in the (GMT+1) morning.
Back to top Go down
View user profile
Daniferrito
Experienced


Posts : 726
Reputation : 70
Join date : 2012-10-10
Age : 22
Location : Spain

PostSubject: Re: Engine Architecture   Mon Apr 01, 2013 5:41 am

I also think that nodes are the less usefull of all the entity framework. However, I have a few concerns about yor plans:

A: Exsctly what you said, performance. One of the purpouses of an entity framework is having all the funcionalities separated into as many systems as possible. If we follow that, we will have a lot of systems. If all of them have to scann all entities each cycle, it will get too processor intensive. We can try it and see how it works.

B: How is that different from the nodes? All the difference i see is that you would keep only a pointer to the entity, instead of its components. That would reduce the memory cost (only storing one pointer instead of 1-3 for each node) but it would increase the computational cost (intead of having the components directly avaible, we would have to search them through the entity's vector of components. Its a tradeoff, and i my vote goes to the actual nodes (memory is less important than processor)

No matter what we do, we should keep the code as interchangable as possible, in case we need to change system. The only thing i can think of right now is using methods to add and remove components, so we can notify whoever is needed.
Back to top Go down
View user profile
Nimbal
Programming Team lead


Posts : 258
Reputation : 24
Join date : 2013-03-17
Age : 32
Location : Ratingen, Germany

PostSubject: Re: Engine Architecture   Tue Apr 02, 2013 4:09 am

After some thought, I agree about Plan A being too naive for those systems that only handle a couple of entities. Teaches me to write about stuff like this late in the evening.

Now about the difference between Plan B and nodes (as they are described in this introduction). Nodes require the engine to know which kind of nodes the systems need. Why should anyone but the systems need to know that? So Plan B is to have the engine tell all systems about new, removed and changed entities and the systems themselves cache their relevant components internally. That way, we can easily change the components a given system handles and only need to touch this one system, nothing more.

I'd also like to use another name for "nodes". As I said, "node" sounds like an important concept, while in reality, they are little more than an optimization by caching. To make that clearer, we should probably call these data structures "ComponentCacheEntry" or similar.

But now to a different matter we should think about now, before we have to hack it in because we didn't account for it in the design.


Multithreading

Utilizing multiple cores will be essential. Maybe not in the microbe stage, but in the later stages, physics and AI (not to mention rendering) will become much more complicated. If we don't want to completely rewrite the engine for this, we should implement multithreading as early as possible.

I couldn't find much information about multithreading in an entity / component framework, but there are some really good discussions about multithreaded game loops:

  • Multithreaded renderloop (4 parts in total)
  • Threading and your game loop
  • Multithreaded game engine architectures

My idea to add multithreading to our engine is heavily inspired by the first link. A TL;DR of the linked article for those with short attention spans (why are you still reading, then?):

  • The world state of the game is split into the "render state", which contains all data required by the graphics engine to draw a frame and "rest state" which contains, well, the rest.
  • The render state is triple buffered. One of those buffers is the "update target" and is currently updated by the update thread. Another buffer is used as a read-only "update source" by the update thread so it knows what happened in the last frame. The render thread uses either also the update source or the third buffer, which is also read-only.
  • When the update thread is done with one game frame, it selects the oldest render state buffer that is not used by the render thread. That buffer is the new update target. The update source is the buffer it just finished updating.
  • When the render thread is done with a display frame, it selects the current update source (which is the latest state) to pull data from for the next frame.

That way, there's always a render state buffer available that can be safely updated by the update thread. The render thread only ever sees a fully updated render state.

The drawback of this approach (apart from the increased memory requirements of the triple buffer) is that it doesn't scale very well. If we wanted to add another thread for physics, a triple buffer wouldn't suffice anymore because inevitably, the situation arises where the update thread is done and all buffers but the latest update target (which just finished updating) are locked by either the render or the physics thread. So a quadruple buffer is needed. Then we add another thread dedicated to AI, and we need a quintuple buffer and so on.

The solution I propose is to have a dedicated "state" component and accompanying system(s) to communicate between the update thread and the auxiliary threads for rendering, AI, physics, and so on. I'll call those threads "processes" from now on. The state components are triple buffered (as described above) and contain everything their respective processes need to do their work. The render state component, for example, contains the following:

  • Transformation matrix
  • Whether it's a sprite, 3D object or light source (probably handled through subclasses)
  • If a sprite, the texture to render
  • If a 3D object, the mesh and material to render
  • If a light source, the type, direction (if any), intensity, color and so on
  • Probably much more

Each entity that wants to be rendered in any way will need at least the render state component. Additionally, it will need the usual components for rendering like a transformation, a render component and so on. Those components are used by the update thread to indirectly change the way the entity is rendered. I'll call those components the "update-side components". Then we introduce a system "RenderPostUpdate" that will be updated as one of the last systems by the update thread. This system will copy all necessary data from the update-side components to the render state component, handling the buffer selection along the way.

Now let's see how we can add another thread for, say, physics. We'll need to define a state component for that, which should contain the following:

  • Transformation matrix (again)
  • Collision hull
  • Material (bounciness, etc.)
  • Mass
  • Velocity
  • Acceleration

We also need a the necessary update-side components for that. And a "PhysicsPostUpdate" system that handles copying the data from the update-side components to the physics state component. Then the update thread can apply acceleration at its leisure and the physics thread will handle the update of velocity and position... wait, something's missing. How will the update thread know about those values when the physics thread computes them? That's where another system "PhysicsPreUpdate" comes in. The physics thread will write its changes back to the physics state and the PhysicsPreUpdate, which is updated as one of the first systems in the update thread, will copy the data from the physics state component back into the update-side component. We may have to introduce quadruple buffering here to do this safely, though.

So, the advantages of this system are that it scales to an (almost) arbitrary number of threads. If we want to offload AI to another thread, we can. Animation? Yep. Evolution? No problem. It should also be relatively easy to implement. The only critical part I see is the buffer switching mechanism.

Of course, there's no such thing as free lunch. We'll have to accept increased memory requirements. All data relevant to the processes will have to be in memory at least 4 times (once on the update side, triple-buffer in the state component). Five times in case the process has to communicate back to the update thread. On the other hand, heavy-weight data such as textures should be held by pointer anyway, so the necessary memory may not be as much as I think.

There's also the performance penalty for updating the state components, but most of those are only a few bytes big, so I reckon that the copying will come out to a rather low percentage in the grand scheme of things.

So, anyone got a better idea or wants to poke holes into mine?
Back to top Go down
View user profile
Daniferrito
Experienced


Posts : 726
Reputation : 70
Join date : 2012-10-10
Age : 22
Location : Spain

PostSubject: Re: Engine Architecture   Tue Apr 02, 2013 8:04 am

About Nodes/ComponentCacheEntrys :

I don’t mind about the name, so if you feel that ComponentCacheEntry makes more sense, we can change it. My only concern is that it is much longer than node, and harder to remember.

I agree that making each system handle its own list of ComponentCacheEntrys makes more sense. The only reason not to is if a lot of nodes are shared among systems, but that shouldn’t happen much. There are two ways I can think of:

First way. Without adding anything. The methods to implement would be:
-Each time an entity is added to the engine, the engine should notify all systems to cache that entity if needed.
-Every time an entity gets a component added, only if that component is one of the needed by the system, check if all components are present and add it if needed.
-When a component gets deleted, if that component is needed by a system it needs to delete its whole cache and rebuild it
-When an entity is deleted, either all systems need to rebuild its whole cache or only the systems affected.

Second way. Adding an extra variable at each ComponentCacheEntry to know what entity it is from. Methods:
-Adding an entity or a component is the same.
-Removing doesn’t require rebuilding caches. We only have to check if the affected entity is on the cache and remove that entry.
I prefer the second one. Again, it is a tradeoff of memory against processor, and I prefer to save on processing power.

About Multithreading:

I wasn’t thinking on something that complicated, but I agree that it is something we need to get done early on. Here is my idea:
(Note that all the multithreading I have done was on java, so some extra problems could arise on c++ that makes my idea impossible)

As far as I have worked, all problems with multithreading come when one thread is working through a vector and a second thread modifies it, or when a thread destroys an object that a second thread is looking at at the moment. So if we keep all object destroying or vector modifying on a single thread, there should be no problems:

The main thread (the one running the engine class) starts off as many threads as possible. Then, once an update starts, it notifies all threads that they should start working. Active threads ask for a task to do, and the main thread gives them a system to run. Once a thread finishes with its task, it asks for a new one, until all tasks are done and they are put on wait mode. Instead of deleting entities or components, it marks them for deletion. Once all tasks are done, the engine deletes the required entities and components. Then it just waits until next frame occurs and it starts with the process again. The threads are never destroyed, only put in wait mode until they are needed.

This brings one problem as tradeoff:
-A system could use updated or unupdated data. That is, data that has just been updated or data that was updated last frame. That will bring some inconsistencies, but they should be small enough to be negligible.

This should be easier than your way, but has inconsistencies, which your way prevents completely.
Back to top Go down
View user profile
Nimbal
Programming Team lead


Posts : 258
Reputation : 24
Join date : 2013-03-17
Age : 32
Location : Ratingen, Germany

PostSubject: Re: Engine Architecture   Tue Apr 02, 2013 9:04 am

Daniferrito wrote:

A system could use updated or unupdated data. That is, data that has just been updated or data that was updated last frame. That will bring some inconsistencies, but they should be small enough to be negligible.

That may be too optimistic. For one, imagine a complex object that's composed of several entities. Maybe a cell with many organelles, all modeled internally as separate entities. When this cell moves quickly across the screen, we will have to update each organelle's position one after another to keep them together. Depending on the velocity, it may happen that organelles are rendered outside the cell because they haven't been updated yet.

Furthermore, physics engines are notoriously sensitive to invalid input data. Collision resolution, for example, usually works (at least partially) by applying a separation force between two objects. If the update thread applies another force (maybe due to controller input to get the player's cell moving), both the update thread and the physics thread will probably want to modify the same variable. If the timing is wrong (and it usually is more often than not), one of the forces will be ignored, resulting in either an unresolved collision or unresponsive controls.

And then there's a much more fundamental problem. Reading / writing a double variable (and many other types) is not guaranteed to be atomic. So it could happen that when one thread writes a double and another one reads it, the reader could get 2 bytes of the old value and 6 (or whatever the remaining size is) of the new value. That could result in a nonsensical value, which, again, is especially fatal for physics simulations.
Back to top Go down
View user profile
Daniferrito
Experienced


Posts : 726
Reputation : 70
Join date : 2012-10-10
Age : 22
Location : Spain

PostSubject: Re: Engine Architecture   Wed Apr 03, 2013 1:27 am

Well, if physics are not consistent all the time it is not a big deal. You wont face the exavt same situation again. And if the updates are done often enough, mistakes wont be too big.

The problem is if the second problem you mentioned, if reading and writing to the same variable at the same time. That might make your way the only way.

Edit: I don't really understand your plan for multithreading. Is it to calculate stuff using a previous game state as input, as the acceleration you mentioned, as often as possible and then on the main thread, taking that acceleration and using it syncronally? If that is the case, i have a few concerns.

First off, if the physics thread is choking, accelerations wont update. if accelerations don't update, an object might go through another without the game noticing. if you make sure all systems are updated before starting the next cycle, that might be solved.

Let me know if this scheme is right:

Update n just started. the main thread is taking all the results calculated on update n-1 and adding them to the current game state, which is update n-1, to create update n. while that is happening, all systems running on different threads are taking the previous game state (n-1) to calculate their results, which will be used to calculate update n+1. Once all systems and the main thread are finished, the next update begins.

Probably it is not right, as this only needs two buffers (the one you are reading from and the one you are writing to, with probably an extra one for graphics).
Back to top Go down
View user profile
Nimbal
Programming Team lead


Posts : 258
Reputation : 24
Join date : 2013-03-17
Age : 32
Location : Ratingen, Germany

PostSubject: Re: Engine Architecture   Tue Apr 09, 2013 3:00 pm

Sorry, I didn't see your edit until just now.

Daniferrito wrote:

First off, if the physics thread is choking, accelerations won't update.
I assume by "choking", you mean that the physics thread has so much work to do that it can't update at a steady 60Hz (or whatever target framerate we choose) anymore. If we get to that point we probably have a design problem because too many physics entities are in the world. Also, I'm not sure which accelerations you are referring to. The physics engine will (ideally) be the sole system responsible for moving stuff around. So until the physics thread is done, everything stays where it is. Meanwhile, the update thread (i.e. the game logic) may still apply forces to entites, maybe in reaction to the player pressing the movement keys. Those forces will be ignored by the physics engine until it is done with the current frame.

The problem about objects passing through another is a fundamental one that can't be reliably solved by making the systems update in lockstep. After all, this problem happens if the physics timestep is larger than the time it takes for the fastest object to fly through the smallest object. So lockstep or asynchronous, we can miss collisions either way. What might be a little easier in a lockstep update is for the game logic to reliably apply forces. It would prevent the update thread from overwriting forces that weren't applied yet or unintentionally exaggerating a force by adding to it multiple times.

Daniferrito wrote:

Let me know if this scheme is right:
I highly recommend the first article I linked about multithreaded gameloops. It explains quite well why three buffers are needed.

Alright, now to some new stuff that needs addressing.

Entities and their Components
I'm happy to report that I'm about 70% done with the Lua integration. It's not as neat as I hoped, but I'll describe the problems with my implementation when I'm at 100%. To get there, I'd like to refactor the current entity and system classes to be more agreeable with the Lua side. The component class already became a victim to that.

The main issue I'm unsure about is whether to allow multiple components of the same type for one entity. For example, if we have a component for rendering a mesh, do we want an entity to have multiple meshes by adding multiple mesh components to it? Or should we create one entity per mesh and "glue" them together somehow?

In the process of writing the above, I realized that the first approach would bring with it a great many problems. Mostly because multiple components only make sense for certain component types. After all, why should an entity have two positions? Quantum state? So I'll go with the second approach and we'll have to figure out a way to make an entity stick to another, which shouldn't be too hard. We could either attach a physics joint between the two or have a system for maintaining a parent / child relation between entities, including updating the children's positions, orientations, etc.

Still, if you have any input on "multiple components of the same type", fire away.
Back to top Go down
View user profile
Daniferrito
Experienced


Posts : 726
Reputation : 70
Join date : 2012-10-10
Age : 22
Location : Spain

PostSubject: Re: Engine Architecture   Tue Apr 09, 2013 8:11 pm

Ok, i was thinking of a phisics thread that only updated accelerations.

Well, and by system, i hope you are refering to a aglomeration of actual systems. Its better to have six small systems than to have one big one.

Yes, objects passing through one another is a common problem. Somephysics engines solve it throug raycasts, but i believe that is costly. Another thing we can do is setting a maximum value for the timestep, ex. If the real timestep is over 50ms, behave like it was a 50ms timestep. That would make the game strange when systems are chocking (yes, i mean rhat, i cant think of a better name) but wont give off strange results.

I get now the buffers. 2 if you are lockstepping, 3 if you are rendering, i believe 4 for a mix of those.

Most entity frameworks face that same question. The usual response everywhere i lookedwas to only allow 1 component of each type unless you strongly need abother thing. You can always define a component that contains an array of models.
Back to top Go down
View user profile
Nimbal
Programming Team lead


Posts : 258
Reputation : 24
Join date : 2013-03-17
Age : 32
Location : Ratingen, Germany

PostSubject: Re: Engine Architecture   Sat Apr 13, 2013 9:50 am

I just pushed the current state of the Lua integration and accompanying entity / component framework to a new branch "lua" in my fork. It's not complete yet, so don't expect to run any Lua scripts. But if anyone wants to have a first glimpse at the C++ code, it's there.

Here's the roadmap ahead:


  1. Add a reusable caching mechanism ("nodes", if you want) for component groups (Done)
  2. Implement some basic systems for rendering, input and rudimentary physics
  3. Once certain that the API is usable, document it with doxygen
  4. Implement a way to add / remove components from Lua scripts
  5. Add a way for Lua scripts to be parsed and run during startup
Back to top Go down
View user profile
Nimbal
Programming Team lead


Posts : 258
Reputation : 24
Join date : 2013-03-17
Age : 32
Location : Ratingen, Germany

PostSubject: Re: Engine Architecture   Mon Apr 15, 2013 2:35 pm

So, I would have loved to go right ahead with point 2 on my agenda and implement some example systems and components. However, after thinking about it, this might not be the wisest course of action, because there's no scaffolding for the multithreading yet. So I decided to attack that first, to head off any trouble we might have with putting it in as an afterthought.

The problem I'm having right now is that I didn't consider multithreading (more specifically, the synchronization involved) when implementing the Lua-accessible properties. During the last hour, I typed out at least 4 different solutions to that. Each time, I banged my head against the wall because the solution couldn't work either because of potential crashes, racing conditions or simply because they were too complicated. Maybe message passing between the threads could work. But that's always so messy, ugh.

Anyway, Daniferrito asked what he (and other programmers, should they read this) could do without causing friction. Problem is, there isn't much in the way of coding yet. I may have to throw out some things I have done already and if someone implements any systems and components based on the current state, chances are that the work will have been for naught.

However, there is some conceptual work to be done, if there are any takers: Sketching out the systems and components necessary. If we already know how the basic components will look like and how their accompanying systems are supposed to work, we can hit the ground running once the basic engine is complete. For example, to build a camera entity, we would need at least the following:

Spoiler:
 

The accompanying system CameraSystem would filter out all entities that contain at least the above components and update a camera object in the Ogre scene accordingly.
Back to top Go down
View user profile
RodGame
Newcomer


Posts : 94
Reputation : 15
Join date : 2013-03-18

PostSubject: Re: Engine Architecture   Mon Apr 15, 2013 2:58 pm

Sorry if this post doesn't bring anything to the actual conversation, but I didn't post on this thread yet.

I just wanted to say that I've read all the link you posted above for entity-component system(and even some other to answer question I had). I still have to go trough the Multi-Threading links. I want to make sure that I understand all of this well for when I'll work on this. However, I can't be of any help yet because you're way ahead of me on those topics. And as you said, it would only add more friction to the development.

Nimbal, you've done an amazing job so far. Building a good framework is so important at this point in the project and I think we're on the good way. I don't have much time lately but I might try to tackle a component architecture as you pointed in the last post. If anyone else want to do it, go ahead. If we eventually comes with two solution, the merge will probably be better than both separated.

All-in-all, I just wanted to say that I follow you on those discussion and that I'll be ready to code when things will be ready. I also think that this should become the main branch. The old one is outdated and it's only more complicated to go to see the right code.
Back to top Go down
View user profile
Daniferrito
Experienced


Posts : 726
Reputation : 70
Join date : 2012-10-10
Age : 22
Location : Spain

PostSubject: Re: Engine Architecture   Mon Apr 15, 2013 3:55 pm

If you mean the "master" branch on the github, i merged the Daniferrito branch into it a few hours ago.

Actually, the code wasnt outdated. We are mostly using it, as only about 50 lines got removed. (I just checked and it is not even removed. The lines are still there, its just that we are not using them)

I'm going to make a thread to discuss what components and systems we need, and how they will be done.
Back to top Go down
View user profile
Nimbal
Programming Team lead


Posts : 258
Reputation : 24
Join date : 2013-03-17
Age : 32
Location : Ratingen, Germany

PostSubject: Re: Engine Architecture   Tue Apr 16, 2013 4:01 pm

The good news: I think I have found a solution for the threading problem. The bad news: it uses shared_ptr, which might bring a performance impact. The runtime penalty should be minimal though, especially if we don't misuse the classes I wrote. It's also a little involved to write a component that has to share data across threads, especially if it should be scriptable from Lua. I just pushed the current state to the lua branch in my fork.

Some notes on this (rarely a post without at least one list from me, it seems):


  • Data that is shared across threads has to be assigned to a so-called "state group". For any given state group, exactly one thread, the "writer", should make modifications to data belonging to that group. This thread must not change during runtime, so data cannot be moved across state groups (unless it's explicitly copied, of course). At most one other thread, the "reader", can safely read from that data simultaneously. For example, I already defined a state group "RenderInput". Data in this state group is modified by the game logic thread and shared with the render thread.
  • All shared data is triple buffered. One buffer is the "latest state" and contains the last complete update to that data. The second buffer is the "stable state", which can be locked by the reader and will not change until unlocked again. The last buffer is the "working copy" which can be locked by the writer for modifications. Once unlocked, it becomes the latest state.
  • The buffer locking / unlocking happens globally, so (providing correct usage) all data within one buffer has a consistent state.


Next up: Implementing a basic rendering system in a separate thread to see if it actually works.
Back to top Go down
View user profile
Daniferrito
Experienced


Posts : 726
Reputation : 70
Join date : 2012-10-10
Age : 22
Location : Spain

PostSubject: Re: Engine Architecture   Wed Apr 17, 2013 4:17 am

Great!

As long as the complexity of writing new components is not too hard, dont worry. And if you provide a guide on how to do it, even better.
Back to top Go down
View user profile
Nimbal
Programming Team lead


Posts : 258
Reputation : 24
Join date : 2013-03-17
Age : 32
Location : Ratingen, Germany

PostSubject: Re: Engine Architecture   Thu Apr 18, 2013 4:03 am

I simplified the usage of shared state a bit, but I need your input on how to handle shared data from Lua. As I said, shared data is triple buffered, the three buffers being "latest", "stable" and "working copy". Now, say we have a property "health" of a component that has to be shared across threads and is thus triple buffered. If we write from Lua into this property, the new value is always written into the working copy, so that's unambiguous. But what about reading the value? We can take the value from either the "latest" or "working copy" buffers.

In most cases, reading the latest buffer would be confusing, as it wouldn't reflect changes you just made:

Code:

oldHealth = player.health
player.health = player.health - 10
newHealth = player.health
if oldHealth == newHealth then
    # Wait, what?
end

That wouldn't happen if properties would be read from the working copy. But in other cases, it's useful to have an old, but consistent copy of the data available. I can't think of a sensible example for this right now, though.

Here are the options I see, feel free to propose more if you have an idea.

1. Read from latest, write to working copy
It's a simple solution, but will confuse script authors that don't read the manual. I wouldn't recommend it. (See edit at bottom)

2. Explicit Buffers
We introduce special fields for the Lua objects to explictly read from buffers other than the working copy:

Code:

# Read from latest buffer
latestHealth = player._latest.health
# Read from stable buffer
stableHealth = player._stable.health
# Read from working copy
newHealth = player._workingCopy.health
# Write to working copy (no choice here)
player.health = 10

Of course, this would preclude properties named "_latest" or "_stable", but that's why I prepended the underscores. We could explicitly forbid any property names starting with an underscore and reserve them for special stuff like this.


3. France it, we'll do it live!
Ha, take that, profanity filter! Ahem... anyway, Lua scripts will just access the working copy for both reading and writing, totally oblivious of the buffering. This is easy to implement and we can still implement option 2 at a later point if we feel the need. (Not a good idea, see edit below)


Edit: I just realized a real problem with only reading the working copy. When the working copy buffer is locked, it isn't updated with the data from the latest buffer. So the data in the working copy might be several frames old. In short, option 3 is out of the question.
Back to top Go down
View user profile
Daniferrito
Experienced


Posts : 726
Reputation : 70
Join date : 2012-10-10
Age : 22
Location : Spain

PostSubject: Re: Engine Architecture   Thu Apr 18, 2013 7:49 am

One second, how does this work? One thread is reading from state A, and writing to state B, overriding whatever you had there? If that's it, i see a big problem:

Let's say we are modifying the health because the creature got attacked.

player.health = player.oldhealth - 10;

After that, a different system realizes that the creature is starving, and it reduce the health again:

player.health = player.oldhealth - 5;

You see the problem? Health was only reduced by 5 points, while it should be reduced by 15.

The only solution i see to this is if we store all the changes we want to do incrementally, and then apply them all at once. Unless I'm missing something.
Back to top Go down
View user profile
Nimbal
Programming Team lead


Posts : 258
Reputation : 24
Join date : 2013-03-17
Age : 32
Location : Ratingen, Germany

PostSubject: Re: Engine Architecture   Thu Apr 18, 2013 8:09 am

Good point. The only feasible solution I see for this is to just copy the latest state to the working copy when locking the working copy, then use only the working copy in Lua. It will be a performance hit, though, especially when the copying is unnecessary. Any other ideas?
Back to top Go down
View user profile
Nimbal
Programming Team lead


Posts : 258
Reputation : 24
Join date : 2013-03-17
Age : 32
Location : Ratingen, Germany

PostSubject: Re: Engine Architecture   Mon Apr 29, 2013 5:18 am

Just as an update on the current state:


  • Signals are pretty much scrapped. They don't play well with multithreading and make it a little unpredictable when a particular piece of code executed.
  • Instead of binding to Lua manually, I'll go with oolua. It's pretty fast and will make it relatively straightforward to expose more complex components to Lua. Unfortunately, it doesn't support data members, so everything must be handled with getters and setters.
  • I've decided to copy a bit out of World of Warcraft's addon API. Entities can be predefined in XML (in addition to procedurally generating them in Lua or C++). An entity can have script handles that call Lua functions on certain events (e.g. every frame or when a key was pressed).


As a rough estimate, it'll be a few days to a couple of weeks until I plugged this all together.
Back to top Go down
View user profile
Nimbal
Programming Team lead


Posts : 258
Reputation : 24
Join date : 2013-03-17
Age : 32
Location : Ratingen, Germany

PostSubject: Re: Engine Architecture   Sat May 11, 2013 11:03 am

Triple post! But with good news! After fighting gcc, Ogre and luabind for a few days, I managed to put everything together. It compiles, runs and does.... something.

I'll liberally apply some Doxygen comments to the source code now to lower the bus factor. Bonus point for anyone who can make sense of the file "res/dist/scripts/test.lua" without documentation!
Back to top Go down
View user profile
Daniferrito
Experienced


Posts : 726
Reputation : 70
Join date : 2012-10-10
Age : 22
Location : Spain

PostSubject: Re: Engine Architecture   Sat May 11, 2013 11:17 am

Do i get even more extra points if i didnt ever saw lua before? Actually, its easier for me as i know what the code it is replacing is like.

The first 6 lines create a new entity for the background.

Then you add a callback. I have no idea what is it listening to or what it does.

Then, you create a new entity, called player, add to it the "Sinbad" model (the little ogre)

Finally, you add a callback for key presses. Whenever one of wasd is pressed, the entity accelerates in the pressed direction. I see we are using z as our vertical axis. I though it was y.

(After looking at the previous code, i realized we were using z as vertical the whole time)

Edit: Yes, increasing the bus factor would actually be good (you said decrease). I'll mess with the code i understaund while you write the coments.
Back to top Go down
View user profile
Nimbal
Programming Team lead


Posts : 258
Reputation : 24
Join date : 2013-03-17
Age : 32
Location : Ratingen, Germany

PostSubject: Re: Engine Architecture   Sat May 11, 2013 12:42 pm

Not bad. When you run Thrive, you may hit on what the callback does.

Anyway, I'm wondering how to best go about documenting the script interface. It will be pretty close to the C++ API, but not quite identical, so pointing script authors to the documentation generated by doxygen would certainly be comfortable, but may get confusing.

Here are the options I could think of:


  1. Use the doxygen comments in the C++ header files for both C++ and Lua, but explain the differences
  2. Create separate doxygen input files for documenting the script API
  3. Use doxygen for C++ and the Wiki for the script API


Option a keeps the script API's implementation and documentation close together, but script authors would have to filter out C++ specific stuff and vice versa.

Option b will require some more effort to keep the documentation in sync with the actual implementation. In my experience, however, forgetting to update the documentation is very common. It doesn't matter whether it resides in a different directory or a few lines above the implementation.

Option c is my least favorite because it can only document one version. If the script API documentation is part of the git repository, it can be updated at the same time as the script API itself.

Overall, I'd prefer option b. Any more ideas or additional input?
Back to top Go down
View user profile
Nimbal
Programming Team lead


Posts : 258
Reputation : 24
Join date : 2013-03-17
Age : 32
Location : Ratingen, Germany

PostSubject: Re: Engine Architecture   Wed Jun 19, 2013 3:40 pm

By now we have a somewhat functioning engine. It's not complete and it certainly isn't a game yet, but it works. And now I'd like to throw about 20% of it away by switching from multi-threaded to "single-threaded" (the quotation marks are deliberate). There are several reasons for this and I will try to outline them here.

While testing the possibility of using rigid body particles for agents and compounds in the microbe stage, I implemented an emitter of such particles that would fill up an area of the environment. Depending on optimization, it works alright for particle counts below 500. At least on Linux. On Windows, even with very few particles, the motion of the player microbe becomes jerky for whatever reason.

So far, I've ruled out thread priority and lack of motion interpolation. I found a problem with boost's sleep function we use for limiting the maximum framerate, but that turned out to not be the culprit either. So I'm stumped. I'm pretty sure that it's got to do something with the SharedState mechanism, but since the problem only seems to occur on Windows, it might be something else entirely.

There's also still a problem with thread synchronization where new entities are rendered before they are properly initialized. That's fixable, but not trivial.

Those two problems, and probably many more down the road, are symptomatic of the multithreading we employ. Back when I started out with a multithreaded approach, I expected problems like this, but I thought the additional effort was worth the potential performance gains. Since then, I've learned a bit more about game engines and how other developers design theirs, especially with respect to single vs multithreading.

As an experiment, I changed our engine to be single-threaded. It took some work, but nothing too complicated. The result is encouraging. The framerate is still at a comfortable level (about 100 FPS for 500 hundred physics entities on screen without too much collision). The code is easier to understand and reason about. We don't need weird systems that just propagate data from physics over script to the graphics thread.

In short, I would be very much in favor of switching to a "single-threaded" model. The quotation marks are there because Bullet and, with limits, Ogre still use multiple threads, but in a transparent way that doesn't concern us. We can also easily use multiple threads for the fluid dynamics simulation and anything else that's easy to parallelize.
Back to top Go down
View user profile
Seregon
Regular


Posts : 263
Reputation : 37
Join date : 2011-08-10
Location : UK

PostSubject: Re: Engine Architecture   Wed Jun 19, 2013 5:00 pm

From what Dani's explained to me of the multi-threading, and how difficult it has been to make some of it work, I would support going single threaded for most gameplay.  Would it be possible, though, to keep the option to do some tasks asynchronously?

What I mean is, rather than now where all threads (physics, scripting, rendering) contribute to every frame, and must finish their work before a frame can be shown; we instead have a single main thread which deals with that, but occasionally spawns worker threads (or uses a pool) to start tasks which don't need to be finished immediately.

Good examples would be the AI's auto-evo steps while the player is in the editor, or the auto-evo/population dynamics of areas outside the players view etc.  I realise none of these will feature any time soon, but it would be good to keep the option open.
Back to top Go down
View user profile
untrustedlife
Regular


Posts : 252
Reputation : 19
Join date : 2013-03-26
Location : [Classified]

PostSubject: Re: Engine Architecture   Sat Jun 22, 2013 11:55 am

I agree with seragen.

we need to keep that open, too many a game project of mine has gone downhill due to lack of planning for things like this.

-----------------
I AM BACK
Back to top Go down
View user profile
Sponsored content




PostSubject: Re: Engine Architecture   Today at 1:43 am

Back to top Go down
 
Engine Architecture
View previous topic View next topic Back to top 
Page 1 of 2Go to page : 1, 2  Next

Permissions in this forum:You cannot reply to topics in this forum
Thrive Game Development :: Development :: Programming-
Jump to: