Labiritna algoritms

[m8t]

Pavisam nesen ienāca prātā doma - uzprogrammēt PHP labirintu ģenerējošu algoritmu. Tā arī nesaņēmos un neķēros klāt, bet gribu jums uzdot jautājumu - kā jūs veidotu šādu algoritmu? Atbildiet un tad lasiet tālāk manu domu.

 

 

 

Tātad, mana doma nav nekāda īpaši sarežģītā. Centīšos te tā smuki, pārskatāmi viņu izklāstīt.

1. Sarēķinam cik daudz lauciņi būs kopā tabulā (x*y)

2. Taisam while() ciklu, kuru izbeidzam tikai tad, kad "iekrāsotie" lauciņi (tie, kuros ir kaut kāds ceļšs) ir >= x*y un iekš cikla:

2.1. Izkalkulējam random ceļu no koordinātēm (1, 1) līdz (max_X, max_Y)

2.2. Pa vienam lauciņam skrienam uz priekšu šo ceļu, katrā lauciņā

2.2.1. Iečekojam cik no aprkārtējiem lauciņiem ir tukši (iečekojam x+1, x-1, y+1, y-1)

2.2.2. Izpildot rand() funkciju un ejot attiecīgajā virzienā ("aizpildam" to lauciņu un pasakam ka pēdējais lauciņš, kur kaut kas ir darīts = tas lauciņš.

2.2.3. Atkārtojot šos 3 punktus līdz atrodamies punktā (max_x, max_y)

2.3. Kad galvenais ceļš ir pabeigts - sākam likt "maldu" ceļus. T.i. - skatamies, kuri lauciņi nav "iekrāsoti". Ja lauciņš ir neikrāsots un blakus iekrāsotajam - atrodam vēlvienu neiekrāsoto un veidojam ceļu uz to.

2.4. Atkārtojam "maldu ceļu" būvniecību līdz visi lauciņi ir iekrāsoti.

3. Kopējam laukā visu

 

Ja visa šī laikā notiek tā, ka neesam nonākuši galapunktā, bet virzieni uz kuriem varam tālāk doties ir 0, tad sākam visu no sākuma.

 

Varbūt jums ir ieteikumi, ko te var uzlabot? Nekas svarīgs jau šis nav, bet vienkārši tāpatās, galvas palauzīšanai.

 

Lūdzu nemetiet linkus uz Google vai citiem saitiem. Šito labāk pats izkalkulē, protams, ja to spēj... ;)

 

 

Edited March 1, 2011 by m8t