Diskuze: LINQ - Nalezení cesty

C# .NET .NET (C# a Visual Basic) LINQ - Nalezení cesty American English version English version

Avatar
Petr Nymsa
Redaktor
Avatar
Petr Nymsa:

Už jsem tu zas a tentokrát bych potřeboval poradit nebo říct jestli je vůbec možné využít LINQ pro nalezení cesty. Dnes předělávám své staré kódy a nyní přišel na řadu algoritmus vlny.

Šíření vlny jsem zkrátil o dobrý 2/3 řádků, je to snad i rychlejší a hezčí. Vlna jak se šíří tak si zaznmenává kde byla -> List objektů PointID (x,y, id). Kvůli šíření je to ještě zapsáno do pole int, kde každé číslo znamená fázi vlny. Tedy oo startu se vlna šíří 1,2,3,4,5,......

Můžu si cestu zpět získat projetím pole od cíle ke startu a to tak že hledám vždy menší číslo nebo mám ještě právě List kde bych chtěl použít LINQ, který by mi ideálně rovnou vrátil List pozic -> cesta od startu k cíli.

Je možné přes LINQ zkombinovat nějakým způsobem cyklus, ubírání hledané hodnoty ? Vždy se vlastně potřebuju mrknout z aktuální pozice všemi 4 směry a hledám o 1 menší hodnotu než na pozici na které stojím.

Zkoušel jsem něco jako toto. No občas to ještě nefunguje :D.

int value = points.Where(obj => curr.X == obj.X && curr.Y == obj.Y).First().ID;

           for (int k = 0; k < points.Count; k++)
           {
               PointID point = points.Where(obj => obj.ID == value).First();
               path.Add(new Point(point.X, point.Y));
               value--;
               if (value == 0)
                   break;
           }

Moje hlavní otázka zní. Použít LINQ -> zkombinovat dotazy nebo prostě použít jeden cyklus a hledat políčka o 1 menší ? Jak moc LINQ brzdí výkon ? Díky :)

Odpovědět 18.5.2013 17:42
Pokrok nezastavíš, neusni a jdi s ním vpřed
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Petr Nymsa
David Čápka:

LINQ to Objects dělá všechny operace v čase O(n), což je stejné jako bys to projel ručně cyklem (on to samozřejmě i tak překládá, jinak to udělat nejde). Takže když ho použiješ rozumně, mělo by to být stejné.

Nahoru Odpovědět 18.5.2013 17:56
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Petr Nymsa
Redaktor
Avatar
Odpovídá na David Čápka
Petr Nymsa:

Jj díky :) Ale nemůžu přijít úplně jak na to :D. Šlo by to napsat na "jeden řádek" -> napíšu takový pseudo kod

path = Najdi kde HODNOTA POZICE je o 1 menší, pozice = nová pozice

Nevím, jestli je to pochopitelné, každopádně jsem na pozici (8,8) s hodnotou 7, hledám tedy pozici aktuální pozice -1, tedy bud 7,8;8,9;8,6,;8,7 -> poté vlastně hledám z té nové pozice a takhle až naleznu pozici Start -> mám cestu.

Jde to vůbec spojit přes několik dotazů v LINQ ? Nebo to je hloupost ? :)

Nahoru Odpovědět 18.5.2013 18:10
Pokrok nezastavíš, neusni a jdi s ním vpřed
Avatar
Petr Nymsa
Redaktor
Avatar
Odpovídá na David Čápka
Petr Nymsa:

Bez použití LINQ to mám takto. Metoda IsNearFinish() kontroluje jeslti už nejsem náhodou blízko hledané pozice - start,cíl, nepřítel,...

bool loop = true;
           while (loop)
           {
               loop = false;
               x = curr.X;
               y = curr.Y;
               for (int k = 0; k < vectors.Length; k++)
               {
                   if (k < 2)
                       x += vectors[k];
                   else y += vectors[k];

                   if (x >= 0 && x < arr.GetLength(0) && y >= 0 && y < arr.GetLength(1) && arr[x, y] == id - 1 && !IsNearFinish(new Point(x,y),start))
                   {
                       path.Add(new Point(x, y));
                       curr = new Point(x, y);
                       id = arr[x, y];
                       loop = true;

                   }
               }
           }
Nahoru Odpovědět 18.5.2013 18:34
Pokrok nezastavíš, neusni a jdi s ním vpřed
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 4 zpráv z 4.