OmnipotentEntity submitted a new blog post: June 20 - Omni Update Continue reading the Original Blog Post
If you find a great answer for the code to define if a line cross a rectangle, could you sent it to me, because rigth now I can only find "not that good" answers
couldn't you detect when the connections are far enough apart to potentially span the screen, and if so place dummy noes along the way that will render the wire if onscreen?
The problem he's describing is due to the way the game renders the screen, around you. Only a certain amount of the world is even loaded into the client's memory, at one time. The game, at this point, only "knows" about the wire if at least one of the end points is currently on-screen. It's a step up from where it was, and Omni is to be thanked for that change. At least, it seems, they have a dev that is thinking about these kind of obscure things when others can't or won't... probably they just aren't geeky enough (+1 Omni for awesomeness... -1 for also fanning the flames)
If this is a matter of making a line (wire) check for crossing a box (the screen) couldn't you use a standard raycasting algorythm? Also, would it be terrible to disallow wiring connections beyond 64 blocks? It feels like that could be solved by introducing a "relay" wiring object, and a simple rule of "x distance is too far for one wire" makes sense for most kinds of actual wires (albeit we're usually talking a pretty good distance)
We can't actually use a ray casting algorithm as it stands right now because the problem is missing information. Right now, when you connect two nodes the connection is stored within both nodes. Both the client and the server might be unaware of either or both nodes, because they're not loaded into memory. If that's the case then the game isn't aware that there is even anything missing TO draw. The fix is we need to store the WireConnections that pass through a chunk as part of that chunk; however, that has its own problems, because the WireConnections in the chunk may come desynced from the WireConnections in the nodes. Which is why I didn't do it immediately. I wanted to fix one bug at a time without introducing more potentially. I'd rather avoid needing a relay wire because that's just an extra layer of complexity.
Here's a solution for Line-Rectangle intersection that comes to mind first (assumes that rectangles aren't rotated, i.e. the sides are parallel with the x and y axes). For detecting the Line-Rectangle intersection, first the algorithm would check to make sure that one of the endpoints is within the rectangle, as that would be the fastest case to determine intersection: The code for this is pretty simple: (I'm assuming that you guys already use this code in your existing checks for whether points are within rectangles. I'm including it for completion and for the sake of others that might read this.) Code: bool DoesRectangleContainPoint(Rectangle r, Point p) { return (p.X >= r.X) && (p.Y >= r.Y) && (p.X <= r.X + r.Width) && (p.Y <= r.Y + r.Height); } bool DoesLineHaveEndpointsInRectangle(Point p1, Point p2, Rectangle r) { return DoesRectangleContainPoint(r, p1) || DoesRectangleContainPoint(r, p2); } In the case where neither endpoint resides in the rectangle and the line just passes completely through, the algorithm will actually treat the check as detecting two Line-Line intersections by checking the line of the wire against the two diagonals of the rectangle, since any line that crosses the rectangle will intersect at least one of these two lines. The code for this is a bit trickier to understand, but it's still a cheap check. It involves treating the points as vectors and using cross products to find at what point along the lines the two vectors have the same value. Check out this guy's StackOverflow answer for an explanation, as he explains it better than I could (URL removed for not meeting forum requirements; apparently exactly 2 posts doesn't meet the "at least 2 posts" rule). The code itself is: Code: bool DoLineSegmentsIntersect(Point p, Point pr, Point q, Point qs) { Point r = pr - p; Point s = qs - q; Point qmp = q - p; double qmpxr = qmp.X * r.Y - qmp.Y * r.X; double rxs = r.X * s.Y - r.Y * s.X; // Are the lines collinear? if (qmpxr == 0 && rxs == 0) { // Do the lines overlap? return ((q.X - p.X < 0) != (q.X - pr.X < 0) != (qs.X - p.X < 0) != (qs.X - pr.X < 0)) || ((q.Y - p.Y < 0) != (q.Y - pr.Y < 0) != (qs.Y - p.Y < 0) != (qs.Y - pr.Y < 0)); } if (rxs == 0) { // Lines are parallel return true; } double u = qmpxr / rxs; double qmpxs = qmp.X * s.Y - qmp.Y * s.X; double t = qmpxs / rxs; return (t >= 0) && (t <= 1) && (u >= 0) && (u <= 1); } bool DoesLineCrossRectangle(Point p1, Point p2, Rectangle r) { Point d1 = new Point(r.X, r.Y); Point d2 = new Point(r.X + r.Width, r.Y + r.Height); Point d3 = new Point(r.X + r.Width, r.Y); Point d4 = new Point(r.X, r.Y + r.Height); return DoLineSegmentsIntersect(p1, p2, d1, d2) || DoLineSegmentsIntersect(p1, p2, d3, d4); } So to tie it all together, a function would only need to check for these two states - whether a line intersects by way of one endpoint being within the rectangle, or whether a line intersects by crossing one of the rectangle's diagonals. Code: bool DoesLineIntersectRectangle(Point p1, Point p2, Rectangle r) { return DoesLineHaveEndpointsInRectangle(p1, p2, r) || DoesLineCrossRectangle(p1, p2, r); } This is my approach to solving the Line-Rectangle intersection problem. I haven't run it through any benchmarks or anything, but since it only involves short functions and simple arithmetic, I imagine that it would run quite fast.
If you can efficiently query for the endpoints, you can use the Cohen-Sutherland algorithm (which I apparently haven't posted here enough to put a link to) to check if a line with the given endpoints crosses the screen.
@Abion47 Your code assumes that the entire space is held in memory at one time, but unfortunately, as Omni is trying to point out, that is not the case. He knows how to make a check to see if a line is crossing the screen, but what happens when one of the end points is not loaded into memory?
Couldn't you use some kind of (quad-)tree structure to keep track of all wires? They are perfect for queries for 2D data. And you can sacrifice some accuracy when displaying cross-chunk wires to keep your data down (the slope need not be exact), because you KNOW there will be people filling every tile with wires to a different chunk. Another way is to allow deferred updates to chunks. What I mean is a way to store changes to be applied to chunks IF and WHEN they get loaded. This way updating a wire will defer updates for all the chunks the wire crosses.
I must have read the article right after I woke up and misinterpreted the problem. Maybe when a chunk gets loaded, it checks the unloaded chunks to the left and right of it for existing nodes, and if there is a node in the left chunks that corresponds to a chunk in the right nodes, the loaded chunk adds those nodes to memory? Though I don't know how wires are stored in the chunks currently, so this wouldn't work if the entire chunk needs to be loaded just to check for wiring. The obvious solution for this would be to save wiring data in a separate structure than terrain so it can be queried even if the chunk isn't loaded, but that might screw up whatever structure they currently have.
@Abion47 I do believe that is what would be required, with the code base as it is. But by all means, with that in mind do keep brainstorming ideas. Maybe you will hit upon something that Omni hasn't yet considered.
