Mai Ƙirƙirar Labirint na Algoritmin Eller

Algorithm na Eller wani tsari ne na samar da mazugi wanda ke samar da mazugi masu kyau (mazugi marasa madaukai da hanya ɗaya tsakanin kowane maki biyu) ta amfani da hanyar layi-layi. Yana samar da mazugi masu kama da algorithm na Kruskal, amma yana yin hakan ta hanyar samar da layi ɗaya kawai a lokaci guda, ba tare da buƙatar adana dukkan mazugi a cikin ƙwaƙwalwa ba. Wannan yana sa ya zama da amfani wajen samar da manyan mazugi a kan tsarin da ba shi da iyaka da kuma samar da abubuwan da ake buƙata a tsari.

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 Eller

David Eller ne ya gabatar da Tsarin Eller.

Tsarin aikin ya shahara saboda ingantaccen tsarin sa na tsara layuka-da-jere don samar da mazugi, wanda hakan ya sa ya dace da mazugi marasa iyaka ko mazugi da aka samar a ainihin lokaci. Ana yawan ambaton sa a cikin samar da abubuwan da aka tsara da kuma adabin samar da mazugi, amma ban sami tushen asali da ke bayanin ainihin littafinsa ba.

Yadda Algorithm na Eller ke Aiki Don Samar da Maze

Tsarin Eller yana sarrafa layi ɗaya bayan ɗaya, yana kiyayewa da kuma gyara saitin ƙwayoyin da aka haɗa. Yana tabbatar da haɗin kai yayin da yake guje wa madaukai, kuma yana faɗaɗa madaukai zuwa ƙasa yadda ya kamata.

A ka'ida, ana iya amfani da shi don samar da mazurari marasa iyaka, duk da haka, don tabbatar da cewa mazurarin da aka samar za a iya warware shi, ya zama dole a canza zuwa dabarar "layi na ƙarshe" a wani lokaci don kammala mazurarin.

Mataki na 1: Fara Layin Farko

• Sanya kowace tantanin halitta a jere wani takamaiman ID na saiti.

Mataki na 2: Haɗa Wasu Ƙwayoyin Hannu Masu Maƙwabtaka a Kwance

• Haɗa ƙwayoyin da ke maƙwabtaka da juna ba zato ba tsammani ta hanyar saita su zuwa ga ID ɗin saiti ɗaya. Wannan yana tabbatar da cewa akwai hanyoyin kwance.

Mataki na 3: Ƙirƙiri Haɗin Tsaye zuwa Layi na Gaba

• Ga kowace saitin da ya bayyana a jere, aƙalla tantanin halitta ɗaya dole ne ya haɗu ƙasa (don tabbatar da haɗin kai).
• Zaɓi ɗaya ko fiye da ƙwayoyin halitta daga kowane saiti don haɗawa zuwa layi na gaba.

Mataki na 4: Matsa zuwa Layi na Gaba

• Ci gaba da haɗin kai tsaye ta hanyar sanya ID ɗin saiti iri ɗaya zuwa ƙwayoyin da suka dace da ke ƙasa.
• Sanya sabbin ID na saiti ga duk wani ƙwayoyin da ba a ba su izini ba.

Mataki na 5: Maimaita Matakai na 2-4 Har sai Layin Ƙarshe ya isa

• Ci gaba da sarrafa layi-layi.

Mataki na 6: Tsara Layin Ƙarshe

• Tabbatar da cewa duk ƙwayoyin halitta a jere na ƙarshe suna cikin saiti ɗaya ta hanyar haɗa duk sauran saitin daban.

Karin Karatu

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

• Recursive Daga baya Maze Generator
• Wilson's Algorithm Maze Generator
• Kruskal na Algorithm Maze Generator