How to prevent crossing lines?
I just make an array of nodes and then connect depends the distance each other, but sometimes have this problem of crossing lines. Any idea how to prevent that?
thanks
If on a gris, each node should keep track of its connections: top, top left/right, right/left, bottom and bottom left/right. When trying to connect diagonally, check 1 node horizontal if it has a connection that would block.
For a grid:
[0][0] [0][1]
[1][0] [1][1]
[0][0] would check [0][1] if bottom left is true.
The distance check is with world location or index within the array?
is with world location. I just store in all the nodes the neigh distance and then just filter. @pezzott1
I also store the x,y positions.
Lots of issues here I’m afraid. You’re only storing neighbors. No distances, no directions, nothing. The BIGGEST mistake here is that you can’t have a neighbor and not be a neighbor yourself. So in your function, when you add the input star to the neighbor list, you MUST also add yourself (the current Star) to the neighbor’s neighbor list as well. You are each other’s neighbors. It has to be a two way relationship.
Next, it can be complicated for the fastest way to handle this without a proper data structure. When you add a neighbor, you’d have to check its neighbors to see if they’re connected to each other AND if they intersect the path you’re trying to add.
Instead of doing that, the simplest way might be to have a global array of connections where you store a pair of end points or stars (only one way). Now each time you add a neighbor, iterate over the global list to see if any existing path intersects the one you’re trying to add. There are plenty of line intersection nodes you can use for this. If there’s an intersection, don’t add it. If there is no intersection, add the neighbors to each other and to the global list.
If you don’t have many stars, this should be fine. If it grows in size, you’ll need a struct with proper information for each neighbor (as the other commenter indicated). If they’re in a grid, only diagonals need to be in the global list. That could speed things up. And you only need to do the global check on diagonals. For horizontal lines, you can just check if the neighbor is already in your neighbor list. This will also become an issue when you fix your current issue. Right now, you have a fix that you check for self. That’s fine for ONE added star. But for additional stars, this “fix” won’t be enough.
1 Like
@AlienRenders Well the idea is to creat a simple map, with no more than 8x8 grid so i think could work. I think if the distance is the same from one star to other it will be stored in each neighbour array.
Each star have some variables like ActualPos(is the position in the map), Coord Pos(position y X,Y), distance (store the distance between the actual star to this star), neighbours (array of stars). Maybe a struct system could work better.
My objective for now it´s have a map like Faster Than Light.
Thanks
Oh, if it’s only 8x8, then you can absolutely do a simple fix.
I don’t think you understand what I mean by double relationship, but since this is only 8x8 and if you’re only interested in one way traversal to the exit, you may not need it.
When you add a neighbor, also add it to a global list (like an array and you store the pair of stars). Before this, add a function (or two functions) where you check if a connection between two stars can be added. This requires 2 steps.
-
Check if the connection exists in the global list already. You will need to check both directions. So check if either pairs (star1, star2) or (star2, star1) exist in the global list. If it does, don’t add the new neighbor. You check the stars themselves or the positions. Doesn’t matter as long as they’re unique.
-
Check if any of the pairs in the global list crosses the line made by (star1, star2). If it does, don’t add the new neighbor.
If both checks pass, then add the neighbor as you do in your function graph and also add it (the pair of stars) to the global list (array).
This should be relatively easy to do and will be more than fast enough for 8x8 grids.
@AlienRenders Ok i will take a look of this. I´m kind of new with this stuff so if can give an extra help it will be great. Also im curius about the double relationship, maybe it could be usefull if i want to expand the universe.
Becouse maybe i don´t need 8 connections between nodes.
Looks like UE doesn’t have line intersection nodes. It’s available in C++. But if you don’t have access to that, I’ve created a blueprint function you can copy and pasted into your project.
You’ll have to create a struct called StarPair like so:
This is the Intersection function. You’ll have to create local variables like so:
(edit: you don’t need Intersect1 variable. That was from a previous attempt.)
You can check the link below to set up your inputs and outputs. The inputs are Vector2D. Then copy and paste the graph into your function.
And for your check function, I created a graph at the link below. Here are the local variables.
IsConnValid must be set to true by default. The input GlobalConnections is an array of StarPair’s that I screeshoted at the top.
Just add the above function node before adding the neighbour followed by a branch node. You will want to use the True connection to your add node. For the global array, you’ll have to create one somewhere that is accessible by all the Star’s.
I haven’t tested this, so you’ll have to verify that it works.
Thanks a lot @AlienRenders well i just pass the functions, i have 2 doubts, 1 is from the distance is the actual distance or the grid position? and 2, i have problems with the global connection, how to populate and where?
Here is the function to add neigh with distance and put the checkConnection.
All the stars are stored in stars(array of star)
The global array will be populated on its own by the CheckConnection function. Just make sure it’s cleared in Get Neighbours before the loop. So you could create the array variable in the actor that GetNeighbours is in and pass it in to Add Neighbours by Distance. Add a clear node just before the loop. It should be of type StarPair and make it an array in the Details panel.
Sorry @AlienRenders i don´t get something i think
And here where i take the x,y and spawn the stars
This is the GetNeighburs, but i have 2 stars to conect one came from the for loop, and the other?
Sorry again i´m blocked
You don’t need the ADD node. Just remove that.
Actually, remove the CLEAR node as well. You only need to clear it once per grid. Sorry for the confusion. I hadn’t looked at this for a while. I think you could clear it where you also clear the Stars at the start of “Spawn Stars” function.
Initially, but it fills up as you go. Notice the ADD node near the return node?
I tried to make it as easy as possible for you to use with minimal changes to your existing graph.
Mmm, ok i get it, but something now is wrong with the connections
Now only show on pairs and not the node back
Why are lines disappearing? That has nothing to do with what I provided you.
I don´t know why
Here is how it works without the checkconnections
Well, you need to look at how you’re drawing the lines because nothing I provided you ever removes anything from any list/array.
Can I see a screenshot of the IsConnValid variable’s detail panel? And also the variable itself including the header it’s in. Thanks.
edit: There’s something wrong when you click on a second node. It’s not connecting to all its neighbours.
edit2: Can you provide the BP graph when you click on a node?
Also, at the end of “AddNeighboursByDistance”, you have a set “NDist” (can’t really make it out) variable. What is that? How is it used? That looks wrong to me.
Ok, that looks fine.
Need to see your BP when you click on a node.