Engellere takılmayan harita üzerinde en kısa yol algoritması

mk148a

Öğrenci
Katılım
4 Haziran 2011
Mesajlar
11
Reaksiyon puanı
0
Puanları
1
Arkadaşlar,benim elimde netcad ve autocad ortamında çizilmiş halde bulunan bir harita var.Harita çizgi ve 3boyutlu yüzey elemanlarından oluşuyor.
Haritada yapmak istediğim karakterin a noktasından b noktasına yollardaki ve kenarlardaki engellere takılmadan en kısa mesafeden rotasını belirlemesini programlamak istiyorum.
Dağ,taş,el arabası ve binalar gibi engeller ve yollar autocad ortamında katmanlara ayrılmış durumda.
Ayrıca harita sol alt köşe orijin olmak üzere 1024x1024 pikselden oluşuyor.
Tüm bunları kullanarak bir program yazmak istiyorum,bu haritanın üzerinde bir noktadan diğer noktaya en kısa engelelre takılmadan gitmesi için hangi algoritmayı kullanmam lazım ve nasıl yazmam lazım.Aynı zamanda bu autocad ortamındaki haritayı programlamada nasıl tanımlarım(yollar,dağlar falan tanuımlanacak).

Bundan daha spesifik olarak aynı bu mantıkla çalışan biraz daha karmaşık bir problem var.Bu harita üzerinde bulunan oyun karakterlerinide bu işleme katarak nasıl yaparız.Yani oyun içinde bizim karakterimizin durduğu noktadan oyun içindeki sabit karakterlere(aynı yerde duran) yolları kullanarak ve engellere takılmayarak gitmesi gerek,şöyle anlatayım örnek vererek.

Benim karakterim dediğim bir araba sabit karakter dediğim benzin istasyonları,yollar var bide yol üstünde ve kenarlarda engeller var.Haritada bir sürü benzin istasyonu var bu benzin istasyonları arasında benim bulunduğum konuma sadece yolları takip ederek yakın olanını bulup,bunu koordinatlarını bana döken bir program lazım.
Bir nevi gps navigasyonu gibi bir mantık.Bana yardım edebilirmisiniz.
 
Katılım
31 Aralık 2007
Mesajlar
17,486
Reaksiyon puanı
189
Puanları
243
Vallahi algoritma mantık olarak hoşuma gitti ama nasıl yaparım bir fikrim yok. Biraz araştırma yapmak gerekir...
 

mk148a

Öğrenci
Katılım
4 Haziran 2011
Mesajlar
11
Reaksiyon puanı
0
Puanları
1
ya bunu hocalarıma danıştım,network analizi ile yapılıyor dediler.Network analizi alogoritamlarından bir isim söylemişti temeli ona dayanıyor dedi,ama bulamadım bu algoritmayı kodlayabilmek lazım.
 

mk148a

Öğrenci
Katılım
4 Haziran 2011
Mesajlar
11
Reaksiyon puanı
0
Puanları
1
baya karışık görünüyor,bunu kodlayabilecek biri varmı acaba.
size bir algoritma vereyim yöntemi örnek vereyim dijkstra algoritması http://www.ce.yildiz.edu.tr/en/mygetfile.php?id=1000
bu algoritmayı benim cad projesinin koordinat sistemini kurarak bir c++ yada vb program yazıp kullanabilirmiyiz?

---------- Post added at 04:17 ---------- Previous post was at 04:15 ----------

yalnız bu algoritmada engellere takılıyormu bahsetmemişler
 
Katılım
31 Aralık 2007
Mesajlar
17,486
Reaksiyon puanı
189
Puanları
243
vallahi daha önce böyle bir şey kodlamadığım için mantık olarak karmaşık geldi. bir kordinat sistemi kesinlikle olmalı. Bu kordinat sistemine bağlı bir ölçeklendirme sistemi de olmalı. İki nokta arasındaki mantıksal bir alan içerisinde yol olarak işaretlenmiş yerleri birbirine ekleye ekleye en kısa yoldan sona kadar olan haritayı deneme yanılma yöntemi ile bulacak bir algoritma lazım. Mantık olarak ya da kafada canlandırma olarak kolay gibi görünse de aslında arkasında çok sağlam bir kodlamaya ihtiyaç var. Boş vaktim olsa hiç üşenmez ilgilenirdim ama şu an projelerim var. Ama konu takibimde :)
 

mk148a

Öğrenci
Katılım
4 Haziran 2011
Mesajlar
11
Reaksiyon puanı
0
Puanları
1
tamam sağ olasın,aynen dediğin gibi basit görünen karmaşık bir kodlama gerektiriyor
 
Katılım
31 Aralık 2007
Mesajlar
17,486
Reaksiyon puanı
189
Puanları
243
Aklıma şöyle bir şey geldi. İnternette mutlaka labirent çözme algoritmaları falan vardır. O algoritmalardan yararlanarak mantığı labirentin üzerine oturtup kodlamayı yapabilirsin. Biraz incele istersen. Ben de merak ettim ben de araştırıcam şimdi...

Hatta wikipedia'da birşeyler var bu algoritmalar ile ilgili.

http://en.wikipedia.org/wiki/Maze_solving_algorithm

Algoritmanın içine uzunluk ölçüleri de girecek senin. Sonuçta haritadaki bir yere 3-5 sokak dolaşarak da gidebileceğin onlarca ihtimal çıkacak ama yolların en kısasını bu ölçülendirme yöntemi ile ancak tespit edebilirsin...

Karmaşık bir konu :) Ama hoşuma gitti :)
 

mk148a

Öğrenci
Katılım
4 Haziran 2011
Mesajlar
11
Reaksiyon puanı
0
Puanları
1
yapay zeka ile çalışacan robotlar bu mantıkla çalışıyor zaten,oldukça karışık bunu kodlamak her yiğdin harcı değil hele benim hiç değil,tek bildiğim vb 6da if then else :D
 
Katılım
31 Aralık 2007
Mesajlar
17,486
Reaksiyon puanı
189
Puanları
243
Senin gönderdiğin algoritma'da zaten labirent çözüm algoritması olarak geçiyor :) Daha birkaç farklı yöntem daha var. Konu aslında çok keyifli bir konu ama sağlam kafa patlatmak gerekiyor :) Yapılmayacak bir şey değil gibi görünüyor. Boş bir vaktimde labirent çözen bir program yazmayı listeme aldım :) Bu benim için baya iyi bir deneyim olacak.

Benim düşüncem recursive fonksiyonlar yardımı ile en mantıklı ve kısası olur gibi geliyor ama recursive olmayan yöntemler de var. Hepsini incelemek lazım :)
 

mk148a

Öğrenci
Katılım
4 Haziran 2011
Mesajlar
11
Reaksiyon puanı
0
Puanları
1
ben harita müh. okuyorum bittcek bu sene,bizde cbs(coğrafi bilgi sistemleri) diye bir alan var,orda geometrik veri ile öznitelik verilerini ilişkilendirerek analiz yapıyoruz,arcgis diye bir program var çok geniş kapsamlı analizler yapılabiliyor.Bunların içinde network analizi diye bir analiz şekli var,orda iki nokta arasında ki en kısa yol güzergah belirleme analizi var bunu yapan belediyelerden biri izmir belediyesi istersen incele.http://212.175.206.243/
 

magnet

Asistan
Katılım
17 Eylül 2005
Mesajlar
499
Reaksiyon puanı
5
Puanları
18
http://en.wikipedia.org/wiki/Minimum_spanning_tree

MST Algorithm olarak geçiyor. Minimum Spanning Tree.
Geçen seneki ODTÜ Programlama yarışması için kullanmıştık.

Şunada bak derim
http://www.yazgelistir.com/Makaleler/1000001435.ygpx
Bunuda bi incele derim ama senin aradığın algoritma MST. Network te paketli verilerin yollarını bulması için de kullanılıyor.

---------- Post added at 03:52 ---------- Previous post was at 03:48 ----------

Tabi engellere takılma olayına bişey diyemem.
 

feldrim

Öğrenci
Katılım
5 Haziran 2011
Mesajlar
5
Reaksiyon puanı
0
Puanları
0
Bu sorunun cevabı kesin olarak A* algoritmasıdır. Basit bir sezgisel algoritmadır ve onlarca geliştirilmiş versiyonu vardır. Temel olarak A* algoritmasını çözersen diğer versiyonlarını daha çabuk çözebilirsin. Wikipedia'daki makale nin linki burada:
http://en.wikipedia.org/wiki/A*_search_algorithm

HPA*, theta*, LPA*, GAA* gibi versiyonları daha sonra denersin. Yurtdışında bu konu akademik olarak da iş sektörü açısından da üzerinde durulan bir konu olduğu için pek çok kaynak var. Daha fazlasını istersen belki yardımcı olabilirim.
 

mk148a

Öğrenci
Katılım
4 Haziran 2011
Mesajlar
11
Reaksiyon puanı
0
Puanları
1
peki bunu benim yollları ve engelleri tanımladığım autocad dosyasında nasıl uygulayacaz,yada bu oyunda engelleri direk tanır mı?
 

feldrim

Öğrenci
Katılım
5 Haziran 2011
Mesajlar
5
Reaksiyon puanı
0
Puanları
0
http://www.policyalmanac.org/games/AStar.zip
Bu linkte 2 boyutlu bir örnek var. Sen tabi ki bunu iki boytlu yapmayacaksın ancak işlev aynı. Hareket edeceğin yüzeyi bölgelere bölüyor ve her bölgeye puan veriyor. Bölgede herhangi bir nesne varsa o yolu kapatıyor. A noktasından B noktasına giden bütün kareler arasından mümkün olan en az işlemle -çünkü binlerce kombinasyon olabilir ve Dijkstra gibi hemen hepsini hesaplamak işlevsiz hale getirir- yapmaya çalışıyor. Sezgisel bir metot olduğundan olasılık da konunun içinde. Yani sonuç "kesinlikle en kısa yoldur" diyemeyiz. En kısa yol olma ihtimali de var ancak bu algoritma en hızlı şekilde bulabildiği en kısa yola bakıyor.

Sen Autocad'de tasarladığın karakterleri C, C#, C++, Visual Basic gibi herhangi bir dille 3D olarak görüntülemeye çalışacaksın. Daha sonra karakterinin hareket algoritmasını hazırlayacaksın. Bundan sonra ancak bu A* algoritmasını kendi karakterinin her bir adımında kullanmasını sağlayacaksın. (Her adım diyorum çünkü çevre değişebilir, engeller hareket edebilir, yol tıkanabilir. A* dinamik bir algoritmadır, kullanmayı bilirsen.) Engelleri de bu yazdığın program içerisinde bir nesne olarak gösterdiğin takdirde A*'a tanıtabilirsin.
 

mk148a

Öğrenci
Katılım
4 Haziran 2011
Mesajlar
11
Reaksiyon puanı
0
Puanları
1
peki çok sağolun biglilendirdiğniiz için,peki autocaddeki çizimi buraya nasıl taşıuacağım 3boyutlu çok karışık oalcaksa 3boyutlu tanıtmaya gerek yok engelleri 2boyutlu çizip tanımlayabilrim,zaten knightta x,y koordinatlarını girince otomaiik gidiyor çünkü x,y koordinlarından z koordinatını hesaplama fonksiyonu var otomaik hesaplıyor,ben bu fonksiyonu bularak 3boyutlu yüzey haritasını çıkarttım oyunun haritasının.FAkat bu koordinat sistemini c++da tanımlamam lazım,şaun elimde codegear rad studio c++ builder var ve kod tecrübem çok az size gerekli verileri sağlarsam bana yardım edeiblrimisiniz?
 

feldrim

Öğrenci
Katılım
5 Haziran 2011
Mesajlar
5
Reaksiyon puanı
0
Puanları
0
Sana tavsiyem Autocad dosyasını yapabiliyorsan başka bir formata dönüştürmen. Autocad dosyalarını başka bir programla açıp kullanmak çok zor birşey. Onun için uğraşacağına dönüştürmeye çalışsan biraz daha işin kolaylaşır. Blender ya da 3Dmax dosyası olsa işin kolaylaşır çünkü yüzlerce örneği var. C++ konusunda malesef yardım edemem.
 

mk148a

Öğrenci
Katılım
4 Haziran 2011
Mesajlar
11
Reaksiyon puanı
0
Puanları
1
Sana tavsiyem Autocad dosyasını yapabiliyorsan başka bir formata dönüştürmen. Autocad dosyalarını başka bir programla açıp kullanmak çok zor birşey. Onun için uğraşacağına dönüştürmeye çalışsan biraz daha işin kolaylaşır. Blender ya da 3Dmax dosyası olsa işin kolaylaşır çünkü yüzlerce örneği var. C++ konusunda malesef yardım edemem.
3ds formatına dönüştürebilirim,ve iki boyutlu kullanacam 2boyutlu 3D studio max dosyası ile bu algoritmayı c++ yada C # dilinde nasıl kodlayabilrim?
 

byharby

Profesör
Katılım
31 Ağustos 2009
Mesajlar
1,365
Reaksiyon puanı
21
Puanları
218
Nesneye dayalı birçok programlama dilinde "çarpışma testi" için komutlar var. Örnek: Action script hit test. Ben bu kadar biliyorum , umarım ilham verir. :)
 

feldrim

Öğrenci
Katılım
5 Haziran 2011
Mesajlar
5
Reaksiyon puanı
0
Puanları
0
C# ve A* algoritması için iki örnek vereyim. http://www.codeproject.com/KB/recipes/graphs_astar.aspx ve http://www.codeguru.com/csharp/csharp/cs_misc/designtechniques/article.php/c12527.
Bu derslerde detaylı olarak ne yapman gerektiğini öğrenebilirsin. Örnek kodlar ve dosyalar bulunuyor. Bildiğim kadarıyla sen bunları yeni bir yazılım yapmak için değil başka bir yazılım üzerinde denemek üzere kullanacaksın. Sen bu algoritmanın mantığını öğrendikten sonra o kullanacağın yazılımın ne gibi değişikliklere/eklemelere izin verdiğine bir bak. Belki bot yazmaya izin veren oyunlarda olduğu gibi script'lerle eklenti hazırlayabilirsin. Ya da kendi editörleri, API'leri, SDK'ları vardır. O açıdan da bir incele bence. Mutlaka senin gibi, o yazılım ile ilgili yapılmaya çalışılmış ufak projeler vardır. Nette arayıp bul, rotanı ona göre çiz. Kullanacağın dili ona göre seçersin.
 
Üst