Beginner Question? Valid-Move Area
Author
Not sure what forum to pose this question on...Isometric or math...
In my game idea, I would be simulating a tabletop wargame.
Pieces in such a game move a certain distance, e.g. 6 inches. I would like to display where a piece can move when selected. In the simplest case, this is just a circle of the move distance in radius. However, a piece may not move directly through other pieces or certain areas on the board. If a piece is nearby, it is not as easy to just cookie-cutter that area out as the moving piece cannot move as far into the areas behind the intervening piece. You end up with a circle with the intervening piece cut out along with the other side a drawn in part of the full-movement circle. Further complications arise when the moving piece has a shape as well, especially square or irregular shapes that are not rotationally symetric. Also, multiple intervening pieces may block out areas that would be accessible when considering them separately, e.g. 2 pieces near to each other would block out any passage between them.
It seems there should be a solution to use the original shape, move distance, and intervening shapes to make a valid move area. I'm not sure if there is a geometric approach or whether there is some sort of deformation approach. I cannot think of a game that does this to cite as an example either. Any help on where to ask further or any documents I could read about the subject would be appreciated.
Thanks in advance
Quote:Original post by darklord4Hm. I think I understand what you're getting at, and it sounds like a pretty tough problem. I'm guessing some sort of solution could be developed based on finding the shortest path around each polygonal obstacle and then, once the obstacle is cleared, using the remaining distance to build up the (deformed) outer periphery of the 'valid move' circle. I think it would take a little thought and effort to implement this, but it is a neat idea (that is, a 'blob' showing where the unit can move).
Any help or suggestions about where to look or rephrase of the question?
Is your game tile-based at all? Even if not, another option would be to sample the space and run A* on all nodes in the 'move area' to build up the 'valid move' blob. Even with a relatively small search space, however, this might be too slow.
Sorry I don't have a definite answer, but at least your post will get bumped back up :) Maybe someone else will be able to offer a different/better suggestion, or go into more detail regarding one or both of the above ideas.
Well, there are several components to your problem. First, an obvious optimization is to discard all objects or parts of objectswhich are not within the unmodified movement circle.
The second part (arbitrary shapes) is actually simpler to handle, you only have to "expand" the existing obstacle shapes by adding to them the dimensions of the object (as expanded from its center) in a direction proportional to their surface. You end up with a circle with radius zero (the object to be moved) and an entire area of objects made up of lines and circle arcs. This is the area that you must move through. As an additional processing step, I would approximate circle arcs with octogons from within.
Now, the edge of the accessible area is composed of a subset of the edges of the obstacles, with the remaining edge being composed of circles. Well, not exactly: when moving around a circle, the edge of accessibility is actually a little bit larger than a circle (which is why a circle-shaped piece is actually not the simplest case: a square or octogon would be), but if most of your obstacles are polygonal (as approximated in the previous step), then you may be able to ignore this effect. The objective, I assume, is to construct that shape, or a polygonal approximation of that shape.
What you will look for is a visibility tree. The basic idea is to perform a dijkstra search on the entire visibility graph within the maximum circle, but cutting off whenever the distance to reach a point is greater than the movement distance allowed (that is, if a point is too far away to be reached, you don't iterate through its neighbours).
Then, you traverse the tree by "filling out" areas which are reachable: starting with the root, consider the spaces between the edges going out of a node (those which go out to children), and draw a cone in each of these spaces (clipped to a triangle if the two children are on the same obstacle. There are some special cases to be handled (for instance, when the reachable area is convex) but all of this can be done by slightly altering the traversal process.
The second part (arbitrary shapes) is actually simpler to handle, you only have to "expand" the existing obstacle shapes by adding to them the dimensions of the object (as expanded from its center) in a direction proportional to their surface. You end up with a circle with radius zero (the object to be moved) and an entire area of objects made up of lines and circle arcs. This is the area that you must move through. As an additional processing step, I would approximate circle arcs with octogons from within.
Now, the edge of the accessible area is composed of a subset of the edges of the obstacles, with the remaining edge being composed of circles. Well, not exactly: when moving around a circle, the edge of accessibility is actually a little bit larger than a circle (which is why a circle-shaped piece is actually not the simplest case: a square or octogon would be), but if most of your obstacles are polygonal (as approximated in the previous step), then you may be able to ignore this effect. The objective, I assume, is to construct that shape, or a polygonal approximation of that shape.
What you will look for is a visibility tree. The basic idea is to perform a dijkstra search on the entire visibility graph within the maximum circle, but cutting off whenever the distance to reach a point is greater than the movement distance allowed (that is, if a point is too far away to be reached, you don't iterate through its neighbours).
Then, you traverse the tree by "filling out" areas which are reachable: starting with the root, consider the spaces between the edges going out of a node (those which go out to children), and draw a cone in each of these spaces (clipped to a triangle if the two children are on the same obstacle. There are some special cases to be handled (for instance, when the reachable area is convex) but all of this can be done by slightly altering the traversal process.
What you are looking for is a path finding function, if you run a search on the forums for "Path finder" should bring up alot of results, many with complete code. That should solve the problem for you.
Blu
Blu
Quote:Original post by bluwind
What you are looking for is a path finding function, if you run a search on the forums for "Path finder" should bring up alot of results, many with complete code. That should solve the problem for you.
Not really. He wants the set of *all possible* paths. Asking "Is there a path to here from the start?" for every path within the movement range is going to take forever.
I think ToohrVyk is on to something; it's more or less what I had in mind. I think what you want to do is extend lines from the center of the movement circle to "interesting points" on the modified obstacle boundaries (tangents to the circular arcs, rejecting those that intersect a boundary); those define regions that you can fill in right away as reachable, and then from the points where you touch the boundary, you can apply the process recursively for the remaining distance at that point. Unfortunately this doesn't really work because marching "around" the circular arcs would require infinitely many steps (you're already "tangent to" the arc when you start the first recursive step), so you'd definitely need to do some approximation :)
Here's a rough illustration of the algorithm.
Author
The idea for the game was to simulate a tabletop miniature wargame, e.g. warhammer, so no tiles(at least as how I understand their use). Everything would be considered in 2D, though. An example would be in strategy RPGs where the valid move squares/hexes are highlighted, except this would be general area, not squares/hexes. The idea is still in the on-paper-at-work use-case stage of development, I was just curious how one would calculate a move area.
I thought irregular or squared shapes would be more difficult as they can be in any orientation, e.g. a square is not always oriented with sides always parallel with other square or rectangular shapes. Further, the shape can be "spun" while moving without losing any movement distance.
I thought there would be some sort of visibility algorithm that could be used, but they don't look cheap process wise. I was hoping that there would be a cheap way to find an area without having to digitize down to a high definition grid, giving a close approximation of free placement.
There are some interesting cases of the "Tangents of Interest" algorithm. It seems there would be a lot of recursive steps to get around a curve.
It is really a set of all possible paths, not just determining is a path possible.
Thanks for all the input, I have some algorithms to look up and explore now.
I thought irregular or squared shapes would be more difficult as they can be in any orientation, e.g. a square is not always oriented with sides always parallel with other square or rectangular shapes. Further, the shape can be "spun" while moving without losing any movement distance.
I thought there would be some sort of visibility algorithm that could be used, but they don't look cheap process wise. I was hoping that there would be a cheap way to find an area without having to digitize down to a high definition grid, giving a close approximation of free placement.
There are some interesting cases of the "Tangents of Interest" algorithm. It seems there would be a lot of recursive steps to get around a curve.
It is really a set of all possible paths, not just determining is a path possible.
Thanks for all the input, I have some algorithms to look up and explore now.
ToohrVyk has pointed you in the right direction, I have this to add:
In computational geometry this problem is sometimes called the piano mover's problem. But it is basically a motion planning problem.
Not very wide awake, but here's my approach:
Eliminate objects/obstacles outside the maximum movement radius.
Add radius of moving object to obstacles, for polygonal obstacles the result is difficult(tm) to construct, suggest using an approximation like 4-8 vertices along the curve that would be generated around vertices.
If you ONLY have circular obstacles:
you can just use a voronoi diagram (dirichlet subdivision) of the plane, neighbouring sites in the voronoi diagram are checked for overlap/intersection, if they overlap, the corresponding voronoi edge is not a valid path and is removed from the tree.
what's left is a loose path tree for the moving actor. Compute a circle-wrapping path tree and cull it at the maximum distance that can be travelled. This last algorithm is non trivial.
If you have a mixture of obstacles:
Compute a planar polygonal union of the obstacles (with pure arcs if you really want a headache), use the resulting obstacle map in a path-finding algorithm.
Final Note:
Doing this well/accurately is NOT EASY, I say this having done Computational Geometry programming for years, be sure and seek assistance as you progress, it will help you go much faster.
Feel free to email me with questions (remember the rules about asking good questions).
In computational geometry this problem is sometimes called the piano mover's problem. But it is basically a motion planning problem.
Not very wide awake, but here's my approach:
Eliminate objects/obstacles outside the maximum movement radius.
Add radius of moving object to obstacles, for polygonal obstacles the result is difficult(tm) to construct, suggest using an approximation like 4-8 vertices along the curve that would be generated around vertices.
If you ONLY have circular obstacles:
you can just use a voronoi diagram (dirichlet subdivision) of the plane, neighbouring sites in the voronoi diagram are checked for overlap/intersection, if they overlap, the corresponding voronoi edge is not a valid path and is removed from the tree.
what's left is a loose path tree for the moving actor. Compute a circle-wrapping path tree and cull it at the maximum distance that can be travelled. This last algorithm is non trivial.
If you have a mixture of obstacles:
Compute a planar polygonal union of the obstacles (with pure arcs if you really want a headache), use the resulting obstacle map in a path-finding algorithm.
Final Note:
Doing this well/accurately is NOT EASY, I say this having done Computational Geometry programming for years, be sure and seek assistance as you progress, it will help you go much faster.
Feel free to email me with questions (remember the rules about asking good questions).
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
