Help How do i approach this problem???
Author
i plan on making a diagram program like visio (i wish)...one thing im stuck is the connector thing...the connector,which is a line connecting to shapes,is so intelligent that it knows where it should go when its path is blocked,how do you suggest i approach this problem? (just think of the shapes as bounded by a rectangle,so collision checking will be easier)
as of now i think i should tackle it pixel per pixel more like the snake game...so if its blocked it will change direction and keep going...but there is a problem i think ill encounter here...its speed...for example i plan on moving one shape, of course the drawing panel will update thus causing the checking to trigger...imagine if the are many connector present...
please help me one this one
I'll assume that your connectors are line strips, i.e. a certain amount of points connected by lines.
First, I'll check the bounding rectangle of a line strip against each bounding rectangle of the other shapes on your diagram. The result is a list of possible colliders.
For each of the possible colliders, check every line segment against it for collision and calculate intersection points. Along your line strip, every collider should either create 0 intersection points (i.e. no collision) or 2 intersection points (one where the line strip enters the collider, one where it leaves the collider).
If you get 2 intersection points, remove every point from your line strip that is between those two. Then move the two points away from the collider along your line strip and create a line strip around the collider (consisting of lines collinear with bounding rectangle's edges) and insert that into your line strip.
The result should be your connector going around your collider.
I probably forgot quite a few special cases here and there, but I hope this helps anyway.
First, I'll check the bounding rectangle of a line strip against each bounding rectangle of the other shapes on your diagram. The result is a list of possible colliders.
For each of the possible colliders, check every line segment against it for collision and calculate intersection points. Along your line strip, every collider should either create 0 intersection points (i.e. no collision) or 2 intersection points (one where the line strip enters the collider, one where it leaves the collider).
If you get 2 intersection points, remove every point from your line strip that is between those two. Then move the two points away from the collider along your line strip and create a line strip around the collider (consisting of lines collinear with bounding rectangle's edges) and insert that into your line strip.
The result should be your connector going around your collider.
I probably forgot quite a few special cases here and there, but I hope this helps anyway.
Author
by you mean about the bounding rectangle of the line strip the bounding rectangle of each line or the whole connector line??
Quote:Original post by Skeezix
by you mean about the bounding rectangle of the line strip the bounding rectangle of each line or the whole connector line??
Sorry, I don't get what you're trying to ask entirely. If you want a clarification on this:
"First, I'll check the bounding rectangle of a line strip against each bounding rectangle of the other shapes on your diagram. The result is a list of possible colliders."
then:
Yes, I mean the bounding rectangle of the whole connector line, i.e. the line strip.
Author
can you make a simple code(even pseudocode) for that? i dont quite get the collision result..im thinking if you check the bounding of the whole connector line and other shape's bounding rect, you might get a lot of collision(per pixel that is)...how can you minimize that? or am i thinking wrong...can you show a code on how to get the collisions? thanks (sorry for the trouble)
Hiya.
It sounds like you want the shortest route between two points that doesn't intersect any shapes?
Sounds like a typical path finding problem to me, A* (or a variant of) may be a good simple solution. I would:
1. Use a grid.
2. Every time a shape is placed mark the neccessary squares in the grid as impassable. Recalculate the intersecting paths.
3. Every time a connector is placed traverse the squares using the A* algorithm to find a minimum cost path.
At the cost of speed, You can improve accuracy by decreasing the grainularity of the grid. You can find all you need to know about the A* algorithm here: http://theory.stanford.edu/~amitp/GameProgramming/
It sounds like you want the shortest route between two points that doesn't intersect any shapes?
Sounds like a typical path finding problem to me, A* (or a variant of) may be a good simple solution. I would:
1. Use a grid.
2. Every time a shape is placed mark the neccessary squares in the grid as impassable. Recalculate the intersecting paths.
3. Every time a connector is placed traverse the squares using the A* algorithm to find a minimum cost path.
At the cost of speed, You can improve accuracy by decreasing the grainularity of the grid. You can find all you need to know about the A* algorithm here: http://theory.stanford.edu/~amitp/GameProgramming/
At first glance the first thing that pops into my head is A* like Adventus suggested.
I found this extremely useful when having to learn A* for the first time:
clicky A*
it even has an available implementation of A* in the source code it provides.
If you only re-calculate your lines using the A* when u absolutely need to, i can see this being a very good method with little speed cost, try the source code in the link above and you will get an idea on the sheer speed A* can be calculated at by a computer. Personally i would think using the right grid size and a good A* implementaion i think you could create the effect you want nicely.
However, saying that if you take Visio as an example, take its straight "snake" like lines, they have points/nodes all along them and when they move out of the way of shapes its not exactly..."exact" it wouldn't surprise me if it was more bounding box or separating axis theorem based.
So if we break it down into steps for a simple example
imagine you draw your line from one box at the top of the page to another at the bottom, and place a box on that line (so now you want the line to move so it detours around the box ).
-1 the program needs to detect that collision between the line and the box? How are you doing broad phase collisition? there are a lot of different methods of checking to see if a line is colliding with a box. What information will you get at this point?
-2 your response to knowing the collision
-2A we want to split the line into more lines that we can move around the box
-2B then we want to move the lines, so we need to know where to split the line, how we are going to do it and how we work out how many points/nodes that line with now have
-2C This will depend on data from your collision detection, if you get some form of projection vector (preferably the shortest projection needed but it doesnt have to be fancy) basically the amount you need to shove the line out of the way and some kind of data telling you where the box intersects with the line. You should be able to get this data in the collision detection/in more detailed collision detection check to be ran after knowing there is some form of collision (narrow phase).
personally, once i had the first intersect, i would add a node to the line (spliting it into two "lines" that are connected), the first part of the line will now not collide at all, as i split it at the intersect (or a few pixels more in the y direction of the projection).
The second part still will, i would add another node in the same place, but push it out in the x direction of the projection. so if you can visualize this now we have node 1, the first point of the line drawing a straight line to node 2, the node we added first, node 2 is drawing a straight line to node 3, the one we pushed out, and node 3 is drawing a line to node 4 the end point of the line.
So by this point only node 3-node 4 is intersecting the box, diagonally, our collision check should pick this up and run a similar algorithm to what we already have, preferably if written correctly the same one.
But at the least the intersection should be detected again, the line should be split again and pushed out again with a new node to align with the x of node 3, at this point there will be a line going around the box but node 4-5 will be diagonal, to make it snake around the last bit you would have to mirror the logic of the first intersection.
you might find information in:
clicky Collision methods 2D-3D
useful
aswell as:
clicky Metanet!
You will find much more information then you need in these two links but i'm pretty sure you will be able to find snippets in them useful. The Metanet one is very good for thinking about collision flow.
***EDIT***
The 2D-3D collision methods doesn't seem to have the 2D collision methods i remember and you may find only the beginning of the first metanet article and section 4 of the second article, but if you skim read it you mite be able to pick somethings.
*******
There are definitely a lot of different ways to approach this, I would say that thinking of what type of lines and shapes you will add as you go along is the most important factor.
Good Luck, Chris
[Edited by - ChrisPepper1989 on November 25, 2008 10:20:12 PM]
I found this extremely useful when having to learn A* for the first time:
clicky A*
it even has an available implementation of A* in the source code it provides.
If you only re-calculate your lines using the A* when u absolutely need to, i can see this being a very good method with little speed cost, try the source code in the link above and you will get an idea on the sheer speed A* can be calculated at by a computer. Personally i would think using the right grid size and a good A* implementaion i think you could create the effect you want nicely.
However, saying that if you take Visio as an example, take its straight "snake" like lines, they have points/nodes all along them and when they move out of the way of shapes its not exactly..."exact" it wouldn't surprise me if it was more bounding box or separating axis theorem based.
So if we break it down into steps for a simple example
imagine you draw your line from one box at the top of the page to another at the bottom, and place a box on that line (so now you want the line to move so it detours around the box ).
-1 the program needs to detect that collision between the line and the box? How are you doing broad phase collisition? there are a lot of different methods of checking to see if a line is colliding with a box. What information will you get at this point?
-2 your response to knowing the collision
-2A we want to split the line into more lines that we can move around the box
-2B then we want to move the lines, so we need to know where to split the line, how we are going to do it and how we work out how many points/nodes that line with now have
-2C This will depend on data from your collision detection, if you get some form of projection vector (preferably the shortest projection needed but it doesnt have to be fancy) basically the amount you need to shove the line out of the way and some kind of data telling you where the box intersects with the line. You should be able to get this data in the collision detection/in more detailed collision detection check to be ran after knowing there is some form of collision (narrow phase).
personally, once i had the first intersect, i would add a node to the line (spliting it into two "lines" that are connected), the first part of the line will now not collide at all, as i split it at the intersect (or a few pixels more in the y direction of the projection).
The second part still will, i would add another node in the same place, but push it out in the x direction of the projection. so if you can visualize this now we have node 1, the first point of the line drawing a straight line to node 2, the node we added first, node 2 is drawing a straight line to node 3, the one we pushed out, and node 3 is drawing a line to node 4 the end point of the line.
So by this point only node 3-node 4 is intersecting the box, diagonally, our collision check should pick this up and run a similar algorithm to what we already have, preferably if written correctly the same one.
But at the least the intersection should be detected again, the line should be split again and pushed out again with a new node to align with the x of node 3, at this point there will be a line going around the box but node 4-5 will be diagonal, to make it snake around the last bit you would have to mirror the logic of the first intersection.
you might find information in:
clicky Collision methods 2D-3D
useful
aswell as:
clicky Metanet!
You will find much more information then you need in these two links but i'm pretty sure you will be able to find snippets in them useful. The Metanet one is very good for thinking about collision flow.
***EDIT***
The 2D-3D collision methods doesn't seem to have the 2D collision methods i remember and you may find only the beginning of the first metanet article and section 4 of the second article, but if you skim read it you mite be able to pick somethings.
*******
There are definitely a lot of different ways to approach this, I would say that thinking of what type of lines and shapes you will add as you go along is the most important factor.
Good Luck, Chris
[Edited by - ChrisPepper1989 on November 25, 2008 10:20:12 PM]
Author
i think A* is a bit overkill for this project of mine is there any simpler approach? i think ill look on the others
Ray/bounding box collision might be the best way to go.
As you draw shapes, put them in a spatial hierarchy, then when a ray is drwan, depending on the start/ end points, check for collisions with the shapes. If a collision is found, you'd need to segment the line at an appropriate point and draw the individual segments
As you draw shapes, put them in a spatial hierarchy, then when a ray is drwan, depending on the start/ end points, check for collisions with the shapes. If a collision is found, you'd need to segment the line at an appropriate point and draw the individual segments
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
