Gosu Forums
Topic Gosu / Gosu Exchange / Help with pathfinding:find closest path if cant reach target  By EdwinOdesseiron Date 2013-12-06 17:29
(Tried to fit thread into given space)

Hi all. I've slightly upgraded my pathfinding, so that it actively searches path between points. This has one pro, and one con:
Pro => is that the path is constantly refreshed; moving objects won't make player suddenly block or glitch
Con => when walking, if one of other moving objects (ex. other player character) blocks only way to reach the target, player stops and pathfinding gets erased. And I have a problem with that thing.

I reckon upgrading path finding in the way that whenever path can't be created, it looks for a closest reachable point and returns path to this point. This wouldn't be that hard to do (if path can't be created, just calculate approximate distance between path ends and target), but the problem is that my pathfinding (script below) works "backwards" - it goes from target to start point. This creates the problem that the "nearest point to target" (in this case: player) will be unreachable.

Thanks to a friend I've found one way I could kind of fix it - series of "waypoints" to which player would go (ofc. closest to target) if he can't reach the target itself. I guess it will work, but if anyone could help me with making it more advanced (so finding nearest available point and walking towards it) I would be really grateful.

My pathfinding code is here:
`def get_path(sx, sy, ex, ey)    map = []    for y in 0...@map_size      map[y] = []      for x in 0...@map_size        map[y][x] = 0      end    end    map[ey][ex] = 1    old_positions = []    new_positions = []    old_positions << [ex, ey]    depth = 2    depth.upto(100) { |step|      loop do        break if old_positions == nil        x, y = old_positions.shift        return [true, map, step] if x == sx and y + 1 == sy        if passable?(x, y + 1) and map[y+1][x] == 0 then          map[y+1][x] = step          new_positions << [x, y+1]        end        return [true, map, step] if x-1 == sx and y == sy        if passable?(x - 1,y) and map[y][x-1] == 0 then          map[y][x-1] = step          new_positions << [x-1, y]        end        return [true, map, step] if x+1 == sx and y == sy        if passable?(x + 1,y) and map[y][x + 1] == 0 then          map[y][x + 1] = step          new_positions << [x+1, y]        end        return [true, map, step] if x == sx and y - 1 == sy        if passable?(x, y - 1) and map[y-1][x] == 0 then          map[y-1][x] = step          new_positions << [x, y-1]        end      end      old_positions = new_positions      new_positions = []    }    return [false, nil, nil]  end`

And explanation - algorithms looks around the given tile, and assigns each surrounding tile a number (i+1, starting at 0). This keeps going on, until it reaches player. Then it returns the path `path = [boolean: path_finished?, [map], current_step]` which player follows (goes from a to b, where b = a - 1. Fairly simple, but it works.

Thanks a lot for any help =)
I played around with some A* a while ago, the repo is here:
https://github.com/shawn42/polaris

You can install it via gem install polaris

It operates on a map and location objects that you define. The common case of 2D can be found in the repo, but I've used it for 3D space and I'm sure you could use it for hex pathing too.

pull requests welcome    :D
Topic Gosu / Gosu Exchange / Help with pathfinding:find closest path if cant reach target