# probability theory – expected value of map generate algorithm

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