Wilson's Algorithm Maze Generator

Tsarin Wilson hanya ce ta tafiya bazuwar da aka goge ta hanyar madauki wadda ke samar da bishiyoyi iri ɗaya don ƙirƙirar maze. Wannan yana nufin cewa duk wasu mazes masu girman da aka bayar ana iya samar da su daidai gwargwado, wanda hakan ya sa ya zama dabarar samar da maze mara son kai. Ana iya ɗaukar tsarin Wilson a matsayin ingantacciyar sigar tsarin Aldous-Broder, domin yana samar da mazes masu halaye iri ɗaya, amma yana aiki da sauri sosai, don haka ban damu da aiwatar da tsarin Aldous-Broder a nan ba.

Cikakken maze shine maze wanda a cikinsa akwai ainihin hanya ɗaya daga kowane wuri a cikin maze zuwa kowane wuri. Wannan yana nufin ba za ku iya ƙarasa da zagayawa cikin da'ira ba, amma sau da yawa za ku gamu da matattu, wanda zai tilasta muku juyo da komawa.

Taswirorin maze da aka samar a nan sun haɗa da sigar tsoho ba tare da kowane matsayi na farawa da ƙare ba, don haka zaku iya yanke shawarar waɗancan da kanku: za a sami mafita daga kowane wuri a cikin maze zuwa kowane wuri. Idan kuna son ilhama, zaku iya kunna shawarar farawa da ƙarewa - har ma da ganin mafita tsakanin su biyun.

Game da Tsarin Wilson

Tsarin Wilson na samar da bishiyoyi masu tsayi iri ɗaya ta amfani da bangon da aka goge da madauki, David Bruce Wilson ne ya ƙirƙira shi.

Wilson ya fara gabatar da wannan tsarin lissafi a shekarar 1996 yayin da yake bincike kan bishiyoyin da ke ratsawa bazuwar da kuma sarƙoƙin Markov a ka'idar yiwuwar samun nasara. Duk da cewa aikinsa ya fi mayar da hankali ne kan lissafi da kimiyyar lissafi, tun daga lokacin an yi amfani da tsarin sosai don samar da tsarin launi saboda iyawarsa ta samar da tsarin launi iri ɗaya.

Yadda Algorithm na Wilson ke Aiki ga Tsarin Maze

Tsarin Wilson yana tabbatar da cewa an haɗa mashin ɗin ƙarshe gaba ɗaya ba tare da wata madaukai ba ta hanyar sassaka hanyoyi daga ƙwayoyin da ba a ziyarta ba ta hanyar amfani da tafiya bazuwar.

Mataki na 1: Fara

• Fara da grid cike da bango.
• Bayyana jerin dukkan ƙwayoyin da za su iya wucewa.

Mataki na 2: Zaɓi Ƙwayar Farawa ta Bazuwar

• Zaɓi kowace tantanin halitta da bazuwar kuma yi mata alama kamar an ziyarta. Wannan yana aiki a matsayin wurin fara aikin maze yayin samarwa.

Mataki na 3: Tafiya bazuwar tare da gogewa ta madauki

• Zaɓi wani tantanin da ba a ziyarta ba kuma fara tafiya bazuwar (yana tafiya bazuwar).
• Idan tafiyar ta kai ga wani tantanin halitta da aka riga aka ziyarta, goge duk wani madaukai a kan hanyar.
• Da zarar tafiyar ta haɗu da yankin da aka ziyarta, yi alama ga dukkan ƙwayoyin da ke cikin hanyar a matsayin waɗanda aka ziyarta.

Mataki na 4: Maimaita Har Sai An Ziyarci Duk Kwayoyin Halitta:

• Ci gaba da zaɓar ƙwayoyin da ba a ziyarta ba kuma yi tafiya bazuwar har sai kowace ƙwayar ta zama ɓangare na maze.

Karin Karatu

Idan kuna jin daɗin wannan sakon, kuna iya kuma son waɗannan shawarwari:

• Mai Ƙirƙirar Labirint na Itace Mai Girma
• Mai Ƙirƙirar Labirint na Farauta da Kisa
• Kruskal na Algorithm Maze Generator