A new offline path search algorithm for computer games that considers damage as a feasibility criterion
Tehditleri dikkate alan yeni bir çevrim dışı yol bulma algoritması
- Tez No: 176782
- Danışmanlar: PROF. DR. FARUK POLAT
- 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: 2008
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 81
Özet
Günümüz bilgisayar oyunlarında kullanılan yol bulma algoritmaları, bir çozümün optimal olma ölçütü olarak yalnızca yol uzunluğu ya da benzer bir değeri kullanırlar. Ancak bu tür oyunlarda genellikle birbirlerine düşman olan ve birimleri diğer tarafların birimlerine hasar verebilen taraflar yer alır. Dolayısıyla, bu oyunlarda iki nokta arasındaki en kısa yol, en güvenli yol olmayabilir. Bu nedenle, haritadaki tehdit unsurlarını da dikkate alan, A* tabanlı, optimal olmayan yeni bir çevrim dışı yol bulma algoritması geliştirilmiştir. Bu algoritma, müsamaha gösterilen hasar miktarının belirtilmesi sonrasında, haritada verilen iki nokta arasında, birimi bu miktarı geçmeyen derecede hasara maruz bırakacak bir yol bulmaya çalışır. Bu özelliği nedeniyle bu algoritma Sınırlı-Hasar A* (LDA*) algoritması olarak adlandırılmıştır. LDA*'ın performansı, rastlansal olarak üretilmiş olan tam gözlenebilir labirent benzeri ızgara soyutlamalı kare haritalarda, optimal ve tam bir algoritma olan Çok Amaçlı A* (MOA*) algoritmasınınkiyle karşılaştırılmıştır. Geliştirilen algoritmanın, MOA*'dan çok daha hızlı olduğu ve izin verilebilir derecede optimal altı sonuçlar verdiği belirlenmiştir.
Özet (Çeviri)
Pathfinding algorithms used in today?s computer games consider path length or a similar criterion as the only measure of optimality. However, these games usually involve opposing parties, whose agents can inflict damage on those of the others?. Therefore, the shortest path in such games may not always be the safest one. Consequently, a new suboptimal offline path search algorithm that takes the threat sources into consideration was developed, based on the A* algorithm. Given an upper bound value as the tolerable amount of damage for an agent, this algorithm searches for the shortest path from a starting location to a destination that would cause the agent suffer no more damage than the specified maximum. Due to its mentioned behavior, the algorithm is called Limited-Damage A* (LDA*). Performance of LDA* was tested in randomly-generated and hand-crafted fully-observable maze-like square environments with 8-way grid-abstractions against Multiobjective A* (MOA*), which is a complete and optimal algorithm. It was found to perform much faster than MOA* with allowable sub-optimality in path length.
Benzer Tezler
- Mobil robotlarda evrimsel metotlar ile optimal hareket planlama
Optimal motion planning with evolutionary methods for mobile robots
SERKAN AYDIN
Doktora
Türkçe
2003
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiElektrik Mühendisliği Ana Bilim Dalı
DOÇ. DR. HAKAN TEMELTAŞ
- Büyük ölçekli havayolu ekip eşleme problemlerinin çözümü için bir kolon türetme stratejisi
A column generation strategy for large scale airline crew pairing problems
BAHADIR ZEREN
Doktora
Türkçe
2017
Uçak Mühendisliğiİstanbul Teknik ÜniversitesiUçak ve Uzay Mühendisliği Ana Bilim Dalı
PROF. DR. İBRAHİM OZKOL
- Control algorithms applied to uav for search and rescue over water
Su üzerinde arama ve kurtarma çalışmaları için UAV'ye uygulanan kontrol algoritmaları
FADY M.A ALALAMI
Doktora
İngilizce
2020
Elektrik ve Elektronik Mühendisliğiİstanbul Üniversitesi-CerrahpaşaElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. ABDULRAHMAN HUSSIAN
- Bağlı veri üzerinde dağıtık sorgulama optimizasyonu
Federated query optimization on linked data
ETHEM CEM ÖZKAN
Yüksek Lisans
Türkçe
2015
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolTOBB Ekonomi ve Teknoloji ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. ERDOĞAN DOĞDU
- Process mining for analysis of indoor customer behaviors
Süreç madenciliği ile iç mekan kullanıcı davranışları analizi
ONUR DOĞAN
Doktora
İngilizce
2019
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. BAŞAR ÖZTAYŞİ