Hello,

I'm working on a point'n'click engine, and I've having some issues with the walkable area (that's the area in the screen where the character can walk to). I define the walkable area using a polygon class where I add the vertices of the polygon (in green). Every time the player clicks on the screen, I check if the destination position (pixel) belongs to the walkable area. If it belongs, I calculate the shortest path to the destination (using Dijkstra algorithm). If not, I calculate the intersection point between the polygon and line from the current char position and the destination position (in blue). The char wont go further the green line.

To check if two segments intersect, I'm using a very common algorithm you can find in Internet:

int LPolygon::getIntersection( int _mouseX, int _mouseY, int _srcX, int _srcY, int* _crossX, int* _crossY ) {
// Function to return IF and WHERE the trajectory from the char and the mouse position intersects with the WalkableArea

float s1_x, s1_y, s2_x, s2_y;
float s, t;
s2_x = _mouseX - _srcX;
s2_y = _mouseY - _srcY;

// Loop through all edges of the polygon
for( int i = 0; i < mNumVertex-1; i++ ) {
s1_x = mVertexArray[i+1].x - mVertexArray[i].x;
s1_y = mVertexArray[i+1].y - mVertexArray[i].y;
s = (-s1_y * (mVertexArray[i].x - _srcX) + s1_x * (mVertexArray[i].y - _srcY)) / (-s2_x * s1_y + s1_x * s2_y);
t = ( s2_x * (mVertexArray[i].y - _srcY) - s2_y * (mVertexArray[i].x - _srcX)) / (-s2_x * s1_y + s1_x * s2_y);
if (s >= 0 && s <= 1 && t >= 0 && t <= 1) {
*_crossX = (int)(mVertexArray[i].x + (t * s1_x));
*_crossY = (int)(mVertexArray[i].y + (t * s1_y));
return true;
}
}
return false;
}

The issue I have is, from this intersection point, next time you click outside the walkable area, sometimes the char escapes the walkable area, depending on the angle (or so I think).

Any ideas/recommendations on how to solve this issue?

Thank you!

The most obvious conclusion would be that your character travels to the exact intersection point, and then moves before doing the next intersection test, thus missing it. Such order-dependent errors are common (in my code at least :D) Of course this is only one of the many possible causes.

Ah, Klaus Kerner! I knew I'd find you here!

Proper response:

I know I'm being annoying here, to suggest you taking a slightly different approach. Ypu already have Dijkstra in place, so how about creating a graph for walkable nodes instead? You could make it so that the character walks to the node nearest to the click (and you could even expand this to allow walking part of the edge between two nodes)

In my mind, this is simpler than gymnastics in image space, but I get that you'd like the freedom from defining a walkable polygon. Perhaps several nodes sprinkled across the polygon would provide a similar effect?

@Prototype Thanks for your answer. The sequence seems to be right. Once the Player clicks on the screen, all the checks and calculations are performed, and then the player starts moving…

Try stepping through your code using breakpoints & watches to see what the actual values are. Is the endpoint still inside the polygon etc. Otherwise there might be a problem with your intersection test. One thing that occurs to me is that you might be missing the closing edge, which goes from the last vertex back to the first. HTH.

@SuperVGA Thanks. This is precisely what I do. I check for concave vertex and create a graph with them. As you can see in the image, the polygon is closed (last edge is back to the first vertex). I think it may be a problem with the intersection accuracy. The game is 1920x1080, but I "floor" all vertex to mod(5), to provide a retro look & feel. This means, the “pixels” in the screen are 5x5, instead 1x1.

@Prototype Thanks, I'm afraid is not gonna be easy to catch the glitch.

I think there may be a bug calculating the intersection point when the source coordinates already belong to the edge… what do you think?

I'm out of ideas, but generally if you want >1 pixel size it's more convenient to render in normal resolution and then do a nearest-neighbour upscaling. That does away with clumsy conversions, saves graphics data and makes your game scalable to other resolutions as well.

Jelonertz said:

I think there may be a bug calculating the intersection point when the source coordinates already belong to the edge… what do you think?

Well that was my first hunch, you would have to test your algorithm with known values to check that. Also note that you probably will be dealing with rounding errors, so it's probably better to not stick exactly on an edge.