So basically this was going to be something of a surprise. I've been working on this script since January, not constantly just occasionally. It works - kinda... The script runs fine if I don't include the heuristic... But when I do it stops about half way through ama_dun01. I think without the heuristic It takes approximately 3 minutes to complete ama_dun01.
Why am I posting this here? Well simply put I don't have enough time to work on it at the moment, and it's just going to disappear forever if I don't.
So what I'm asking is for anyone to optimize this and maybe help me figure out why it's stopping with the heuristic value.
Before anyone says it, if they even do. Yeah it would be faster on Hercules because of unlimited arrays and ++.@r but that's obvious. I want this to work on rAthena .
I'll try to update this topic when I get some more time. ( I've got a few other projects to finish first. )
Thanks in advance any input on this is appreciated.
( There are a few bits I left out because they were mainly for debug/or were part of the main event which I felt wasn't developed enough. )
Question
Skorm
So basically this was going to be something of a surprise. I've been working on this script since January, not constantly just occasionally. It works - kinda... The script runs fine if I don't include the heuristic... But when I do it stops about half way through ama_dun01. I think without the heuristic It takes approximately 3 minutes to complete ama_dun01.
Why am I posting this here? Well simply put I don't have enough time to work on it at the moment, and it's just going to disappear forever if I don't.
So what I'm asking is for anyone to optimize this and maybe help me figure out why it's stopping with the heuristic value.
Before anyone says it, if they even do. Yeah it would be faster on Hercules because of unlimited arrays and ++.@r but that's obvious. I want this to work on rAthena
.
I'll try to update this topic when I get some more time. ( I've got a few other projects to finish first. )
Thanks in advance any input on this is appreciated.
( There are a few bits I left out because they were mainly for debug/or were part of the main event which I felt wasn't developed enough. )
//Diagonal = 14 //} G //Adjacent = 10 //} G function script abs { //.@v = getarg(0); //.@mask = .@v >> 4 * 8 - 1; //return ((.@v + .@mask) ^ .@mask); .@i = getarg(0); return ( (.@i < 0) ? -.@i : .@i ); } function script max { .@i = ((getarg(0) > getarg(1)) ? getarg(0) : getarg(1)); return .@i; //return getarg(0) ^ ((getarg(0) ^ getarg(1)) & -(getarg(0) < getarg(1))); } ama_dun01,233,9,3 script npc_go 100,{ OnGo: setarray .@dx, 1, 1, 0, -1, -1, -1, 0, 1; setarray .@dy, 0, 1, 1, 1, 0, -1, -1, -1; .@x = 233; //Start Pos .@y = 11; //Start Pos .@s_x = 233; //Start Pos .@s_y = 11; //Start Pos .@len = getarraysize(.@dx); .@e_x = .e_x; //End Pos .@e_y = .e_y; //End Pos .@map_size = 240*240; .@g = 0; dispbottom .@x+"!="+.@e_x+"&&"+.@y+"!="+.@e_y+"||"+.@q+"<"+.@map_size; debugmes "-------------Starting---------------"; set(.@time,gettimetick(0)); freeloop(1); setarray getd(".@node_x"+.@x+"y"+.@y+"c"), 1, .@x, .@y; .@v = 1; .@ar[getarraysize(.@ar)] = .@v; while( .@q<.@map_size ) { LOOP4: set(.@x2,.@x+.@dx[.@a]); set(.@y2,.@y+.@dy[.@a]); .@mes$ = .@x2+" "+.@y2+" "+.@v+" "+.@a+"|"+.@x+" "+.@y; set(.@tmp5$,".@node_x"+.@x2+"y"+.@y2); //----------------------------------------------------> (".@node_x"+.@x2+"y"+.@y2) Temp string. copyarray .@tc_ary, getd(.@tmp5$+"c"), 6; //-------------------------------------------------> .@tc_ary = "Testing closed-list array(node)". if( !.@tc_ary ) { //.@a++; .@q++; continue; } //---------------------------------------------> Challenge closed node. if(checkcell("ama_dun01",.@x2,.@y2,cell_chkwall) || checkcell("ama_dun01",.@x2,.@y2,cell_chkcliff) || checkcell("ama_dun01",.@x2,.@y2,cell_chkwater) || checkcell("ama_dun01",.@x2,.@y2,cell_chknopass) || checkcell("ama_dun01",.@x2,.@y2,cell_chknoreach)) { //---------------------------------> Challenge turf walk-able. .@mes$ = .@mes$+" Not valid turf!"; } else { set .@a$, .@tmp5$+"o"; //-------------------------------------------------------------> (".@node_x"+.@x2+"y"+.@y2+"o") Open-list node. copyarray .@to_ary, getd(.@a$), 6; //-------------------------------------------------> .@to_ary = "Testing open-list array(node)". set(.@m,!.@dx[.@a]||!.@dy[.@a]?10:14); //---------------------------------------------> Challenge diagonal. //dispbottom "Parent G: "+getd(".@node_x"+.@to_ary[1]+"y"+.@to_ary[2]+"c[0]"); //if(.@to_ary) { set(.@g,getd(".@node_x"+.@to_ary[1]+"y"+.@to_ary[2]+"c[0]")+.@m); } /*else {*/ if( .@to_ary ) { //-------------------------------------------------------------------> Testing open node. "True: Test if better parent to current closed node." set .@tmp$, ".@node_x"+.@x+"y"+.@y; //---------------------------------------------> (".@node_x"+.@x+"y"+.@y) Temp string. copyarray .@cc_ary, getd(.@tmp$+"c[0]"), 6; //-------------------------------------> .@cc_ary = "Current closed array". (Parent to testing nodes.) .@mes$ = .@mes$+" On open list... Testing!"; if( (.@cc_ary[0] + .@m ) < .@to_ary[0] ) { //--------------------------------------> Challenge current node g plus distance to parent less than testing node g. //dispbottom "New Parent: "+.@x2+", "+.@y2; .@mes$ = .@mes$+" shorter route!"; setarray getd(.@tmp$+"c[0]"), //-----------------------------------------------> (".@node_x"+.@x+"y"+.@y+"c[0]") (.@cc_ary[0] + .@m ), .@x2, .@y2, //----------------------------------------> new g, new parent >Recalculate current closed node. ((.@cc_ary[0] + .@m ) + getd(".h_x"+.@x+"_y"+.@y)); //-----------------------> g + heuristic = new heuristic. killmonster "ama_dun01",strnpcinfo(0)+"::On"+.@x2+"-"+.@y2; monster "ama_dun01",.@x2,.@y2,"New Parent",1936,1,strnpcinfo(0)+"::On"+.@x2+"-"+.@y2; killmonster "ama_dun01",strnpcinfo(0)+"::On"+.@x+"-"+.@y; monster "ama_dun01",.@x,.@y,"New Child",1935,1,strnpcinfo(0)+"::On"+.@x+"-"+.@y; copyarray getd(".@node_x"+.@x2+"y"+.@y2+"c[0]"), .@to_ary[0], 6; //------------> Move testing open-list node to closed-list node. } else { .@mes$ = .@mes$+" Not shorter!"; } } else { //---------------------------------------------------------------------------> Testing open node. "False: Add it to the open-list!" .@mes$ = .@mes$+" Not on the open list... Adding!"; set .@g, getd(".@node_x"+.@x+"y"+.@y+"c[0]")+.@m; //-------------------------------> Testing open node g equals current closed node g plus distance to testing open node g. .@f = .@g + getd(".h_x"+.@x2+"_y"+.@y2); //----------------------------------------> Testing open node f equals g plus heuristic. setarray getd(.@a$), .@g, .@x, .@y, .@f, .@x2, .@y2; //----------------------------> Set testing open list node values. //dispbottom "Adding: "+ .@g+", "+.@x+", "+.@y+", "+.@f+", "+.@x2+", "+.@y2; monster "ama_dun01",.@x2,.@y2,"Added",1934,1,strnpcinfo(0)+"::On"+.@x2+"-"+.@y2; //if( getarraysize(getd("@open_list"+.@v+"$")) >= 32 ) //----------------------------> Is current operating open-list greater than or equal to thirty-two? // .@ar[getarraysize(.@ar)] = .@v++; //-------------------------------------------> Not enough room for child/parent store value in a new open-list. if( getarraysize(getd("@open_list"+.@v+"$")) >= 32 ) { while( getarraysize(getd("@open_list"+.@v+"$")) ) .@v++; .@ar[getarraysize(.@ar)] = .@v; } //debugmes "Adding: ("+.@f+"|"+.@x2+"|"+.@y2+") to @open_list"+.@v+"$ Len: "+getarraysize(getd("@open_list"+.@v+"$")); .@loops = callfunc("AddHeap", (.@f+"|"+.@x2+"|"+.@y2), getd("@open_list"+.@v+"$")); //--------> Adding open node to the heap/open-list. } } } else { .@mes$ = .@mes$+" On Closed List!"; } dispbottom .@mes$; if( .@v == 737/* && .@a == 7*/ ) end; .@a++; jump_zero ( .@a >= .@len ), LOOP4; //.@u = .@cu = .@w_temp = 0; .@u = 0; //-------------------------------------------------------------------------------------------> Current open-list. .@cu = 0; //-------------------------------------------------------------------------------------------> Challenged open-list. .@w_temp = 0; //----------------------------------------------------------------------------------------> Smallest f value. .@v_len2 = .@v_len; .@v_len = getarraysize(.@ar); //-------------------------------------------------------------------------> Size of condensed open-lists. if(.@v_len2 < (.@v_len-1)) { debugmes .@v+"Dropped Value! "+.@v_len2+"<"+(.@v_len-1); } while( .@u<.@v_len //---------------------------------------------------------------------------------> While testing list within open list range /*|| !.@v_len //------------------------------------------------------------------------------------> or open-list doesn't exist >Find shortest open-list f. ( Might not need last parts double check. ) && .@u<=.@v_len*/ ) { //----------------------------------------------------------------------------> and testing list less than length lists. .@cu = .@ar[.@u]; .@len2 = getarraysize(getd("@open_list"+.@cu+"$")); .@tmp = atoi(getd("@open_list"+.@cu+"$")); debugmes .@u+" OpenList Array "+.@ar[.@u]; if( .@tmp<.@w_temp || !.@w_temp ) { .@w_temp = .@tmp; .@w_len = .@len2; .@w_ptr = .@u; .@w = .@cu; } //dispbottom "Len: "+.@len2+" "+getarraysize(getd("@open_list"+.@u+"$"))+"| Temp: "+.@tmp+"| .@w: "+.@w+"| .@u: "+.@u; .@u++; } //dispbottom "Before: "+getarraysize(getd("@open_list"+.@w+"$")); explode .@array$, getd("@open_list"+.@w+"$"), "|"; copyarray .@temp[0], getd(".@node_x"+.@array$[1]+"y"+.@array$[2]+"o[0]"), 6; //if(!(.@w_len-1)) { dispbottom "Deleteing: "+.@ar[.@w_ptr]+" | Array Size: "+getarraysize(getd("@open_list"+.@w+"$"))+" | Array: "+getd("@open_list"+.@ar[.@w_ptr]+"$"); } callfunc "DelHeap", 0, getd("@open_list"+.@w+"$"), .@w_len; if( .@w_len==1 ) { deletearray .@ar[.@w_ptr],1; } if( !getd(".@node_x"+.@array$[1]+"y"+.@array$[2]+"c[0]") ) { if(.@temp) { viewpoint 2, .@x, .@y, /*(*/.@q/*+.@a)*/, 0xFF0000; .@x = .@temp[4]; .@y = .@temp[5]; copyarray getd(".@node_x"+.@x+"y"+.@y+"c[0]"), .@temp, 6; deletearray getd(".@node_x"+.@x+"y"+.@y+"o"); setarray .@temp, 0, 0, 0, 0, 0, 0; ////monster "ama_dun01",.@x,.@y,"Using",1934,1; } } set(.@a,0); if(.@x==.@e_x&&.@y==.@e_y) { dispbottom "We did it"; break; } //We've reached the end. //if(.@x==.@l_x&&.@y==.@l_y) { dispbottom "Can't be solved!"; end; } //This puzzle can't be solved. .@l_x = .@x; .@l_y = .@y; .@q++; if(.stop) end; if(!(.@q%1000)/*.@v2 != .@v*/ ) { .@v2 = .@v; //viewpoint 1, .@x, .@y, /*(*/.@q/*+.@a)*/, 0xFF0000; //dispbottom "Still Working: .@q="+.@q+" | @open_list"+.@v+"$ Len="+getarraysize(getd("@open_list"+.@v+"$"))+" | .@ar Size: "+getarraysize(.@ar)+" | Cords: "+.@x+", "+.@y; sleep2(1); } if( getarraysize(getd("@open_list"+.@v+"$")) > 32 ) end; //dispbottom "Still Working: .@q="+.@q+" | @open_list"+.@v+"$ Len="+getarraysize(getd("@open_list"+.@v+"$"))+" | .@ar Size: "+getarraysize(.@ar)+" | Cords: "+.@x+", "+.@y; } LOOP3: .@x2 = getd(".@node_x"+.@x+"y"+.@y+"c[1]"); .@y2 = getd(".@node_x"+.@x+"y"+.@y+"c[2]"); monster "ama_dun01",.@x2,.@y2,"Path",1934,1; viewpoint 1, .@x, .@y, .@ii++, 0x00FF00; if(.@p_len>=128) { .@j++; .@p_len=0; } setd ".@p_l"+.@j+"$["+.@p_len+"]", .@x2+"|"+.@y2; .@p_len++; .@x = .@x2; .@y = .@y2; if( .@x == .@s_x && .@y == .@s_y ) GOTO L_1; if( !.@x && !.@y ) end; GOTO LOOP3; L_1: while(.@t<=.@j/*getarraysize(getd(".@p_l"+.@t+"$"))*/) { if(.@t<.@j) { .@len=64; .@i_len=128; } else { .@i_len = getarraysize(getd(".@p_l"+.@t+"$")); .@len =.@i_len/2; } for(.@y = 0; .@y < .@len; .@y++) { .@temp$ = getd(".@p_l"+.@t+"$["+.@y+"]"); setd(".@p_l"+.@t+"$["+.@y+"]",getd(".@p_l"+.@t+"$["+(.@i_len-.@y-1)+"]")); setd(".@p_l"+.@t+"$["+(.@i_len-.@y-1)+"]",.@temp$); } .@t++; } dispbottom "This process took: "+(gettimetick(0)-.@time)+" ms"; Clear: while(.@cu<=.@v) { deletearray getd("@open_list"+.@cu+"$"); .@cu++; } if(.@clear){ dispbottom "Cache Cleared"; end; } .@gid = bg_monster(.@a,"ama_dun01",233,8,"--ja--",3999,strnpcinfo(0)+"::OnDeadMob"); getmapxy(.@map$,.@m_x,.@m_y,3,""+.@gid); sleep2(100); set(.@z,.@t-1); while(getarraysize(getd(".@p_l"+.@z+"$"))) { while(.@k<getarraysize(getd(".@p_l"+.@z+"$"))) { explode(.@array$,getd(".@p_l"+.@z+"$["+.@k+"]"),"|"); unitwalk(.@gid,atoi(.@array$),atoi(.@array$[1])); sleep2(500); .@k++; } .@k=0; set(.@z,.@z-1); } end; OnGoHome: .stop = 1; end; OnGoClear: .@clear = 1; goto Clear; OnGoStart: warp "ama_dun01",233,9; end; OnList: getmapxy(.@map$,.@x,.@y,0); if(checkcell(.@map$,.@x,.@y,cell_chkwall) || checkcell(.@map$,.@x,.@y,cell_chkcliff) || checkcell(.@map$,.@x,.@y,cell_chknopass) || checkcell(.@map$,.@x,.@y,cell_chknoreach)) { dispbottom "Failed"; } else dispbottom "Added"; end; OnInit: bindatcmd "@stop",strnpcinfo(0)+"::OnGoHome"; bindatcmd "@clear",strnpcinfo(0)+"::OnGoClear"; bindatcmd "@list",strnpcinfo(0)+"::OnList"; bindatcmd "@start",strnpcinfo(0)+"::OnGoStart"; setarray .@map_max, 240, 0; .e_x = 232; //End Pos .e_y = 144; //End Pos freeloop(1); set(.@time,gettimetick(0)); if(!.h_switch) { .@x = 0; .@y = 240; LOOP1: LOOP2: if(checkcell("ama_dun01",.@x,.@y,cell_chkwall) || checkcell("ama_dun01",.@x,.@y,cell_chkcliff) || checkcell("ama_dun01",.@x,.@y,cell_chknopass) || checkcell("ama_dun01",.@x,.@y,cell_chknoreach)) {} else setd(".h_x"+.@x+"_y"+.@y, (10*(abs([email protected]_x ) + abs([email protected]_y )))); jump_zero ((.@y--)<.@map_max[1]),LOOP2; .@y = 240; jump_zero (.@x++>.@map_max),LOOP1; npctalk "This process took: "+(gettimetick(0)-.@time)+" ms"; } else { .@x_d = abs(.@x2-.@e_x); .@y_d = abs(.@y2-.@e_y); if(.@x_d > .@y_d) .@h = 14*.@y_d + 10*(.@x_d-.@y_d); else .@h = 14*.@x_d + 10*(.@x_d-.@x_d); //.@x_d = abs(.@x2 - .@e_x); //.@y_d = abs(.@y2 - .@e_y); //.@h = /*.@m*/14 * max(.@x_d, .@y_d); } } function script AddLeaf { .@key = getarg(0,0); .@ptr = getarg(1,0); if(!getstrlen(@node$)) @node$ = getarg(0)+"||"; else if(getarg(0) < atoi(@node$[.@ptr])) { if(getarraysize(@node$)>=(2*.@ptr)+1) { if(@node$[(2*.@ptr)+1]!="") //charat(.@node$[.@ptr],strpos(.@node$[.@ptr],"|")+1) callfunc("AddLeaf",((2*.@ptr)+1)); else @node$[(2*.@ptr)+1] = getarg(0)+"||"; } else { @node$[(2*.@ptr)+1] = getarg(0)+"||"; } } else if(getarg(0) > atoi(@node$[.@ptr])) { if(getarraysize(@node$)>=(2*.@ptr)+2) { if(@node$[(2*.@ptr)+2]!="") //charat(.@node$[.@ptr],strpos(.@node$[.@ptr],"|")+1) callfunc("AddLeaf",((2*.@ptr)+2)); else @node$[(2*.@ptr)+2] = getarg(0)+"||"; } else { @node$[(2*.@ptr)+2] = getarg(0)+"||"; } } else { dispbottom "The key has already been added to the tree."; } } //AddHeap({<value>,<array>,<pointer>}); function script AddHeap { .@key = getarg(0,0); .@ke$ = getarg(0,0); .@ptr = getarg(2,getarraysize(getarg(1,@node$))); copyarray .@ar$, getarg(1,@node$), .@ptr; LOOP: .@loops++; ///if(.@ptr>64) return 1; if(.@ptr) { .@pnt = (.@ptr-1)>>1; } if( getarraysize(.@ar$) ) if( countstr("#"+implode(.@ar$,"#")+"#", "#"+.@ke$+"#", 0) > 1 ) { debugmes .@ke$+" exists in "+implode(.@ar$,"#")+" loops "+.@loops; } if(!/*getstrlen(*/getarraysize(.@ar$)/*)*/) { .@ar$ = .@ke$; } else if(atoi(.@ar$[.@pnt]) > .@key) { .@temp$ = .@ar$[.@pnt]; .@ar$[.@pnt] = .@ke$; .@ar$[.@ptr] = .@temp$; .@ptr = .@pnt; goto LOOP; } else if(getarraysize(.@ar$)<=.@ptr) { .@ar$[.@ptr] = .@ke$; } copyarray getarg(1,@node$), .@ar$, getarraysize(.@ar$); return .@loops; } function script DelHeap { .@ptr = getarg(0,0); .@len = getarg(2,getarraysize(getarg(1,@node$)))-1; if( .@len < 0 ) end; copyarray .@ar$, getarg(1,@node$), .@len+1; .@ar$[.@ptr] = .@ar$[.@len]; .@ar$[.@len] = ""; deletearray getelementofarray(getarg(1,@node$),.@len),1; LOOP: .@cn1 = (.@ptr<<1)+1; //.@cn1 = (.@ptr*2)+1; .@cn2 = .@cn1+1; .@ptn = atoi(.@ar$[.@ptr]); .@cd1 = atoi(.@ar$[.@cn1]); if(.@len>.@cn2) { .@cd2 = atoi(.@ar$[.@cn2]); if(.@cd1>.@cd2) { if(.@ptn>.@cd2) { .@temp$ = .@ar$[.@ptr]; .@ar$[.@ptr] = .@ar$[.@cn2]; .@ar$[.@cn2] = .@temp$; .@len = getarraysize(.@ar$); .@ptr = .@cn2; goto LOOP; } } else { if(.@ptn>.@cd1) { .@temp$ = .@ar$[.@ptr]; .@ar$[.@ptr] = .@ar$[.@cn1]; .@ar$[.@cn1] = .@temp$; .@len = getarraysize(.@ar$); .@ptr = .@cn1; goto LOOP; } } } else if(.@ptn>.@cd1&&.@len==2) { .@temp$ = .@ar$[.@ptr]; .@ar$[.@ptr] = .@ar$[.@cn1]; .@ar$[.@cn1] = .@temp$; } else if(!.@ptn&&.@len==2) { .@temp$ = .@ar$[.@ptr]; .@ar$[.@ptr] = .@ar$[.@cn1]; .@ar$[.@cn1] = .@temp$; } copyarray getarg(1,@node$), .@ar$, getarraysize(.@ar$); return; } function script PrintInOrder { .@ptr = getarg(0); if(getarraysize(@node$)) { if(getarraysize(@node$)>=(2*.@ptr)+1) { if(@node$[(2*.@ptr)+1]!="") callfunc("PrintInOrder",((2*.@ptr)+1)); } .@message = .@message + @node$[.@ptr]; if(getarraysize(@node$)>=(2*.@ptr)+2) { if(@node$[(2*.@ptr)+2]!="") callfunc("PrintInOrder",((2*.@ptr)+2)); } } else { dispbottom "The tree is empty."; } } function script test { copyarray .@array$, getarg(0), getarraysize(getarg(0)); for(.@a=0;.@a<getarraysize(getarg(0));.@a++) { //dispbottom ""+getelementofarray(getarg(0),.@a); dispbottom .@array$[.@a]; } //return; dispbottom "done"; } test_map,7,82,5 script AtoI-Test 100,{ /*freeloop(1); .@time=gettimetick(0); for(.@a=0;.@a<1000;.@a++) { .@b = atoi("100|32432|10"); //.@b = atoi("100#32432#10"); //.@b = atoi("100a32432a10"); } npctalk "Test 1 "+(gettimetick(0)-.@time)+"ms"; Sleep(100); .@time=gettimetick(0); for(.@a=0;.@a<1000;.@a++) { explode(.@a$,"100|32432|10","|"); //explode(.@a$,"100#32432#10","#"); //explode(.@a$,"100a32432a10","a"); } npctalk "Test 2 "+(gettimetick(0)-.@time)+"ms";*/ deletearray @node$; ///setarray .@keys$, "50", "76", "21", "4", "32", "64", "15", "52", "14", "100", "83", "2", "3", "70", "87", "80"; ///setarray .@keys, 410, 705, 732, 23, 195, 78, 452, 970, 804, 970; setarray .@keys$, "9212", "7387", "1821", "4979", "9241", "1309", "4870", "4946", "707", "3081", "2141", "2135", "5324", "9566", "9638", "8759", "8749", "5620", "8667", "7287", "8", "668", "4899", "3688", "5614", "2754", "8833", "8783", "1682", "2781", "2720", "7709", "2120", "306", "6410", "4590", "6040", "3933", "2124", "5542", "6361", "7499", "3610", "155", "35", "9936", "1935", "8725", "9049", "4406", "5905", "4539", "6843", "9243", "3569", "5038", "2712", "8041", "2181", "796", "9083", "3534", "891", "1687"; dispbottom "Len "+getarraysize(.@keys$); ///callfunc("test",.@keys$); debugmes implode(@node$,"#"); .@tick = gettimetick(0); for(.@a=0;.@a<getarraysize(.@keys$);.@a++) callfunc("AddHeap",(.@keys$[.@a]),.@node$); ///callfunc("PrintInOrder"); debugmes implode(.@node$,"#"); for(.@a=0;.@a<getarraysize(.@keys$);.@a++) { callfunc("DelHeap",0,.@node$); debugmes implode(.@node$,"#"); } .@tock = gettimetick(0); debugmes ( .@tick-.@tock )+"ms"; }Link to comment
Share on other sites
8 answers to this question
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.