Click here to Skip to main content
15,896,912 members

Welcome to the Lounge

   

For discussing anything related to a software developer's life but is not for programming questions. Got a programming question?

The Lounge is rated Safe For Work. If you're about to post something inappropriate for a shared office environment, then don't post it. No ads, no abuse, and no programming questions. Trolling, (political, climate, religious or whatever) will result in your account being removed.

 
GeneralRe: yay, another vs update... Pin
Slacker00716-Aug-18 6:31
professionalSlacker00716-Aug-18 6:31 
GeneralRe: yay, another vs update... Pin
W Balboos, GHB16-Aug-18 5:56
W Balboos, GHB16-Aug-18 5:56 
GeneralRe: yay, another vs update... Pin
lopatir16-Aug-18 6:25
lopatir16-Aug-18 6:25 
GeneralRe: yay, another vs update... Pin
W Balboos, GHB16-Aug-18 6:28
W Balboos, GHB16-Aug-18 6:28 
GeneralRe: yay, another vs update... Pin
kmoorevs16-Aug-18 6:40
kmoorevs16-Aug-18 6:40 
GeneralRe: yay, another vs update... Pin
kmoorevs16-Aug-18 6:58
kmoorevs16-Aug-18 6:58 
GeneralRe: yay, another vs update... Pin
Marc Clifton16-Aug-18 7:29
mvaMarc Clifton16-Aug-18 7:29 
GeneralA common bug-inducing pattern: building a grid out of linked nodes. Pin
harold aptroot15-Aug-18 23:39
harold aptroot15-Aug-18 23:39 
By "grid" I just mean a good old 2D arrangement of cells like a chess board. Building it out of linked nodes means making every cell a node with explicit references to neighbouring node objects.

This is something that I've seen novices do quite a lot more than necessary. There can be reasons to do it, but usually it results in an over-explicit and over-redundant data structure and plenty of bugs. Every degree of redundancy is an opportunity for the data structure to get out of sync with itself, and anything explicit can be explicitly incorrect. Usually the reason they give for doing it is "because path finding algorithms work on graphs", but graphs are an abstract interface, not an implementation.

What tends to happen (obviously it is also possible to "just write correct code", but the point is it's easy to get wrong), especially if nodes are dynamically added and removed, is that the links decay over time. Nodes start disagreeing about whether they are connected, resulting in one-way connections, and the bad state starts to infect everything. Nodes that should have been disconnected entirely turn out to be linked to by some random other node. Multiple nodes that represent the same coordinate come into being. "Wild links" are teleporting all over the map for no clear reason. The path finding gets very confused and the programmer does too since what they see in the debugger (if they look at all, which many novices avoid for some reason) doesn't make any sense.

Perhaps the funniest part is that while all that is going on, it is realised that a 2D array is needed in order to quickly find a node with given coordinates, and from that point on all those buggy links are worse than useless: the location in the array implicitly defines the neighbours. All problems could have been avoided by just working with that 2D array to begin with. The only way you have a node is because you had its coordinates, so you always know where its neighbours are without even storing the coordinates on the node object. There are no more explicit neighbour links, so they cannot be incorrect. Marking a cell in the grid as non-walkable implicitly deletes whatever links that needs to delete, it cannot go wrong since there are no actual links to actually delete.

This phenomenon still surprises me. Building a grid out of linked nodes is something I had never even considered doing before I saw someone else making that mistake. Surely a 2D array is the first thing you think of when your data has the shape of a 2D array, that just makes sense. Or maybe it doesn't, because I've seen this anti-pattern a lot.

GeneralRe: A common bug-inducing pattern: building a grid out of linked nodes. Pin
Pete O'Hanlon15-Aug-18 23:51
mvePete O'Hanlon15-Aug-18 23:51 
GeneralRe: A common bug-inducing pattern: building a grid out of linked nodes. Pin
harold aptroot15-Aug-18 23:55
harold aptroot15-Aug-18 23:55 
GeneralRe: A common bug-inducing pattern: building a grid out of linked nodes. Pin
Pete O'Hanlon16-Aug-18 0:18
mvePete O'Hanlon16-Aug-18 0:18 
GeneralRe: A common bug-inducing pattern: building a grid out of linked nodes. Pin
Eddy Vluggen16-Aug-18 0:13
professionalEddy Vluggen16-Aug-18 0:13 
GeneralRe: A common bug-inducing pattern: building a grid out of linked nodes. Pin
harold aptroot16-Aug-18 0:17
harold aptroot16-Aug-18 0:17 
GeneralRe: A common bug-inducing pattern: building a grid out of linked nodes. Pin
Eddy Vluggen16-Aug-18 0:18
professionalEddy Vluggen16-Aug-18 0:18 
GeneralRe: A common bug-inducing pattern: building a grid out of linked nodes. Pin
harold aptroot16-Aug-18 0:26
harold aptroot16-Aug-18 0:26 
GeneralRe: A common bug-inducing pattern: building a grid out of linked nodes. Pin
Eddy Vluggen16-Aug-18 0:34
professionalEddy Vluggen16-Aug-18 0:34 
GeneralRe: A common bug-inducing pattern: building a grid out of linked nodes. Pin
harold aptroot16-Aug-18 0:56
harold aptroot16-Aug-18 0:56 
GeneralRe: A common bug-inducing pattern: building a grid out of linked nodes. Pin
Eddy Vluggen16-Aug-18 1:14
professionalEddy Vluggen16-Aug-18 1:14 
GeneralRe: A common bug-inducing pattern: building a grid out of linked nodes. Pin
harold aptroot16-Aug-18 1:25
harold aptroot16-Aug-18 1:25 
GeneralRe: A common bug-inducing pattern: building a grid out of linked nodes. Pin
Eddy Vluggen16-Aug-18 1:44
professionalEddy Vluggen16-Aug-18 1:44 
GeneralRe: A common bug-inducing pattern: building a grid out of linked nodes. Pin
Eytukan16-Aug-18 17:21
Eytukan16-Aug-18 17:21 
GeneralRe: A common bug-inducing pattern: building a grid out of linked nodes. Pin
Eddy Vluggen16-Aug-18 21:39
professionalEddy Vluggen16-Aug-18 21:39 
GeneralRe: A common bug-inducing pattern: building a grid out of linked nodes. Pin
CodeWraith16-Aug-18 0:34
CodeWraith16-Aug-18 0:34 
GeneralRe: A common bug-inducing pattern: building a grid out of linked nodes. Pin
harold aptroot16-Aug-18 0:38
harold aptroot16-Aug-18 0:38 
GeneralRe: A common bug-inducing pattern: building a grid out of linked nodes. Pin
CodeWraith16-Aug-18 1:16
CodeWraith16-Aug-18 1:16 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.