[Solved]Question about Dictionary.Any Vs Dictionary.ContainsKey

Hey guys,


Could anyone please explain to me why...

Code (CSharp):

1. if (aDictionary.Any(p => p.Key == aVector2))

...returns True when the Key is present, and....

Code (CSharp):

1. if (aDictionary.ContainsKey(aVector2))

...sometimes returns True, and sometimes False, on the exact same situation?

I can't see a difference between the two, and I also have no idea why .ContainsKey is returning apparently-crazy values. All I know is .Any is extremely slow, and I need to get rid of it.

 

This is because of how == operator and GetHashCode method are implemented for the Vectors in unity (2,3, and 4).

Here is the implementation of == in Vector3 (it's basically the same in Vector2):

Code (csharp):

1.  
2.     public static bool operator ==(Vector3 lhs, Vector3 rhs)
3.     {
4.       return (double) Vector3.SqrMagnitude(lhs - rhs) < 9.99999943962493E-11;
5.     }
6.  

Note that it checks if the value is 'close' by seeing if it's within some epsilon. It's not actually testing if x,y,z are equal, it tests if they're very very close with some minor error tolerance.

Where as GetHashCode is:

Code (csharp):

1.  
2.     public override int GetHashCode()
3.     {
4.       return this.x.GetHashCode() ^ this.y.GetHashCode() << 2 ^ this.z.GetHashCode() >> 2;
5.     }
6.  

Dictionary keys rely on the hashcode generated from the key value to play them in the hashtable (this is why a dict is also known as a hashtable).

But the hashcode relies on the exact values of x,y,z. So 2 vectors slightly off from one another will have different hashcodes.

And since Vector2,3,4 all use floats, they're prone to float error, and thusly don't usually have 'exact' values. There's almost always a slight error to the underlying value and as a result floats should never be trusted for equals.

This is why the == operator of Vector does the 'nearly' equality. And things like Mathf.Approximately exists.

...

Why are you using Vector's as keys anyways? Is it necessary? There probably is a better solution. Especially since the "Any" technique is very slow, unlike ContainsKey.

Note, you can implement your own IEqualityComparer for the dictionary key and pass it into its constructor. With this you could generate more stable hashcodes:
https://docs.microsoft.com/en-us/do...em_Collections_Generic_IEqualityComparer__0__

The algorithm would require figuring out how granular you needed your vectors. Like if you needed them within in a grid of 0.5 unit separation. You could multiply each x,y,z by 2, round, and xor them together.

 

Floating-point rounding error means it's probably a bad idea to use floats or anything containing floats as the keys in your dictionary, but since Unity overloads Vector == to mean approximate equality instead of exact equality, they are actually violating the rules that Dictionary relies on to guarantee correctness and consistency of its algorithms (for instance, "equality" is not transitive, and things that are equal are not guaranteed to have the same hash code), so you should expect a lot of weird bugs if you use vectors as keys.

 

I'm using it for pathfinding -- a Dictionary<Vector2, Vector2> in which the Key is the Node position, and the Value its parent. So the Key must, necessarily, be a Vector2. Maybe I could separate it into an X and a Y Dictionary, but... that would be quite horrible.

I'll have to study that, but I'll see if I can get it to work. Or just forget about Dictionaries and use something else. I'll figure it out tomorrow.

I'm glad it's just a float problem, and not me going crazy, though.

 

Could you use integer coordinates instead of floats? You can just define your own class that's similar to a Vector2 but using int instead of float. Here's one I've used before (you might want to remove the bits at the bottom if you don't otherwise need a Direction enum):

Code (CSharp):

1. using System;
2. using UnityEngine;
3.  
4. [Serializable]
5. public struct Loc
6. {
7.     public int x;
8.     public int y;
9.  
10.     public Loc(int x, int y)
11.     {
12.         this.x = x;
13.         this.y = y;
14.     }
15.     public Loc(Loc other)
16.     {
17.         x = other.x;
18.         y = other.y;
19.     }
20.  
21.     public static Loc Zero { get { return new Loc(0, 0); } }
22.  
23.     public int Mag { get { return x + y; } }    // Magnitude
24.  
25.  
26.     // Arithmetic
27.     public static Loc operator +(Loc l, Loc r)
28.     {
29.         return new Loc(l.x + r.x, l.y + r.y);
30.     }
31.     public static Loc operator -(Loc l, Loc r)
32.     {
33.         return new Loc(l.x - r.x, l.y - r.y);
34.     }
35.     public static bool operator ==(Loc l, Loc r)
36.     {
37.         return l.x == r.x && l.y == r.y;
38.     }
39.     public static bool operator !=(Loc l, Loc r)
40.     {
41.         return !(l == r);
42.     }
43.     public override bool Equals(object obj)
44.     {
45.         return obj is Loc && this == (Loc)obj;
46.     }
47.     public override int GetHashCode()
48.     {
49.         return y ^ (x << 8);
50.     }
51.  
52.  
53.     public override string ToString()
54.     {
55.         return string.Format("({0},{1})", x, y);
56.     }
57.  
58.  
59.     // Allow automatic promotion of a Loc to a Vector2
60.     public static implicit operator Vector2(Loc l)
61.     {
62.         return new Vector2(l.x, l.y);
63.     }
64.     // Allow explicit casting of a Vector2 to a Loc
65.     public static explicit operator Loc(Vector2 v)
66.     {
67.         return new Loc((int)v.x, (int)v.y);
68.     }
69.  
70.  
71.     // Treat a direction as a vector
72.     public static explicit operator Loc(Direction dir)
73.     {
74.         switch (dir)
75.         {
76.             case Direction.East:
77.                 return new Loc(1, 0);
78.             case Direction.North:
79.                 return new Loc(0, 1);
80.             case Direction.West:
81.                 return new Loc(-1, 0);
82.             case Direction.South:
83.                 return new Loc(0, -1);
84.             default:
85.                 throw new ArgumentException("Invalid movement direction: " + dir);
86.         }
87.     }
88.  
89.     public static Loc operator +(Loc start, Direction dir)
90.     {
91.         return start + (Loc)dir;
92.     }
93.     public static Loc operator -(Loc start, Direction dir)
94.     {
95.         return start - (Loc)dir;
96.     }
97. }

 

That's an interesting suggestion, but over-complicated. Too much code to work around a relatively simple issue.

I spent the last half hour or so trying to multiply the Vector2s' X/Y values, Math.Truncate them, then divide by the same factor to nullify the floats' "error margin." This should work. It hasn't yet, because, although conceptually simple, implementing it is rather messy, and I probably misplaced a parenthesis amid hundreds somewhere, but it should work eventually.

 

So you're trying to use a dictionary to create a linked list?

Why not just create a linked list?

To give you an example here are some graph resolvers I've written:

Dijkstra:
https://github.com/lordofduct/space.../SPPathfinding/Graphs/DijkstraPathResolver.cs

A*:
https://github.com/lordofduct/space...ter/SPPathfinding/Graphs/AStarPathResolver.cs

(note - the A* contains a 'stepping' algorithm that allows synchronously solving the path over multiple steps if you can't use threading)

Both use a simple linked list (the VertexInfo class) to trap a path. To save on garbage collection I just pool the objects for reuse in the A* version (never implemented it in Dijkstra yet just cause I don't use dijkstra much).

 

Actually, I'm pretty sure that won't work. Truncating means a float that is slightly smaller than the int you expected is still going to end up with the wrong value. If you absolutely must use this approach--which I recommend against--I believe you want to be rounding your floats instead of doing this multiply-truncate-divide thing.

Also, the equality functions on Vector2 still don't satisfy the requirements that Dictionary expects, so you might still get weird, hard-to-predict bugs that aren't necessarily due to rounding error.

Also, I vehemently disagree with your characterization of this being "simpler" than using integers. The computer is doing substantially more steps, which means more chances for something to go wrong. The math involved is more complicated, as evidenced by the fact that you and I reached different conclusions about whether or not it would work if implemented correctly. And you're talking about misplacing parentheses among hundreds, which suggests the source code is complex, too.

 

I've never heard of "linked lists" before, so I don't know. But yes, I'm using a Dictionary since I only need 2 parameters and retrieving values from dictionaries is pretty fast. It's working just fine, the only problem is this issue with the floats.

You, lordofduct, and others, have actually already helped me with some pathfinding issues in another thread a few months ago. I still have it "favorited" here if the need arises but, again, other than this .Any Vs .ContainsKey issue, everything in my code is currently working perfectly for what I need.


@Antistone

That would only be a problem if the distance between two points was really small. My nodes are 0.5f apart, I just need to get rid of the floats' variation margin and everything should fall into place. I've already printed a few tests, and got all the ContainsKey results to match Any's (well... up to 128 cycles, then I got an exception because of some other issue that rose while I was trying to implement this stuff.)

If things go wrong it's because I made a mistake somewhere, then it's just a matter of finding and fixing it (at least now that, theoretically, the floats' error margin is gone and everything is what it's supposed to be). Otherwise, it's just processing, and the effort required to do Math stuff compared to sorting through the algorithm's closed list is virtually irrelevant. It won't make any real difference in the end.

Either way, by "simpler" I actually meant it's "conceptually" simpler (as you can probably tell by now, I'm not a programmer, so I try to stick to what I fully understand when possible).

The code in itself is quite simple, but I've got to Math.Truncate X and Y separately, in Vector2's that are partly formed by "new Vector2's()," and there's also the need to cast the Truncate result as a float, so... lots of parentheses pop up. I didn't get back to it yet because I'm done for the day, but so far everything indicates this method should work. I'll let you know if/once I manage to get it working.

 

If you're hard set on using this dictionary (which I strongly suggest against doing... use a linked list), then the 'Truncate' trick you're talking about wanting to do can be done implicitly like so:

Code (csharp):

1.  
2. public class VectorNodeEqualityComparer : IEqualityComparer<Vector2>
3. {
4.  
5.     public const float FACTOR = 10f;
6.     private const float HALF_RECIPROCAL = 1f / (FACTORY * 2f);
7.  
8.     public bool Equals(Vector2 a, Vector2 b)
9.     {
10.         //we check if the distance between a and b is less than half the factor (halving to simulate rounding)
11.         //of course done as squares to avoid sqrt cost
12.         return (b - a).sqrMagnitude < HALF_RECIPROCAL * HALF_RECIPROCAL;
13.     }
14.  
15.     public int GetHashCode(Vector2 v)
16.     {
17.         //calculate a hashcode based off the factor
18.         return (int)System.Math.Truncate(v.x * FACTOR) ^ (int)System.Math.Truncate(v.y * FACTOR);
19.     }
20.  
21. }
22.  
23.  
24. Dictionary<Vector2, Vector2> myDict = new Dictionary<Vector2, Vector2>(new VectorNodeEqualityComparer());
25.  

Now if you toss Vector2's into this. It'll automatically compare vector's based on the rules you described. I used a factor of 10 here (so 0.1 distance between vectors), but you could use any factor you want really.

How this works is by passing in this equality comparer you're overriding how Dictionary determines how keys are equal.

Note that 2 very close vectors will be considered equal doing this. So make sure your nodes are always 1/FACTOR distance apart at minimum. This same rule would apply if you did this by hand like you previously mentioned.

...

I STILL strongly suggest against doing this though. This is an overly convoluted manner of creating what is effectively a linked list. Especially since you also must have other data you're holding, like if it's A* the g score and what not.

If you share your code we could probably assist in showing you how to optimize and clean it up.

You may say:

But there in lies the issue... it works up until it doesn't.

Cleaning my floors with ammonia and bleach works really well up until I choke on the chlorine gas.

I could open the windows, turn on a fan, and hope nothing goes wrong (create this truncate work around).

Or I could just stop mixing ammonia and bleach!

 

@Antistone you were right. Doing the Truncates seems to be taking an enormous amount of processing (I tried * 10000 / 10000). Do correct me if I'm wrong, but what I infer from this is that multiplication and division are actually much heavier processes than I previously thought.

@lordofduct I took a brief look at it, and using linked lists does make sense -- I just had never heard about them before. I'll try to implement that now, since it seems to be the cleaner solution.

 

Actually, I was concerned that a few issues might rise with a linked list, so I decided to try the IEqualityComparer you, lordofduct, kindly provided first and... well, that solved it. The algorithm is 10 times faster now and working as it should.

Do you mind explaining to me how some of it works, though, because I don't quite get it?

1 - What does "reciprocal" means in this context?
2 - Why did you assign it as "1 / (factor * 2)" ? Is it just an arbitrary value?
3 - What exactly does the ^ operator do? I never used it before, and reading about it on MSDocs didn't help. (They should really make those texts more didactic... terms such as "bitwise exclusive-OR" are not exactly "user-friendly.")

Thanks for the code. I had to change the Equals' return to

return Vector2.Distance(nodeA, nodeB) < halfReciprocal;

though, just to feel like I contributed [negatively] with something and not so bad about myself for cheating. (The practical results were the same.)

 

Upon another reading (although the text isn't, MSDocs' examples are [sometimes] actually helpful) I infer the ^ operator is meant just to convert the values being used to binary.

If that is so, then, in the present case, with just 2 2-digit Int's, only 4 different hashcodes can be generated. I don't see how that could be useful to differentiate the nodes from one another, so... what is IEqualityComparer's GetHashCode()'s purpose?

I just need a general idea of everything in case I ever have to use a custom IEqualityComparer again.

 

A reciprocal is 1 / x. To multiply by the reciprocal of x, is = to dividing by x.

In what you described for your truncating, you said you multiplied by a factor (x), truncated, and the divided by that factor.

The reciprocal represents that 'division'.

Basically... if your factor is 10, really what you're saying is that the distance between each node is minimum 0.1. And 0.1 is 1 / 10.

I then halve this 1/10 because we're checking for nearest. So if the distance between a node is 0.02 it's closer to 0, but if it's 0.07 it's closer to 0.1.

The idea of rounding/truncating off some amount based on a factor is really just taking an infinitely small value and making it finitely small.

This is what I'm doing in the code. Efficiently testing how close to that finite point our unpredictable vector is.

^ is the XOR operator. Exclusive OR. It is a bitwise operator.
https://docs.microsoft.com/en-us/dotnet/csharp/language-reference/operators/xor-operator

Basically it takes any 2 integers and for each bit of it, it compares each bit, and sets the bit of an output integer based on the rule:

both 0 = 0
either 1 = 1
both 1 = 0

So the value:

Code (csharp):

1.  
2. 10110
3. 11011 ^
4. ----------
5. 01101
6.  

So why I do it is because the method is GetHashCode.

So this requires a bit of background. A dictionary is what is known as a "Hash Table":
https://en.wikipedia.org/wiki/Hash_table

A hash table works by getting a "hash" for a key, from that hash computing an index, and placing its paired value into a bucket/slot at that index.

This reduces search times for objects placed into it. Instead of having to loop over the collection testing equality on every object. Instead we calculate a hash which finds a semi-unique index. And then we only have to loop the objects that happen to collide with our hash. Which should theoretically be < N, where N is the size of the collection.

Of course this relies on the hash being semi-unique. If all values had the same hash, then they'd all end up in the same bucket/slot, and you'd effectively just have a Linked List (because buckets are implemented usually as a linked list... you really should look into linked lists, they're a fundamental collection type in computer science... I'll describe them more in depth later).

Now all a hash is, it's an integer representation of a value/object. And the algorithm that calculates that hash will always return the same hash for 2 values that are considered equal.

In the case of an int, its hash is itself. 8 hashes to 8. So that any value of 8 always hashes as 8.

But what of values that are none integers. Like say a char, well a char's hash is just its ascii/utf number. Since it easily converts to an int that way.

Problem arises though since a hash must be an int, giving only 4 bytes of space. So what if you hash like a string or something? It could be any number of chars long, meaning any number of bytes long. So really what they just do is loop over all characters, convert them to ints/bytes, and join them together.

This is strings GetHashCode in mscorlib:

Code (csharp):

1.  
2.     [SecuritySafeCritical]
3.     [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
4.     [__DynamicallyInvokable]
5.     public override unsafe int GetHashCode()
6.     {
7.       if (HashHelpers.s_UseRandomizedStringHashing)
8.         return string.InternalMarvin32HashString(this, this.Length, 0L);
9.       string str = this;
10.       char* chPtr1 = (char*) str;
11.       if ((IntPtr) chPtr1 != IntPtr.Zero)
12.         chPtr1 += RuntimeHelpers.OffsetToStringData;
13.       int num1 = 5381;
14.       int num2 = num1;
15.       char* chPtr2 = chPtr1;
16.       int num3;
17.       while ((num3 = (int) *chPtr2) != 0)
18.       {
19.         num1 = (num1 << 5) + num1 ^ num3;
20.         int num4 = (int) *(ushort*) ((IntPtr) chPtr2 + 2);
21.         if (num4 != 0)
22.         {
23.           num2 = (num2 << 5) + num2 ^ num4;
24.           chPtr2 += 2;
25.         }
26.         else
27.           break;
28.       }
29.       return num1 + num2 * 1566083941;
30.     }
31.  

Note how it XOR's values together. But it also does bitshifts as well. The bitshifts are because chars are actually 1 byte in size, and the hash can be 4 bytes. So might as well use all 4 bytes to get a better bit depth out of the value.

But you might wonder, why use XOR? Why not ADD them, or AND them, or OR them? Problem is those operations will continually grow the hash larger and larger... pushing the hash towards the upper bounds. Which increases the odds of collision.

XOR on the other hand doesn't. Due to the nature of how it works (as I showed earlier), 2 large numbers might result in a small number just because those large numbers are similarish.

It's the fact that XOR 0's out similar values that it's used. It creates variance.

...

Honestly speaking, the GetHashCode I created for that IEqualityComparer is actually sort of naive. I didn't test it or anything... I literally just wrote it tossed it onto the forum.

But actually... I shouldn't just convert x and y to int, and then xor them. Odds are most vectors are going to be in a near range. So what I just did was keep the hashes very small, upping the chances of collision.

You want to spread the hashes around the number line from 0->2^32 (in uint).

Which if you look at Vector2's GetHashCode, Unity does this by doing a bit shift:

Code (csharp):

1.  
2.     public override int GetHashCode()
3.     {
4.       return this.x.GetHashCode() ^ this.y.GetHashCode() << 2;
5.     }
6.  

So you might want to change my implementation to something like:

Code (csharp):

1.  
2.     public int GetHashCode(Vector2 v)
3.     {
4.         //calculate a hashcode based off the factor
5.         return (int)System.Math.Truncate(v.x * FACTOR) ^ (int)System.Math.Truncate(v.y * FACTOR) << 2;
6.     }
7.  

Note, I still multiply by FACTOR and truncate to make sure that 'near' vectors hash to the same value. Because the rule is that vectors that are considered equal should hash the same.

I STILL stress this a hack ass fix.

I only demonstrated it for theoretical purposes.

You really should NOT be doing this.

It is NOT a good idea.

Honestly... I didn't even test the code I gave you. It technically might still have edge cases that cause issues. Your algorithm of multiplying by a factor, truncating, and dividing, still has the potential to introduce float error that causes the very issue you're inherently having.

Floats can NOT be trusted.

Heck, even looking at my implementation I'm starting to see some flaws in my Equals method. It actually doesn't work the same as my GetHashCode. I did round on Equals, and Truncate on GetHashCode. Creating edge cases that might break your system (probably should change Truncate to Round as a hack fix).

...

Linked Lists are THE WAY to go.

Hell... Dictionary uses a linked list inside itself.

...

To explain a linked list.
https://www.cs.cmu.edu/~adamchik/15-121/lectures/Linked Lists/linked lists.html

A linked list is a very fundamental collection type in computer science. They're very important to learn about. They're up there along side arrays as being both simple, fundamental, and VERY POWERFUL.

So... a problem that arises with arrays is that they take up large contiguous portions of memory. You have an array of ints that is 100 in length? Well you just took up 400 bytes of contiguous memory.

Furthermore, an array needs to know its size up front. You can't allocate an array of variable length... instead if you have to resize it, you must create a brand new array and copy the entries over.

You might say "But lordofduct, List is of variable length!".

NO ITS NOT.

A List is really just a wrapper around an array. It maintains an array slightly larger than the size it needs to be. If you Add entries to the List that make it get larger than the size of the array inside... it creates a new much larger array, copies the values over, and continues adding.

This is why when you create a List there exists a constructor that allows you to pass in the anticipated size of the List. This way it doesn't have to constantly resize:
https://docs.microsoft.com/en-us/do...ollections_Generic_List_1__ctor_System_Int32_

If you ever were creating a list knowing you were going to add 100+ things to it... never say:

Code (csharp):

1.  
2. var lst = new List<obejct>();
3. for(int i = 0; i < 100; i++)
4. {
5.     lst.Add(...);
6. }
7.  

Instead you should be saying:

Code (csharp):

1.  
2. var lst = new List<object>(100);
3. for(int i = 0; i < 100; i++)
4. {
5.     lst.Add(...);
6. }
7.  

Really a List is just a facade around an array that streamlines the resize/copy requirements of arrays when growing.

...

Furthermore, arrays have an issue with insertion. If you need to insert a value in the middle of the array, what you need to do is loop the array starting at the insertion point, move each value one slot over, then put the inserted value into its spot.

Again List.Insert just streamlines this for you... but it's doing all this work underneath.

This looping and shifting and copying is SLOW.

A Linked List exists to resolve these issues... with some trade offs. Iterating over a linked list can actually be slower since how it is organized around in memory. Also accessing values at specific indices is slow since accessing a Linked List requires iterating over it.

But if your collection is intended to always be accessed via iteration... you can speed up the insertion, resizing, and memory usage.

How this is done is making each slot/node in the collection point to the next.


(note that our image, taken from that article I linked, spells out 'HEAP'. With good reason. The concept of non-contiguous memory is often called a 'heap', and yes, this is the same general concept used by the .net/mono runtime in its 'heap memory')

In code, simply put...

Code (csharp):

1.  
2. public class LinkedListMember<T>
3. {
4.  
5.     public LinkedListMember Next; //the link
6.     public T Value; //the value you want stored
7.  
8. }
9.  

Do not confuse this with the .net LinkedList<T>:
https://docs.microsoft.com/en-us/do....generic.linkedlist-1?view=netframework-4.7.2

Though this is technically a LinkedList implementation. We're not talking about this specific thing... we're talking about the concept of a Linked List right now. Furthermore... Microsoft's implementation is sort of inefficient, they've traded off efficiencies so that it is more generic (generic is good in OOP sometimes, it promotes code re-use).

So why is it powerful?

Well...

Appending just requires making the last element in the linked list point to the new last element.

Inserting just requires find the insertion point, making it point to the new element, and making the new element point to the one that the insertion point had already pointed to.

Removing just means removing an element and making the previous element point to the element that removed one pointed to.

Resizing is implicit. Adding/removing entries just automatically resizes the collection. The memory is non-contiguous, so it doesn't matter.

...

And for your needs. This is perfect.

You are creating a "path". The path is yet to be know... you yet to know its length, you yet to know its order, all you know is that once done you need to loop over it.

OK... that's a linked list!

As you find nodes in your path, you just append them to the path.

Code (csharp):

1.  
2. public class VertexInfo
3. {
4.     public Vector2 Node;
5.     public VertexInfo Next;
6. }
7.  

And the best part is that the node can contain more information, such as the g score:

Code (csharp):

1.  
2. public class VertexInfo
3. {
4.     public Vector2 Node;
5.     public VertexInfo Next;
6.     public float g;
7.     public float h;
8.     public float f;
9. }
10.  

And in the case of mine I showed you... we can even abstract out the type of the node (what happens when you need to create a Vector3 version of your A* or Dijkstra???)

Code (csharp):

1.  
2. public class VertexInfo
3. {
4.     public T Node;
5.     public VertexInfo Next;
6.     public float g;
7.     public float h;
8.     public float f;
9. }
10.  

...

As for implementing this into your specific algorithm.

Well... I have no idea how yours looks.

But it honestly shouldn't be hard to swap them out.

If you could just show us the code, we could assist you in that.

Rather than using a HACK FIX that potentially WILL BREAK at some time in the future for UNKNOWN or HARD TO DETERMINE reasons.

Case in point...

You have been in this thread for well over a day trying to hack a fix for your algorithm that "almost works"... when refactoring with the appropriate Linked List would have probably taken far less time.

Not only would it have taken less time. You would have learned about a new fundamental part of computer science and done it the right way, rather than a hack way.

 

Damn, man, you're like a book! I didn't mean to make you go through the trouble of writing all that. I can't say I absorbed all of it, but it did clear a bunch of things up.

I get your point about the linked lists, but you'll be utterly disappointed to know that, honestly, I still don't intend to switch to them (at least not at this moment). I don't need perfection, just something that, for practical reasons, works perfectly, and that's what I got right now. I couldn't be happier with my algorithm's current performance. You should have seen what the first version of it looked like -- now that sucked.

I'm trying to do an entire game on my own, without any prior knowledge of C# or Unity, and if I keep going for the best way to do everything, I'll never finish this. When something is not working as I want it to, I fix it every single time, but when it is... I just let it keep working.

If I were to try and do the best possible about my pathfinding algorithm, implementing linked lists wouldn't even be the first step -- that would be changing the whole thing to a Flow Field solution. And that would mean a lot more trouble.

Also, if, with the custom equality comparer in place, floats intrinsic variations still pop up eventually, that won't cause any real harm to the path. We're talking about a single character moving in a screen-wide environment here, it's pretty much as simple as it gets. Even with the floats' variation hitting the fan at full power -- when I was trying to use .ContainsKey and getting random true/false values -- the character still made it to the target position... just with a rather messed up path.

So far, all the tests I made had perfect results so, if floats ever act up again, it seems to me that that will be a pretty rare occurrence -- and the practical result would be maybe one step off the path.

You fully understand this stuff, I don't. Whenever I change something, something else falls apart. What takes you a few minutes to solve/implement, takes me a few days. So... unless it needs fixing, I don't fix it. (Although our definitions of "need" may vary... but that would lead to an infinite discussion.)

I'll keep linked lists in mind. If another opportunity arises to use them, I will. Or if my pathfinding algorithm ever causes me any trouble again -- then they're going right in there.

 

I type at well over 100 wpm, typing all that honestly is no big deal to me. It's how I while about my time regardless.