Friday, 13 September 2013

Pathfinding, agar tidak Kesasar


Ada banyak algoritma untuk pencarian jalur tercepat. Pencarian jalus alias Pathfinding bukan hanya sekedar mencari jalur tercepat tapi juga jalur yang dapat dilalui. Jika kita hanya berdasarkan pengecekkan biasa seperti jika koordinat X kotak A, lebih kecil dari koordinat X kotak B maka koordinat X kotak A, akan ditambah untuk mencapai target tujuan. Permasalahannya muncul jika ada sebuah penghalang seperti tembok, maka kotak A tidak akan pernah mencapai kotak B, kecuali ada yang ngangkut .

Karena saya juga dalam tahap belajar sehingga masih perlu belajar untuk struktur data pada pemetaan Node. Sejauh ini saya cukup menggunakan beberapa tipe data bentukan seperti berikut:

//Koordinat struct Koor { int X,Y; }; //Node atau Tile struct Node { int tekstur; int biaya; bool Bebas; }; struktur Koor untuk menyimpan koordinat (X,Y) , untuk keperluan jalur yang harus dilalui, misal dari A ke B, melalui koordinat (0,1), (0,2), (1,2), dst. Jika ditambah dengan kombinasi std::vector<Koor> myTrack dijamin rekaman untuk jalur yang harus dilalui makin sip! . Sedangkan Node untuk membuat peta, tekstur merupakan informasi warna atau gambar yang akan ditampilkan dan juga sebagai penanda apakah path ini adalah penghalang (contoh tembok) atau bukan, biaya adalah berapa banyak biaya untuk mencapai Node atau titik tersebut. Sedangkan variabel bebas sebagai penanda apakah Node (simpul) ini sudah diperiksa atau belum, ini berguna pada Algoritma yang akan digunakan nanti.


Ubin-ubin yang ditandai

Bisa dilihat pada gambar diatas (gambarnya ada kan? ) . Pada gambar diatas, kotak A dimulai dengan koordinat (0,0) atau pojok kiri atas menuju target, yaitu kotak B pada koordinat paling kanan bawah (yah pokoknya diujung kanan ) . Secara default kita beri biaya 9999 atau lebih yang dipenting diisi dengan nilai-nilai yang tidak bisa dilalui sebagai inisialiasi awal. Selanjutnya kita periksa setiap node dengan memberi nilai atau biaya yang diperlukan dari node tersebut ke kotak A (node start) dengan syarat node tersebut dapat dilalui lalu tandai bahwa node tersebut sudah diperiksa. Proses terus berlanjut sampai tidak ditemukan jalur yang bisa dilalui. Jika memang jalur target dapat dilalui, kita mulai menyimpan koordinat-koordinat yang diperlukan pada variabel tertentu, contoh variabel Track.

Berikut ini contoh aplikasi Pathfinding yang sudah saya kembangkan (binary only)
Link : http://www.mediafire.com/download/4j4rp4wc19vao8p/SDL_Map_PathFinding_DFS_04.7z (Size 600KB)
Intruksi penggunaan :
  • Tombol AWSD untuk mengerakkan kamera.
  • Tombol T agar kamera mengikuti kotak.
  • Tombol Panah Atas untuk menambahkan kotak yang mengikuti.
  • Tombol M untuk mengacak Map.
  • Tombol Escape atau klik Close Button untuk keluar dari program.

- Krofz

1 comment:

Maaf jika komentar anda lama terbitnya ^__^, penulis berusaha OL sesering mungkin. Komentar anda adalah semangat blog ini, dan juga semangat para blogger lainnya. You can use XHTML tags: <a href="" rel="link"> </a>, <strong> </strong>, <b> </b>, <em> </em>, <i> </i>.

Spesial character use :
&lt; for <
&gt; for >


Use Pastebin.com for alternative to display your code :) .

 

back to top

back to top