Recursive Daga baya Maze Generator

Tsarin sake-sake na baya-bayan nan bincike ne na farko da aka yi amfani da shi don zurfafa bincike. Idan aka yi amfani da shi don ƙirƙirar mazugi, yana ɗan gyara shi don zaɓar hanyar a bazata, yayin da idan aka yi amfani da shi don dalilai na bincike na ainihi, yawanci mutum zai bincika kowane mataki a cikin tsari mai layi. Yana haifar da mazugi tare da dogayen hanyoyi masu lanƙwasa da kuma mafita mai tsayi da karkacewa.

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.

Tsarin sake-sake na backtracker hanya ce ta bincike mai zurfi don samar da cikakkun mazugi (mazugi ba tare da madaukai ba da hanya ɗaya tsakanin kowane wuri biyu). Yana da sauƙi, inganci, kuma yana samar da mazugi masu kyau tare da dogayen hanyoyi masu lanƙwasa.

Duk da sunansa, ba lallai ba ne a aiwatar da shi ta amfani da recursion. Sau da yawa ana aiwatar da shi ta hanyar maimaitawa ta amfani da layin LIFO (watau tarin bayanai). Ga manyan mazes, amfani da recursion yana iya haifar da ambaliya na tarin bayanai, ya danganta da harshen shirye-shirye da ƙwaƙwalwar da ake da ita. Jerin bayanai na LIFO za a iya daidaita shi cikin sauƙi don sarrafa adadi mai yawa na bayanai, har ma da ajiye layin a kan faifai ko a cikin rumbun bayanai idan ƙwaƙwalwar da ke akwai ba ta isa ba.

Yadda Yake Aiki

Tsarin bincike yana aiki ta amfani da hanyar bincike mai zurfi-farko. Ga bayanin mataki-mataki:

1. Zaɓi tantanin halitta mai farawa kuma yi masa alama kamar an ziyarta.
2. Duk da yake akwai ƙwayoyin da ba a ziyarta ba: Duba ƙwayoyin da ke maƙwabtaka waɗanda ba a ziyarta ba tukuna. Idan akwai aƙalla maƙwabci ɗaya da ba a ziyarta ba: Zaɓi ɗaya daga cikin maƙwabtan da ba a ziyarta ba. Cire bangon tsakanin ƙwayar da ke yanzu da maƙwabcin da aka zaɓa. Matsar zuwa maƙwabcin da aka zaɓa kuma yi masa alama a matsayin wanda aka ziyarta. Tura ƙwayar da ke yanzu a kan tarin. Idan babu maƙwabtan da ba a ziyarta ba: Koma baya ta hanyar zana ƙwayar da ta gabata daga tarin.
3. Ci gaba da wannan tsari har sai tarin ya zama babu komai.

Wani abu mai ban sha'awa game da wannan tsarin aiki shine cewa yana aiki duka a matsayin janareta na maze da kuma a matsayin mai warware maze. Idan ka kunna shi akan maze da aka riga aka samar kuma kawai ka tsaya lokacin da ka isa wurin da aka ƙayyade, tonon zai ƙunshi mafita ga maze.

A gaskiya ina da nau'ikan wannan algorithm guda biyu a wannan shafin: layin LIFO wanda aka gina bisa ga tsarin LIFO don samar da tsarin LIFO a wannan shafin da kuma wanda aka gina bisa ga tsarin LICU don warware tsarin LICU, haka kuma tsarin LICU don warware tsarin LICU don warware tsarin LICU (haka ake yin taswirar da ke ɗauke da mafita). Samun nau'ikan guda biyu daban-daban na wasanni ne kawai domin ni ƙwararren masani ne wanda yake ganin abin sha'awa ne, ɗayansu zai iya aiki ga duka biyun ;-)

Karin Karatu

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

• Mai Ƙirƙirar Labirint na Algoritmin Eller
• Wilson's Algorithm Maze Generator
• Mai Ƙirƙirar Labirint na Itace Mai Girma