Questions Re: Building the Path with ConnectedTo

[Shadow64]

In this section, Gary talks about the BuildPath function in PathFinder.cs and he uses:

while(currentNode.connectedTo != null)

It makes sense because the start location is never given “connectedTo” values. The thing is, before watching his answer, I came up with this:

while(currentNode != startNode)

As far as I can tell my version works (I’m keeping his in a commented line above in case mine breaks something later), but I’m a little curious if there’s a reason he chose to use .connectedTo instead of just checking if currentNode was the startNode.

I’m pretty sure it accomplishes the same task and it’s less obscured than detecting if the node’s .connectedTo is null.

I’m just trying to make sure I’m not missing something. If it’s a preference thing or just another way of doing it, that’s fine. Just curious.

Thanks.

[Shadow64]

Oddly enough, when I got to the “Valid Path” lecture (two lessons beyond this), my “currentNode != startNode” version no longer works and results in some odd behavior, but Gary’s works.

I’ve tried debugging through it to see if I can figure out what the difference is, but no luck. I really would’ve thought they’d result in the same node being returned.

From what I can tell currentNode.connectedTo should only return null if it retraces back to the startNode which has no connectedTo values. Maybe it’s a code order issue? Honestly no idea.

[Nina]

Hi Shadow64,

It’s great to see that you are trying to implement your own idea.

@Shadow64

Oddly enough, when I got to the “Valid Path” lecture (two lessons beyond this), my “currentNode != startNode” version no longer works and results in some odd behavior, but Gary’s works.

What is the ‘odd behaviour’?

---

Let me explain the data structure we have in this game. It’s a linked list. Let’s say we have 4 Node objects: A, B, C, D, E. Then our path could look like this: A → B → C → D → E → null.

Or in code: A.connectedTo.connectedTo.connectedTo.connectedTo. The last connectedTo references our E.

In each iteration step, we check the value of connectedTo of the current Node object. If our startNode is A, whose connectedTo variable is A?

[Shadow64]

Hi Nina,

Thanks for the response. The odd behavior using my version is that it won’t place additional towers (which is correct), but it does create additional blocked positions (when it shouldn’t be able to). Gary’s version doesn’t result in the latter part, which is strange because they should mean the exact same thing. Let me explain my logic.

In each iteration step, we check the value of connectedTo of the current Node object. If our startNode is A, whose connectedTo variable is A?

This is where the currentNode.connectedTo would be null, right? Node B would have a connectedTo of A, but A would have nothing and return null.

Because A was the first element explored in ExploreNeighbors() (passed into via the BeadthFirstSearch method) it’s never assigned a connectedTo value.

neighbor.connectedTo = currentSearchNode; 

Maybe I’m misunderstanding, but I thought that we were then starting BuildPath() with the end:

List<Node> path = new List<Node>();
Node currentNode = destinationNode;

And then because of that, BuildPath works backwards - which is why we reverse it before returning the final path.

So the chain of connected would be E > D > C > B > A > Null. Those get added to the chain during BuildPath in that order. Since A is never assigned a connectedTo (since it’s never a neighbor) it would be the last one added. E however would have a connectedTo value of D. A then is simultaneously the only one with a null value for connectedTo and it would also be the startNode.

At least that’s where my confusion is coming from. We explore from start to finish, then build the bath backwards using the reverse connections we made, so A wouldn’t have any connections.

Am I making sense? Sorry, it’s late here.

[Nina]

Yes, you are absolutely right. I forgot that we start with the destination node. We use the linked list to fill our path list in this order. Then we reverse the order to get our actual path starting from the startNode. At this point, connectedTo is not needed anymore because we use the order of the Node objects in the path to move our enemies.

Regarding the while-condition, I can only guess but maybe Gary wanted to follow the standard way of finding the end of the linked list. In the context of this concept (linked list), that’s usually null or an equivalent of ‘no object reference’. See the definition and the examples on Wikipedia.

However, in the context of this game, it also makes sense to check against startNode because we want our last element to be a specific value: the value of startNode.

while (currentNode != startNode) is a valid solution and a matter of personal preference.

[Shadow64]

Okay thanks! That makes me feel a little more sane to know that my thinking wasn’t off.

I’ve done some further digging. I decided to put a log directly under the start of the while loop.

Debug.Log((currentNode.connectedTo == null) + " " + (currentNode == startNode));

Basically just trying to see if these evaluate to the same thing. When I use Gary’s code, they always result in “False False”. However, when I use my version and I try to place a blocking tower, it results in “True False” which is bizarre.

Somehow that means that the while loop is evaluating currentNode != startNode to true and then immediately saying the current node has no connected to nodes, but isn’t the first node.

I’m wondering if this has something to do with using GetNewPath() in WillBlockPath. It didn’t make a ton of sense to me that he uses the current path and then clears it to rebuild the old one if it would block. I’m going to try changing it to see if I can build a copy of the path, then if the copy is a usable path, set the main path to the alternative and if not, just leave the original path alone?

Not sure. But worth a shot. I feel like somewhere in rebooting the path it’s getting messed up, maybe.

Anyway, I’ll let you know what I find. Thanks again for trying to help me get to the bottom of it.

[Shadow64]

Hmm. Don’t think that’s it. Tried it and it didn’t make a difference. Also, trying to not use GetNewPath gets complicated because even BuildPath involves directly changing the values of grid node attributes. Since everything is tied into the original for the check and not a copy, you can’t just switch one part of it without still interfering with the rest, so using GetNewPath is required unless I wanted to completely change how all of this works.

I’m guessing eventually I’ll better understand why these two things that should be equal are not evaluating that way, but “Not today!”

Just gonna move on.