Welcome to the Bitcave! Nerdiness, Jokes, Mods, Ideas, and coding!

Modding
59

NB: I wrote most of this several hours ago and just didn’t hit post so it may seem to ignore the two most recent posts in part.

Analysis! Alrighty here we go, in any old order here are things to look into for improving it.

  • Break statements, they can get rid of the end_condition stuff.
  • Store the obstacles as a list of coordinates to allow for multiple
  • You don’t actually have a 6x6 limit, your alg would work for any size if you put in other numbers.
  • You can strip the giant if block to two statements to move it towards the target each time. Make them like so: los_x = los_x + (target_x-los_x)/abs(target_x-los_x)

And now for an improved los alg. First the one you have has two major issues, it’s slow having to loop through every intermediate square and it doesn’t work as shown in this rather bad image your code checks the brown path where it should be checking something similar to the red path.

Now for code to check the red path. What you need to do here is actually just run a rect line collision test and a rect rect collision test. First off for the rect rect test you just check whether the obstacle is within the rect by the target and position to see whether it’s possible to collide at all. Psuedocode follows

if obs_x >= min(pos_x, tar_x) and 
   obs_x <= max(pos_x, tar_x) and 
   obs_y >= min(pos_y, tar_y) and 
   obs_y <= max(pos_y, tar_y) then
    test succeded
end

The line square collision is slightly more complex but still fairly simple. Treating the center of each square as the grid points it would go as follows.

gradient = (pos_y-tar_y)/(pos_x-tar_x)
if (obs_x - pos_x + 0.5*sign(gradient)) * gradient <= 
                                              (obs_y - pos_y - 0.5) and 
   (obs_x - pos_x - 0.5*sign(gradient)) * gradient >= 
                                             (obs_y - pos_y + 0.5) then
    test suceeded
end

They rely on the fact that all obstacle are 1x1 squares but could be easily modified for rects of other sizes, other shapes would require more substantial changes however. It’s all a matter of how you do and what suits the scenario, checking every square is better when the path is shorter than the amount of obstacles and my example is better in the opposite.

2 Likes