Sign in to follow this  
Doggan

Unity Truth Table Data Structure

Recommended Posts

I am throwing some ideas around my head, but I want some feedback from the GameDev community. How would you go about implementing a 'truth table' in C++? i.e. what data structure would you use? Basically if I have some graph (nodes and directed edges), each node in the graph will have an associated truth table. The number of entries in the node's table is a function of the # of parents of the node (entries = 2^numParents). For example: 0 parents = 1 entry = t 1 parents = 2 entries = t / f 2 parents = 4 entries = tt / tf / ft / ff .. etc. Given the node, you will of course know the values of it's parents. These parent values are used to index into the current node's truth table. It gets tricky, though, because the # of indices used to index into the truth table equals the number of parents of that node. Because of this uniqueness to the problem, you can't use a simple associative array. This is essentially a Bayesian Network. It's so common I'm wondering how most applications go about implementing this. Thanks~

Share this post


Link to post
Share on other sites
In this case you could use a single dimensional array of size 2^N.


T *truthTable = new T[1 << numPredecessors];


You should then be able to use the predecessors' true/false as bits of the index into the array:


int index = 0;
for (int i=0; i<numPredecessors; ++i)
index |= (predecessors[i]->IsTrue() ? 1 : 0) << i;


This should also account for the "no predecessors" case where your index is always 0 (the first index).


Is that sort of what you wanted? The major downside of this approach is that it will use an astronomical amount of memory if you get a lot of predecessors.

If you have a large number of predecessors but only a couple entries in the truth table are true (or only a couple are false) then you would be better off with a set of bit-patterns that represent the "rare" state and assume everything else is the "default" state.

Share this post


Link to post
Share on other sites
... I started trying to write this and it wasn't much fun. But probably something with boost::multi_array<bool, N> and type erasure techniques (so that you don't have to know the number of dimensions ahead of time).

Edit: Of course, that's assuming you demand a pretty, iterative-subscripting interface. If you're willing to pack bits together, then just indexing into 2^N bit field is just fine. (Consider using a std::vector<std::bitset<32> > for example, and doing some shifting to figure out a vector index and a position within the bitset.)

Share this post


Link to post
Share on other sites
Thanks for the help!

Quote:
Original post by Nypyren
Is that sort of what you wanted? The major downside of this approach is that it will use an astronomical amount of memory if you get a lot of predecessors.

If you have a large number of predecessors but only a couple entries in the truth table are true (or only a couple are false) then you would be better off with a set of bit-patterns that represent the "rare" state and assume everything else is the "default" state.


The one thing I wasn't clear on, I guess, was that each entry in the truth table holds some float value (not a bool). So I guess I should have just called it a Bayesian Network instead of a truth table :) There is no way around the fact that a node with a lot of parents will use up a lot of memory storing these table entries.

Based on the above posts, I have come up with a solution, using an array indexing scheme. I can allocate the correct # of required entries for the table, and then use an indexing algorithm to index into the array.

Thanks again.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this  

  • Announcements

  • Forum Statistics

    • Total Topics
      628378
    • Total Posts
      2982347
  • Similar Content

    • By sveta_itseez3D
      itSeez3D, a leading developer of mobile 3d scanning software, announced today a new SDK for its automatic 3D avatar generation technology, Avatar SDK for Unity. The Avatar SDK for Unity is a robust plug-n-play toolset which enables developers and creatives to integrate realistic user-generated 3D avatars into their Unity-based applications. SDK users can allow players to create their own avatars in the application or integrate the SDK into their own production processes for character design and animation.
      “Virtual avatars have recently become increasingly popular, especially in sports games and social VR apps. With the advance of VR and AR, the demand to get humans into the digital world is only increasing”, said Victor Erukhimov, itSeez3D CEO. “Our new Avatar SDK for Unity makes it super-easy to bring the avatar technology into any Unity-based game or VR/AR experience. With the Avatar SDK for Unity now every developer can bring face scanning technology into their games and allow players to create their own personalized in-game avatars, making the gameplay much more exciting and immersive.”
      Key features of the Avatar SDK for Unity:
      Automatic generation of a color 3D face model from a single selfie photo in 5-10 seconds (!). Works best with selfies, but can be used with any portrait photo.
      Shape and texture of the head model are unique for each person, synthesized with a deep learning algorithm crafted by computer vision experts
      Head models support runtime blendshape facial animations (45 different expressions)
      Generated 3D heads include eyes, mouth, and teeth
      Algorithms synthesize 3D meshes in mid-poly resolution, ~12k vertices, and ~24k triangles
      Six predefined hairstyles with hair-recoloring feature (many more available on request)
      Avatar generation API can be used in design-time and in run-time, which means you can allow users to create their own avatars in your game
      Cloud version is cross-platform, and offline version currently works on PCs with 64-bit Windows (support for more platforms is coming soon)
      Well-documented samples showcasing the functionality.
       
      Availability
      The Avatar SDK for Unity is offered in two modes - “Cloud” and “Offline”. The “Cloud” version is available at http://avatarsdk.com/ and the “Offline” version is available by request at support@itseez3d.com.
      ###
      About itSeez3D
      At itSeez3D, we are working on the computer vision technology that turns mobile devices into powerful 3D scanners. itSeez3D has developed the world's first mobile 3D scanning application that allows to create high-resolution photorealistic 3D models of people's' faces, bodies and objects. The application is available for iOS and Windows OS mobile devices powered with 3D cameras. In 2016 the company introduced Avatar SDK that creates a realistic 3D model of a face from a single selfie photo. To learn more about itSeez3D scanning software and 3D avatar creation technology, please visit www.itseez3d.com and www.avatarsdk.com.

      View full story
  • Popular Now