3D Array of Bool

Show 80 post(s) from this thread on one page
Page 3 of 3 First 123
• 06-28-2007
cybernike
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.
• 06-28-2007
iMalc
Quote:

Originally Posted by cybernike
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!
• 06-28-2007
iMalc
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
• 06-28-2007
iMalc
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).
• 06-28-2007
Queatrix
Quote:

Originally Posted by ChaosEngine
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; }```
• 06-28-2007
indigo0086
Just because you can cast a type to another doesn't mean that the types fundamentally hold one another.
• 06-28-2007
Daved
>> 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.
• 06-28-2007
DavidP
Just to bring everyone onto the same page about vector<bool>:

Quote:

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.
Show 80 post(s) from this thread on one page
Page 3 of 3 First 123