Geri Dön

Oyun motorlarında güzergah belirleme

Routing in game engines

PDF İndir

  1. Tez No: 676560
  2. Yazar: ABDULKADİR BAYTİMUR
  3. Danışmanlar: DOÇ. DR. CANER GÜNEY
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilim ve Teknoloji, Science and Technology
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2021
  8. Dil: Türkçe
  9. Üniversite: İstanbul Teknik Üniversitesi
  10. Enstitü: Bilişim Enstitüsü
  11. Ana Bilim Dalı: Bilişim Uygulamaları Ana Bilim Dalı
  12. Bilim Dalı: Coğrafi Bilgi Teknolojileri Bilim Dalı
  13. Sayfa Sayısı: 91

Özet

Geçmişte oyun motorları sadece oyun yapımında kullanılan programlar olarak kabul edilirdi. Günümüzde ise oyun motorları sağladıkları özgür üç boyutlu ortam, çalışma anındaki anlık etkileşim olanağı ve kişiselleştirilebilir araçlarının olması gibi nedenlerle; oyun endüstrisi dışında da birçok sektörde kullanım alanı bulmuştur. Bunlardan biri de farklı tematik alanlarda mekansal veri kümelerinin analizi ve görselleştirmesi üzerinde çalışan Coğrafi Bilgi Sistemleri (CBS) sektörüdür. CBS uygulamalarında hali hazırda kullanılan bir çok açık kaynaklı ve ticari yazılım bulunsa da, bunlar genel olarak üç boyutlu ortamda çalışmak için gerekli grafik hesaplama yetisine sahip olmadıklarından bu tür işler için hantal kalabilmektedir. Özetle CBS yazılımları oyun motorları kadar performans sunamamaktadır. Bu tez çalışmasında, oyun, oyun motoru ve CBS arasındaki ilişkiden bahsedilmeye çalışılmıştır. Çalışma kapsamında NavMesh sistemi ve yapay zeka karakterlerinin otonom güzergah bulması konusu açıklanmıştır. Unity oyun motoru kullanılarak güzergah belirleme uygulaması geliştirilmiş ve daha sonra Data-Oriented Technology Stack gibi oyun motorundaki farklı yaklaşımlar kullanılarak güzergah belirleme uygulamasının nasıl daha performanslı hale getirildiği açıklanmıştır. Günümüzde güzergah belirleme pek çok farklı alanla kullanılmaktadır. Amacı ne olursa olsun güzergah belirlerken temel olarak bir başlangıç ve bir hedef noktası olması gerekmektedir. Bu iki nokta arasında farklı gereksinimler ve parametrelerle (en az maliyetli, en verimli, en kısa yol vb.) güzergah belirlenebilmesi için Djikstra ve A* gibi güzergah belirleme algoritmaları kullanılmaktadır. Tez çalışması kapsamında Unity oyun motorunda nesne odaklı (object oriented) ve veri odaklı (data oriented) olmak üzere A* algoritması kullanılarak bir çok güzergah belirleme uygulaması geliştirilmiştir. Nesne odaklı yaklaşımda Unity oyun motoru doğrudan kullanılmıştır. Veri odaklı yaklaşımda Unity oyun motorunda henüz yeni bir teknoloji olan ve farklı bir bakış açısı getiren Data-Oriented Technology Stack (DOTS) kütüphanesi eklenerek geliştirme yapılmıştır. DOTS; C# İş Sistemi, Entity-Component-System, Burst Derleyicisi olmak üzere temel olarak 3 farklı bileşeni içermekte ve hepsinin ortak amacı performans artışı sağlamaktır. DOTS ile bu performans artışı; üç boyutlu nesnelerin, nesne yerine veri olarak işlenmesi, C# kodunun daha optimize yazımı ve kodların derlenmesindeki yöntem farkı ile sağlanmaktadır. Bu çalışma için, Unity'de birim karelerden oluşan ve 20*20 ve 100*100 boyutlarında olan, kare şeklinde 2 farklı grid ağ oluşturulmuştur. Daha sonra A* güzergah belirleme algoritması simüle edilmiştir. Kare gridin en sol alt köşesinden (başlangıç noktası) en sağ üst köşesine (hedef noktası); eş zamanlı olarak 5'er ve 50'şer güzergah belirleme işleri aynı anda çalıştırılmıştır. Bu test nesne odaklı sistem, C# İş Sistemi, C# İş Sistemi + çoklu işlem parçacığı metodu ve son olarak tüm C# İş Sistemi + çoklu işlem parçacığı metodu + Burst Derleyicisi birlikte kullanımı biçiminde 4 farklı yöntem için denenmiştir. Nesne odaklı sistemde 20*20'lik gridde 5'er güzergah hesaplama eş zamanlı yapıldığında 330-400 milisaniye arasında, sadece C# İş Sistemi 1.6 milisaniyede, C# İş Sistemi + çoklu işlem parçacığı metodu ile 0.11 milisaniyede ve C# İş Sistemi + çoklu işlem parçacığı + Burst Derleyicisi birlikte kullanıldığında 0.04 milisaniyede güzergah bulunmuştur. 100*100'lük gridde 50'şer güzergah hesaplama eş zamanlı yapıldığında ise; nesne odaklı sistem çökmüş ve çalışmamıştır, C# İş Sistemi 46 milisaniyede, C# İş Sistemi + çoklu işlem parçacığı 4.5 milisaniyede, C# İş Sistemi + çoklu işlem parçacığı metodu + Burst Derleyicisi birlikte 1.5 milisaniyede hesaplamayı tamamlamıştır. Çalışmada beklenildiği gibi veri odaklı yöntemin nesne odaklı yönteme göre çok daha performanslı çalıştığı belirlenmiştir. Sonraki aşamada bu uygulamaya ECS sistemi entegre edilmiştir. Böylece ECS ile birlikte DOTS'un tüm elemanları kullanılmıştır. Hareketli ajanlar oyun nesnesinden, varlıklara dönüştürülmüştür. Kullanılan iş sistemleri tarafından, bu varlıklar için güzergah bulma algoritmaları çalıştırılmıştır. 100 hareketli ajanın güzergah belirleme işi Burst Derleyicisi kapalıyken 9.76 milisaniyede, Burst Derleyicisi açıkken 1.01 milisaniyede hesaplanmıştır. Daha sonra, ECS'nin sınırlarını zorlamak adına Burst Derleyicisi açıkken, 20000 ajan kullanılmış ve güzergah bulma işi 236.04 milisaniyede hesaplanmıştır.

Özet (Çeviri)

In the past, game engines were considered only as programs used in game production. Today, game engines have found use in many sectors outside the game industry; due to reasons such as free three-dimensional environment they provide, the opportunity for instant interaction at run-time, and the fact that they have customizable tools. One of these sectors is the Geographic Information Systems (GIS) field, which works on the analysis and visualization of spatial datasets in different thematic areas. Although there are many open source and commercial softwares currently used in GIS applications, they can be cumbersome for this type of work as they generally do not have the necessary graphical computation ability to work in a three-dimensional environment. In summary, GIS software cannot offer as much performance as game engines. In this thesis, the relationship between game, game engines and GIS were tried to be mentioned. It was tried to explain with several examples that how some video games benefit from real world spatial data. While the game industry makes great use of the real world; it has been mentioned that the GIS industry does not sufficiently benefit from games and game engines. Although GIS softwares are generally considered sufficient in 2D studies, it cannot quickly apply the technological possibilities brought by game engines in 3D systems and interactive applications. Game engines are an advanced development environment for building GIS applications and running simulations. They offer a high-level visualization system, include pyhsics engine that allows realistic simulations. Also they provide an animation system, audio engine, cross-platform software support. Game engines have advanced script structure that allows users to build their own tools. In addition, game engines have an extremely large developer community and is constantly developing new tools and features. Storing and using location data is critical in the GIS approach. For this reason, GIS softwares work integrated with databases. The game development environment supports the storage and use of datasets from various sources, just like a GIS software does. Since there is an advanced script structure in game engines, it is possible to find a library suitable for all kinds of database needs. By adding these libraries to the game engine, data sets can be worked on. Terrains can be brought into the game engine, models of pyhsical objects (building, road, etc.) can be added. In addition, the information of each object (meta-data) can be stored in databases and used by the game engine. Within the scope of the study, the subject of autonomous path finding system and artificial intelligence (AI) characters were explained. In this thesis, two different AI navigation method were explained and used in different applications. These are grid-based system and navigation mesh system. In grid-based system, the world is divided up into an even grid and A* search algorithm is used to find the shortest path in this grid. A navigation mesh system divedes the world surface into polygons and calculates shortest path according to these areas. Unity game engine's own navigation mesh system (NavMesh) were explained and a pathfinding application was develeoped by using the Unity game engine. After that a grid-base pathfinding application were developed by using a basic A* algorithm. This application was later used for performance comparison with subsequent applications. Today, pathfinding is used in many different fields. Regardless of its purpose, it is essential to have a starting point and a destination while determining the route. Pathfinding algorithms such as Djikstra and A* are used to determine routes between these two points with different requirements and parameters (least cost, most efficient, shortest route, etc.).Within the scope of the thesis, many pathfinding applications have been developed using the A* algorithm for object-oriented and data-oriented approaches in the Unity game engine environment. Unity game engine is used directly in the object-oriented approach. In the data-oriented approach, the Unity game engine has been developed by adding the Data-Oriented Technology Stack (DOTS) library, which is a new technology and brings a different perspective. DOTS includes 3 different components such as C# Job System, Entity-Component-System and Burst Compiler and the common purpose of all of them is to increase performance. With DOTS, this performance increase is achieved by processing three-dimensional objects as data instead of objects, more optimized writing of C# code, and the difference in the way the codes are compiled. C# Job System makes use of multi-core processors to run several jobs at the same time. One of the main problems with Unity game engine performance has always been that the main-thread is single-threaded. With C# Job System, many paths can be calculated at the same time and this leads to an increase in performance. ECS writes code from a different perspective; it requires dividing the code into two, as logic and data. Instead of standard game objects, there are entities, components and systems that converts game objects to data which also increases performance. And lastly, the Burst Compiler takes all written C# code and turns it into highly optimized machine code. It automatically makes the code being compiled benefit from certain optimizations for certain platforms. For this study, 2 different grid networks in the form of squares, consisting of unit squares and having dimensions of 20*20 and 100*100, were created in Unity. Then the A* pathfinding algorithm was simulated from the bottom left corner (starting point) to the top right corner (destination point) of the square grid. 5 and 50 pathfinding jobs were run simultaneously. This test has been tested for 4 different methods such as object-oriented system, C# Job System, C# Job System + multi-threading method and finally all C# Job System + multi-threading method + Burst Compiler together. When calculating 5 routes on a 20*20 grid simultaneously; the object-oriented system took between 330-400 milliseconds, C# Job System took 1.6 milliseconds, C# Job System + multi-threading took 0.11 milliseconds and when C# Job System + multi-threading + Burst Compiler used together, the paths were found in 0.04 milliseconds. When calculating 50 routes simultaneously on a 100*100 grid; the object-based system crashed and did not work, C# Job System completed the calculations in 46 milliseconds, C# Job System + multi-threading comleted the calculations in 4.5 milliseconds, C# Job System + multi-threading + Burst Compiler together completed the calculations in 1.5 milliseconds. As expected in the study, it was determined that the data-oriented method works much more efficiently than the object-oriented method. In the next stage, the ECS was integrated into this application. Thus, all elements of DOTS were used. Moving agents have been converted from game objects to entities. Pathfinding algorithms for these entities were run by the job systems. Pathfinding job of the 100 agents was calculated in 9.76 milliseconds while Burst Compiler turned off, and calculated in 1.01 milliseconds while Burst Compiler turned on. Then, to push the limits of ECS, with the Burst Compiler turned on, 20000 agents were used and the pathfinding job was calculated in 236.04 milliseconds.

Benzer Tezler

  1. Tez No

    295272

    Oyun ortamında iskelet tabanlı programlamaya yönelik etap üretimi ve mimari mekanların canlandırılması

    Level production and animating of architectural spaces in game environment according to skeleton based programming

    AYKUT DOĞANAY ALBAYRAK

    Yüksek Lisans

    Türkçe

    Türkçe

    2011

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Bilişim Ana Bilim Dalı

    DR. HAKAN TONG

  2. Tez No

    559891

    Oyun motorlarının mimarı tasarım ve temsil süreçlerinde değerlendirilmesi

    Evaluation of game engines in architectural design and representation processes

    OSMAN SÜMER

    Yüksek Lisans

    Türkçe

    Türkçe

    2019

    Bilim ve Teknolojiİstanbul Teknik Üniversitesi

    Bilişim Ana Bilim Dalı

    PROF. DR. MİNE ÖZKAR KABAKÇIOĞLU

  3. Tez No

    613815

    Altıncı sınıf Türkçe dersi ses olayları konusunda geliştirilen eğitsel oyunun akademik başarıya etkisi

    The effect of developing educational game on the learning of determined achievements at the Turkish lesson

    FEYZA ŞAHİN

    Yüksek Lisans

    Türkçe

    Türkçe

    2019

    Eğitim ve ÖğretimBalıkesir Üniversitesi

    Bilgisayar ve Öğretim Teknolojileri Eğitimi Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ MEHMET EMİN KORKUSUZ

  4. Tez No

    360582

    Modeling student behaviors in a virtual classroom using Belief Desire Intention model

    Sanal bir sınıfta öğrenci davranışlarının Belief Desire Intention modeli ile modellenmesi

    EMRE CANBAZOĞLU

    Yüksek Lisans

    İngilizce

    İngilizce

    2014

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik Üniversitesi

    Modelleme ve Simülasyon Ana Bilim Dalı

    PROF. DR. VEYSİ İŞLER

  5. Tez No

    448184

    Günümüz bilgisayar oyunlarında yeni grafik çözümlemeleri ile bu çözümlerin 3 boyutlu sanal müze yapımında kullanımı ve bir proje çalışması

    The use of the new graphic analysis of the contemporary computers and the use of these solutions in the production of 3 dimensional virtual museums and a project study

    MEHMET EMİN DİNÇ

    Yüksek Lisans

    Türkçe

    Türkçe

    2016

    Güzel SanatlarYaşar Üniversitesi

    Sanat ve Tasarım Ana Bilim Dalı

    YRD. DOÇ. İSMAİL OKAY

Geri Dön