[realtime]

makasih buat mas admin yang udah PM saya
dan maaf buat wandah, karena udah tak marahin
terlepas dari semua itu semua udah berakhir

ini adalah hasil test saya terhadap algo index

TEST PERTAMA
test standard untuk path finding
algoritma index ternyata mampu menghasilkan lebih dari satu jalur penyelesaian, dan hasilnya selalu optimal


TEST KEDUA
test tentang indexnya, saya mengetes apakah akan terjadi konflik
apabila jalur pengindexannya di pecah dan menempuh jarak yang berbeda
hasilnya ternyata indexnya berhasil mulus dan lagi-lagi
jalur yang dihasilkan adalah jalur terpendek


TEST KETIGA
test apakah algo ini bisa dioptimisasi
saya mencoba melakukan double indexing dari awal dan dari akhir
dengan mengalikan index dari awal dengan angka 2
hasilnya ternyata sama, dan ternyata algo ini belum bisa saya optimasi


TEST KEEMPAT
saya mencoba apakah bisa dikembangkan ke diagonal
dan ternyata bisa, dan tidak terjadi konflik dalam pengindekannya


TEST KELIMA
saya mencoba apakah algo ini bisa memecahkan masalah yang tidak bisa diatasi oleh algo yang lain

soal:
saya sedang mengkonsep sebuah game, dimana pemain harus menemukan jalan terpendek dari dua tempat, namun dalam game ini pemain boleh menggunakan alat-alat tertentu seperti
transport warp untuk berpindah cepat dari tempat satu
ke tempat yang lain
dengan menggunakan algo pathfind yang saya ketahui
jalan tercepat untuk mencapai target adalah garis lurus, namun
dalam persoalan ini hal itu adalah salah
perhatikan gambar berikut
dari gambar berikut terlihat bahwa dengan menggunakan algo indexing
hasil yang dicapai adalah optimal.
pemain akan lebih cepat sampai di tempat tujuan bila menggunakan warp
sedangkan A*Path finding akan menyimpulkan jalan tercepat untuk
mencapai tujuan adalah garis lurus
dengan warp dekat dengan start maka A*path find menang
tapi dengan warp berada jauh dari start maka algo index yang menang
garis biru adalah hasil dari A*path find
garis hijau adalah algo index



kesimpulan
- algo index menghasilkan lebih dari satu jalur penyelesaian
- jalur tercepat untuk mencapai tujuan bukan garis lurus
- algo index tidak menggunakan heuristic
- algo index tidak menggunakan konsep jarak
- mirip dengan algo flood fill, hanya beda fungsi

berdasarkan konsep bahwa jarak berbanding terbalik dengan waktu
bahwa jarak yang pendek membutuhkan waktu terlama dan waktu terpendek menghasilkan jarak terboros
maka algo index termasuk algo yang memakan waktu terlama dan jarak yang optimal

pertanyaan yang belum bisa dijawab.
apakah algo ini bisa dibilang baru?
apa yang menyebabkan sebuah algo dibilang baru?
apakah perbedaan algo-algo yang sudah ada sehingga bisa membuat mereka dikatakan berbeda?

demikian analisa saya
tolong test kelima saya dikomentari, apakah ada algo yang bisa lebih cepat dari hal itu. ini yang paling penting.
terima kasih
Q.E.D

[gus]

algorithm flood fill ini PASTI menghasilkan optimal path. karena sifat-nya yang bisa dibilang brute force (eg: mencoba semua kemungkinan).

bagi yang hobby recursive, algorithm ini bisa2 terpikir karena menggunakan teknik recursive dasar sekali untuk memecahkan masalah path finding buat grid based map. jadi bisa juga si ali menemukan sendiri dan nggak tau kalo emang sudah ada .

cuman bedanya implementasi ali kalo liat dari penjelasannya (males baca script-nya ) recursive-nya diimplement pake stack dengan manfaatin cell array map-nya untuk menyimpan stack entry-nya.

tapi, salut buat ali. anak SMP jarang2 yg udah ngerti sampe sini

[eins]

1.oh ngerti jadi kalo emang misalnya kita menemukan sesuatu terus ternyata udah ada orang yang menemukan duluan meskipun kita tidak tau menahu tentang penemuan orang itu tetap tidak bisa dianggap penemu kan.
2.kalo ternyata punya ali ini tidak dipublishkan dan ternyata ada orang luar yang menemukan sama/mirip dengan punya ali. dan orang luar terebut mempublishnya berarti dianggap penemuan orang tersebut atau tidak?
3.ada kemungkinan gak kalo ali bener bener 100%nemuin algo ini, atau 70 % logika sendiri dan 30 % dari luar?apa mesti ngerti algo sebelumnya buat menemukan suatu algo baru. bagaimana dengan penemuan algo yang pertama kali ditemukan?
maaf nanya soalnya masih bingung sih..(gw sendiri gak ngerti algo sih karena itu bertanya he he)

[pe-e-be]

yo.. ternyata peer-reviewnya udah jauh ya.. sampe om gus bersedia datang.. ckckck..

jadi akhirnya ini algoritma breadth-first search, salut juga gw.. gw sma klas 2 aja nggak ngeh sama BFS sampe-sampe diterangin sama yang udah kuliah di ilkom ui tetep nggak mudeng..

secara alamiahnya di kepala gw itu dfs brute force, haha.. jadi nostalgia sma..

@realtime:algoritma brute-force milik ali tidak bisa dibandingkan dengan informed search(heuristic) seperti A*. karena ada kemungkinan desisi pemilihan node lanjut lebih dikendalikan oleh fungsi heuristik (h()) dibandingkan fungsi biaya (g()).

algoritma yang diimplementasi ali ini prinsipnya adalah BFS yang IMO kurang efisien, yang berbeda adalah ali menerapkan prinsip node-index caching (precomputed index) yang akan lebih efisien jika titik awalnya dan konfigurasi peta statis (tidak banyak berubah).

kelemahan algoritma ali adalah ketika petanya bersifat dinamis (musuh berubah, objek bisa hancur, dan posisi awalnya berubah-ubah) maka proses indexing akan dihitung ulang (proses indexing ini seperti floodfill tapi yang diisikan jaraknya dari titik awal).

[CizCuz]

@alijaya : thanks udah bikin thread yg seru cukup menarik tuh akhirnya keluar banyak penjelasan berbagai macam AI gara2 thread kamu, sayang ada yg bikin illfeel ditengah2. Kalau emang bener itu semua murni hasil pikiran lo, salut deh.. kecil2 dah jago AI serem dah gede jadi apa tuh.

@realtime : thanks uda bikin gw illfeel ama thread ini.... sering2 ya biar kena infraction yg banyak . Sorry kalo gw sewot banget, soalnya post lo bener2 keterlaluan gak pandang bulu ngata2in semua member yg aktif di thread ini (padahal gw tau banget member2 yg reply di thread ini adalah orang2 yg kritis & open minded, dan enggak sepicik yg loe bayangin). Pake bawa2 flash programmer vs C segala, pake bawa2 umur segala ssshh... stresss ah..

[yanuart]

napa om cuz.. streesss ya sadar kalo dah berumurr hehehe?
ikutan nimbrung deh, dari skimming pertama kali algonya sih dah rada keliat kalo ini brute force dengan precompute nodes.

Sayang kurang ada penjelasan di struktur data node(index)nya jadi rada malas baca codenya hehe. Asik2 aja kok ..

Either way, kalo masalah siapa yg nemuin, yah kalo di jaman skrg sih mungkin rada naif kalau mengira bisa menemukan sesuatu yang baru (bukan berarti tidak mungkin loh). Alasannya sih, yah orang2 sono dah buaaaannyyyyaaaakk bikin riset dan sudah dariii duullluuuu kala, whitepaper tentang ginian itu sebejibuunnn kalo mau cari.

Lagipula, mungkin lebih arif kalau membuat sesuatu tapi tidak mengaku-ngaku siapa yang membuat, code bisa dicopyright n patenkan tapi algorithm setahu gua gak bisa. Kalau memang karya kita bagus dan bermanfaat, dunia pasti mengakui.. Coba liat thread sebelah tentang fast inverse square root, saking kagumnya programmer2 ama sepotong code itu sampai dibela2in diselidiki siapa yang bikin. Dan kalo kamu perhatikan, bahkan nama2 besar di dunia game programming pun ga ada yang mau ngakui dan saling lempar sampai akhirnya ketemu beneran siapa yang bikin.

Gimanapun juga Newton pun omong : I can see far cause im standing on the shoulder of a giant

Kita semuapun bisa programming krn begitu kan ?

[exavolt]

Originally Posted by pe-e-be

algoritma yang diimplementasi ali ini prinsipnya adalah BFS yang IMO kurang efisien, yang berbeda adalah ali menerapkan prinsip node-index caching (precomputed index) yang akan lebih efisien jika titik awalnya dan konfigurasi peta statis (tidak banyak berubah).

hehehe. thanks pe-e-be. jd dpt ide.

[pe-e-be]

vote new title "boy genius" for alijaya!!

[ace]

the boy wonder.... kayak robin

eh robin sih daggio

[einz]

Originally Posted by pe-e-be

vote new title "boy genius" for alijaya!!

sama kayak yang kupikirin 2 hari yang lalu bedanya yang kupikirin malah kebalikannya"genius boy" he he