1
$\begingroup$

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
$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.