If condition bash alike - check and assignment

Question

I am implementing A* algorithm and I am stuck with the following piece of pseudo code :

 if neighbor not in openset or tentative_g_score <= g_score[neighbor] 
     came_from[neighbor] := current
     g_score[neighbor] := tentative_g_score
     f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)
     if neighbor not in openset
         add neighbor to openset

I want to optimize the openset checking so that I won't check if a node is openset twice in one algorithm pass.

I know that in bash there is something like :

if(( false == openedList_.ContainsNodeXY(n.X, n.Y)) && 
     InOpenSet = false ){ .... }

With this I would have information about node being in or not in the openset.

How can I do this in C# ?

EDIT openList_ is a List ( I have to have it sorted ) so it can't be a HashSet.

score 0 · Answer 1 · edited May 23 '17 at 12:27

0

You can use the HashSet<T> object in C# for this. HashSet will quickly be able to tell you if an object is a member of the Set.

HashSet has Add and Contains methods.

Based on your comment you probably want SortedList. It will not be faster, HashSet is O(1) in most cases. SortedList will be O(n) on insert. SortedList also has Contains (since they both implement IDictionary).

See this helpful answer.

edited May 23 '17 at 12:27

Community

1
1

answered Dec 30 '12 at 15:43

Hogan

69,564
10
76
117

1. I need this to be a List (I appropriately sort it) 2. I thought that I can do it additional bool - as I think this will be faster than (even! HashSet) check – Patryk Dec 30 '12 at 15:48

score 0 · Answer 2 · answered Dec 30 '12 at 16:27

I think what A* requires is a priority queue that also supports fast Contains. SortedSet<T> is this class. As far as I understand it it is a Red-Black-Tree.

Warning: Don't use the SortedList<T> classes from the BCL. It is legacy stuff based on a horrible O(n^2) algorithm.

If condition bash alike - check and assignment

2 Answers2