3D Array of Bool

This is a discussion on 3D Array of Bool within the C++ Programming forums, part of the General Programming Boards category; Thanks to Budda, David, and everyone else. I will incorporate your ideas and run empirical tests to compare the speeds. ...

  1. #31
    Registered User
    Join Date
    Jun 2007
    Posts
    30
    Thanks to Budda, David, and everyone else. I will incorporate your ideas and run empirical tests to compare the speeds.

    I'll let you all know the results.

  2. #32
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Quote Originally Posted by cybernike View Post
    Let me state the problem more clearly. In a 1000x1000x1000 space, there are 1000 particles. We can only move one particle at a time, and the particle can move in one of the six directions by 1 unit as long as it is not blocked by the other particles.

    I am sure there are more efficient ways to represent the data in terms of space.
    However, please let me ask your opinion on this. Is there any other way that is faster or as fast as using a 3D-matrix to determine if a move is allowed. As I said, I wouldn't want to sacrifice any speed.
    Okay, given the updated information, using voxels is certainly going to be slower, for two reasons:
    1. It takes far more memory, and memory will probably be the bottleneck.
    2. Only 1 cell out of a million will be occupied, therefore every update will process 999999 empty cells for each occupied cell.

    Try using a list of particles plus a multiway-trie structure for the data.
    For a 1000-way trie this means an array of 1000 pointers that are either NULL, or point to arrays of 1000 pointers, which themselves are either NULL, or point to an array of 1000 bits.

    Write a function called e.g. 'trieLookup', that takes 3 parameters (x, y, z) and does a lookup in the trie structure to see if the point is occupied.
    Each update, iterate through the list calling trieLookup up to 6 times as necessary for each particle, then remove the particle from the multiway-trie structure, and insert it again at the new position.
    trieLookup should be very fast, still O(1), yet this uses much less memory than before.
    Using a free-list or custom allocator can make this even faster.

    You can trade off between memory usage and steps per lookup by making the trie size configurable. You may find that a 10-way trie of up to 9 levels gives even better performance due to less memory usage, for example.
    Better still, this method would allow you to scale up to 10000x10000x10000, no worries!
    Last edited by iMalc; 06-28-2007 at 02:30 AM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #33
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    My post crossed with Bubba and DavidP.

    A trie is much faster than a map in this case. It's log(k) levels vs log(n) levels (k is fixed), and has a much lower constant factor too (no tree rebalancing etc).
    Heck, I'll even write Add, Remove, and Lookup functions for you if you want. It's really easy.

    If you wanted to get really carried away, you could try and implement a Van-Emde-Boas tree... I haven't tried that myself yet though...
    http://en.wikipedia.org/wiki/Van_Emde_Boas_tree
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #34
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Okay, well I've just implemented my Multiway Trie idea.
    Haven't finished testing it, but I'm optimistic it should work well.

    You'll find it in the Useful Classes section of my web page (link in my sig).
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #35
    Registered User Queatrix's Avatar
    Join Date
    Apr 2005
    Posts
    1,342
    Quote Originally Posted by ChaosEngine View Post
    what the hell are you talking about?
    Compile and run this and you will see what I'm talking about.
    Code:
    #include <windows.h>
     
    int main()
    {
       BOOL boolean;
       boolean = (BOOL)((rand()%1000) - 500); // I'm putting an int into a bool here.
       char sz[250];
       wsprintf(sz, "boolean = %d", (int)boolean); // This puts the "bool" back into int from.
       MessageBox(0, sz, "Report", MB_OK); // As you can see.
       return 0;
    }

  6. #36
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901
    Just because you can cast a type to another doesn't mean that the types fundamentally hold one another.

  7. #37
    Registered User
    Join Date
    Jan 2005
    Posts
    7,344
    >> Compile and run this and you will see what I'm talking about.

    You are confusing bool and BOOL. They are two completely different types. BOOL is a typedef for an integral type, so of course it can hold integer values, while bool can only hold true and false.

    The reason a bool is a byte is because a byte is the smallest addressable size, and a bool variable must be able to have a unique address. This is why vector<bool> is screwy, because vectors work like regular arrays for all types except bool. When you have a vector<bool>, the individual bools are no longer addressable.

  8. #38
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,738
    Just to bring everyone onto the same page about vector<bool>:

    The 1998 C++ Standard Library defines a specialization of the vector<bool> class. To optimize space, the elements are packed so that every bool only uses one bit of memory. This is widely considered a mistake. vector<bool> does not meet the requirements for a STL container.For instance, a container<T>::reference must be a true lvalue of type T. This is not the case with vector<bool>. Similarly, the vector<bool>::iterator does not yield a bool& when dereferenced. There is a general consensus among the C++ Standard Committee and the Library Working Group that vector<bool> should be deprecated or entirely removed from the next version of the standard.
    Quote taken from Wikipedia.
    My Website

    "Circular logic is good because it is."

Page 3 of 3 FirstFirst 123
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 16
    Last Post: 05-29-2009, 08:25 PM
  2. Code review
    By Elysia in forum C++ Programming
    Replies: 71
    Last Post: 05-13-2008, 10:42 PM
  3. DirectInput help
    By Muphin in forum Game Programming
    Replies: 2
    Last Post: 09-10-2005, 12:52 PM
  4. How do I play an MP3?
    By Hunter2 in forum Windows Programming
    Replies: 28
    Last Post: 05-20-2002, 09:49 PM
  5. 3d array
    By Pamela in forum C++ Programming
    Replies: 1
    Last Post: 10-24-2001, 04:59 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21