Anything can be used as a key in a dictionary or keyed hashtable, including a collection of values. I think you’ve already got some good advice but I’m curious to find out more about your specific situation.
You say the size of the neighborhoods is variable as well as the number of states each element can take-on. Seems to me this would result in an explosion of possible combinations. How does your user specify a probability for each of the, say 4^25 = 1,125,899,906,842,624 combinations? Are some combinations much more likely than others? Are some combinations impossible?
The way I envision it (I haven’t yet set this up) is that there will be an open field for the user to enter values into, and then to the right of that will be a grid. At first it’s just the central cell of interest. But the user can add columns/rows in any direction - up, down, left, and right.
Then the user clicks any one of the cells on the grid. This increments the state of that cell on the grid by one. This will be reflected in color (the user also sets the color of each state), but also with a number, so the user can see what state the cell is.
Then, after the user supplies all information and closes that temporary dialog box (I’m making this in a WinForm - started in Unity but moved to a WinForm for a few reasons), the program examines each configuration and sets it as a key, with the corresponding user-inputted probability (literally just a 0-1 number) as the value.
Then, I imagine the cells during the actual CA “run” doing much the same thing - examining the surrounding neighborhood and building a key from that, and then comparing that to the dictionary or whatever format the storage takes.
Writing this out, I realize there’s an issue: these neighborhoods are not meant to be exclusive. In my first example image, it should ONLY check the cells directly above and below the current cell for their state - not any others. However, if on the real grid it happens to have other cells around it filled, those WILL be part of the created key and will prevent it from matching up.
Thus, at each cell it needs to select the appropriate dictionary or whatever (one dictionary for each state, I imagine), then parse the key to get ONLY the locations in the key, and then check those. And if successful, return the value.
I’m unsure for the moment what I’m going to do with the returned values. If I have a grid with red cells in both vertical AND horizontal directions, for example, both configurations will fire. Not sure whether they should be additive or exclusive. Probably best to make it dependent on situation. I’ll probably allow the user to select that…which may mean the configuration has additional data which must be stored in it.
I wondered the same, even with only 2^9 (e.g. the Moore Neighborhood) it’ll already be quite much to configure manually.
But what would be progamming without great extensions?
There’s so much freedom to that, I just imagine throwing in an ‘IProbabilityCalculator’ or ‘IProbabilityGenerator’ or whatever you wanna call that.
That one would calculate / determine a prob-value for combinations that occured the first time during a run and have not been set manually.
That’d actually allow to try alot of fancy stuff. State-occurence-based, randoms, pattern-based, threshold-based, rules restrictions and all kinds of algorithms.
So far so good, but the following confuses me:
Isn’t that how it’s supposed to work? Im not that deep into it, but that’s what I imagined it would be like. How would they affect each other if it wasn’t? I know the agents can be “static” or move around, but… my brain’s messed up now.
That doesn’t make much sense, does it?
From what I’ve read so far, if there was a vertical and horizontal line (like the sample images but combined) it would just be a completely different configuration with its own prob-value. Please correct if I’m wrong.
Maybe I should do some further reading, any good online resources other than the ones you get as top results using google?
Now that is interesting and it probably makes most example implementations you will find irrelevant.
You’ve basically defined a state on every community “template” which represents “anyvalue”, or “transparent”. Even in a system with two values: occupied or vacant, your templating system needs to handle three values: occupied, vacant, or either. I see two approaches to dealing with this.
Add an entry for every permutation of possible states for the transparent cells into a single hashset.
Manage multiple hashsets for each combination of transparent cells defined by the user.
#1 would be slow at definition time as the algorithm to calculate the permutations could be run immediately when the user defines the template. This would be the fastest of the two approaches for runtime but it would also use a lot of memory since every combination would be recorded.
#2 fragments the lookups because you need to check each dictionary for a match. If there isn’t a lot of overlap in the transparent cells of the defined templates, this could become rather inefficient. This approach would use less memory though since you would only need to store the defined templates. It also lends itself to multithreading which might speed things up a little bit.
As you noted, either way you go, you’ll have to deal with the ambiguous match problem in which more than one template matches the current configuration.
Yeah I think there’s a ton of potential in all of this. It’s a field that has been relatively niche for a while, but I personally love it and would like to move it forward.
Eh, not necessarily. The way it works now is that the user determines a probability for incrementally more neighbors of a certain state. Like for von Neumann:
Transition probability of state 0 to state 1 with 0 neighbors of state 1.
Transition probability of state 0 to state 1 with 1 neighbor of state 1.
Transition probability of state 0 to state 1 with 2 neighbors of state 1.
Transition probability of state 0 to state 1 with 3 neighbors of state 1.
Transition probability of state 0 to state 1 with 4 neighbors of state 1.
For the first four of those - it doesn’t care what the remaining neighbors are. They can be anything. As long as it includes whatever the criteria is–one neighbor, three neighbors, heck zero neighbors–it fires off that probability.
Well, remember that there are a bunch of configurations for each state. Like the example I just presented was five different configurations for state 0. In this case there are also five different configurations for state 1 (going to state 0).
Or maybe it should be even MORE specific - a dictionary for each configuration based on what state it’s transitioning TO. Because it’s possible for identical configurations for transition to DIFFERENT states (such as “to state 1/2/3/4 with zero neighbors”) to exist.
In a moment I’m going to post an example of two mutually exclusive configurations both acting on a cell at once (for the time being, consider this video I made for some additional clarity). But for your second paragraph–google “Paul Seybold Cellular Automata.” The sixth link down for me is for a book he wrote - another one of the book’s authors who works at the linked university seems to have made that chapter available online.
In these images, I assign each point on the grid to a pixel, so a 100x100 pixel image, quite small, is actually 10,000 cells. A 1000x1000 pixel image, still on the small side, is one million cells. Anyway, in the bottom-left corner there are three black yet-to-be-transitioned cells. Let’s take a look at the upper-right of those.
Edit: I’m sorry, this image MAY need to be downloaded to see the pixels correctly. Chrome is using interpolation when I try to zoom in online, making the image blurry.
I don’t remember if this used the von Neumann or Moore neighborhood, but for the sake of completeness let’s assume it’s Moore. In that case, it has 2 red neighbors and 4 blue neighbors.
Now, the original way the program worked was that when determining transition to blue, it only checked for blue neighbors. Same way for transition to red - it only checked red neighbors.
I changed this, to allow for transition to blue checking red neighbors, and visa versa. Needed it for a few applications (consider a system made of alternating elements, like a salt for the chemically inclined. The addition of element X is predicated upon the existence of element Y). This knowledge isn’t strictly necessary to understand the next step, but understand that how I next describe it is simplified from how it now works.
Anyway. That cell there has 4 blue neighbors and 2 red neighbors. So it checks for the number of red neighbors - it’s two. It returns a probability of changing to red - we’ll say 0.010. It also checks for the number of blue neighbors - four. It then returns a probability of changing to blue - 0.020.
The program stores these amounts, as well as 1 - (total) = 0.970.
So then a random number generator fires a value between 1 and 0 (SysRand.Next or something). If the value is between 0 and 0.010, the cell changes to red. If the value is between 0.010 and 0.030, the cell changes to blue. If the value is between 0.030 and 1, it stays the same.
So the way it works, it doesn’t care about the other neighbors when checking a neighborhood, ONLY the ones of interest. I need to build this into the new system as well.
Edit: notice I said nothing at all about the two neighbor black cells. I completely forgot about them But that’s all the more reason why it ignores the state of any cell not “pre-designed” to be a neighbor.
Hopefully my next two posts have made what I’m attempting clearer, if that changes anything. Anyway, I confess that I only slightly understand what you’re suggesting with 1, and don’t really understand 2 at all.
I intend to look up hash tables and all that stuff–as I mentioned I don’t have any real formal training with this. But, a question. Would these methods (or at least #1) be faster than what I suggested–storing ONLY the active locations in a key, and then having each cell (at runtime) parse the key for each location and then check it?
This suggests that the positioning of the neighbors isn’t important. Is that true? If so, you can simplify the problem quite a bit. If it’s true but only part of the time, then you’ve really got a challenging issue!
I think you actually do understand this approach. Maybe I’m just confusing you with programming terms. Look back to this part of your older post:
There is obviously a bit of a disconnect because you don’t understand dictionaries yet, but I’ll see if I can explain…
The idea behind a dictionary is to speed up lookups. Imagine you have a 2×2 grid and each cell in the grid has a possible value of 0 or 1. The number of possible layouts is then 2^4 = 16. Say you want to assign a probability to each of these possible layouts according to the following table:
Lets say we are iterating through a large universe and are currently considering this environment:
One approach is to scan through the table until we find the correct value. In this case, it will take 10 steps to find the corresponding match. Sometimes it will take fewer and sometimes it will take more. On average, we assume it will take the size of the table (n) / 2 to find matches using a standard scanning algorithm. You can see how this will scale poorly as your environment size increases. A 3×3 environment will take, on average, 2^9 / 2 = 256 steps to find a match and a 4×4 environment will take 2^16 / 2 = 32768 steps. If you increase the number of possible states, the numbers get even larger.
Dictionaries or Hashsets take a different approach. They define an equation to calculate a “hash” for each possible combination. Let’s go back to the 2×2 example from above. Instead of considering each cell separately, let’s come up with a formula to assign each possible environment with a unique hash. Consider this:
Each time we consider an environment, we will calculate its hash by adding the number from the corresponding cell to a total if that cell is “active” (blue in my case). If we reconsider the environment form above
we see that cells 2 and 8 are active, so the hash for this environment is 10. Because of the way I designed my hash formula, I know that every combination will have its own unique hash. Now we can create a table that is indexed to the possible hashes.
Now instead of scanning through the table, I can just jump directly to position 10. This changes a scanning algorithm which can take n/2 steps into a math and jump algorithm, which in this case is at most 4 additions and one jump.
In general, hashsets are more efficient for lookups than scanning. However, adding something to the hashset requires its hash to be calculated upfront so we trade fast lookups for slow inserts. Figuring out the best tradeoffs for your circumstance is what computer science is all about.
That’s how it used to work. But I need it to be more specific. I DO need the neighbor positioning to matter.
My professor (the aforementioned book writer) and I are looking at a system which might replicate the design of a Bengal tiger or a zebra’s stripes. This will involve a system where vertical growth is supported, but horizontal growth is suppressed.
Now under the current system, I could go in and define two whole new neighborhoods like my initial two images. One the two vertical, one the two horizontal. But at that point I’m getting into these weirdly specific neighborhoods. And I’m in the process of moving from Unity to the WinForm, so I pretty much have to recreate everything already, so a refactor doesn’t seem like a big deal. My proposed system (custom configurable neighborhoods) just seems like it allows for a ton more flexibility.
Okay, I understand. However, I’d like to point out that you are moving from an algorithm which doesn’t care about positioning at all to an algorithm which relies completely on positioning. These are basically two sides of a continuum but there are other options in between. I would call these options “categories” or “archetypes”. For instance, a formula which weighs the vertical neighbors more heavily than the horizontal neighbors.
double CalculateProbability(Vector2 me, Vector2 neighbor)
{
var dx = Math.Abs(neighbor.X - me.X);
var dy = Math.Abs(neighbor.Y - me.Y);
if (dy>dx)
return 0.1;
else
return 0.05;
}
This gives twice as much weight to cells which are further away on the y axis than the x axis: i.e., directly above and below for a 3×3 and upwards in a funnel shape for 4×4 and beyond. You could also get fancy and define a continuous function rather than discrete.
I would call this a categorization: “vertical neighbors matter more”. Technically, you could describe this using your template matrix approach but it would take a lot of work to enter all of the combinations, especially if your environment of consideration grows beyond a few cells.
This is a fantastic explanation. Thank you so much. This makes total sense, and I have encountered the general concept before. However…I still don’t feel like I really understand what you were getting at with your #2 statement. If you feel like it a practical example of the difference between 1 and 2 would help me understand…however you already mention that 1 is naturally faster at runtime than 2. So that seems like the route to take. I’ll address multi-threading in a moment.
My implementation will be a bit more complex than your example, because it’s not just living or dead, but there are multiple possible states. So to continue with your image:
If I have more possible cell states, what would that change? Would that change the base? So three possible states becomes 1, 3, 9, 27?
Additionally…I mentioned it before, but while most of my work has been with static (agents don’t move) systems with a full grid, I’m starting to move into incorporating systems where the number of agents is a subset of the grid size, and where they move about the grid. In that case, you have the possibility for empty spots on a grid. Not just undefined in configuration, straight up empty. Would this be considered nothing more than another state for the purposes of this hashset concept?
As far as multi-threading goes…the way the system works now is that it saves a backup copy of the grid. And then each location on the grid checks that backup copy for any changes, before sending it’s updated state to the new “iterated” grid. This is to prevent any artifacts with location affecting the growth of the grid. So I think in that respect multi-threading is already possible for an immobile CA.
For mobile CA though, multi-threading is more difficult. Because each cell needs to check if the adjacent cell is empty before moving to it. However, one possible way I see that working is if the grid is divided up into (number of cores or threads) sections or something. Then, in each section, the inner locations–only locations which can check adjacent locations in the same section–update. This would prevent a cell from crossing a boundary and overlapping in location with another cell. At that point all sections are put back together and the remaining agents are checked. I’m not convinced that’s the best solution however. In any case multi-threading is on the back burner for now.
That’s not a direct answer to what I was confused with, but also interesting. It’s much clearer now how you’d like to set the probs. I think that was a little confusing, as we had the impression you wanted the user to be able to just pick any number of all possible (4^25) combinations and assign just some value for it.
I got the same feeling like @eisenpony in regards to dictionaries.
The example you’ve posted is almost as i had imagined it. Maybe it’s just due to my ability to understand complex topics in English or my wording which is also a little off… Idk
Thanks for the recommendations btw, I might have a look at it.
The difference between 1 and 2 is essentially levels of hierarchy. Option 1 flattens everything out into a single hashset. In order to do that, you need to calculate every possible combination of environment based on the template entered by the user. Option 2 maintains a different hashset for each “mask” defined by the user’s templates. For instance, let’s look at these three template environments:
Option 1
With this approach you have a lot of work to do as soon as the user enters a template. Consider just template 1. We need to identify every environment this template might match so we can calculate all matching hashes.
That’s 2^6 = 64 possibilities. And that’s just for the blue squares! Things will get crazy once you consider orange squares too, because …
Unfortunately, no. Instead, the exponent increases. A 2×2 environment with 3 possible states could use a hash formula roughly like this: For our above example with template #1, that means 2^12 = 4096!
Edit: In retrospect, I realize I went a little overboard here. It probably doesn’t make any sense for a cell to be both blue AND orange, so we can eliminate a lot of possibilities. For the actual number of states, the math works out as you expected, just increase the base from 2 to 3. Unfortunately, for the numbers in the hash formula, the same trick doesn’t work. Understanding why requires a pretty deep dive into bits and base 2 math which I’m not ready to get into as part of an edit. Suffice it to say each time you want to add another state, you may need to increase the exponent or you may not. When moving from two states to three, we do need to take the exponent increase.
The next time you need to increase your bits is at 4 states, adding one to 5 and after that 8 states, adding one to 9. The increases always happen when you move past a 2^x threshold (e.g., 2^1=2, 2^2=4, 2^3=8, etc…).
Even though the total space used up in my example is 2^12 = 4096 bits, the total number of combinations needed would be, as you guessed, 3^6 = 729 (which is still a lot of combinations!) That could seem like a lot of wasted space in the hashset but most implementations are smart about how they structure their data under the hood. Those unused “slots” shouldn’t use up much memory in a well implemented hashset.
Once you’ve found all the compatible combinations, you would calculate a hash for each and assign the same probability to each one. This way, no matter which of the environments you find in your universe, you have an entry in your hashtable.
Of course, as you already identified, you will run into some collisions. Just consider template #3. The possible matches will be largely the same as template #1. You’ll have to deal with this “ambiguous match problem” with either of my suggestions though .. just put that on the shelf for now.
Option 2
For this approach we will make a “mask” for each template.
Notice template 1 and 2 have the same “vertical” mask, so these templates end up in one hashset. Template 3 has a different “horizontal” mask, so we need a new hashset to manage that template. Within the vertical hashset, there would be two templates. When we examine any given environment in the universe, we would use a hash formula that looks like this
Notice I left a number of the cells blank. That’s because, for the purpose of finding a matching template within the vertical hashset, we only care about the cells directly above and below the center. For template 1, the hash would work out to 5 and for template 2, the hash would be 10. Using this same hash formula against any 3×3 environment in the universe, regardless of the other cells, would match one of these templates if the center top/bottom cells were both blue or orange.
However, we can’t neglect the possibility there is another match in our horizontal hashset. The horizontal hashset would use a different formula.
(can’t upload another image since I’m capped at 5, but it’s essentially a transposed version of above)
So for every unique mask, we need a different hashset formula and must check the hash of each environment we iterate across in the universe against each of the formulas. Unfortunately, even in this case it’s possible for multiple hashsets to hold a template matching our current environment. If more than one hashset has a matching template, then we are back to the ambiguous match problem.
Regarding multithreading …
When you say
I think you might be confused about what multithreading is useful for. Sure, each of your “agents” could be programmed to use its own thread but that’s just one possibility. For the sake of our conversation, I will define an “independent operation” as something which works on data that doesn’t change. This is a bit simplified but it works to illustrate here. You can see that calculating different hashes on a given environment using two different formulas will not change the environment. Further, using those hashes independently to lookup values in independent hashsets makes no changes to the environment nor the hashsets. This means the task of calculating multiple hashsets per environment and looking for matches can safely be multithreaded. That doesn’t mean your whole implementation is multithreaded; just this one tiny piece.
What would be really cool is if you could find a way to describe each template as a matrix transformation. This kind of stuff can be simplified with linear algebra so you might find a way to calculate hashes based on eigenvectors or eigenvalues.
Alternatively, a shader might allow you to do this analysis on the computer’s GPU. That would speed things up significantly.
Once you’ve got you mind wrapped around it, Id suggest discussing the problem with a math prof at your university. Or maybe ask another question here using the keywords “GPU” or “Shader” in your topic title. You might attract some talent that would otherwise skip this conversation.
But that’s all the more reason why it ignores the state of any cell not “pre-designed” to be a neighbor.
