Darwin Project ve Bölgeler

January 12, 2021

Son 2-3 gündür Darwin Project adında battle royale tipinde bir oyun oynuyorum. Bilmeyenler için açıklamak gerekirse haritada oyuna diğer oyuncularla birlikle başlıyorsunuz. Gördüğünüz adamları vuruyorsunuz veya onlar sizi vuruyor. Çatışma çıkıyor. En son hayatta kalan kazanıyor. Oyun yapımcıları oyuncuların haritada birbirinden kaçmasını önlemek için haritayı rastgele bölgeleri kapatarak daraltıyor.

Daha önce oynadığım battle royale oyunlarında harita kare veya çember şeklinde daralıyordu. Nasıl bir şeçim yaparsanız yapın oyuncuların erişelemeyecek alanda olmamasını garanti ediyordu. Bu oyunda ise harita 7 tane altıgen bölgeden oluşuyor. Merkezde bir altıgen ve kenarlarına bitişik şekilde başka altıgenler var.Desen olarak bal peteği şeklinde.

darwin project map

Şeklinde bir yerleşim var. Soldan sağa, yukarıdan aşağıya 0 dan 6 ya doğru numaralandırdığımızı düşünelim. Paintte çizmeme gerek yok sanırım.

Eğer 0, 3, 6(y = -x denklemi doğrultusu) bolgelerini kapatırsanız 2 numaralı bölgedeki adamla 4 numaralı bölgedeki adam birbiri ile çatışma şansını kaybediyor. Tabiki bu durumu istemiyoruz.

Oyun programcısı ben olsam oyundaki haritayı nasıl daraltırım diye düşündüm. 2 tane yöntem buldum

Ben 2. seçeğini seçtim. Aşağıda python implementasyonunu bulabilirsiniz.

Çözüm

 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

from random import randrange
from itertools import permutations
from collections import defaultdict 

class Graph(object): 
    def __init__(self, edges, n): # initialize graph
        self.free_zones = range(n)
        self.g = defaultdict(list)
        for e in edges:
			self.g[e[0]].append(e[1])
			self.g[e[1]].append(e[0])

    def dfs_visit(self, visited, vertex_number): # dfs
        visited[vertex_number] = True
        for neighbor in self.g[vertex_number]:
            if not visited[neighbor]:
                self.dfs_visit(visited, neighbor)

    def is_connected(self): # check if it is segmented into two or more region
        if len(self.g) <= 1:
            return True
			
        c = 0
        visited = dict([(i, False) for i in self.g])

        for vertex in self.g:
            for neighbor in self.g[vertex]:
                if not visited[neighbor]:
                    c += 1
                    self.dfs_visit(visited, neighbor)

        return c <= 1 and all(visited.values())

    def delete_vertex(self, zone): # remove zone from current configuration
        del self.g[zone]
        for key in self.g:
            for i in self.g[key]:
                if i == zone:
                    self.g[key].remove(zone)

    def next_zone(self): # get new zone id to forbid
        last_valid_configuration = self.g
        index = randrange(len(self.free_zones))
        zone = self.free_zones[index]

        if not self.is_connected():
            self.g = last_valid_configuration
            return self.next_zone()

        self.free_zones.pop(index)
        return zone

    def is_valid_order(self, order): # checks pre given order satisfies the property of reachable
        for c in order:
            self.delete_vertex(int(c))
            if not self.is_connected():
                return False
        return True

edges = [(0, 1), (0, 2), (0, 3), (1, 3), (1, 4), (2, 3), (2, 5), (3, 4), (3, 5), (3, 6), (4, 6), (5, 6)]
perms = [''.join(p) for p in permutations('0123456')]
valid_perms = []
for perm in perms:
    g = Graph(edges, 7)
    if g.is_valid_order(perm):
        valid_perms.append(perm)

print len(valid_perms) # 2160 sonuc varmış

Olası İyileştirmeler

Oyunu geliştiren ekipte olsam bunu muhtemelen hardcoded olarak kaynak kodun içinde tutardım. Her maç başlangıcında bir tane sıralama seçip daha sonra oyun içinde hesaplamakla uğraşmazdım.

0..6 arasındaki sayıları 4 bitle ifade edelim. Bit compression yapması kolay olur. 7 tane bölge için 7 tane sayıya ihtiyacımız var. Her oyun için 2160 tane geçerli konfigurasyon olduğunu bildiğimize göre 4 * 7 * 2160 / (8bit * 1024bytes) ~ 7.4 KB bellek karşılığında böyle bir hesaplama yapma zahmetinde kurtuluruz.

Düzeltme

Kodu inceleyen bir arkadaşım daha basit bir yöntem önerdi. Açık alan sayısı ile bir tek dfs-visit ile gezdiğimiz eleman sayısı eşitse haritada sadece 1 tane connected component vardır. Bu durumda aşağıdaki gibi düzeltme yapabiliriz.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

    def is_connected(self):
        visited = set()
        self.dfs_visit(visited, choice(self.free_zones))
        return len(visited) == len(self.free_zones)

    def dfs_visit(self, visited, vertex_number):
        visited.add(vertex_number)
        for neighbor in self.g[vertex_number]:
            if neighbor not in visited:
                self.dfs_visit(visited, neighbor)
« Transactional Stack & Recursion
Palindrom Problemi ve Bit »

hidden

John von Neumann – The Man from the Future

Before I read The Man from the Future by Ananyo Bhattacharya, I only knew about John von Neumann in two contexts: that computers use the von Neumann architecture, and that he appeared in a story about a mathematical problem I … Continue reading →

via Henrik Warne's blog

The Review Is the Action Item

2024/05/30The Review Is the Action ItemI like to consider running an incident review to be its own action item. Other follow-ups emerging from it are a plus, but the point is to learn from incidents, and the review gives room for that to happen.This is no…

via Ferd.ca

HOWTO: Change your behavior

In theory, behavior change should be easy. At first glance, it seems like you control your behavior. So, if you desire different behavior, why doesn’t your behavior change as instantly as your desire to change it? In short, lasting change of habitual behavio…

via Matt Might's blog