Cellular Automata
Did you manage to build the algorithm and spot the issue?
Here's one version of the code. We've just stepped in one from the edges to keep the boundary conditions simple. We can add special rules for the edges later, when we're happy the core code is working. We certainly don't want a torus world, as this wouldn't be especially realistic for a fire starting at one point.
for step in range(number_of_iterations):
for h in range(1, height - 1):
for w in range(1, width - 1):
fire = False
if (environment[h-1][w-1] < fuel_amount): fire = True
if (environment[h-1][w] < fuel_amount): fire = True
if (environment[h-1][w+1] < fuel_amount): fire = True
if (environment[h][w-1] < fuel_amount): fire = True
if (environment[h][w] < fuel_amount): fire = True
if (environment[h][w+1] < fuel_amount): fire = True
if (environment[h+1][w-1] < fuel_amount): fire = True
if (environment[h+1][w] < fuel_amount): fire = True
if (environment[h+1][w+1] < fuel_amount): fire = True
if (fire == True) & (environment[h][w] > 0):
environment[h][w] -= 1
print_environment()
The first couple of iterations look like this:
5 5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5 5
5 5 5 5 4 5 5 5 5 5
5 5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5 5
5 5 5 4 4 4 4 4 4 5
5 5 4 4 3 4 4 4 4 5
5 4 4 4 4 4 4 4 4 5
5 4 4 4 4 4 4 4 4 5
5 4 4 4 4 4 4 4 4 5
5 4 4 4 4 4 4 4 4 5
5 5 5 5 5 5 5 5 5 5
Which is clearly wrong. The fire has spead right and down much faster than up and left. Indeed, it has totally spread right and down in one iteration! What we have here is a model artifact. The order in which we are choosing the cells (which is completely an issue of the model, not reality) is causing the fire to propagate one direction faster than the other. This is because we're adjusting the cells as we go along: as we process a row, the row above it has potentially already got fire in it, meaning the row will catch fire. Because we're instantly reducing the fuel in the row, the next row down will also have the same issue within the same iteration and so on. The same isn't true of rows above the fire, as these are already processed before we reach the fire.
This issue affects a wide range of models. In agent-based models, for example, a list of agents processed in the same order each time will cause some agents to be advantaged over others (for example, in auctions). The solution there is to shuffle the order of the agents before running through them, as we saw on the core course. Unfortunately, shuffling the cells wouldn't really solve the issue here (it would cut it down, but not completely. Given this, CAs tend to go for the other solution, which is to delay updating until all the cells are processed. We do this by having a results array, which we add the results to, continuing to check the cells in the original array but adjusting the results array. When all of the cells have been checked, we then copy the results array back over the environment. This way, we aren't checking altered cells. Given this, we double up on the environment making, to create a results list:
environment = []
results = []
for h in range(height):
row = []
results_row = []
for w in range(width):
row.append(fuel_amount)
results_row.append(fuel_amount)
environment.append(row)
results.append(results_row)
and then iterate thus:
for step in range(number_of_iterations):
for h in range(1, height - 1):
for w in range(1, width - 1):
fire = False
if (environment[h-1][w-1] < fuel_amount): fire = True
if (environment[h-1][w] < fuel_amount): fire = True
if (environment[h-1][w+1] < fuel_amount): fire = True
if (environment[h][w-1] < fuel_amount): fire = True
if (environment[h][w] < fuel_amount): fire = True
if (environment[h][w+1] < fuel_amount): fire = True
if (environment[h+1][w-1] < fuel_amount): fire = True
if (environment[h+1][w] < fuel_amount): fire = True
if (environment[h+1][w+1] < fuel_amount): fire = True
if (fire == True) & (environment[h][w] > 0):
results[h][w] -= 1
environment = results
print_environment()
Try this, and see the difference.