This isn’t really a scripting question, more of a data structures one I suppose.
Anyway, consider the following grids:
I want to store the locations and states (represented by colors) of each cell here. The locations are relative to the central cell, so the information would be something like:
0 0 state 0
0 1 state 1
0 -1 state 1
and
0 0 state 0
1 0 state 1
-1 0 state 1.
Then for each configuration, I want them to return a single value - a probability. When the grid looks like the first example, it spits out a probability. When it looks like the other example, it spits out another probability. I’ll deal with whether they’re exclusive or additive later.
How might I do this? I would definitely start with a list - there can be a variable number of these configurations, and presumably the configuration storage won’t be a primitive type. But how do I store the configuration?
Remember, I want the entire configuration to return a single (user-defined) probability. A 3D array or list or dictionary would have all of these as separate entries with individual values. I suppose in a pinch I could do that (just divide the user-defined prob by the number of active cells and then put that value for each spot in the configuration), but it seems like a better idea to just have a single return value stored which gets called later.
Not sure that I fully understand what you want to get out of this, specifically what you mean by probability.
If you’re looking for a precise match of one grid or the other, you could assemble a string out of the cells involved (one color is one character) and then check equality.
The probability isn’t important - literally just a float (or double) value the user inputs that gets used later. I’m making a cellular automata where the state of cells changes based on probabilities.
That’s a good idea. As I was driving home I also thought of having a dictionary where the full configuration (say something like : (0, 0, 0, 0, 1, 1, 0, -1, 1) for the first configuration) is the key, and the value is the probability the user inputs. But I don’t know how easy it would be to check the key for that, and it would be a dictionary with literally only one entry.
How many total configurations are there? Is each cell just either 1, 0 or -1? If so, then the domain is 3^9. You can effectively store a configuration inside of an integer, and you’d only need 19k integers to store every possible configuration. Integers have at least 32 bits, so dedicate the first 2 bits to the state of the first cell, the second 2 bits to the second cell, and so on.
public override int GetHashCode()
{
int ret =
cell[0] + 1 &
cell[1] + 1 << 2 &
cell[2] + 1 << 4 &
...
return ret;
}
Well normal “neighborhoods” can also extend out to the next level–to a 5x5 grid (rare, but we do it sometimes). Additionally, the number of states is theoretically infinite, it’s defined by the user. I’ve used up to four before, but you could have any infinite number. Just using four though, it’s 4^25 = 1,125,899,906,842,624 possible configurations. To be fair though when using the larger neighborhood, it’s typically 12 neighbors, so in that case it would be 4^12 = 16,777,216.
Just checked what a ‘cellular automata’ is all about, and I find it really interesting. I’d be happy to see the final result if that’s possible. I’m not referring to source code, just interested in the way it looks like when it’s finished.
Unfortunately I don’t have any concrete / other idea how to approach this, but I’d say this could actually benefit from native code and all the tricks & features you’ve got there.
You probably want some kind of hashing solution. The problem is how to hash the grid state in a way that’s fast, gives good hashes (few collisions), and work for arbitrary grid sizes and state types. If you have that, you can just use an object representation of your grid as a key in a Dictionary, and you should be pretty good. Just remember to implement Equals correctly, so the Dictionary can handle collisions correctly.
I’ve actually already got the CA working, just not with this type of functionality. I had a different solution (thanks to a user here named takatok) previously which merely checked the number of filled neighbors of a different state. Additionally, I’ve actually used the program for research in a master’s program. A few images:
If the file names don’t make it clear (edit: nvm, you can only see the file names when viewing the image separately), the last two files are from the same “run” at different points in time. I’d post more but you can only attach 5 images at a time.
Let me point out that while many CA (such as the Game of Life, the most famous) are deterministic (you give it a certain neighborhood, it ALWAYS produces a “living” or “dead” cell), mine are probabilistic, which means you can get dramatic variance even in very simple systems.
I’ve also made a short little game using the same concept (though I haven’t distributed it publicly), basically having the user generate the level in real-time with a CA. And because it’s probabilistic, they get a new level each time (with the elements on the level defined by what the level looks like, so there’s additional variance there).
Presumably fast lookup. There are not going to be many states, and not a whole bunch of configurations, but there will be 10,000-1,000,000 agents using it every iteration.
I haven’t implemented it yet, but I thought the string idea was good. I could move through the grid in a certain pattern, say radially out from the center (starting at the center, then directly above it, then around) and give the coordinates along with state for each occupied space, and have that define a configuration. Like, for the left one in my OP it would be like how I did it before - (0, 0, 0, 0, 1, 1, 0, -1, 1) - and then have a list of doubles for the probabilities. Would it be better or worse to have a couple of lists where I check one and implement the other, compared to a single Dictionary? Or is there a better option?
Game of Life, i know that. We’ve implemented that long time ago at university, though I didn’t know it’s just a trivial example of such an exciting and interesting domain. If I just had the time do delve into all the fascinating stuff that I came across all the years…
That approach would produce tons of garbage, because you always have to determine the new “configuration” for all the agents (in each iteration) which is based on the permanently changing states, unless I’m totally wrong. And I’m pretty sure the only reason it’s been suggested is due to the lack of information we had in the beginning.
I’d generally rather try to work with bits and bytes, similar to what has already been suggested. There’s no extra garbage involved, at least not for the process of assembling the config from the states, the operations are fast and the resulting integers will already be a good hash value, as they wouldn’t collide.
Alright. My programming knowledge is very weak (I first started doing anything with programming in Unity, back when I made this account, and I’m only now taking an introductory course just for the experience), so I wouldn’t even have the first idea how to work with bits and bytes.
The array approach posted earlier in this thread looks as if it aims in the correct direction.
In C and C++ you could even optimize that a little more.
How did you implement the data structure in the existing version? And what’s exactly the reason that you’re trying to improve it? Performance issues?
Right now as I mentioned it just checks for a certain number of neighbors within a specified neighborhood. It uses a list of floats. Here’s a constructor in the relevent class:
public StatePageInfo(int totalStates, int neighbors, int currentState)
{
stateNum = currentState;
color = 0;
startingAmount = 0;
probs = new float?[totalStates, totalStates, neighbors + 1];
}
To deal with the idea of customizable configurations I basically need to rebuild this from the ground up. A custom “key” which contains all of the grid information (locations and state) and returns a single value seems like the perfect way to do that. But again, I want it to be fast, because as I said before I’ve used up to 1,000,000 agents before. Normally it takes about 1 second for each iteration. But it would be great if that could be faster.
So let me restate the problem to make sure I understand it.
You have an arbitrarily large 2D array.
You have a set of configuration rules, each rule has a probability associated with it.
You need to evaluate every location in the large array to see if it conforms with the rules.
Based on those assumptions, I would store your rules in a matrix (2D array). Then you can compare the matrix with each cell in the 2D array. There are some clever operations you could use working with bits directly to make the process quick.
I don’t really have a 2D array. If you’re referring to the positions on the grid with that one - I’ve made a class for agents on the grid (because on occasion there will be LESS agents than the grid size, and they will move around), and I just created a list of those. I iterate through those, just a foreach. They have access to their location, so they can check locations around themselves.
I thought about something like a 2D array, but to my limited understanding one couldn’t correctly define the configurations in the array when half of the relative positions will be negative (such as the bottom red cell on the left image, or the left red cell on the right image). I’ll point out again though that that’s really not something I have a great deal of experience with.
I’d google for fast solutions to Game Of Life if I were you. It’s not exactly the same thing, but you can probably generalize the solution somehow.
For example, this StackExchange question’s top rated answer explains exactly how they’re handling patterns like what you’re describing in a Game Of Life solution.
Well, the negative indeces are not the problem, you could use an offset if you really need your origin in the “center” of the whole grid.
I also think the post linked by @Baste could be a good starting point, you can try to combine that with @ suggestions, since you’re dealing with more than two states.
Urgh, 1 second… That’s quite long.
I’m afraid that, even when you improved your structures based on the ideas in this thread, it could still be a little too slow for your ambitions with so many agents, multiple states and a larger neighborhood, so if you could eliminate some more calculations and array-lookups, that’d be a great performance boost.
Anyways, I still wanna try to implement that by myself now, hope I’ll find some time soon to delve into it.
Thanks for this. Yeah, it looks like it’s almost exactly the same. I’ll see what I can do with this.
Gotcha.
Initial implementation certainly isn’t difficult. I had it up and running pretty quickly. It was only when I starting amping up the customization that things got taxing.
