Take the 2-minute tour ×

I apologize for the somewhat generic title. I'm really don't have much clue about how to accomplish what I'm trying to do, which is making it harder even to research a possible solution.

I'm trying to implement a path marker of sorts (maybe there's a most suitable name for it, but this is the best I could come up with).

In front of the player there will be a path marker, which will determine how the player will move once he finishes planning his turn. The player may click and drag the marker to the position they choose, but the marker can only be moved within a defined working area (the gray bit).

Path Marker Diagram

So I'm now stuck with two problems:

First of all, how exactly should I define that workable area? I can imagine maybe two vectors that have the player as a starting point to form the workable angle, and maybe those two arcs could come from circles that have their center where the player is, but I definetly don't know how to put this all together.

And secondly, after I've defined the area where the marker can be placed, how can I enforce that the marker should only stay within that area? For example, if the player clicks and drags the marker around, it may move freely within the working area, but must not leave the boundaries of the area. So for example, if the player starts dragging the marker upwards, it will move upwards until it hits he end of the working area (first diagram below), but if after that the player starts dragging sideways, the marker must follow the drag while still within the area (second diagram below).

First Diagram: Moving Upwards Second Diagram: Following the drag

I hope this wasn't all too confusing. Thanks, guys.

Edit: In case this makes a difference, I'm using C++ with Marmalade SDK.

share|improve this question
I think the term you're looking for is "waypoint", and can you mathematically define the grey area? The solution to your problem will probably be a lot easier if it is. –  John McDonald Oct 8 '12 at 0:04
Arent waypoints related to pathfinding and such? Also, mathematically defining the gray area is one of my problems :P I think I could figure out something like a rectangle or even a circle, but that kind of shape, with two arcs for sides and two other sides on an angle... It's a bit over my head. –  Vexille Oct 8 '12 at 5:24
You'll also need to specify which language and/or toolkit you're using, as solutions are primarily platform-dependent. –  Raceimaztion Oct 8 '12 at 9:35
Really? I figured an algorhithmic solution or even pseudocode would help. I'll edit the question anyway, just in case. –  Vexille Oct 8 '12 at 19:40
Define the shape in polar coordinates (max angle from characters angle and min/max distance from character). Then only update the waypoint to where the mouse is if the mouse is within those boundaries. If it exceeds any of those extreems snap it to the most extreem value possible. Start updating when clicked inside the area and stop when mouse is released. –  ClassicThunder Oct 8 '12 at 22:24

2 Answers 2

up vote 8 down vote accepted

You can define a workable area like the one in your question with three values:

float innerRadius;
float outerRadius;
float maxAngle;

These values will be based off a center point which may or may not be the player's position. The shape of the workable area depends on where you place this point.

enter image description here

In the example above the center position lies a certain distance (let's say 50 units) behind the player. This could be easily calculated as:

float offset = -50;
Vector2 centerPosition = playerPosition + offset * playerForward;

To limit the position of the marker to that workable area, first move the marker as you normally would. Then validate the distance between the center point and the marker:

Vector2 direction = markerPosition - centerPosition;
float distance = direction.Length();
markerPosition = centerPosition + direction * clamp(distance, innerRadius, outerRadius);

Finally, validate the angle of the marker to the specified range. I'll use pseudocode for this one:

- Find angle between vector C->M and vector playerForward
- If abs(angle) <= maxAngle Then do nothing
- Else If angle > 0 Then rotate M around C by maxAngle-angle
- Else If angle < 0 Then rotate M around C by -maxAngle-angle

Look around on how to rotate a point around another. It can be done either with trigonometry or a transformation matrix.

You might also want to take into account the marker's size and make the radius and angle a little smaller to compensate.

Edit: On second thought, it might look more natural if you validate the angle first, then the distance, so try both alternatives!

share|improve this answer
Great solution! I've come across something that involved two circles and a triangle, but your solutiong elegantly simplifies that. About the angle validation, I had thought of something along the lines of having a normalized vector that stood at maxAngle (and another at -maxAngle) from playerForward, which could be multiplied by the length of C->M in case it was of bounds, angle-wise. I'm assuming your solution of rotating M around C would be less costly, is that right? –  Vexille Oct 8 '12 at 23:17
@Vexille Well, rotating involves a cos and a sin operation, so I'm not sure. But to calculate those two vectors you also need to rotate them, although you only need to do it when the forward vector changes. Should not matter much anyway, pick the one you prefer to implement. –  David Gouveia Oct 8 '12 at 23:25
Great! Thanks, David. –  Vexille Oct 9 '12 at 0:24

I was thinking how the problem could be solved if the shape was irregular, and one couldn't define it mathematically. Warning: this is a dirty solution, not for the faint of heart.

1. Take your area:

enter image description here

2. And convert it to a monochromatic bitmap:

enter image description here and name it scale_0

3. Clone the bitmap and scale it down to 50%:

enter image description here and name it scale_1

4. And so on, until there's a bitmap less then 4 pixels wide/tall:

enter image description here enter image description here enter image description here enter image description here enter image description here scale: 2, 3, 4, 5, 6

5. Now we have our area as monochromatic bitmaps of different resolutions: enter image description here

6. Take the last image (here "scale_6") and iterate through all of it's pixels.

  • translate each pixel's coordinates to screen coordinates: x = Math.pow ( 2, scale_level ); where scale_level is the number we added after "scale_". We could also call it a quad tree level, though we're not really working with a quad tree. Do same with y.
  • check if pixel at translated x & y is black. If not, then it's not part of the shape, and you should just continue to next step of the loop
  • check if the pixel is closer to mouse cursor than previously checked pixel - if yes, save coordinates of the pixel - use the coordinates before translation, that is coordinates inside the bitmap.
  • at the end of the loop, multiply these coordinates by 2: x *= 2; y*=2; to translate them to coordinates in next image (previous scale)

7. Take previous image (here "scale_5"), but don't loop through all pixels; start at x = saved_x and end with x = saved_x + 2, same with y. That is, since now you will only loop through 4 pixels for every level! The rest is as in p. 6.

8. Take first image (the biggest = the one with biggest resolution), again loop through 4 pixels, and you finally have the pixel that is closest to mouse cursor:

enter image description here

enter image description here

enter image description here

9. However, I'm treating "M" as a point here. If you want it to be a circle that fits completely, you need to contract (shrink) the shape by circle.radius pixels first.

I thought I'd add that this algorithm will only work if you will use not monochromatic but grayscale images and treat a pixel as "full" if it's not white, and as "empty" if it's exactly white... OR if your resizing algorithm changes every group of 4 pixels into 1 black pixel every time when at least one of these 4 pixels wasn't white.

share|improve this answer
+1 Quite interesting :) –  David Gouveia Oct 8 '12 at 23:31
+1 for an answer for shapes that are difficult (if not impossible) to express mathematically. –  Cypher Oct 8 '12 at 23:39
Wow, very interesting. +1 too :D –  Vexille Oct 9 '12 at 0:02
I implemented it in real project, and I must say some problems emerged. Basically, you need to make a list of grid cells, where you take the closest grid cell named closest, and check for the distance to furthest point in the closest - let's name the distance furthest_dist. Now you need to remove from the list all cells which have their nearest point further than the furthest_dist and go level deeper. So instead of something like this: i.imgur.com/4UuFo.png It's something like this: i.imgur.com/dyTT3.png –  Markus von Broady Nov 13 '12 at 12:02

Your Answer


