Jump to content

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


Леший
 Share

Recommended Posts

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

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

Леший

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

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

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 - bubu
  • Patīk 1
Link to comment
Share on other sites

Леший

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 - Леший
Link to comment
Share on other sites

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 kontu

Pierakstīties

Jums jau ir konts? Pierakstieties tajā šeit!

Pierakstīties tagad!
 Share

×
×
  • Izveidot jaunu...