Map sketch generation through multiobjective evolutionary algorithms
Çok amaçlı evrimsel algoritmalar kullanılarak harita eskizi üretimi
- Tez No: 485367
- Danışmanlar: DOÇ. DR. AYŞE ŞİMA UYAR
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2017
- Dil: İngilizce
- Üniversite: İstanbul Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Bilgisayar Mühendisliği Bilim Dalı
- Sayfa Sayısı: 79
Özet
Büyüyen video oyun endüstrisi ve oyunlara yapılan yatırımların artmasıyla tüketiciler (bundan sonra oyuncular olarak adlandırılacaktır) hiç olmadığı kadar çok seçeneğe sahipler. Bu durum oyuncuların ortalama bir oyundan beklentilerini de artırmaktadır. Bu beklentileri karşılamak için oyun stüdyoları her yıl daha iyi oyunlar çıkarmak zorundadırlar. Burada bahsi geçen daha iyi tamlaması çok sübjektif olsa da çoğu büyük ölçekli, yüksek bütçeli oyun firmalarının daha iyi'yi hissedilebilir kalite olarak algılamakta olduklarını yaptıkları oyunlarda en çok dikkat çeken özelliklerin kaliteli grafikler ve sesler, yüksek bütçeli müzikler ve film kalitesinde ara videolar olmasından çıkarabiliriz. Yüksek bütçeli ve kalitede oyunlar büyük firmalar tarafından ulaşılabilir olsa da, düşük bütçeli oyun stüdyoları/geliştiricileri (bağımsız oyun geliştiricileri) bu durumdan kötü etkilenmektedirler. Bağımsız oyun geliştiricileri çok az hatta bazen neredeyse hiç bütçeyle büyük firmalarla yarışmak zorunda. Durum böyleyken hissedilebilir kalite'de yarışamayacaklarından dolayı son zamanlarda bu oluşumlar daha yenilikçi-inovatif senaryolara, oyun stillerine, sonsuzluk hissiyatına vb. gibi çözümlere başvurmuşlardır. İnsan gücü olarak küçük ve eksik olmalarına rağmen bu eksikliklerini Posedürel İçerik Oluşturma (PIO) yöntemlerini kullanarak oluşturdukları içeriklerle kapatmaya çalışmaktadırlar. Başka bir deyişle insan gücünü hesaplama gücüyle Prosedürel İçerik Oluşturma yöntemlerini kullanarak değiştirmişlerdir. Video oyunlarında Prosedürel İçerik Oluşturma görünürde yeni bir çalışma alanı, konsept olarak görülse de kökleri 1980'lere Rogue oyununa dayanır. Bu oyunda kullanılan tekniklerdeki temel fikir değerli ve hali hazırda az olan belleği az kullanmaktı. Bundan dolayı Rogue'un haritaları otomatik olarak oyunun içindeyken oluşturuluyordu, yani kaynak eksikliğinden fırsat çıkarılmıştı. 1980'lerden bu yana pek-çok oyun stüdyosu Prosedürel İçerik Oluşturma yöntemlerini kullanmaya devam etti. Örnek vermek gerekirse Minecraft(2011) ve Terraria(2011) oyunlarının haritaları bu teknikler kullanılarak yeni bir oyun başlatılmadan önce oluşturulmaktadır. Daha yeni ve ilginç bir örnek ise No Man's Sky(2016) koca bir evren (sıfırdan elle yapılması bir insanın hayat boyunu aşan) tamamen otomatik olarak oluşturuldu. Prosedürel İçerik Oluşturma oyunun yalnızca haritalarını, bölümlerini değil senaryosunu, müziğini ve grafiklerini oluşturmak için de kullanılmaktadır. Okumakta olduğunuz yüksek lisans tezinde gerçek zamanlı strateji oyunları için en yeni çok objektifli evrimsel algoritma (NSGAIII) kullanılarak otomatik harita eskizleri oluşturan bir algoritma anlatılmaktadır. Algoritmanın çıktısı içinde bulunan tüm harita eskizleri farklı tasarım yönlerinde optimize edilmiş üç objektifli bir Pareto Front'tur. Bu çıktıya ulaşabilmek için Liapis'in çalışmasında önerdiği üç objektif fonksiyonu, üç denge gonksiyonu ve problem çözüm temsili (kromozomu) kullanılmıştır. Genel yönelim olan yalnızca birleşim fonksiyonları kullanmak yerine hem NSGAIII hem de birleşim fonksiyonları birlikte kullanılmıştır. Yine genel yönelim olan dolaylı temsil ve dekoder fonksiyonları yerine direkt temsil kullanılarak yüksek yerellik korunarak daha kaliteli çözümler bulmak amaçlanmıştır. Bahsedilen direkt temsil harita eskiz'i olarak adlandırılmaktadır. Bu yaklaşım hem oyunun boyutunu azaltmakta hem de yerliliği yüksek tutmaktadır. Başka bir artısı ise yeni objektif fonksiyonlar oluşturmanın rahat ve kolay olmasıdır. Harita eskiz'i yaklaşımı kısaca haritanın tüm özelliklerini oluşturmak yerine (duvarların açıları, estetik öğeler vb.) sadece optimize edilmesi planlanan öğelerden oluşan bir yapıdır. Bu tezde örnek oyun olarak seçilen StarCraft oyunu için düşünülürse bu öğeler; üsler, kaynaklar, geçilebilir alanlar ve geçilemez alanlar olarak sınıflandırılabilir. Genel amaçların dışında, iki yeni hızlı ve efektif evrimsel operatör tanımlanmıştır. Bunlar; gaus'çu yer değiştirme mutasyonu ve tek çizgi matris çaprazlaması'dır. Gausçu yer değiştirme mutasyonu kısaca yer değiştirme mutasyonunda değişecek genlerin Gaus dağılımından gelmesidir. Yani, yer değiştiren iki harita eskiz'i karesi büyük olasılıkla birbirlerine yakın yerlerden seçilecektir. Bu operatör tasarlanırken, mutasyonun olabildiğince anlamlı değişiklikler yapması amaçlanmıştır. Harita geneline bakıldığında birbirine uzak öğelerin birbiriyle yer değiştirmesi, etkisi çok yüksek ve geri düzeltilmesi zor problemlere neden olabilmektedir, bunun tamamen engellenmeyip şansının azaltılması başarımımızı artırmıştır. Alana katkı olarak sunduğumuz tek çizgi matris çaprazlaması da benzer bir şekilde çaprazlama operatörünün olabildiğince anlamlı olması fikri üzerine oluşturulmuştur. Burada temel amaç tek nokta çaprazlamasının kenar noktaları hariç noktalarda birbiriyle alakasız karelerin hep birlikte çocuk eskizlere taşınmasını önlemektir. İkinci bir amaç ise tek nokta çaprazlama yönteminin tek yönlü yapabildiği (dikey) bölünme yerine hem yatay hem dikey bölünmenin mümkün olmasını sağlamaktır. Rapor edilen sonuçlar çok objektifli evrimsel algoritmaların, prosedürel içerik oluşturma alanında birleştirme fonksiyonları yerine kullanılabileceğini ortaya koymuştur. Ayrıca yaptığımız bu testler çeşitli hiper parametrelerin ideal değerlerinin aralıklarını çıkarmıştır. Bunun dışında alana yeni katkılarımız olan gaus'çu yer değiştirme mutasyonu ve tek çizgi matris krosoverı yapılan testler ve analizlerde değerlerini kanıtlamış ve geleneksel yöntemleri geçmiştirler. Yapılan ölçeklenebilirlik testleri algoritmanın yavaşlığını ortaya koymuş ve daha fazla çalışmanın görece daha büyük harita oluşturma algoritmaları üzerine yapılması gerektiğini göstermiştir. Harita eskizi yaklaşımı temsil edilen haritaya göre boyutu büyük bir oranda azaltabilmesine rağmen, objektif fonksiyonlarının farklı sayıda üs, kaynak ve boyutlarda ölçeklenebilirliğinin zayıf olması nedeniyle algoritma genel anlamda bakıldığında ölçeklenebilir olmadığını göstermiştir. Algoritmanın daha genelleştirilebilmesi için objektiflerin yeniden tasarlanması ve/veya bu çalışmada sunulduğu gibi probleme veya alana yönelik yeni evrimsel operatörler üzerine çalışmalar yapılmalıdır. Algoritmanın başarımını kanıtlamak için yaptığımız testler ve analizler ayrıca problemin davranışını ortaya koyarak bilinmeyen noktalara açıklamalar getirmiştir. Sunulan algoritma ve genel anlamda yapılan çalışma oyun harita ve bölüm tasarımcıları için rehber bir araç olarak kullanılabileceği gibi direkt olarak oyunun içine entegre edilerek kullanılabilir. Direkt olarak oyunun içinde kullanılması durumlarında, oluşturulan sonuç bir ara modül kullanılarak oyunun haritasına dönüştürülmelidir. Görece büyük haritalarda ise bir arka plan prosesi olarak kullanılabilir, böylece uzun bekleme ekranlarından kaçınılabilir. Ticari kullanımlardan ayrı olarak; algoritma aynı zamanda kıyaslama veri setleri oluşturmada kullanılabilir, çünkü farklı problemler için (en kısa yol, yapay zeka botları vb.) farklı özelliklerde haritalar oluşturulabilmektedir.
Özet (Çeviri)
With the growing market size of the video game industry and increasing investments in games consumers (will be referred as players from now on) have more option than ever. Increasing quantity also increases players' expectation from a game. To satisfy player expectations game studios obligated to make better and better games each year. While the word better is highly subjective, most of the high-budgeted game studios are defining the word as perceivable quality. They offer high quality graphics and sounds, high-budgeted soundtracks, detailed cut-scenes etc. While this is attainable for high-budgeted corporations, low-budgeted game studios(or developers) namely indie game developers suffer from it greatly. They now need to compete this huge corporations with little or close to nothing resources. Since they are not able to compete on perceivable quality, they are focusing more on innovative scenarios, game-play, sense of infinity etc. Although they are short on man power, they have computation power so lot of them tend to replace man power with computation power using Procedurally Generated Contents in their games using Procedural Content Generation (PCG) techniques. Although Procedural Content Generation seemly new concept it's roots goes all back to game Rogue (1980). The idea was to generate game levels within the game to save valuable memory space, create opportunity from lack of resources. From then to now, lot of game studios used PCG in their games. For example Minecraft(2011) and Terraria(2011) create their game world entirely using PCG techniques. Another more recent example is No Man's Sky(2016) creates entire universe automatically. It's not just the maps or levels, PCG techniques can be used to create another game contents such as; scenario, music, graphics etc. In this thesis a method to generate map sketches for real time strategy (RTS) games using state of the art many-objective evolutionary algorithm (namely NSGAIII) presented. Output of the algorithm is three objective Pareto front that has many solutions (map sketches) to problem which all are non-dominated and strong in different aspects of a game map. To achieve this output Liapis' three objective functions, three balance functions and problem solution representation is adapted. Instead of using aggregating functions we used a combination of aggregating functions as well as MOEAs to generate high variety and quality solutions with a single run. Also in this study we used direct representation instead of indirect representation and decoders to maintain high locality as well as easiness of objective functions. Other than the main purposes and achievements we aimed and attained, we also introduced two new operators that are robust and efficient which are: gaussian swap mutation and one line matrix crossover. Reported results in this study are promising and prove that MOEAs are decent alternatives to aggregating functions. Other than that our novel contributions gaussian swap mutation and one line matrix crossover proved their value in the analyses done. Within the study high variety of tests and statistical analysis are done. These tests are not only statistically shows our approach's success also clarify some behaviours and features of the landscape of the problem. Scalability tests that have executed for this study shows that further research is required to solve bigger maps due to slowness of the approach for relatively big map sketches. The algorithm that is presented in this thesis and the study in general can be used as a guidance tool for game level/map designers or it can be directly integrated to a video game. Also other than commercial usages, it can be used as a benchmark test data-set generator for various computational intelligence problems such as; shortest path, artificial intelligence design for RTS bots etc.
Benzer Tezler
- Exploring the cognitive processes of map users employing eye tracking and EEG
Göz izleme ve EEG yöntemleri kullanılarak harita kullanıcılarının bilişsel süreçlerinin araştırılması
MERVE KESKİN
Doktora
İngilizce
2020
Coğrafyaİstanbul Teknik ÜniversitesiGeomatik Mühendisliği Ana Bilim Dalı
DOÇ. DR. AHMET ÖZGÜR DOĞRU
PROF. DR. PHILIPPE DE MAEYER
- Spatial cognition: Application of space syntax on Beyazıt district, İstanbul
Mekansal bilişim: Mekan dizim yönteminin Beyazıt, İstanbul kapsamında uygulanması
SAMİRA MALEK
Yüksek Lisans
İngilizce
2015
Mimarlıkİstanbul Teknik ÜniversitesiKentsel Tasarım Ana Bilim Dalı
PROF. DR. AYŞE SEMA KUBAT
- City image and metro; case study: Batıkent metro
Kent imajı ve metro; Batıkent metrosu örneği
FİLİZ KIRSAKAL
Yüksek Lisans
İngilizce
2002
Şehircilik ve Bölge PlanlamaOrta Doğu Teknik ÜniversitesiŞehir ve Bölge Planlama Ana Bilim Dalı
YRD. DOÇ. DR. ADNAN BARLAS
- The contribution of immediate surroundings of symmetric buildings to wayfinding behavior: Taskisla as a case
Simetrik yapılarda yön bulma daranışına yakın çevrenin katkısı: Taşkışla örneği
MUHAMMED ATAULLAH DİLSİZ
Yüksek Lisans
İngilizce
2016
Mimarlıkİstanbul Teknik ÜniversitesiMimarlık Ana Bilim Dalı
YRD. DOÇ. DR. DİLEK YILDIZ
