A common bug-inducing pattern: building a grid out of linked nodes.
-
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 sen
harold aptroot wrote:
All problems could have been avoided by just working with that 2D array to begin with.
harold aptroot wrote:
especially if nodes are dynamically added and removed
I'm not going to "remove" a part of a 2D array. I might flag it, but refuse to remove it.
Bastard Programmer from Hell :suss: If you can't read my code, try converting it here[^] "If you just follow the bacon Eddy, wherever it leads you, then you won't have to think about politics." -- Some Bell.
-
harold aptroot wrote:
All problems could have been avoided by just working with that 2D array to begin with.
harold aptroot wrote:
especially if nodes are dynamically added and removed
I'm not going to "remove" a part of a 2D array. I might flag it, but refuse to remove it.
Bastard Programmer from Hell :suss: If you can't read my code, try converting it here[^] "If you just follow the bacon Eddy, wherever it leads you, then you won't have to think about politics." -- Some Bell.
-
Your initial specification there talked about nodes, rather than the data the nodes contained.
This space for rent
-
That's done with a flag; you don't remove the location, since the location still exists - only one of its properties has changed.
Bastard Programmer from Hell :suss: If you can't read my code, try converting it here[^] "If you just follow the bacon Eddy, wherever it leads you, then you won't have to think about politics." -- Some Bell.
-
That's done with a flag; you don't remove the location, since the location still exists - only one of its properties has changed.
Bastard Programmer from Hell :suss: If you can't read my code, try converting it here[^] "If you just follow the bacon Eddy, wherever it leads you, then you won't have to think about politics." -- Some Bell.
-
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 sen
harold aptroot wrote:
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.
Arrays are the worst choice of all. How about a quadtree for 2D structures or octrees for 3D structures?
I have lived with several Zen masters - all of them were cats. His last invention was an evil Lasagna. It didn't kill anyone, and it actually tasted pretty good.
-
I never said what you imagined I said. The "removing" thing is in the context of nodes. Anyway I think you can reasonably assume that I'm not a total idiot.
harold aptroot wrote:
I never said what you imagined I said. The "removing" thing is in the context of nodes.
If you implement the map as a list of nodes, you'd still use a flag instead of removing the nodes.
harold aptroot wrote:
Anyway I think you can reasonably assume that I'm not a total idiot.
I don't like assumptions, and don't know how your coworkers think. I can also state that I am a certified idiot; that's why I need specifications, and come asking questions that may seem obvious to others. Let them play Rimworld, might help :)
Bastard Programmer from Hell :suss: If you can't read my code, try converting it here[^] "If you just follow the bacon Eddy, wherever it leads you, then you won't have to think about politics." -- Some Bell.
-
harold aptroot wrote:
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.
Arrays are the worst choice of all. How about a quadtree for 2D structures or octrees for 3D structures?
I have lived with several Zen masters - all of them were cats. His last invention was an evil Lasagna. It didn't kill anyone, and it actually tasted pretty good.
-
harold aptroot wrote:
I never said what you imagined I said. The "removing" thing is in the context of nodes.
If you implement the map as a list of nodes, you'd still use a flag instead of removing the nodes.
harold aptroot wrote:
Anyway I think you can reasonably assume that I'm not a total idiot.
I don't like assumptions, and don't know how your coworkers think. I can also state that I am a certified idiot; that's why I need specifications, and come asking questions that may seem obvious to others. Let them play Rimworld, might help :)
Bastard Programmer from Hell :suss: If you can't read my code, try converting it here[^] "If you just follow the bacon Eddy, wherever it leads you, then you won't have to think about politics." -- Some Bell.
-
OK sure, there would be a flag. Do I really need to specify implementation details like that though?
harold aptroot wrote:
OK sure, there would be a flag. Do I really need to specify implementation details like that though?
Not required, it just helps me understand what the problem is. Might be beneficial if I encounter it myself. My apologies if I'm not helping in any way :thumbsup: If you have a flag and don't remove nodes, how can there be invalid (double/missing) nodes?
Bastard Programmer from Hell :suss: If you can't read my code, try converting it here[^] "If you just follow the bacon Eddy, wherever it leads you, then you won't have to think about politics." -- Some Bell.
-
No way, arrays are great. Quadtrees are fun and powerful, but at the cost of being at least an order of magnitude more complicated.
harold aptroot wrote:
being at least an order of magnitude more complicated
Which ltttle object oriented me would just hide by properly encapsulating it away in methods and properties.
I have lived with several Zen masters - all of them were cats. His last invention was an evil Lasagna. It didn't kill anyone, and it actually tasted pretty good.
-
harold aptroot wrote:
being at least an order of magnitude more complicated
Which ltttle object oriented me would just hide by properly encapsulating it away in methods and properties.
I have lived with several Zen masters - all of them were cats. His last invention was an evil Lasagna. It didn't kill anyone, and it actually tasted pretty good.
-
harold aptroot wrote:
OK sure, there would be a flag. Do I really need to specify implementation details like that though?
Not required, it just helps me understand what the problem is. Might be beneficial if I encounter it myself. My apologies if I'm not helping in any way :thumbsup: If you have a flag and don't remove nodes, how can there be invalid (double/missing) nodes?
Bastard Programmer from Hell :suss: If you can't read my code, try converting it here[^] "If you just follow the bacon Eddy, wherever it leads you, then you won't have to think about politics." -- Some Bell.
-
Exactly, that's the point: there would be no possibility of creating invalid states that way. Any state that can be represented is valid .. it might be the wrong state, but it cannot be internally inconsistent.
harold aptroot wrote:
Exactly, that's the point: there would be no possibility of creating invalid states that way. Any state that can be represented is valid .. it might be the wrong state, but it cannot be internally inconsistent.
That's how most games will approach it. Sometimes there's water or land in the Rimworld map where there shouldn't be - but the map in itself is "valid" and hence, playable.
Bastard Programmer from Hell :suss: If you can't read my code, try converting it here[^] "If you just follow the bacon Eddy, wherever it leads you, then you won't have to think about politics." -- Some Bell.
-
Hiding complexity under the rug doesn't make it go away, you'd still have to actually implement that quad tree.
Sure, but I have already done that a few times and I never had much trouble managing a few pointers and memory. Anyway, in many languages overstepping the boundaries of an array may have worse consequences than just causing an exception. Your implementation therefore also offers the advantage to allow as little or as much error handling as is needed.
I have lived with several Zen masters - all of them were cats. His last invention was an evil Lasagna. It didn't kill anyone, and it actually tasted pretty good.
-
Sure, but I have already done that a few times and I never had much trouble managing a few pointers and memory. Anyway, in many languages overstepping the boundaries of an array may have worse consequences than just causing an exception. Your implementation therefore also offers the advantage to allow as little or as much error handling as is needed.
I have lived with several Zen masters - all of them were cats. His last invention was an evil Lasagna. It didn't kill anyone, and it actually tasted pretty good.
CodeWraith wrote:
Anyway, in many languages overstepping the boundaries of an array may have worse consequences than just causing an exception.
Not too hard to write a method that takes any value and checks for overflows. If you overflow on the right of the map, set the value to zero, and you re-appear on the left of the map.
Bastard Programmer from Hell :suss: If you can't read my code, try converting it here[^] "If you just follow the bacon Eddy, wherever it leads you, then you won't have to think about politics." -- Some Bell.
-
CodeWraith wrote:
Anyway, in many languages overstepping the boundaries of an array may have worse consequences than just causing an exception.
Not too hard to write a method that takes any value and checks for overflows. If you overflow on the right of the map, set the value to zero, and you re-appear on the left of the map.
Bastard Programmer from Hell :suss: If you can't read my code, try converting it here[^] "If you just follow the bacon Eddy, wherever it leads you, then you won't have to think about politics." -- Some Bell.
Map? Reappear on the other side? How primitive! I have a map of a galaxy with 4 billion x 4 billion x 4 billion coordinate points and who knows how many hundreds of thousands of stars. There are 4 billion of these galaxies in each of the 4 billion universes. One of the galaxies should last the players forever. Don't try to store all that in an array. :-)
I have lived with several Zen masters - all of them were cats. His last invention was an evil Lasagna. It didn't kill anyone, and it actually tasted pretty good.
-
Map? Reappear on the other side? How primitive! I have a map of a galaxy with 4 billion x 4 billion x 4 billion coordinate points and who knows how many hundreds of thousands of stars. There are 4 billion of these galaxies in each of the 4 billion universes. One of the galaxies should last the players forever. Don't try to store all that in an array. :-)
I have lived with several Zen masters - all of them were cats. His last invention was an evil Lasagna. It didn't kill anyone, and it actually tasted pretty good.
CodeWraith wrote:
Map? Reappear on the other side? How primitive!
May be, but it is simple and it works :)
CodeWraith wrote:
I have a map of a galaxy with 4 billion x 4 billion x 4 billion coordinate points and who knows how many hundreds of thousands of stars. There are 4 billion of these galaxies in each of the 4 billion universes. One of the galaxies should last the players forever. Don't try to store all that in an array. :)
Tell me you are building Elite III or a new Master of Orion :D
Bastard Programmer from Hell :suss: If you can't read my code, try converting it here[^] "If you just follow the bacon Eddy, wherever it leads you, then you won't have to think about politics." -- Some Bell.
-
CodeWraith wrote:
Map? Reappear on the other side? How primitive!
May be, but it is simple and it works :)
CodeWraith wrote:
I have a map of a galaxy with 4 billion x 4 billion x 4 billion coordinate points and who knows how many hundreds of thousands of stars. There are 4 billion of these galaxies in each of the 4 billion universes. One of the galaxies should last the players forever. Don't try to store all that in an array. :)
Tell me you are building Elite III or a new Master of Orion :D
Bastard Programmer from Hell :suss: If you can't read my code, try converting it here[^] "If you just follow the bacon Eddy, wherever it leads you, then you won't have to think about politics." -- Some Bell.
I still play Master of Orion II very often. I have not really worked on my game in quite a while now. It's more a browser game that has accidentally fallen out of the browser. I have posted the link to the video before, but you can see what I need octrees for: link[^]
I have lived with several Zen masters - all of them were cats. His last invention was an evil Lasagna. It didn't kill anyone, and it actually tasted pretty good.
-
I still play Master of Orion II very often. I have not really worked on my game in quite a while now. It's more a browser game that has accidentally fallen out of the browser. I have posted the link to the video before, but you can see what I need octrees for: link[^]
I have lived with several Zen masters - all of them were cats. His last invention was an evil Lasagna. It didn't kill anyone, and it actually tasted pretty good.
Have you considered a pre-release on Steam? If you need someone to test the game, please let me know :D
Bastard Programmer from Hell :suss: If you can't read my code, try converting it here[^] "If you just follow the bacon Eddy, wherever it leads you, then you won't have to think about politics." -- Some Bell.