Tentokrát popíši postup algoritmu, který dokáže generovat náhodné 2D bludiště zadaných rozměrů.
Generování náhodného bludiště s přepážkami
Bludištěm s přepážkami je myšleno dvourozměrné bludiště (matice) s jednotlivými políčky (buňkami), po kterých se dá procházet, přičemž mezi sousedícími políčky v jednotlivých čtyřech směrech buď je a nebo není přepážka, tedy daný směr buď není (přepážka tam je) či je (přepážka tam není) průchozí.
Nejprve nadefinujeme výčet směrů (Směr), kterými se dá mezi jednotlivými políčky bludiště pohybovat. Každému směru také přiřadíme unikátní číslo, které bude v jeho binární podobě možné kombinovat s ostatními čísly (směry) tak, abychom z něho vždy byli schopni dekódovat, které všechny směry toto číslo zahrnuje. Použita tedy budou čísla z řady mocniny dvou. Atribut [Flags] pak tomuto výčtu dává možnost kombinování těchto směrů pro proměnné typu Smer, tj. např. proměnná typu Smer bude mít hodnotu 10, což znamená, že bude zároveň obsahovat hodnoty D a L (2 a 8), což půjde pro jednotlivé směry snadno ověřovat pomocí metody HasFlag, kterou takové výčty mají.
[Flags]
public enum Smer
{
N = 1, // 0001 Nahoru
D = 2, // 0010 Dolů
P = 4, // 0100 Pravo
L = 8, // 1000 Levo
}
Nyní vytvoříme třídu Bludiste, která bude zastřešovat všechny potřebné metody. Třída může být statická, jelikož v sobě nebude potřebovat uchovávat žádné stavy ani hodnoty, veškeré operace se vždy vyřeší v rámci jednotlivých metod.
public static class Bludiste { ... }
Ve třídě si nadefinujeme a rovnou i vytvoříme generátor náhodných čísel random a pomocný slovník Protismer, který bude překládat každý ze čtyř možných směrů na jeho opačný směr (Nahoru = Dolů, Dolů = Nahoru atd.)
// Generátor náhodných čísel
private static Random random = new Random();
// Překlad směru na směr opačný
private static Dictionary<Smer, Smer> Protismer = new Dictionary<Smer, Smer>
{
{ Smer.N, Smer.D },
{ Smer.D, Smer.N },
{ Smer.P, Smer.L },
{ Smer.L, Smer.P }
};
Metoda Vytvor si nejprve vyvtoří proměnnou mapa typu dvourozměrné pole celých čísel o vstupními parametry (sloupcu a radku) zadaných rozměrech, do které vygeneruje náhodné bludiště zavoláním metody ZpracujPolicko s výchozími souřadnicemi 0,0 (levý horní roh). Mapa (matice mapa) bude na začátku obsahovat samé nuly (výchozí hodnota pro Int32), což je hodnota značící dosud nezpracovaná pole se všemi čtyřmi přepážkami do všech možných směrů (nahoru, dolů, doleva a doprava) uzavřenými. Po zpracování bude každý z členů matice obsahovat nenulové číslo, které v sobě bude kódovat, přepážky kterých všech směrů jsou v něm otevřeny, tj. do kterých směrů lze přejít na sousední pole.
/// <summary>
/// Vygeneruje a vrátí bludiště zadaných rozměrů
/// </summary>
public static int[,] Vytvor(int sloupcu, int radku)
{
var mapa = new int[radku, sloupcu]; // Vytvoření 2D proměnné pro mapu bludiště
ZpracujPolicko(0, 0, ref mapa); // Vygenerování průchodů bludiště z výchozí souřadnice 0,0
return mapa; // Vrácení mapy
}
Metoda ZpracujPolicko zpracovává jedno políčko (buňku) referenčně předávané mapy mapa na zadaných souřadnicích posX a posY a toto zpracování rekurzivně posílá dál všem jeho dosud nezpracovaným sousedům v náhodném pořadí. Náhodného zpracování jednotlivých sousedů a přechodů na ně je docíleno procházením pomocného seznamu smery, který obsahuje všechny čtyři směry z výčtu Smer, jež jsou v tomto seznamu zamíchány pomoci LINQ seřazení OrderBy dle náhodného čísla vygenerovaném přímo v daném lambda výrazu. Díky zamíchání seznamu pak mohou být směry zpracovány již v klasickém foreach cyklu. V něm jsou nejprve určeny souřadnice sousední buňky, na kterou daný směr vede (newX, newY). Pokud tyto souřadnice nejsou mimo rozsah mapy a toto sousední políčko dosud nebylo zpracováno (jeho hodnota je 0), je v aktuálním políčku zrušena přepážka tímto směrem a u souseda zrušena přepážka vedoucí na toto políčko (opačný směr než před tím). Toto zrušení přepážek je realizováno funkcí binární OR (značeno jednou svislou čárou "|"), která skombinuje dvě celá čísla (int) do jednoho na binární úrovni (např. 0010 | 0100 = 0110, tj. 2 | 4 = 6). Po úspěšném zpracování každého ze směrů je zpracování rekurzivně předáno na políčko v tomto směru sousedící. Díky tomu jsou postupně zpracována všechna políčka na mapě (v matici), tzn. všechna z nich jsou propojena náhodným postupem zpracování po celé mapě.
/// <summary>
/// Zpracuje jedno políčko bludiště a rekurzí jej pošle dál všem svým sousedům v náhodném pořadí
/// </summary>
private static void ZpracujPolicko(int posX, int posY, ref int[,] mapa)
{
// Vytvoření pomocného seznamu všech směrů, kterými lze z tohoto pole odejít, v náhodném pořadí
var smery = new List<Smer>() // Pomocný seznam všech možných směrů
{
Smer.N, Smer.D, Smer.P, Smer.L // Všechny směry, kterými lze z tohoto pole odejít
}.OrderBy(x => random.NextDouble()); // Náhodné zamíchání položek v seznamu
// Zpracování sousedního políčka pro daný směr
foreach (var smer in smery) // Opakování pro všechny směry v zamíchaném pořadí
{
// Určení souřadnic cílového sousedního políčka v daném směru
var newX = posX + (smer == Smer.P ? 1 : smer == Smer.L ? -1 : 0);
var newY = posY + (smer == Smer.D ? 1 : smer == Smer.N ? -1 : 0);
// Test, jsou-li souřadnice políčka stále v mezích mapy bludiště
if (newY < 0 || newY >= mapa.GetLength(0) || // Řádky jsou nad nebo pod mapou, nebo...
newX < 0 || newX >= mapa.GetLength(1)) // ... sloupce jsou před či za mapou ...
continue; // ... přeskočení zpracování daného směru
if (mapa[newY, newX] != 0) // Ověření, nebyl-li již na cílovém políčku
continue; // ... pokud tam již byl, daný směr je přeskočen
mapa[posY, posX] |= (int)smer; // Zrušení přepážky mezi tímto z tohoto políčka na sousední pro daný směr
mapa[newY, newX] |= (int)Protismer[smer]; // Zrušení přepážky ze sousedního políčka sem pro opačný směr
ZpracujPolicko(newX, newY, ref mapa); // Předání zpracování sousednímu políčku, na které se právě zrušila přepážka
}
}
Mapa bludiště je vygenerována, tak si ji tedy vykreslíme, alespoň do okna konzole. To obstará metoda Vypis, které se předá vygenerovaná mapa a ona ji vypíše pomocí standardních znaků podtržítka (_) a svislé čáry (|). Při postupném vypisování mapy bude stačit vykreslovat pouze dolní a pravé přepážky, plus horní a levý okraj mapy, díky čemuž budou pro každé další políčko levé a horní přepážky již takto vykresleny od jejich předchůdců. Zatímco podtržítko je prázdným znakem s čárou až u své spodní hrany a lze tak použít pro vykreslení jak průchozího prostoru, tak i spodní přepážky zároveň, znak svislé čáry má tuto čáru uprostřed tohoto znaku a s podtržítkem stejně skombinovat nelze, čímž nevyhovuje naznačení průchodnosti pole s pouhou přepážkou napravo, a musí se tak ve výpisu v konzoli skombinovat se znakem mezery (tj. " |", "_|", "_ " nebo " ").
_ _ _ |_|_|_| |_|_|_|
Díky tomu způsobu výpisu bude mít mapa bludiště ve výpisu do šířky dvojnásobný počet znaků než je jeho skutečná šířka, zatímco do výšky bude počet znaků korespondovat s jeho skutečnou výškou, což je v důsledku i výhodnější, neboť znaky v konzoli mají cca dvojnásobnou výšku než šířku. Pro každý sloupec tedy bude vypsáno nejprve buď podtržítko (dolů projít nelze) nebo mezera (dolů projít lze) a následně (druhý znak) buď svislá čára (doprava projít nelze) či mezera (doprava projít lze).
/// <summary>
/// Vypsání mapy bludiště do konzolového okna
/// </summary>
/// <param name="mapa">Mapa vygeneroaného bludiště</param>
public static void Vypis(int[,] mapa)
{
// Horní hranice
Console.Write(" "); // Mezera odsazení
for (int j = 0; j < mapa.GetLength(1); j++) // Opakování pro všechny sloupce
Console.Write(" _"); // Výpis mezery a čáry
Console.WriteLine(); // Zalomení řádku
// Řádky bludiště
for (int i = 0; i < mapa.GetLength(0); i++) // Opakování pro všechny řádky
{
Console.Write(" |"); // Levá hranice
for (int j = 0; j < mapa.GetLength(1); j++) // Opakování pro všechny sloupce
{
var d = (Smer)mapa[i, j]; // Načtení hodnoty buňky (směrů s otevřenými dveřmi)
Console.Write(d.HasFlag(Smer.D) ? " " : "_"); // Vypsání průchodu/dveří dolů
Console.Write(d.HasFlag(Smer.P) ? " " : "|"); // Vypsání průchodu/dveří doprava
}
Console.WriteLine(); // Zalomení řádku
}
}
Třída Bludiste nyní již obsahuje vše potřebné, můžeme tedy vyzkoušet bludiště vygenerovat a vypsat. V hlavní metodě aplikace (Program.Main) zavoláme nejprve metodu Vytvor, která nám vrátí mapu bludiště jako 2D pole (matici) celých čísel zadaných rozměrů a tuto mapu necháme následně vypsat metodou Vypis. Na konec metody přidáme příkaz Consola.ReadLine, který zastaví běh programu (jeho okamžité vypnutí), dokud nestiskneme klávestu Enter.
class Program
{
static void Main(string[] args)
{
var mapa = Bludiste.Vytvor(12, 6); // Vygenerování mapy s přepážkami
Bludiste.Vypis(mapa); // Vypsání mapy s přepážkami
Console.ReadLine(); // Vyčkání s koncem programu na stisk Enteru
}
}
Výstup v konzolovém okně pak může vypadat například takto (3 různá spuštění pro rozměr 12x6).
Výstupem je tedy plnohodnotné bludiště, v němž je přístupné každé z jeho políček (žádné není uzavřeno ze všech čtyř stran, ani žádná oblast není zcela uzavřena) a zároveň zde není žádné pole zcela otevřené (není zde zbytečně volný prostor větší než 4x4). Větší bludiště (35x20) pak může vypadat například následovně.
Konverze na blokové bludiště
Vytvořené bludiště je tedy bludištěm s přepážkami. To znamená, že na každé jeho políčko lze někudy vstoupit a to, mezi kterými dvěma políčky lze či nelze přejít určují přepážky, které mají vzhledem k políčkům nulovou tloušťku. Toto se dobře vykresluje čarami ve čtvercové síti (gridu / tabulce), nicméně pokud má mít hra, pro kterou je bludiště určeno, nějaký prostorový charakter, ať již 2D (např. viz Mission game) nebo i 3D, je třeba z přepážek udělat samostatné prostorové čtvercové bloky, o velikosti samotných políček. Postup této konverze si ukážeme na bludišti o rozměrech 5x5, kód jehož mapy je následující.
var mapa = new int[,] {
{2, 4, 2+4+8, 4+8, 2+8},
{1+4, 2+8, 1, 2+4, 1+2+8},
{2, 1+4, 4+8, 1+8, 1+2},
{1+2, 2+4, 4+8, 2+8, 1+2},
{1+4, 1+4+8, 8, 1+4, 1+8}
};
|
 |
Celý postup konverze si rozkresleme do několika kroků. Jelikož se přepážky (A) mají stát prostorovými bloky, je třeba rozměry bludiště nejprve zdvojnásobit (B). V dalším kroku pak pro každé původní políčko, kde byla přepážka vpravo nebo dole, přidáme blok zdi do nového dvojbloku k pravé případně k dolní straně dvojbloku (C).
Jak se která přepážka promítne do kterých dvou bloků zdí, ukazuje následující barevně vyznačený obrázek.
V určitých případech však dochází k tomu, že blok zdi není dosazen až do rohů a vzniká tak diagonálně průchozí políčka. To ukazuje následující výřez konverze. Políčko s původními souřadnicemi 0,2 (souřadnice jsou uváděny jako index řádku a index sloupce, jako v maticích) nemá dole ani vpravo žádnou přepážku, ta ani nepřidá žádný blok. Políčko 1,2 pak naopak má přepážku dole i vpravo. Tak je přidán blok zdi na nové souřadnice 3,4 a 3,5 (za dolní přepážku) a na 2,5 a 3,5 (za pravou přepážku). Na souřadnici 3,5 je tak přidána zeď 2x, což sice nevadí, ale chybí tak na souřadnici 1,5, aby zeď nebyla "zubatá" a diagonálně průchozí.
Tento problém však nastává pouze výjimečně na polích s oběma lichými indexy a chybějící zeď lze identifikovat z přítomnosti zdi pod nebo napravo od tohoto políčka v nové mapě. Díky tomu není problém na nové mapě provést korekci, která problém opraví. Celý kód konverze, včetně této korekce uvádí následující metoda Konverze.
/// <summary>
/// Konverze mapy bludiště s dveřmi (průchody) na blokové bludiště, kde jsou zdi tvořeny samostatnými bloky
/// </summary>
/// <param name="mapaP">Vstupní, vygenerované bludiště s dveřmi (průchody), značenými číselnými hodnotami (Direction)</param>
/// <returns>Výstupní blokové bludiště, kde false = průchozí blok, true = neprůchodný blok (zeď)</returns>
public static bool[,] Konverze(int[,] mapaP)
{
// Vytvoření 2D proměnné pro konvertovanou mapu bludiště, dvojnásobné velikosti než zdrojové
var mapaB = new bool[mapaP.GetLength(0) * 2, mapaP.GetLength(1) * 2];
// Konverze bludiště
for (int i = 0; i < mapaP.GetLength(0); i++) // Pro všechny řádky zdrojové mapy
for (int j = 0; j < mapaP.GetLength(1); j++) // Pro všechny sloupce zdrojové mapy
{
var d = (Smer)mapaP[i, j]; // Načtení hodnoty určující otevřené dveře
if (!d.HasFlag(Smer.P)) // Nejsou-li otevřeny dveře doprava, pak...
{
mapaB[i * 2, j * 2 + 1] = true; // ... vlož zeď do nové mapy o jeden blok doprava
mapaB[i * 2 + 1, j * 2 + 1] = true; // ... vlož zeď do nové mapy o jeden blok doprava dolů
}
if (!d.HasFlag(Smer.D)) // Nejsou-li otevřeny dveře dolů, pak...
{
mapaB[i * 2 + 1, j * 2] = true; // ... vlož zeď do nové mapy o jeden blok dolů
mapaB[i * 2 + 1, j * 2 + 1] = true; // ... vlož zeď do nové mapy o jeden blok doprava dolů
}
}
// Korekce (doplnění) lichých bloků, které konverze nedoplnila
for (int i = 1; i < mapaB.GetLength(0) - 1; i += 2) // Pro všechny liché řádky v nové mapě
for (int j = 1; j < mapaB.GetLength(1) - 1; j += 2) // Pro všechny liché sloupce v nové mapě
if (mapaB[i, j + 1] || mapaB[i + 1, j]) // Je-li napravo či pod zeď, pak...
mapaB[i, j] = true; // ... vlož zeď i sem
return mapaB;
}
Výstupem konverze je opět matice, tentokrát ovšem nikoli číselná, ale logických hodnot. Logická hodnota false v ní značí průchozí blok, logická hodnota true pak neprůchozí blok (zeď). Dále přidáme metodu, která tuto novou blokovou mapu bludiště vypíše do konzolového okna. Pro průchozí pole je zde již pouze mezera a pro blok se zdí je tentokrát použit znak vyplněného obdélníku, který lze nalézt přes mapu znaků. Výpis samotný je pak jednodušší než u verze s přepážkami, protože jedno políčko je vždy právě jeden znak.
/// <summary>
/// Vypsání mapy blokového bludiště do konzolového okna
/// </summary>
/// <param name="mapa">Mapa vygeneroaného bludiště</param>
public static void VypisBloku(bool[,] mapa)
{
Console.WriteLine(" ".PadRight(mapa.GetLength(1)+2, '█')); // Horní hranice bludiště
for (int i = 0; i < mapa.GetLength(0); i++) // Pro všechny řádky v mapě
{
Console.Write(" █"); // Levá hranice bludiště
for (int j = 0; j < mapa.GetLength(1); j++) // Pro všechny sloupce v mapě
Console.Write(mapa[i, j] ? "█" : " "); // Vypsání bloku (mezery nebo zdi)
Console.WriteLine(); // Zalomení řádku
}
}
Nyní použijeme znovu všechny metody v hlavní části programu.
class Program
{
static void Main(string[] args)
{
var mapa = Bludiste.Vytvor(12, 6); // Vygenerování mapy s přepážkami 12x6
Bludiste.Vypis(mapa); // Vypsání mapy s přepážkami
Console.WriteLine(); // Prázdný řádek
var maze = Bludiste.Konverze(mapa); // Konverze mapy s přepážkami na blokovou mapu
Bludiste.VypisBloku(maze); // Vypsání blokové mapy
Console.ReadLine(); // Vyčkání s koncem programu na stisk Enteru
}
}
Výsledné výstupy pak mohou vypadat například následovně (3x mapa o rozměrech 12x6).
Jak je z výstupů patrné, na šířku jsou mapy ve výpisu stejně široké, protože přepážková verze používala pro výpis každé buňky dva znaky na šířku. Bloková verze je pak ovšem dvojnásobná i na výšku. Ve větším rozměru (35x12) pak samostatná bloková mapa může vypadat například následovně.
