포스트

[ Unity ] 유전 알고리즘 적용

게시
By Kwon hyeok soo 11 분읽는 시간

분석

Match-3 게임 맵을 자동 생성하기 위해, 유전 알고리즘을 사용한다.

유전자를 통한 맵 구성을 사용, 유전자와 같은 크기의 그리드 형태의 맵 생성한다.

int genes$[col*row]$ : 0과 1로 구성된 1차원 정수 배열.

유전자 배열의 각 index는 맵의 index와 일치, 각 index의 배열 값은 맵의 index 위치 셀에 배치될 블록 정보로 값에 따라 블록을 생성한다.

  • 0 : 특수 블록
  • 1 : 빈 셀 (일반 블록은 게임 시작 시 랜덤하게 생성되므로, 게임 시작 시 빈 셀에 일반 블록 랜덤 배치)

이를 활용하여 맵 생성 과정을 코드로 표현 시, 아래와 같은 코드가 나온다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67


internal void fillGrid(bool noMatches, MatchGrid g, Dictionary<int, TargetData> targets, Spawner spawnerPrefab, SpawnerStyle spawnerStyle, Transform GridContainer, Transform trans, LevelConstructSet IC)
{
	System.Random randomGa = new System.Random(); 
	GeneticAlgorithm<char> ga = new GeneticAlgorithm<char>(Cells.Count, randomGa, getRandomGene, getGenes, m3h); 
	getMatch3Level(trans, sC);
}

void getMatch3Level(Transform trans, SpawnController sC)
{
    for (int i = 0; i < m3h.limits.geneticGeneration; i++)
    {
        for (int j = 0; j < ga.population.Count; j++)
        {
            if (ga.population[j].fitness == 0)
            {
                initialize();
                setCells(ga.population[j], sC);
                calculateFitness(ga.population[j], sC, trans);

                if (ga.bestFitness < ga.population[j].fitness && ga.population[j].isFeasible)
                {
                    ga.bestFitness = ga.population[j].fitness;
                }

                if (ga.bestFitness >= ga.targetFitness)
                {
                    ga.population[0] = ga.population[j];
                    break;
                }
            }
        }

        if (ga.bestFitness >= ga.targetFitness) break;
        else ga.newGeneration();
    }
}

public void setCells(DNA<char> p, SpawnController sC)
{

    for (int i = 0; i < m3h.grid.Cells.Count; i++)
    {
        if (p.genes[i] == '1')
        {
			m3h.grid.Cells[i].setObject(특수 블록);
        }

        else
        {
            m3h.grid.Cells[i].setObject(랜덤 일반 블록);
        }
    }
}

internal GridObject SetObject(GridObject prefab)
{
    if (!prefab) return null;

    int a = prefab.ID;
    GridObject gO = prefab.Create(this, MBoard.TargetCollectEventHandler);
    if (gO && !GameObjectsSet.IsDisabledObject(prefab.ID)) sRenderer.enabled = true;
    return gO;
}

그런데 한 가지 주의해야 할 점은 장애물 랜덤 배치로 인해 실제 플레이 불가능한 맵이 생성될 수 있다.

일반 블록이 생성되는 spawn cell들과 연결되어 있지 않은 셀은 match 발생 시 새로운 일반 블록이 생성될 수 없어 게임 플레이에 악영향을 준다.

이러한 연결되어 있지 않은 셀은 주변 셀들도 유효하지 못하게 하는 성질이 있어,이웃한 연결되어 있지 않은 셀들을 하나의 요소로 묶어, 요소들의 개수로 맵의 유효성을 판단한다.

그래서 기본 유전 알고리즘을 FI-2Pop을 활용한 유전 알고리즘으로 변경하여 맵을 생성한다.

기존 알고리즘은 맵은 유효성 검사를 통해 플레이 가능 여부를 판단하여 feasible, infeasible로 나누고 feasible 맵만 종결 조건 충족 검사를 진행.  이로 인해 최적해 탐색 세대 수 증가하게 된다.

대신 FI-2Pop 알고리즘을 사용하여 feasible 유전자와 infeasible 유전자 각각의 진화 연산을 진행하면 자식의 유효성에 따른 해집단 이동을 통해 infeasible 유전자는 feasible 유전자에 가까워지며 feasible 유전자는 적합도의 분산이 감소하여 최적해에 수렴하여 더 적은 최적해 탐색 세대를 통한 맵 생성할 수 있다.

따라서 유전자 생성 코드를 아래와 같이 설정.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141

using Mkey;
using System;
using System.Collections.Generic;

public class GeneticAlgorithm<T>
{
    public int geneticGeneration;
    public int generation;

    public int populationSize;
    public int elitism;
    public float mutationRate;
    public int targetMove;
    public double targetStd;
    public double targetFitness;

    public List<DNA<T>> population;
    public List<DNA<T>> feasiblePopulation;
    public List<DNA<T>> infeasiblePopulation;

    private Random random;
    private int dnaSize;

    public double bestFitness;
    public double feasibleFitnessSum;
    public double infeasibleFitnessSum;

    public GeneticAlgorithm(int cellSize, Random random, Func<T> getRandomGene, Func<T[]> getGenes, Match3Helper m3h)
    {
        geneticGeneration = 1;
        generation = 1;

        populationSize = 20;
        elitism = 2;
        mutationRate = 0.01f;
        targetMove = 0;
        targetStd = 0;
        targetFitness = 1;

        population = new List<DNA<T>>(populationSize);
        feasiblePopulation = new List<DNA<T>>();
        infeasiblePopulation = new List<DNA<T>>();

        this.random = random;
        dnaSize = cellSize;

        bestFitness = 0;
        feasibleFitnessSum = 0;
        infeasibleFitnessSum = 0;

        bestPottential = 0;

        for (int i = 0; i < populationSize; i++)
        {
            population.Add(new DNA<T>(dnaSize, random, getRandomGene, getGenes, m3h.getSetGenes, shouldInitGenes: true));
        }
    }

    public void newGeneration()
    {
        population.Clear();

        if (feasiblePopulation.Count != 0)
        {
            feasiblePopulation.Sort(CompareDNA);

            for (int i = 0; i < feasiblePopulation.Count; i++)
            {
                if (i < elitism) population.Add(feasiblePopulation[i]);

                else
                {
                    DNA<T> parent1 = ChooseParentInFeasible();
                    DNA<T> parent2 = ChooseParentInFeasible();
                    DNA<T> child = parent1.Crossover(parent2);
                    child.Mutate(mutationRate);
                    population.Add(child);
                }
            }

            feasibleFitnessSum = 0;
            feasiblePopulation.Clear();
        }

        if (infeasiblePopulation.Count != 0)
        {
            infeasiblePopulation.Sort(CompareDNA);

            for (int i = 0; i < infeasiblePopulation.Count; i++)
            {
                if (i < elitism) population.Add(infeasiblePopulation[i]);

                else
                {
                    DNA<T> parent1 = ChooseParentInInfeasible();
                    DNA<T> parent2 = ChooseParentInInfeasible();
                    DNA<T> child = parent1.Crossover(parent2);
                    child.Mutate(mutationRate);
                    population.Add(child);
                }
            }

            infeasibleFitnessSum = 0;
            infeasiblePopulation.Clear();
        }
        geneticGeneration++;
    }


    private int CompareDNA(DNA<T> a, DNA<T> b)
    {
        if (a.fitness > b.fitness) return -1;
        else if (a.fitness < b.fitness) return 1;
        else return 0;
    }

    private DNA<T> ChooseParentInFeasible()
    {
        double randomNumber = random.NextDouble() * feasibleFitnessSum;

        for (int i = 0; i < feasiblePopulation.Count; i++)
        {
            if (randomNumber < feasiblePopulation[i].fitness) return feasiblePopulation[i];
            randomNumber -= feasiblePopulation[i].fitness;
        }
        return null;
    }

    private DNA<T> ChooseParentInInfeasible()
    {
        double randomNumber = random.NextDouble() * infeasibleFitnessSum;

        for (int i = 0; i < infeasiblePopulation.Count; i++)
        {
            if (randomNumber < infeasiblePopulation[i].fitness) return infeasiblePopulation[i];
            randomNumber -= infeasiblePopulation[i].fitness;
        }
        return null;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

public class DNA<T>
{
	public T[] genes { get; private set; }
	private System.Random random;
    private Func<T[]> getGenes;
    private Func<T> getRandomGene;

    public bool isFeasible = false;
    public int infeasibleCellCnt;
    public double fitness;

    public DNA(int size, Random random, Func<T> getRandomGene, Func<T[]> getGenes, bool getSetGenes, bool shouldInitGenes = true)
	{
        gridObjects = new List<int>();
        objectProtection = new List<int>();
        genes = new T[size];
		this.random = random;
        this.getGenes = getGenes;
        this.getRandomGene = getRandomGene;
	    isFeasible = false;
        infeasibleCellCnt = 0;
        fitness = 0;
        if (shouldInitGenes)
        {
	        for (int i = 0; i < size; i++) genes[i] = getRandomGene();
        }
    }

    public void calculateFeasibleFitness(int wantDifficulty, int difficultyTolerance)
    {
        fitness = Math.Abs(allPottential.map - (double)wantDifficulty);
        if (fitness > difficultyTolerance) fitness = 1.0 / (1.0 + Math.Abs(fitness));
        else fitness = 1;

    }
    
    public void calculateInfeasibleFitness()
    {
        fitness = 1.0 / (1.0 + Math.Abs(infeasibleCellCnt));
    }
    
    public DNA<T> Crossover(DNA<T> otherParent)
	{
		DNA<T> child = new DNA<T>(genes.Length, random, getRandomGene, getGenes, false, shouldInitGenes: false);

		for (int i = 0; i < genes.Length; i++)
		{
            if(random.NextDouble() < 0.5)
            {
                child.genes[i] = genes[i];
            }

            else
            {
                child.genes[i] = otherParent.genes[i];
            }
        }
		return child;
	}

	public void Mutate(float mutationRate)
	{
		for (int i = 0; i < genes.Length; i++)
		{
			if (random.NextDouble() < mutationRate) genes[i] = getRandomGene();
		}
	}
}

1
2
3
4
5

public char getRandomGene()
{
    int number = Random.Range(0, 2);
    return (char)(number + '0');
}

FI-2Pop 알고리즘을 통한 맵 생성 과정을 진행한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

void getMatch3Level(Transform trans, SpawnController sC)
{
    for (int i = 0; i < m3h.limits.geneticGeneration; i++)
    {
        for (int j = 0; j < ga.population.Count; j++)
        {
            if (ga.population[j].fitness == 0)
            {

                initialize();
                setCells(ga.population[j], sC);
                estimateIsFeasible(ga.population[j]);
                calculateFitness(ga.population[j], sC, trans);

                if (ga.bestFitness < ga.population[j].fitness && ga.population[j].isFeasible)
                {
                    ga.bestFitness = ga.population[j].fitness;
                }

                if (ga.bestFitness >= ga.targetFitness)
                {
                    ga.population[0] = ga.population[j];
                    break;
                }
            }

            else
            {
                if (ga.population[j].isFeasible)
                {
                    ga.feasiblePopulation.Add(ga.population[j]);
                    ga.feasibleFitnessSum += ga.population[j].fitness;
                }

                else
                {
                    ga.infeasiblePopulation.Add(ga.population[j]);
                    ga.infeasibleFitnessSum += ga.population[j].fitness;
                }
            }
        }

        if (ga.bestFitness >= ga.targetFitness) break;
        else ga.newGeneration();
    }
}

public void estimateIsFeasible(DNA<char> p)
{
    m3h.CreateFillPath(m3h.grid);
    p.infeasibleCellCnt = 0;

    for (int i = m3h.grid.Columns.Count(); i < m3h.grid.Cells.Count; i++)
    {
        bool isCan = false;

        if(m3h.grid.Cells[i].fillPathToSpawner == null)
        {
            if(m3h.grid.Cells[i].Blocked == null)
            {
                isCan = false;
            }

            else
            {

                if (m3h.grid.Cells[i].Neighbors.Top != null)
                {
                    if (m3h.grid.Cells[i].Neighbors.Top.fillPathToSpawner != null || m3h.grid.Cells[i].Neighbors.Top.spawner && m3h.grid.Cells[i].Neighbors.Top.Blocked == null)
                    {
                        continue;
                    }
                }

                if (m3h.grid.Cells[i].Neighbors.Left != null)
                {
                    if (m3h.grid.Cells[i].Neighbors.Left.fillPathToSpawner != null || m3h.grid.Cells[i].Neighbors.Left.spawner && m3h.grid.Cells[i].Neighbors.Left.Blocked == null)
                    {
                        continue;
                    }
                }

                if (m3h.grid.Cells[i].Neighbors.Right != null)
                {
                    if (m3h.grid.Cells[i].Neighbors.Right.fillPathToSpawner != null || m3h.grid.Cells[i].Neighbors.Right.spawner && m3h.grid.Cells[i].Neighbors.Right.Blocked == null)
                    {
                        continue;
                    }
                }
            }

            if (!isCan) p.infeasibleCellCnt++;

        }
    }

    if (p.infeasibleCellCnt == 0) p.isFeasible = true;
    else p.isFeasible = false;
}



public void calculateFitness(DNA<char> p, SpawnController sC, Transform trans)
{
    if (p.isFeasible)
    {
        p.calculateFeasibleFitness(m3h.wantDifficulty, m3h.difficultyTolerance);
        ga.feasiblePopulation.Add(p);
        ga.feasibleFitnessSum += p.fitness;
    }

    else
    {
        p.calculateInfeasibleFitness();
        ga.infeasiblePopulation.Add(p);
        ga.infeasibleFitnessSum += p.fitness;
    }
}
Unity
unity gameEngine match-3Game geneticAlgorithm cSharp
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.