Enforcing the player to follow a polyline (More challenging than it looks)

[tapir]

Hi guys/gals,

Capture.PNG (15.84 KiB) Viewed 2471 times

I'm working on a Qix/Volfied like game.
So the player is only allowed to move on the white line shown above. I've managed that easily with the code below except with one big problem.

Code: Select all

-- Check where will the player be next frame
-- But don't update the actual position yet
local x = player_pos.x + dt * player_vector.x * player_speed
local y = player_pos.y + dt * player_vector.y * player_speed

-- Check if the future position is still on the polyline
-- check_point_collision() returns the single line that the player is on if the point is on it
-- otherwise return nil 
local line = polyline:check_point_collision(x, y)
if line ~= nil then
	-- Check if the line is horizontal or vertical
	if line[1].x == line[2].x then
		-- If it's a vertical line then the future position's x should
		-- be the same as this vertical line (snap to line)
		x = line[1].x
	else
		-- If it's a horizontal line then the future position's y should
		-- be the same as this horizontal line (snap to line)
		y = line[1].y
	end
	
	-- Update the actual position of the player
	player_pos:set(x, y)
end
-- If the future position is out of the polyline then do nothing (don't update the actual position)

Some of you can already see the the problem: Corners.
The position update expression that I use gives a player step of 1.13 pixels per frame for 60 FPS. That means I will most probably miss the corner positions by fractions of pixels (meaning I will never really reach the corner) thus my check_point_collision() method will never see the other line that makes up the corner so the player will get locked.

I've also tried snapping to exact position of the corner when near it but at high FPS because the player step per frame is really really small, you can't escape the corner's snap force.
Also trying to detect an upcoming corner with a collision check (point in box) gives problems with the very small cornery areas like shown in above picture: It will detect more than one corner.

I feel like I'm missing a really obvious way to do it. If you have any pointers I would really appreciate it.

Thanks

[pgimeno]

Yeah, not simple. What follows is the approach I'd take.

I'd define the polyline like this:

Code: Select all

{ x1, y2, x3, y4, x5, y6, ... }

With that structure, the player's position within the polyline is a number between 0 and math.abs(x1)+math.abs(y2)+math.abs(x3)+...+math.abs(yN). With that in mind, it should be fairly clear how to calculate the player's coordinates. Say lx0, ly0 is the starting point of the polyline; then you set lx, ly = lx0, ly0 and length = 0, and while length < playerpos you do length = length + math.abs(polyline[ i ]) and update lx, ly (by alternating between lx = lx + polyline[ i ] and ly = ly + polyline[ i ] each iteration). When length >= playerpos, you've found the current segment the player is at. A simple rule of three using the difference between the previous segment's sum and the player's position, applied to lx and ly, tells you the actual player's coordinates.

That way the player would always lie within the polyline. If the player starts cutting, then the player's position becomes the cutting start position, and the player would be free to move (more or less).

It should be possible to save calculations by keeping track of which segment the player is at, and the partial polyline length, and update them every frame according to the distance advanced.

Did that make sense?

EDIT: Proof of concept:

Code: Select all

local lg = love.graphics

local polyline = { 50, 120, -20, -70, -30, -50 }
local polyLength = 50 + 120 + 20 + 70 + 30 + 50
local lx0, ly0 = 80, 15

local playerPos = 0
local playerVel = 50

function love.update(dt)
  playerPos = (playerPos + playerVel * dt) % polyLength
end

function love.draw()
  local px, py
  local lx, ly = lx0, ly0
  local lxn, lyn = lx0, ly0
  local length = 0
  for i = 1, #polyline do
    if i % 2 == 1 then lxn = lxn + polyline[i] else lyn = lyn + polyline[i] end

    lg.line(lx+0.5, ly+0.5, lxn+0.5, lyn+0.5)

    local segLen = math.abs(polyline[i])
    if length + segLen >= playerPos and length < playerPos then
      -- Found the segment where the player is. Calculate the ratio of the
      -- player position with respect to the segment it's at.
      local t = (playerPos - length) / segLen

      -- Apply the ratio to the segment (lerp). Reason for this formula here:
      -- http://math.stackexchange.com/questions/907327/accurate-floating-point-linear-interpolation
      px = lx - lx*t + lxn*t
      py = ly - ly*t + lyn*t
    end
    length = length + segLen

    lx, ly = lxn, lyn
  end

  lg.circle("fill", px+0.5, py+0.5, 3.5)
end

Even with a playerVel of 500 it always stays within the polygon, as it should.

[tapir]

Thanks for the detailed explanation. I kinda solved it with my current method by changing the "snap" behaviour but I will try yours as well. It looks like very clean way of doing it but I didn't understand it yet fully.

[ivan]

pgimeno's approach seems a lot more robust IMO.
The only thing I would change is, move the code into a function like:

Code: Select all

local px, py = getPointFromPolyline(polyline, length)

[pgimeno]

The basic idea is to calculate the total perimeter of the polyline, starting at a certain point, and express the player's position as the distance from that point along the polyline.

The perimeter is the sum of the lengths of the sides, which is calculated by absolute values of the coordinate increments (there's no point in using the Euclidean formula for axis-aligned lines).

The position of the player is then given by a number between 0 and the total perimeter of the polyline. If it is between 0 and the length of the first segment, then the player is in the first segment; else if it's between the length of the first segment and the combined lengths of the first and second segments, then it's in the second segment, and so on.

To calculate the current position of the player, you add segment lengths until you find the segment that the player is at. Then you can interpolate as I indicated to find the exact position. As long as the player's position is less than the total perimeter of the polyline, you will have the player always within the polyline.

@ivan: Yeah, I was going to, but as I was writing that proof of concept, I noticed that I could use the same loop for drawing and for finding the player's position, so I left that as an exercise to the reader