Леший 3 Posted February 22, 2012 Share Posted February 22, 2012 Sveiki! Vajag algoritmu, kas atrod ceļu starp x1,y1 un x2,y2. Ceļam nav jābūt īsākam, ir dots soļu skaits, un ceļam ir jābūt +/- tādā garumā. Ceļam ir jābūt ar randomu. Protams, vienkāršākais veids ir saģenerēt punktus p2, p3, ... p(n-1), un sazīmēt random taisnus ceļus starp tiem, pēc tam to visu salikt vienā ceļā, bet tur parādās visādi izņemumi, piemēram, ceļš var krustoties, ko manā gadījumā nedrikst pieļaut utt. Gribēju uzzināt, varbūt ir jau kaut kas tāds gatavs, lai man nebūtu jāizgudro riteni. Quote Link to post Share on other sites
kirils 2 Posted February 22, 2012 Share Posted February 22, 2012 kas ir "solis"? ko nozīmē "±tādā garumā"? kas Tev ir dots vispār? grafs? dekarta koordināšu sistēma? Quote Link to post Share on other sites
Леший 3 Posted February 22, 2012 Author Share Posted February 22, 2012 dekarta koordināšu sistēma? atrod ceļu starp x1,y1 un x2,y2. Tb, jā Solis ir pāreja no vienas (x,y) koordinates uz blakus esošo. "±tādā garumā" - tb, ja dotais soļu skaits ir 40, tad rezultātā man ir jadabū ceļu, kas ir veikts ar 40 soļiem +/- piemēram 2 (gadījumiem, kad ar 40 soļiem nedaudz nepietika). Faktiski man vajag kaut ko līdzīgu sakombinētiem Self avoiding walk un Random walk . Quote Link to post Share on other sites
kirils 2 Posted February 23, 2012 Share Posted February 23, 2012 nedomāju, ka gatavu moduli kaut kur atradīsi, bet nu es darītu šādi: cels(x1,y1,x2,y2,garums): mingarums:= | x1-x2 | + |y1-y2| garums:= max(mingarums,garums) garums+= 2 ;; ±2 ☺ extra:=mingarums-garums virziens:=(x1-x2)/|x1-x2| ;; ja x1=x2, tad virziens var būt brīvi -1 vai +1 nogrieznis(x1,y1,x1+virziens*extra,y1) nogrieznis(x1+virziens*extra,y1,x1+virziens*extra,y2) nogrieznis(x2,y2); nu un tad papildus var randomiski (X reizes atrodot random koordināti, kas pieder ceļam) šajā ceļā aizvietot: taisnus apgabalus ar _ _| |_ un ieliektos leņķus ar izliekiem. Quote Link to post Share on other sites
bubu 1 Posted February 23, 2012 Share Posted February 23, 2012 (edited) Varbūt var mēģināt pielietot A* algoritmu, kur ceļa svara funkciju izveidot tā, lai tā dotu lielāku svaru ceļam vajadzīgajā garumā. T.i. paņem prasto Eiklīda vai Manhetenas distances funkciju un, piemēram, pareizini ar 2, ja ceļa garums ir +/- vajadzīgajā gaurmā. Edited February 23, 2012 by bubu 1 Quote Link to post Share on other sites
Леший 3 Posted February 23, 2012 Author Share Posted February 23, 2012 (edited) Tātad, pašlaik es apstājos pie šāda varianta: ir algoritms, kas veido īsāko ceļu starp 2 punktiem, pie tam, ceļš sanāk randomā, tas ir, nevis | | |________________ bet |___ |__ |____ Tālāk, es ģenerēju n punktus dotājā laukumā (n ir atkarīgs no laukuma izmēra), un ar ta algoritma palīdzību, es tos punktus savienoju. Ir problēmas ar pašiem punktiem, jo īsti nenāk prātā, kā tos labāk ģenerēt, lai būtu daudz maz true random, un lai ceļš nekrustotos. Edited February 23, 2012 by Леший Quote Link to post Share on other sites
japets 0 Posted February 24, 2012 Share Posted February 24, 2012 Es arī balsotu par A* ar "nekorektu" svara funkciju. Quote Link to post Share on other sites
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.