Jump to content

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


Леший

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 post
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 post
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 post
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ā.

Edited by bubu
  • Patīk 1
Link to post
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.

Edited by Леший
Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
×
×
  • Create New...