Diskuze: Generátor bludiště - nahrazení switch

V předchozím kvízu, Test znalostí C# .NET online, jsme si ověřili nabyté zkušenosti z kurzu.

Aktivity

Petr Nymsa

Tvůrce

Petr Nymsa:21.4.2013 13:21

Ahoj, udělal jsem si jednoduchý generátor bludiště. Jeho rychlost není nijak závratná, taže zkouším různě optimalizovat (což mi nikdy moc nešlo). Každopádně pokusil jsem se o rekurzi. Problém je že je tam stále ošklivý switch, který určuje směr pokládání zdí. Myslíte že půjde nějak nahradit ?
Generátor je vlastně ten co je zde popsán, ještě zkusím algoritmus prohledávání do hloubky, ale to až časem.

Mám tedy pole, kde si připravím základny. Základna je místo odkud se vždy začne generovat zeď. Jakmile narazím na Ntou základnu nebo na ze´d ukončím pokládání a vyberu náhodně další základnu a směr. Připravení základen mám takto.

private void PrepareBase()
       {
           for (int x = 0; x < sizeX; x++)
           {
               for (int y = 0; y < sizeY; y++)
               {
                   if (x == 0 || x == sizeX - 1 || y == 0 || y == sizeY - 1)
                   { pole[x, y] = 1; }// základní zeď
                   else if (x % 2 == 0 && y % 2 == 0 && !(x == 0 || x == sizeX - 2 || y == 0 || y == sizeY - 2))
                   { pole[x, y] = 2; position.Add(new Position(x, y)); Base.Add(new Position(x, y)); }

               }

           }
       }

Základna je v poli představována 2. List position uchováv pozice základen a slouží i jako indikátor zbývajícich základen. List Base uchovává taktéž základny kvůli debugu. Tj není potřeba pro správné vygenerování.

Zde je metoda která generuje. Ten swtich se mi tam nelíbí ale nevím jak ho nahradit.

private bool Put(Position put, int smer, int n)
        {
            int pocet = 0;
                if (n < 2)
                    n = 2;

                switch (smer)
                {
                    case 0: // vlevo
                        for (int x = put.X; x > 0; x--)
                        {
                            if (pole[x, put.Y] == 2)
                            {
                                pole[x, put.Y] = 1;
                                position.Remove(new Position(x, put.Y));
                                pocet++;
                                if (pocet >= n)
                                    break;
                            }
                            else if (pole[x, put.Y] == 0)
                                pole[x, put.Y] = 1;
                            else break;
                        }

                        break;
                    case 1: //vpravo
                        for (int x = put.X; x < sizeX; x++)
                        {
                            if (pole[x, put.Y] == 2)
                            {
                                pole[x, put.Y] = 1;
                                position.Remove(new Position(x, put.Y));
                                pocet++;
                                if (pocet >= n)
                                    break;
                            }
                            else if (pole[x, put.Y] == 0)
                                pole[x, put.Y] = 1;
                            else break;
                        }

                        break;
                    case 2: // nahoru
                        for (int y = put.Y; y > 0; y--)
                        {

                            if (pole[put.X, y] == 2)
                            {
                                pole[put.X, y] = 1;
                                position.Remove(new Position(put.X, y));
                                pocet++;
                                if (pocet >= n)
                                    break;
                            }
                            else if (pole[put.X, y] == 0)
                                pole[put.X, y] = 1;
                            else break;
                        }

                        break;
                    case 3: //dolu
                        for (int y = put.Y; y < sizeY; y++)
                        {
                            if (pole[put.X, y] == 2) // nalezl základnu
                            {
                                pole[put.X, y] = 1; // položí zed
                                position.Remove(new Position(put.X, y)); // vymaže základnu
                                pocet++;
                                if (pocet >= n)
                                    break;
                            }
                            else if (pole[put.X, y] == 0)
                                pole[put.X, y] = 1;
                            else break;
                        }
                        break;
                }
                if (position.Count == 0)
                    return true;
                else
                    return Put(position[rnd.Next(0, position.Count)], rnd.Next(0, 4), rnd.Next(0, position.Count)); ;


        }

Proměnná n indikuje počet základen , které potkám než zastavím generování. Podmínka s n je jenom taková vychytávka, aby se nevygenerovala jenom zeď o jednom políčku.

Nějaká rada jak to urychlit / vylepšit ? Napadlo mě použít zásobník, ale nevím jak ho využít s náhodným generováním.

Editováno 21.4.2013 13:22

Odpovědět

21.4.2013 13:21

Pokrok nezastavíš, neusni a jdi s ním vpřed

Antonín Jehlář

Člen

Antonín Jehlář:24.8.2020 20:23

Sice trochu pozdě, ale pokud jde čistě o switch, tak se dá určitě zjednodušit. Začal bych stejnými částmi a to tak, že bych je odstranil tedy vyšlo by:

int border = 0;
int step = 0;
          switch (smer)
          {
              case 0: // vlevo
                  border = -sizeX;
                  step = -2;
              case 1: //vpravo
                  border += sizeX;
                  step += 1;
                  for (int x = put.X; x != border; x += step)
                  {
                      if (pole[x, put.Y] == 2)
                      {
                          pole[x, put.Y] = 1;
                          position.Remove(new Position(x, put.Y));
                          pocet++;
                          if (pocet >= n)
                              break;
                      }
                      else if (pole[x, put.Y] == 0)
                          pole[x, put.Y] = 1;
                      else break;
                  }

                  break;
              case 2: // nahoru
                  border = -sizeY;
                  step = -2;
              case 3: //dolu
                  border += sizeY;
                  step += 1;
                  for (int y = put.Y; x != border; x += step)
                  {
                      if (pole[put.X, y] == 2) // nalezl základnu
                      {
                          pole[put.X, y] = 1; // položí zed
                          position.Remove(new Position(put.X, y)); // vymaže základnu
                          pocet++;
                          if (pocet >= n)
                              break;
                      }
                      else if (pole[put.X, y] == 0)
                          pole[put.X, y] = 1;
                      else break;
                  }
                  break;
          }

Okay, takže počet cyklů se nám s mírnými úpravami změnil na polovinu.
Jenže to pořád není to co chceme pořád tam máme switch který nechceme a 2 velmi podobné cykly.
Ok tak se zbavíme duplicity - vytáhneme cyklus ven:

int border = 0;
int step = 0;
int defaultI;
int IX;
int IY;
int stepX;
int stepY;

switch (smer)
{
        case 0: // vlevo
                border = 0;
                step = -1;
                defaultI = put.X;
                IX = defaultI;
                IY = put.Y;
                stepX = step;
                stepY = 0;
                break;
        case 1: //vpravo
                border = sizeX;
                step = 1;
                defaultI = put.X;
                IX = defaultI;
                IY = put.Y;
                stepX = step;
                stepY = 0;
                break;
        case 2: // nahoru
                border = 0;
                step = -1;
                defaultI = put.Y;
                IX = put.X;
                IY = defaultI;
                stepX = 0;
                stepY = step;
                break;
        case 3: //dolu
                border = sizeY;
                step = 1;
                defaultI = put.Y;
                IX = put.X;
                IY = defaultI;
                stepX = 0;
                stepY = step;
                break;
}

for (int i = defaultI; i != border; i += step)
{
        if (pole[IX, IY] == 2) // nalezl základnu
        {
                pole[IX, IY] = 1; // položí zed
                position.Remove(new Position(IX, IY)); // vymaže základnu
                pocet++;
                if (pocet >= n)
                        break;
        }
        else if (pole[IX, IY] == 0)
                pole[IX, IY] = 1;
        else break;
        IX += stepX; // Přibylo
        IY += stepY; // Přibylo
}

Dobře ale pořád máme ošlkivý switch který nás nutí nastavovat spousty věcí. Začít bychom opět mohli tím, že vynecháme duplicity. Ovšem zde už je porovnání obsahu switche více zřejmé. Můžeme tedy celý obsah switche vytáhnout ven a učinit tak změny vně:

int shift = (smer % 2) ? 0 : 2;

int border = 0;
int step = -1 + shift;
int defaultI, IX, IY, stepX, stepY;

if (smer < 2) {
        defaultI = put.X;
        IX = defaultI;
        IY = put.Y;
        stepX = step;
        stepY = 0;
        border += sizeX * (shift >> 1);
} else {
        defaultI = put.Y;
        IX = put.X;
        IY = defaultI;
        stepX = 0;
        stepY = step;
        border += sizeY * (shift >> 1);
}

for (int i = defaultI; i != border; i += step)
{
        if (pole[IX, IY] == 2) // nalezl základnu
        {
                pole[IX, IY] = 1; // položí zed
                position.Remove(new Position(IX, IY)); // vymaže základnu
                pocet++;
                if (pocet >= n)
                        break;
        }
        else if (pole[IX, IY] == 0)
                pole[IX, IY] = 1;
        else break;
        IX += stepX; // Přibylo
        IY += stepY; // Přibylo
}

Toto je asi finální kód, který by mohl nahradit switch. Ovšem switch je sice méně přehledný, ale zato bude zabírat méně systémového času. (není tam zbytek po dělení, if a násobení a je tam o dvě inkrementace v cyklu méně) Ovšem zde se eliminují duplicity a razantně se zvyšuje použitelnost toho cyklu. Toto řešení je zase náročnější na představivost, jelikož musíš například v inkrementační části cyklu pochopit, že step může být i záporný.
If lze taky vynechat, ale to už je jiná písnička.

Nahoru Odpovědět

24.8.2020 20:23

Předstírat hloupost na správném místě je někdy velice moudré.

Naučíme tě pracovat na home-office.

Zjistit více...

Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 2 zpráv z 2.