Collision 'mesh' problem

[EulersIdentity]

I'm trying to set allowed and disallowed areas for characters to move to. What I'm doing is using a png to act as a sort of nav mesh. I then check if the pixel color at a location in my 'nav mesh' is green, if so the character is allowed to move there (turn-based rules).

Here's what I mean:


At first I set it up to check this every time update was called:

Code: Select all

-- return true if x,y is in the allowed area of the navmesh
function level.isAllowed(x,y)
  local r, g, b, a = level.navMeshData:getPixel( x, y )
  if r == LVL_ALL_R and g == LVL_ALL_G and b == LVL_ALL_B then
    return true
  else
    return false
  end
  -- !if
end
-- !isAllowed

function ent:update()   -- this is called in love.update()
  -- make current pc follow mouse if it's been grabbed
  if self.clicked then
    local x,y = love.mouse.getPosition( )
    x,y = x + camX, y + camY
    if level.isAllowed(x,y) then
       self.x,self.y = x,y 
    end
  end -- !if
end
-- !update

So this works fine...except it stops the character prematurely if you cross the boundary too quickly with the mouse. It also means that the character ceases all movement once the mouse is moving in the non-allowed area. It would be nice to have it snap to the nearest allowed spot in a straight line from where it started. My first thought that would work is to check every pixel along the path from the character's starting point to where the mouse currently is and have the character be placed at the first non-allowed pixel. This actually gives the desired behavior of not letting characters move through fences or boxes in their path in a straight line. My problem is that this seems like an insanely inelegant and inefficient way to code it. I don't want to check a series of 200, 300, 400 pixel x,y values on every call of update. Is there a neater way to solve this?

[Robin]

Here's a method that runs in O(log N) when moving N pixels
Check goal pixel. If green, go there, if not, do a bisection.
A bisection is like this:

bisect from A (start) to B (end)
check if the gap between A an B is large enough (say, larger than 1 pixel), if it isn't, move the player to A and stop the algorithm
find C (the midpoint between A and B, so (A + B) / 2)
if C is green:
bisect from C to B
else:
bisect from A to C

[EulersIdentity]

Thanks! That's a good solution. I had to think about how it would run for a second because at first glance I didn't believe that it would give me O(log N).