Diskuze: LINQ - Nalezení cesty

Petr Nymsa

Tvůrce

Petr Nymsa:18.5.2013 17:42

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 .

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

David Hartinger

Vlastník

David Hartinger:18.5.2013 17:56

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

New kid back on the block with a R.I.P

Petr Nymsa

Tvůrce

Petr Nymsa:18.5.2013 18:10

Jj díky Ale nemůžu přijít úplně jak na to . Š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

Petr Nymsa

Tvůrce

Petr Nymsa:18.5.2013 18:34

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

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 4 zpráv z 4.