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 |