Vajadzīgs algoritms ceļu ģenerēšanai ar noteikto soļu skaitu

[Леший]

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.

[kirils]

kas ir "solis"? ko nozīmē "±tādā garumā"? kas Tev ir dots vispār? grafs? dekarta koordināšu sistēma?

[Леший]

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 .

[kirils]

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.

[bubu]

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

[Леший]

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 - Леший

[japets]

Es arī balsotu par A* ar "nekorektu" svara funkciju.