I designed a program to create a map in my 2D game program. And I have three questions…

**algorithm:**

**step1:**

```
create a cell in (0,0), and select it as first cell, and mark the step1 is round 0
```

**step2:**

```
in round i (start from 1), for every cell created in i - 1 round :
for adjacent index in up, down, left, and right:
generate a random value between (0, 1), create a new cell in this index if the random value if less than P
```

**step3:**

```
if some cells created in this round, go to step 2, else finish this algorithm
```

**here is my python code**

```
def calc(P):
mp = {}
s = (0, 0)
ds = ((-1,0), (0,-1), (1,0),(0,1))
q = (s)
ql = 0
mp(s) = 1
while len(q) > ql:
idx = q(ql)
round = mp.get(idx, -1)
ql += 1
for d in ds:
cur_idx = (idx(0) + d(0), idx(1) + d(1))
if mp.get(cur_idx, -1) == -1 and P(round) > random.random():
mp(cur_idx) = round + 1
q.append(cur_idx)
return len(mp) # count of cells
```

this algorithm will create a map by a function that gradually decays based on the generation rounds. But I don’t know how to calculate the expected value of how many cells will be created by this algorithm. the $P$ is a function about round

**question 1:** what’s the expected value of how many cells will be created when $P(mathtt{round}) = C$, where $C$ is a constant value and greater or equal than $0$.

C | Simulation results of my program |
---|---|

0.1 | 1.545 |

0.15 | 2.043 |

0.2 | 3.051 |

0.25 | 4.316 |

0.3 | 7.108 |

0.35 | 13.104 |

0.4 | 30.791 |

0.45 | 160.748 |

**question 2:** If the number of generated cells is limited, what should $P(mathtt{round})$ satisfy?

**question 3:** what’s the expected value of how many cells will be created when

$$

P(mathtt{round}) = exp(-mathtt{round}/a),

$$

with $a>1$.

a | Simulation results of my program |
---|---|

1 | 3.132 |

2 | 7.985 |

3 | 14.951 |

4 | 24.016 |

5 | 34.462 |

10 | 117.747 |

15 | 243.395 |

20 | 413.916 |

25 | 627.373 |

30 | 886.66 |

35 | 1180.763 |

40 | 1512.886 |

45 | 1888.011 |

50 | 2319.398 |

60 | 3274.22 |

70 | 4403.592 |

80 | 5690.979 |

90 | 7134.92 |