Pracuję nad realizacją algorytmu A-Star w C # w jedności.

Muszę ocenić kolekcję węzła :

class Node
    {
        public Cell cell;
        public Node previous;
        public int f;
        public int h;

        public Node(Cell cell, Node previous = null, int f = 0, int h = 0)
        {
            this.cell = cell;
            this.previous = previous;
            this.f = f;
            this.h = h;
        }
    }

Mam sortowany , który pozwala mi przechowywać kilka węzeł , posortowany przez H nieruchomości. Chociaż muszę być w stanie przechowywać dwa węzły z tym samym obiektem H . Dlatego wdrożyłem konkretny ICOMPARER , w pewien sposób, który pozwala mi sortować właściwość H i równości triggranicznej tylko wtedy, gdy dwa węzły reprezentują dokładnie tę samą komórkę.

class ByHCost : IComparer<Node>
    {
        public int Compare(Node n1, Node n2)
        {
            int result = n1.h.CompareTo(n2.h);
            result = (result == 0) ? 1 : result;
            result = (n1.cell == n2.cell) ? 0 : result;
            return result;
        }
    }

Mój problem: Mam trudność do usunięcia rzeczy z moich sortowanej (nazwałem go OpenseT ). Oto przykład:

W pewnym momencie algorytm muszę usunąć węzeł z listy na podstawie niektórych kryteriów (NB: używam ISCell127 zmiennej, aby skupić moje debugowanie na unikalnej komórce)

int removedNodesNb = openSet.RemoveWhere((Node n) => {
    bool isSame = n.cell == candidateNode.cell;
    bool hasWorseCost = n.f > candidateNode.f;

    if(isCell127)
    {
       Debug.Log(isSame && hasWorseCost); // the predicate match exactly one time and debug.log return true
    }

    return isSame && hasWorseCost;
});

if(isCell127)
{
   Debug.Log($"removed {removedNodesNb}"); // 0 nodes where removed
}

Tutaj metoda Removewhere wydaje się znaleźć dopasowanie, ale nie usuwa węzła. Próbowałem inny sposób:

 Node worseNode = openSet.SingleOrDefault(n => {
      bool isSame = n.cell == candidateNode.cell;
      bool hasWorseCost = n.f > candidateNode.f;
      return isSame && hasWorseCost;
 });

 if(isCell127)
 {
      Debug.Log($"does worseNode exists ? {worseNode != null}"); // Debug returns true, it does exist.
 }

 if(worseNode != null)
 {
      if(isCell127)
      {
          Debug.Log($"openSet length {openSet.Count}"); // 10
      }
      openSet.Remove(worseNode);
      if(isCell127)
      {
          Debug.Log($"openSet length {openSet.Count}"); // 10 - It should have been 9.
      }
 }

Myślę, że problem jest związany z moim dość niezwykłym ickomparrem, ale nie mogę zrozumieć tego, co z wyjątkiem problemu.

Chciałbym również wiedzieć, czy istnieje znaczna poprawa wydajności na temat korzystania z auto sortowanej zamiast listy sortowanej ręcznie, zwłaszcza w przypadku użycia algorytmu A-star.

0
SimStuch 27 marzec 2020, 18:23

2 odpowiedzi

Najlepsza odpowiedź

Odpowiem na własny temat, ponieważ mam całkiem kompletny.

porównanie

Porównanie interfejsu ICOMPARER musi przestrzegać niektórych zasad. Jak powiedział @frenchy, moje własne porównanie zostało złamane. Oto podstawy matematyczne porównania I Cumally Forgot (znalazłem je Tutaj ):

1) A.CompareTo(A) must return zero.

2) If A.CompareTo(B) returns zero, then B.CompareTo(A) must return zero.

3) If A.CompareTo(B) returns zero and B.CompareTo(C) returns zero, then A.CompareTo(C) must return zero.

4) If A.CompareTo(B) returns a value other than zero, then B.CompareTo(A) must return a value of the opposite sign.

5) If A.CompareTo(B) returns a value x not equal to zero, and B.CompareTo(C) returns a value y of the same sign as x, then A.CompareTo(C) must return a value of the same sign as x and y.

6) By definition, any object compares greater than (or follows) null, and two null references compare equal to each other.

W moim przypadku zasada 4) - Symetria - została złamana.

Musiałem przechowywać wiele węzła z tą samą własnością H, ale także do sortowania przez właściwość H. Musiałem więc uniknąć równości, gdy właściwość H są takie same.

To, co zdecydowałem się zrobić, zamiast domyślnej wartości, gdy h Porównanie prowadzi do 0 (co złamała 4 regułę), doprowadza porównanie w sposób, który nigdy nie prowadzi do 0 z unikalną instancją węzła Foreach. Cóż, ta realizacja prawdopodobnie nie jest najlepsza, może jest coś lepszego do zrobienia dla wyjątkowej wartości, ale tutaj jest to, co zrobiłem.

private class Node
{
   private static int globalIncrement = 0;

   public Cell cell;
   public Node previous;
   public int f;
   public int h;
   public int uid;

   public Node(Cell cell, Node previous = null, int f = 0, int h = 0)
   {
       Node.globalIncrement++;

       this.cell = cell;
       this.previous = previous;
       this.f = f;
       this.h = h;
       this.uid = Node.globalIncrement;
   }
}

private class ByHCost : IComparer<Node>
{
   public int Compare(Node n1, Node n2)
   {
       if(n1.cell == n2.cell)
       {
           return 0;
       }

       int result = n1.h.CompareTo(n2.h);
       result = (result == 0) ? n1.uid.CompareTo(n2.uid) : result; // Here is the additional comparison which never lead to 0. Depending on use case and number of object, it would be better to use another system of unique values.
       return result;
   }
}

Metoda wyjścia

Wyjść, użyj predykatu, aby spojrzeć w kolekcję, więc nie pomyślałem, że troszczy się o porównanie. Ale wyjść do użycia wewnętrznie usuń metodę, która dbają o porównanie. Tak więc, nawet jeśli wyjmowanie znalazło jeden element, jeśli porównanie jest niekonsuźne, cicho przekaże drogę. To dość dziwne wdrożenie, nie?

1
SimStuch 28 marzec 2020, 13:06

Jeśli piszę twój test:

          n1.h < n2.h
          n1.cell = n2.cell -> final result = 0

          n1.h > n2.h
          n1.cell = n2.cell -> final result = 0 

          n1.h = n2.h
          n1.cell != n2.cell -> final result = 1      

          n1.h < n2.h
          n1.cell != n2.cell -> final result = -1  

          n1.h > n2.h
          n1.cell != n2.cell -> final result = 1 

Gdy masz równość na wartości H (numer testowy 3), wybierzesz zawsze ten sam wynik -> 1. Więc nie ma dobrego, musisz mieć inny test na komórce, aby wyjaśnić pozycję Bacause, jest zamieszanie z innym testem, który daje Ten sam wynik (numer testowy 5)

Mógłbym przetestować z próbką, ale jestem pewien, że łamiesz rodzaj.

Więc jeśli wyjaśniasz test, proponuję użyć Linq z listą ... jego najlepszą wydajnością.

1
Frenchy 27 marzec 2020, 20:00