Генератор на лавиринт и игра

Како се користи генераторот на лавиринт

1. Поставете Ширина (колони) и Висина (редови), од 4 до 60 полиња секое, и изберете Алгоритам. Кликнете Нов лавиринт.
2. Вашата позиција е точката во зелениот влез горе лево. Стигнете до црвениот излез долу десно.
3. Движете се со стрелките или WASD (ZQSD на француска тастатура). Држете Shift со стрелка за да трчате по ходникот до следната раскрсница. На телефон или таблет повлечете по лавиринтот за да трчате во таа насока или допрете ги копчињата со стрелки под него за единечни чекори.
4. Мерачот на време почнува со вашиот прв потег и запира на излезот. Вашата патека се црта зад вас; враќањето по неа ја брише, па секогаш го покажува патот по кој сте.
5. Заглавивте? Прикажи решение ја црта најкратката патека од местото каде што стоите до излезот. Назад на почеток ве враќа на влезот со ресетиран мерач на време.
6. За игра на хартија кликнете Печати или Преземи PDF. Прво штиклирајте Додај страница со решение ако сакате одговорот на втора страница.

Споделете лавиринт со неговиот код

Секој лавиринт има Код на лавиринтот, како на пример b20x15-k3j9x2: буквата на алгоритмот (b, p или k), ширина × висина и случајна почетна вредност. Истиот код секогаш го гради точно истиот лавиринт на кој и да е уред, па можете да го предизвикате пријателот да го надмине вашето време на истиот распоред. Впишете или залепете код и кликнете Вчитај код, или користете Копирај врска за да споделите веб-адреса што директно го отвора тој лавиринт.

Трите алгоритми за генерирање

Сите три градат совршен лавиринт: до секое поле може да се стигне и меѓу кои и да се две полиња има точно една патека, па нема јамки ниту затворени области. Тие се разликуваат по изгледот на лавиринтот:

• Рекурзивно враќање (долги ходници) оди случајно од поле до поле, урнувајќи ѕидови, и се враќа назад кога ќе стигне до слепа улица. Создава долги вијугави премини со малку разгранувања: решението обично е долго и ве води низ поголемиот дел од мрежата.
• Prim (многу кратки слепи улици) го расте лавиринтот нанадвор од случајно поле, додавајќи секој пат случајно гранично поле. Добивате многу кратки странични гранки, па лавиринтот изгледа зафатено, но главната патека се гледа полесно.
• Kruskal (рамномерно, разгранато) отстранува случајно избрани ѕидови меѓу полиња што сè уште не се поврзани (следено со структура union-find). Резултатот е рамномерно разгранат насекаде, без видлива почетна точка.

Линијата над лавиринтот ја дава големината, должината на најкратката патека и бројот на слепи улици, па алгоритмите можете да ги споредите со еден поглед.

Како се наоѓа решението

Решението користи пребарување по ширина (BFS): почнувајќи од вашето поле, ги истражува сите соседи оддалечени еден чекор, потоа два чекори и така натаму, сè додека не стигне до излезот. Бидејќи секој чекор чини исто, BFS секогаш ја наоѓа најкратката патека. Во совршен лавиринт таа патека е и единствената без враќање. Кога решението е прикажано во текот на играта, вашето завршно време не се зачувува како најдобро време.

Совети за печатење

Печатените и PDF верзиите цртаат чисти црни ѕидови на бела подлога, со кодот на лавиринтот во насловот за да можете повторно да го најдете истиот лавиринт. Големини околу 15 × 15 одговараат на мали деца; 30 × 30 и повеќе претставуваат солидна загатка за возрасни. Многу големите лавиринти (50 × 60) имаат тесни ходници на страница A4, па печатете ги на цела големина на страницата.