artık bu blog'a daha fazla yazı eklemeyeceğim, onun yerine başka bir blog başlattım. Bu blogdaki tüm yazılar orada da var. Aslında devamı gibi. Yeni blogum artık hem ingilizce hem de türkçe olacak. Çok az post olmasından dolayı şu an için ingilizcesine ulaşılamıyor ama zaman içerisinde o da çalışır hale gelicektir. Hemen gitmek için;
Sonradan gelen düzenleme;
Sürekli güncellemeydi, spamdi derken blog'umu tekrar blogspot'a taşımış bulunmaktayım.
29 Eylül 2009 Salı
5 Eylül 2009 Cumartesi
Yol Bulma (Path Finding)
İnternette path finding ile ilgili bir makale okudum, önemli birkaç konuya değiniyordu, bu yüzden ben de bu makaleyi biraz özetleyerek türkçe olarak aktarmaya karar verdim. Umarım yardımcı olur. Bu makalenin orjinalini bu adreste bulabilirsiniz.
Oyunlarda hala yol bulma ile ilgili ciddi problemler bulunmaktadır, aşağıdaki video'da çeşitli oyunlardaki çeşitli hatalar gösterilmiştir.
Video'da görüldüğü gibi, bir çok oyundaki yol bulma algoritmaları her durumda doğru sonuç vermemektedir. Ancak bu sorunların çoğu, yol bulma işleminin way-point'ler ile hesaplanmasından kaynaklanmaktadır.
(Waypoint, gezilebilinen alanları tanımlamak için konan noktalardır. Buna 'yol noktaları' diyebiliriz.)
Waypoint'ler Neden Yol Bulmak için Uygun Değildir ?
Aşağıda tipik bir waypoint örneği bulunmakta.
[World of Warcraft'daki Stormwind City]
[Waypointlerin konulmuş hali]
Gezilebilir alanları (yolları) way-pointlerle belirtebildiğimiz gibi konveks poligonlarla da ifade edebiliriz. Bu AI'a yol hakkında daha fazla bilgi ve daha düzgün karar verme olanağı verir. Bu şekildeki geometriler "navigation mesh" olarak adlandırılmıştır.
1. Bazı alanlarda, çok yüksek miktarda waypoint kullanmamız gerekebilir.
Geniş, açık alanlarda, AI'ın düzgün bir hareket yakalaması için çok fazla poligon gerekebilir.
Aşağıdaki resim, World of Warcraft'taki "Halaa" ismindeki kasabadan. NPC'lerin açık kısımlarda rahatça hareket etmesi isteniyor.
Açık alanlar için çok fazla waypoint koymamız gerekiyor. Ancak bu sayı bile yeterli değil, waypointlerimizi daha da arttırmazsak, karakterlerimiz hareket ederken zig-zaglar çizerek ilerleyecektir.
Diğer yandan, navigation mesh ile tanımlama yaparsak, çok daha az poligon kullanarak işimizi bitirmiş oluruz.
Bu sayede daha az arama yaparak, yol bulma işleminin hızını da arttırabilirisiniz.
2. Karakterler ilerlerken zig-zaglar çizerek ilerleyebilir.
Waypoint'ler belirlediğiniz zaman, karakteriniz bu waypointlerin üzerinde hareket edecektir. Bu yüzden, büyük ihtimalle seçtiğiniz herhangi iki nokta arasında, düzgün waypointler bulunmayacağından, karakteriniz zig-zaglar çizerek hareket edecektir.
Karakterimizin A'dan B'ye gittiğiniz düşünelim.
Burada da sarı ile gösterilmiş olan yol, A'dan B'ye giden en ideal waypoint'leri göstermektedir.
Bu noktalar ile daha yumuşak olarak bir eğri oluşturmayı da düşünebilirsiniz, fakat waypointler etrafındaki objelerle ilgili bir bilgi barındırmadığından, eğrinin istenmeyen bir noktadan geçip geçmeyeceğini hesaplamanız zor olabilir.
Ancak, navigation mesh kullansaydık, en doğru yolu bulmamız daha kolay olacaktı. Aşağıda ise aynı işlemin navigation mesh ile yapılmış hali bulunmakta.
Bu durumda ise, karakterlerin dolaşabileceği alanın tümünü bildiğimizden dolayı, hesapladığımız yolu istediğimiz gibi yumuşatabiliriz. Aynı şekilde, aşağıdaki resimde, kırmızı olarak işaretlenen yol waypoint kullanıldığında ortaya çıkarken, mavi ile gösterilen yol ise navigation mesh kullandığımızda oluşturuluyor. (Tabii ki mavi olan yol programcının kullandığı algoritmaya göre değişir.)
3. Waypointler kullandığımızda yolu, dinamik olarak değişen çevreye göre, değiştirmemiz daha zordur.
Eğer çevre dinamik olarak değişiyorsa ve sizin o bölgede yeterli sayıda waypointiniz yoksa, yol bulma işlemi başarısız olabilir. Aşağıdaki resimde yol üzerinde bir kutu olduğunu düşünelim. Bu durumda çok az waypoint bulunduğundan, karakter kutunun yanından düzgün bir şekilde dolaşamayacaktır.
Ancak, navigation mesh kullanırsak, çevre hakkında da bilgi sahibi olduğumuzdan, çeşitli yöntemlerle daha uygun bir yol bulabiliriz.
4. Waypoint'ler farklı hareket tipleri olan karakterler için düzgün sonuç vermez.
Genişliği, yüksekliği, dönüş şekli ve bunun gibi bir çok parametrenin değiştiği durumlarda waypoint sistemi düzgün çalışmayabilir. Örnek olarak, aşağıdaki resimde bir panzer ile bir kişinin olduğunu düşünelim. Kişi, kum torbalarının yanından kolaylıkla yürüken, bir panzer bunu yapamaz.
Kırmızı çizgi kişinin, mavi çizgi ise panzerin yolunu göstermektedir.
Waypoint'lerin düzgün çalışması için farklı waypoint grupları belirtebilirsiniz. Ancak bu işlem çok vakit isteyebilir. Bunların yanında waypointleri birleştirip panzerin nerede dolaşabileceğini hesaplayabilirsiniz ki, bu durumda waypointlerinizle bir navigation mesh oluşturmuş olursunuz.
Yukarıdaki resimde gördüğünüz gibi, gezilebilinen alanların köşeleri belirli. Bu durumda, her farklı karakteriniz için bir yarıçap belirtebilirsiniz. Örnek olarak bir kişinin yarıçapı 1m, panzerin ise 5m olarak belirlenebilir.
Aynı zamanda farklı tipte karakterler için farklı hareket stilleri belirtebilirsiniz. Örnek olarak bir motorsiklet köşeleri daha yuvarlak alırken, bir insan köşeli dönüşler yapabilir.
Yukarıdaki resimde, motorsiklet kırmızı yolu izleyebilirken, sarı yolu izleyemez.
5. Waypointler karakterlerinizin, yol bulma dışındaki işlemleri için yeterli veri barındırmaz.
Bazı zamanlarda, yol bulma için kullanılan verilerin, AI'a nasıl davranacağını veya hareket edeceğini hesaplamada yardım etmesi gerekir. Örnek olarak bir karakterin belirli bir yola değilde, bir düşmana göre yer değiştirdiğini düşünelim. Bir canavar tarafından kovalanan köylü, kendine göre bir algoritmayla kaçmaya başlayacaktır. Eğer siz waypoint kullandıysanız, karakteriniz bu waypointleri kullanarak sağa sola koşamaz veya atlayamaz. Bu durum navigation mesh ile giderilebilir. Yani her nokta için, o noktanın uygun olup olmadığını hesaplayabilirsiniz. Bu işi, fizik motorunuz da sizin yerinize yapabilir, ancak navigation mesh kullanarak daha az sistem kaynağı tüketen bir AI sistemi yazabilirsiniz.
Hala ikna olmayanlar, makalenin orjinalinde yer alan soru/cevap kısmını inceleyebilirsiniz. http://www.ai-blog.net/archives/000152.html
Oyunlarda hala yol bulma ile ilgili ciddi problemler bulunmaktadır, aşağıdaki video'da çeşitli oyunlardaki çeşitli hatalar gösterilmiştir.
Video'da görüldüğü gibi, bir çok oyundaki yol bulma algoritmaları her durumda doğru sonuç vermemektedir. Ancak bu sorunların çoğu, yol bulma işleminin way-point'ler ile hesaplanmasından kaynaklanmaktadır.
(Waypoint, gezilebilinen alanları tanımlamak için konan noktalardır. Buna 'yol noktaları' diyebiliriz.)
Waypoint'ler Neden Yol Bulmak için Uygun Değildir ?
Aşağıda tipik bir waypoint örneği bulunmakta.
[World of Warcraft'daki Stormwind City]
[Waypointlerin konulmuş hali]
Gezilebilir alanları (yolları) way-pointlerle belirtebildiğimiz gibi konveks poligonlarla da ifade edebiliriz. Bu AI'a yol hakkında daha fazla bilgi ve daha düzgün karar verme olanağı verir. Bu şekildeki geometriler "navigation mesh" olarak adlandırılmıştır.
1. Bazı alanlarda, çok yüksek miktarda waypoint kullanmamız gerekebilir.
Geniş, açık alanlarda, AI'ın düzgün bir hareket yakalaması için çok fazla poligon gerekebilir.
Aşağıdaki resim, World of Warcraft'taki "Halaa" ismindeki kasabadan. NPC'lerin açık kısımlarda rahatça hareket etmesi isteniyor.
Açık alanlar için çok fazla waypoint koymamız gerekiyor. Ancak bu sayı bile yeterli değil, waypointlerimizi daha da arttırmazsak, karakterlerimiz hareket ederken zig-zaglar çizerek ilerleyecektir.
Diğer yandan, navigation mesh ile tanımlama yaparsak, çok daha az poligon kullanarak işimizi bitirmiş oluruz.
Bu sayede daha az arama yaparak, yol bulma işleminin hızını da arttırabilirisiniz.
2. Karakterler ilerlerken zig-zaglar çizerek ilerleyebilir.
Waypoint'ler belirlediğiniz zaman, karakteriniz bu waypointlerin üzerinde hareket edecektir. Bu yüzden, büyük ihtimalle seçtiğiniz herhangi iki nokta arasında, düzgün waypointler bulunmayacağından, karakteriniz zig-zaglar çizerek hareket edecektir.
Karakterimizin A'dan B'ye gittiğiniz düşünelim.
Burada da sarı ile gösterilmiş olan yol, A'dan B'ye giden en ideal waypoint'leri göstermektedir.
Bu noktalar ile daha yumuşak olarak bir eğri oluşturmayı da düşünebilirsiniz, fakat waypointler etrafındaki objelerle ilgili bir bilgi barındırmadığından, eğrinin istenmeyen bir noktadan geçip geçmeyeceğini hesaplamanız zor olabilir.
Ancak, navigation mesh kullansaydık, en doğru yolu bulmamız daha kolay olacaktı. Aşağıda ise aynı işlemin navigation mesh ile yapılmış hali bulunmakta.
Bu durumda ise, karakterlerin dolaşabileceği alanın tümünü bildiğimizden dolayı, hesapladığımız yolu istediğimiz gibi yumuşatabiliriz. Aynı şekilde, aşağıdaki resimde, kırmızı olarak işaretlenen yol waypoint kullanıldığında ortaya çıkarken, mavi ile gösterilen yol ise navigation mesh kullandığımızda oluşturuluyor. (Tabii ki mavi olan yol programcının kullandığı algoritmaya göre değişir.)
3. Waypointler kullandığımızda yolu, dinamik olarak değişen çevreye göre, değiştirmemiz daha zordur.
Eğer çevre dinamik olarak değişiyorsa ve sizin o bölgede yeterli sayıda waypointiniz yoksa, yol bulma işlemi başarısız olabilir. Aşağıdaki resimde yol üzerinde bir kutu olduğunu düşünelim. Bu durumda çok az waypoint bulunduğundan, karakter kutunun yanından düzgün bir şekilde dolaşamayacaktır.
Ancak, navigation mesh kullanırsak, çevre hakkında da bilgi sahibi olduğumuzdan, çeşitli yöntemlerle daha uygun bir yol bulabiliriz.
4. Waypoint'ler farklı hareket tipleri olan karakterler için düzgün sonuç vermez.
Genişliği, yüksekliği, dönüş şekli ve bunun gibi bir çok parametrenin değiştiği durumlarda waypoint sistemi düzgün çalışmayabilir. Örnek olarak, aşağıdaki resimde bir panzer ile bir kişinin olduğunu düşünelim. Kişi, kum torbalarının yanından kolaylıkla yürüken, bir panzer bunu yapamaz.
Kırmızı çizgi kişinin, mavi çizgi ise panzerin yolunu göstermektedir.
Waypoint'lerin düzgün çalışması için farklı waypoint grupları belirtebilirsiniz. Ancak bu işlem çok vakit isteyebilir. Bunların yanında waypointleri birleştirip panzerin nerede dolaşabileceğini hesaplayabilirsiniz ki, bu durumda waypointlerinizle bir navigation mesh oluşturmuş olursunuz.
Yukarıdaki resimde gördüğünüz gibi, gezilebilinen alanların köşeleri belirli. Bu durumda, her farklı karakteriniz için bir yarıçap belirtebilirsiniz. Örnek olarak bir kişinin yarıçapı 1m, panzerin ise 5m olarak belirlenebilir.
Aynı zamanda farklı tipte karakterler için farklı hareket stilleri belirtebilirsiniz. Örnek olarak bir motorsiklet köşeleri daha yuvarlak alırken, bir insan köşeli dönüşler yapabilir.
Yukarıdaki resimde, motorsiklet kırmızı yolu izleyebilirken, sarı yolu izleyemez.
5. Waypointler karakterlerinizin, yol bulma dışındaki işlemleri için yeterli veri barındırmaz.
Bazı zamanlarda, yol bulma için kullanılan verilerin, AI'a nasıl davranacağını veya hareket edeceğini hesaplamada yardım etmesi gerekir. Örnek olarak bir karakterin belirli bir yola değilde, bir düşmana göre yer değiştirdiğini düşünelim. Bir canavar tarafından kovalanan köylü, kendine göre bir algoritmayla kaçmaya başlayacaktır. Eğer siz waypoint kullandıysanız, karakteriniz bu waypointleri kullanarak sağa sola koşamaz veya atlayamaz. Bu durum navigation mesh ile giderilebilir. Yani her nokta için, o noktanın uygun olup olmadığını hesaplayabilirsiniz. Bu işi, fizik motorunuz da sizin yerinize yapabilir, ancak navigation mesh kullanarak daha az sistem kaynağı tüketen bir AI sistemi yazabilirsiniz.
Hala ikna olmayanlar, makalenin orjinalinde yer alan soru/cevap kısmını inceleyebilirsiniz. http://www.ai-blog.net/archives/000152.html
Kaydol:
Kayıtlar (Atom)