A New Pathfinding Algorithm

Beberapa waktu yang lalu disebuah forum yang aku ikuti, ada seorang member baru yang posting kalau dia baru saja menemukan finding path baru.

alijaya said :
ah lega akhirnya nemuin finding path buatan sendiri.
dan kayaknya nih finding path gak musingin banget.
tapi nih masih percobaan.
kalo ada yang mau ditanyakan tanya ajah.

Ketika ditanya oleh salah seorang programmer dari Serenity Mega Media, algoritma path-finding-nya pake Djikstra, Breadth First, Depth First, ato A*, dia menjawab :

lynxluna said :
Pake apa neh? Djikstra? Breadth First? Depth First? A*?

alijaya said :
bukan semuanya.
kayaknya sih.
dan aku blom pernah baca artikelnya satu2.
kecuali A* tapi itu juga aku baca tak dimengerti.
jadi asli buatan sendiri.
selama 3 hari kalo gak salah.
tapi konsepnya udah lama sekitar 10 hari kalo gak salah.

Wooo? Benarkah dia nemuin algoritma path-finding baru? Benarkah ada algoritma path-finding baru? Source codes-nya seperti dibawah ini (memakai ActionScript 2) :

tile_1=

{	walkable:true,

frame:1};

tile_2=

{	walkable:false,

frame:2};

map1=

[	[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],

[1,1,1,2,1,1,1,1,1,2,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1],

[1,1,1,1,1,1,2,1,1,1,1,1,1,1,2,1,1,1,1,1,1,1,2,1,1],

[2,2,2,1,1,1,1,1,1,1,1,2,1,1,1,1,1,1,1,1,1,1,2,1,1],

[1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,2,1,2,1,1,1],

[1,1,1,1,1,1,1,1,2,1,1,2,1,1,1,1,1,1,1,1,1,1,1,1,1],

[1,1,1,1,1,1,2,1,1,1,2,1,2,1,1,2,1,1,1,1,1,1,1,1,1],

[1,2,2,1,1,1,1,1,1,2,1,1,2,2,1,1,1,1,1,1,1,1,1,1,1],

[1,1,1,1,2,1,1,1,1,1,1,1,1,2,1,1,1,1,2,1,1,2,1,1,1],

[1,1,1,1,1,1,2,2,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],

[1,1,1,1,1,1,1,1,2,2,1,2,1,1,2,2,1,1,1,1,1,1,1,1,1],

[1,1,1,2,1,1,2,1,1,2,2,1,1,1,1,2,1,1,2,1,1,1,1,1,1],

[1,1,1,1,2,1,1,1,1,1,2,1,1,1,1,2,1,1,1,1,1,1,1,1,1],

[1,1,2,1,2,1,1,1,1,1,2,1,1,2,1,2,2,1,1,1,1,1,1,1,1],

[1,1,2,1,2,1,1,2,1,1,1,1,1,1,1,1,2,1,1,1,1,1,1,1,1],

[1,1,1,2,1,1,1,1,1,1,1,1,1,2,1,1,1,2,1,1,1,2,1,1,1],

[1,1,1,1,1,1,1,1,1,1,1,2,1,2,1,1,1,2,1,1,1,1,1,1,1],

[1,1,1,2,2,2,2,2,2,1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1],

[1,1,1,1,1,1,1,1,1,2,1,1,1,1,2,1,1,1,1,1,1,1,1,1,1],

[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],

[1,1,1,1,1,1,1,1,1,2,2,1,1,1,1,1,1,2,1,1,1,1,1,1,1],

[1,1,1,1,1,1,2,1,1,1,1,1,2,1,1,2,1,1,1,1,2,1,1,1,1],

[1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1],

[1,1,1,1,1,1,1,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,1,1],

[1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,1,1,1,1,1,1]	]

map2=

[	[1,1,1,1,1,1,1,1,1,1],

[1,2,1,1,1,1,2,1,1,1],

[2,2,1,1,1,1,2,1,1,1],

[1,1,1,1,2,1,2,2,1,1],

[1,1,2,1,1,1,1,1,1,1],

[1,1,1,1,1,1,1,1,1,1],

[1,1,1,1,2,1,1,1,1,1],

[1,1,2,1,1,1,2,2,2,1],

[1,1,2,2,1,1,1,1,1,1],

[1,1,1,1,1,2,1,1,1,1]	]

dep=0;

game=new Object();

char=new Object();

cursor=new Object();

function buatMap(map){

_root.attachMovie("empty","penampung",100);

_root.penampung._x=0;

_root.penampung._y=0;

var panjang=map[0].length;

var lebar=map.length;

for(i=0;i

for(j=0;j

var nama="t_"+i+"_"+j;

_root.penampung.attachMovie("tile",nama,dep++);

game[nama]={dep:_root.dep , walkable:_root["tile_"+map[i][j]].walkable , frame:_root["tile_"+map[i][j]].frame};

game[nama].clip=_root.penampung[nama];

game[nama].clip.gotoAndStop(game[nama].frame);

game[nama].clip._x=j*20;

game[nama].clip._y=i*20;

}

}

_root.penampung.attachMovie("char","char",dep++);

char.clip=_root.penampung.char;

char.X=0;

char.Y=0;

char.Xtile=Math.floor(char.X/20);

char.Ytile=Math.floor(char.Y/20);

char.clip._x=char.X;

char.clip._y=char.Y;

_root.penampung.attachMovie("cursor","cursor",dep+10);

cursor.clip=_root.penampung.cursor;

cursor.Xtile=0;

cursor.Ytile=0;

cursor.X=cursor.X*20;

cursor.Y=cursor.Y*20;

cursor.clip._x=cursor.X;

cursor.clip._y=cursor.Y;

setIndex(char,map);

}

buatMap(map1);

onMouseMove = function(){

if((_xmouse+_root.penampung._x)0 && (_ymouse+_root.penampung._y)0){

cursor.Xtile=Math.floor((_xmouse+_root.penampung._x)/20);

cursor.Ytile=Math.floor((_ymouse+_root.penampung._y)/20);

cursor.X=cursor.Xtile*20;

cursor.Y=cursor.Ytile*20;

cursor.clip._x=cursor.X;

cursor.clip._y=cursor.Y;

}

}

onMouseDown = function(){

if((_xmouse+_root.penampung._x)0 && (_ymouse+_root.penampung._y)0){

if(char.index["t_"+cursor.Ytile+"_"+cursor.Xtile].shortPath!=undefined){

makePath(char,cursor.Xtile,cursor.Ytile);

goalPoint.text="("+cursor.Ytile+","+cursor.Xtile+")";

shortPath.text=char.index["t_"+cursor.Ytile+"_"+cursor.Xtile].shortPath;

maxPossible.text=char.index["t_"+cursor.Ytile+"_"+cursor.Xtile].maxPossible;

}else{

goalPoint.text="";

shortPath.text="";

maxPossible.text="";

}

}

}

function setIndex(ob,map){

ob.index=new Object();

var panjang=map[0].length;

var lebar=map.length;

for(i=0;i

for(j=0;j

var nama="t_"+i+"_"+j;

ob.index[nama]=new Object();

ob.index[nama].shortPath=undefined;

ob.index[nama].maxPossible=0;

ob.index[nama].source=new Array();

ob.index[nama].destiny=new Array();

}

}

ob.index["t_"+ob.Ytile+"_"+ob.Xtile].shortPath=0;

ob.index["t_"+ob.Ytile+"_"+ob.Xtile].maxPossible=1;

var dicari=[];

var mencari=[{Ytile:(ob.Ytile),Xtile:(ob.Xtile)}];

while(mencari.length!=0){

dicari=mencari;

mencari=[];

for(n=0;n

var nama="t_"+(dicari[n].Ytile)+"_"+(dicari[n].Xtile);

var nama_atas="t_"+(dicari[n].Ytile-1)+"_"+(dicari[n].Xtile);

var nama_bawah="t_"+(dicari[n].Ytile+1)+"_"+(dicari[n].Xtile);

var nama_kiri="t_"+(dicari[n].Ytile)+"_"+(dicari[n].Xtile-1);

var nama_kanan="t_"+(dicari[n].Ytile)+"_"+(dicari[n].Xtile+1);

if(game[nama_atas].walkable==true){

if(ob.index[nama_atas].shortPath==undefined){

ob.index[nama_atas].shortPath=ob.index[nama].shortPath+1;

ob.index[nama_atas].maxPossible+=ob.index[nama].maxPossible;

ob.index[nama].destiny.push({Ytile:(dicari[n].Ytile-1),Xtile:(dicari[n].Xtile)});

ob.index[nama_atas].source.push({Ytile:(dicari[n].Ytile),Xtile:(dicari[n].Xtile)});

mencari.push({Ytile:(dicari[n].Ytile-1),Xtile:(dicari[n].Xtile)});

} else if(ob.index[nama_atas].shortPath==ob.index[nama].shortPath+1){

ob.index[nama_atas].maxPossible+=ob.index[nama].maxPossible;

ob.index[nama].destiny.push({Ytile:(dicari[n].Ytile-1),Xtile:(dicari[n].Xtile)});

ob.index[nama_atas].source.push({Ytile:(dicari[n].Ytile),Xtile:(dicari[n].Xtile)});

}

}

if(game[nama_bawah].walkable==true){

if(ob.index[nama_bawah].shortPath==undefined){

ob.index[nama_bawah].shortPath=ob.index[nama].shortPath+1;

ob.index[nama_bawah].maxPossible+=ob.index[nama].maxPossible;

ob.index[nama].destiny.push({Ytile:(dicari[n].Ytile+1),Xtile:(dicari[n].Xtile)});

ob.index[nama_bawah].source.push({Ytile:(dicari[n].Ytile),Xtile:(dicari[n].Xtile)});

mencari.push({Ytile:(dicari[n].Ytile+1),Xtile:(dicari[n].Xtile)});

}else if(ob.index[nama_bawah].shortPath==ob.index[nama].shortPath+1){

ob.index[nama_bawah].maxPossible+=ob.index[nama].maxPossible;

ob.index[nama].destiny.push({Ytile:(dicari[n].Ytile+1),Xtile:(dicari[n].Xtile)});

ob.index[nama_bawah].source.push({Ytile:(dicari[n].Ytile),Xtile:(dicari[n].Xtile)});

}

}

if(game[nama_kiri].walkable==true){

if(ob.index[nama_kiri].shortPath==undefined){

ob.index[nama_kiri].shortPath=ob.index[nama].shortPath+1;

ob.index[nama_kiri].maxPossible+=ob.index[nama].maxPossible;

ob.index[nama].destiny.push({Ytile:(dicari[n].Ytile),Xtile:(dicari[n].Xtile-1)});

ob.index[nama_kiri].source.push({Ytile:(dicari[n].Ytile),Xtile:(dicari[n].Xtile)});

mencari.push({Ytile:(dicari[n].Ytile),Xtile:(dicari[n].Xtile-1)});

}else if(ob.index[nama_kiri].shortPath==ob.index[nama].shortPath+1){

ob.index[nama_kiri].maxPossible+=ob.index[nama].maxPossible;

ob.index[nama].destiny.push({Ytile:(dicari[n].Ytile),Xtile:(dicari[n].Xtile-1)});

ob.index[nama_kiri].source.push({Ytile:(dicari[n].Ytile),Xtile:(dicari[n].Xtile)});

}

}

if(game[nama_kanan].walkable==true){

if(ob.index[nama_kanan].shortPath==undefined){

ob.index[nama_kanan].shortPath=ob.index[nama].shortPath+1;

ob.index[nama_kanan].maxPossible+=ob.index[nama].maxPossible;

ob.index[nama].destiny.push({Ytile:(dicari[n].Ytile),Xtile:(dicari[n].Xtile+1)});

ob.index[nama_kanan].source.push({Ytile:(dicari[n].Ytile),Xtile:(dicari[n].Xtile)});

mencari.push({Ytile:(dicari[n].Ytile),Xtile:(dicari[n].Xtile+1)});

}else if(ob.index[nama_kanan].shortPath==ob.index[nama].shortPath+1){

ob.index[nama_kanan].maxPossible+=ob.index[nama].maxPossible;

ob.index[nama].destiny.push({Ytile:(dicari[n].Ytile),Xtile:(dicari[n].Xtile+1)});

ob.index[nama_kanan].source.push({Ytile:(dicari[n].Ytile),Xtile:(dicari[n].Xtile)});

}

}

}

}

}
function makePath(ob,Xgoal,Ygoal){

var nama_goal="t_"+Ygoal+"_"+Xgoal;

ob.path=[{Ytile:Ygoal,Xtile:Xgoal}];

while(ob.path.length

var nama_akhir="t_"+(ob.path[ob.path.length-1].Ytile)+"_"+(ob.path[ob.path.length-1].Xtile);

ob.path.push(ob.index[nama_akhir].source[random(ob.index[nama_akhir].source.length)]);

}

var pathCad=new Array();

for(n=0;n

pathCad[n]=ob.path[ob.path.length-n-1];

}

ob.path=pathCad;

makeArea(ob);

}

function makeArea(ob){

_root.penampung.attachMovie("goal","goal",(ob.clip.getDepth()+1));

_root.penampung.goal._x=ob.path[ob.path.length-1].Xtile*20;

_root.penampung.goal._y=ob.path[ob.path.length-1].Ytile*20;

_root.penampung.attachMovie("empty","path",(ob.clip.getDepth()+2));

var dep=0;

for(n=0;n

var Ytile=ob.path[n].Ytile;

var Xtile=ob.path[n].Xtile;

var nama="a_"+Ytile+"_"+Xtile;

_root.penampung.path.attachMovie("area",nama,dep++);

_root.penampung.path[nama]._y=Ytile*20;

_root.penampung.path[nama]._x=Xtile*20;

}

}

function traceArrayObject(array){

var tulisan=new String();

tulisan+="[";

for(n=0;n

tulisan+="[{Xtile:"+array[n].Xtile+",Ytile:"+array[n].Ytile+"}]";

}

tulisan+="]";

trace (tulisan);

};

Dan langkah-langkahna menurut penjelasannya seperti ini :

7.nah dari tempet yang kita cari kasih panah ke semua arah yang ada garisnya & bukan garis yang nunjuk ke arah tile yang diperiksa deket tepi garis tile dan tile yang ditunjuk dikasih penomoran 1 lebihnya dari tile yang diperiksa sekarang.(artinya menunjuk ke tempet yang diperiksa berikutnya)

8.ngerjanya harus berurutan jadi misalnya kita ngecek yang
mempunyai nomor 8 gak boleh tengah2 kita langsung ngecek yang nomor 9. jadi harus selese semuanya yang nomor 8 baru ngelanjutin ke nomor selanjutnya.

9.lakukan terus sampe habis.(gak ada yang bisa dinomori lagi)

10.nah untuk mencari path nya:
-tunjuk salah satu tilenya
-nah dari tile tersebut liat yang ada panah yang nunjuk ke tile itu
-nah jadi sekarang liat tempet yang nunjukin panah itu.
-nah ulangi lagi ngeliatin panah yang nunjukin tile yang sekarang kita liat.
-trus sampe ketemu start kita.

Yang bikin menarik, menurut Wandah Wibawanto, seorang developer Flash Games yang tinggal di Dubai, United Arab Emirates, source codes diatas ternyata mirip sekali dengan source codes pathfinding dari salah seorang Master Flash bernama Tonypa dan Earl Vergara. Source codes-nya 90% sangat mirip dengan source codes Tonypa, membuat semua orang meragukan kalau itu source codes buatan dia sendiri.

Sedang beberapa member lain bilang, dari langkah-langkahnya, itu juga bukan algoritma baru. Kemungkinan besar Breadth-first Search Algorithm.

lynxluna said :
Wyehehe… tapi dari sourcenya koq bau2 breadth first yaks.. apa cuma perasaan sayah ajah.

Kiki said :
Sound pretty much like Breadth First Search to me ( a pretty nonoptimal algorithm for pathfinding)

Kemudian setelah Wandah menanyakan kepada Earl Vergara, ternyata Master Flash itu bilang itu bukan script Tonypa, mirip tapi bukan.

Lalu bagaimana dengan algoritma-nya? Benarkah itu algoritma baru? Untuk membuktikannya, hanya perlu dibuat graph-nya dan dibandingin dengan graph algoritma yang sudah ada. Karena penasaran, aku mencobanya. Contoh kasus yang aku pakai :

Kemudia graph-nya seperti ini :

Kemudian, karena aku belibet nerjemahin langkah-langkah path-finding-nya, graph penemuan node yang kudapat malah jadi seperti ini :

Dan itu cukup membingungkanku, karena ketika dibuat tree, graph-nya beda sekali dengan algoritma path-finding yang sudah ada… Jadi aku agak gak yakin aku bener nerapin path-finding nya. Ternyata setelah dikonfirm dengan pemilik source codes-nya, graph-nya yang bener seperti ini :

Kalau seperti itu, udah jelas algoritma yang dipakai adalah Breadth-first Untuk lebih membuktikannya, dibuat tree-nya, hasilnya dibandingkan dengan algoritma Breadth-first Search :

Langkahnya sama persis Kesimpulannya, menurut FX Yanuar Tanzil, pemilik dari IPlayAllDay Studio :

yanuart said :
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.

Sebuah kasus analisis algoritma yang menarik… Dan yang bikin lebih mengejutkan, ternyata yang menulis source codes tersebut masih kelas 2 SMP! Wow… Masa depan Indonesia ternyata lumayan cerah juga dengan banyaknya anak-anak berbakat…

Walo masih terlalu cepat untuk bilang menemukan algoritma path-finding baru…