Ang Algorithm Maze Generator ng Kruskal

Ang algorithm ng Kruskal ay isang minimum spanning tree algorithm na maaaring iakma para sa pagbuo ng maze. Ito ay partikular na epektibo para sa paglikha ng perpektong maze. Ang isang kahalili sa algorithm ng Kruskal ay ang algorithm ng Prim, na isa ring pinakamababang algorithm ng spanning tree, ngunit dahil bumubuo sila ng magkaparehong mga maze at mas mabilis ang pagtakbo ng Kruskal, hindi ako nag-abala sa pagpapatupad ng Prim's.

Ang perpektong maze ay isang maze kung saan mayroong eksaktong isang landas mula sa anumang punto sa maze hanggang sa anumang iba pang punto. Nangangahulugan iyon na hindi ka maaaring maglibot sa mga bilog, ngunit madalas kang makatagpo ng mga patay na dulo, na pinipilit kang tumalikod at bumalik.

Ang mga mapa ng maze na nabuo dito ay may kasamang default na bersyon nang walang anumang mga posisyon sa pagsisimula at pagtatapos, kaya maaari kang magpasya para sa iyong sarili: magkakaroon ng solusyon mula sa anumang punto sa maze hanggang sa anumang iba pang punto. Kung gusto mo ng inspirasyon, maaari mong paganahin ang isang iminungkahing posisyon sa pagsisimula at pagtatapos - at kahit na makita ang solusyon sa pagitan ng dalawa.

Tungkol sa Algorithm ni Kruskal

Ang algorithm ni Kruskal ay nilikha ni Joseph Bernard Kruskal, Jr., isang Amerikanong matematikal, statistician, at computer scientist. Inilarawan niya ang algorithm noong 1956 sa kanyang papel na "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem."

Ang algorithm ay dinisenyo upang hanapin ang minimum spanning tree (MST) ng isang graph, tinitiyak na ang lahat ng vertices ay konektado gamit ang pinakamababang posibleng kabuuang bigat ng gilid habang iniiwasan ang mga cycle.

Paano Gumagana ang Algorithm ni Kruskal sa Pagbuo ng Maze

Hakbang 1: I-Initialize

• Itrato ang bawat cell sa maze bilang isang hiwalay na set (isang natatanging bahagi).
• Ilista ang lahat ng pader sa pagitan ng magkasunod na cells bilang potensyal na mga gilid.

Hakbang 2: Ayusin ang mga Pader

• Paghaluin o ayusin nang random ang mga pader. Kung ipinatutupad ito bilang isang tunay na algorithm ni Kruskal, ayusin ang mga pader sa isang random na pagkakasunod (dahil hindi kailangan ng mga bigat sa pagbuo ng maze).

Hakbang 3: Proseso ng mga Pader

• I-iterate ang mga pader na inihalo.
• Kung ang dalawang cells na hinati ng pader ay kabilang sa magkaibang set (ibig sabihin, hindi pa sila konektado sa maze), alisin ang pader at pagsamahin ang mga set.
• Kung sila ay nasa parehong set na, laktawan ang pader (upang maiwasan ang mga cycle).

Hakbang 4: Magpatuloy Hanggang Matapos

• Sa dulo, ang bawat cell ay konektado sa iba nang walang mga loop o isolated na bahagi.

Dahil ang algorithm ni Kruskal ay umaasa sa pagsasama ng mga set, maaari itong mapabuti gamit ang Union-Find algorithm, na nagbibigay ng isang mahusay na paraan upang subaybayan ang mga konektadong cells habang binubuo ang maze. Maaari mong makita ang aking PHP na implementasyon ng Union-Find algorithm dito: Disjoint Set (Union-Find Algorithm) sa PHP