Леший Ierakstīts Februāris 22, 2012 Share Ierakstīts Februāris 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. Link to comment Share on other sites More sharing options...
kirils Februāris 22, 2012 Share Februāris 22, 2012 kas ir "solis"? ko nozīmē "±tādā garumā"? kas Tev ir dots vispār? grafs? dekarta koordināšu sistēma? Link to comment Share on other sites More sharing options...
Леший Februāris 22, 2012 Author Share Februāris 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 . Link to comment Share on other sites More sharing options...
kirils Februāris 23, 2012 Share Februāris 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. Link to comment Share on other sites More sharing options...
bubu Februāris 23, 2012 Share Februāris 23, 2012 (labots) 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ā. Labots Februāris 23, 2012 - bubu 1 Link to comment Share on other sites More sharing options...
Леший Februāris 23, 2012 Author Share Februāris 23, 2012 (labots) 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. Labots Februāris 23, 2012 - Леший Link to comment Share on other sites More sharing options...
japets Februāris 24, 2012 Share Februāris 24, 2012 Es arī balsotu par A* ar "nekorektu" svara funkciju. Link to comment Share on other sites More sharing options...
Recommended Posts
Izveido kontu, vai pieraksties esošajā, lai komentētu
Jums ir jābūt šī foruma biedram, lai varētu komentēt tēmas
Izveidot jaunu kontu
Piereģistrējies un izveido jaunu kontu, tas būs viegli!
Reģistrēt jaunu kontuPierakstīties
Jums jau ir konts? Pierakstieties tajā šeit!
Pierakstīties tagad!