Dynamic Pathfinding

[Jimmie]

Dynamic Pathfinding
by Jimmie
Sep 24 2006

This is a locked, single-post thread from Creation Asylum. Archived here to prevent its loss.
No support is given. If you are the owner of the thread, please contact administration.

Warning from Jimmie

Zeriab has posted an updated version, check post now for the new script!

What is this?
It's a pathfinding system based on the A* heurestics and algorithms.
Meaning: Call a script and sit back while your event moves. Other events and such are included in calcultions.

Should I use this in my game?
Actually, no.
It's still not stable enough to guarantee that your game won't hang up because of it. Also, it still doesn't work perfectly. It's awesome for mazes where the event is the only thing in it, but when other events come it, the route can get needlessly complicated because of the way this works.

Then why post it?
To show you guys that I'm stil active

Nah. Feel free to edit the script as much as you want, and if you make it work better, please post it here so the rest of us can improve on your improvements etc.
Ultimately, we'll have the best pathfinding system there is for RMXP


  Path_Finding_A_star.rar (Size: 196.14 KB / Downloads: 2)

In the demo, talk to Thief 01 to make him move towards the light.

Code:

class Pathfinding
  def move(event, trgx, trgy)
    @open = []
    @closed = []
    @tried = []
    @event = $game_map.events[event]
    @target_x = trgx
    @target_y = trgy
    @start_x = @event.x
    @start_y = @event.y

    @now_x = @event.x
    @now_y = @event.y

    @distance = Math.sqrt((@target_x - @now_x)**2 + (@target_y - @now_y)**2)
    @open.push(Waypoint.new(@now_x, @now_y,@distance,nil,0))

    while @open != []
      @open.sort!{|a,b|a.estimate<=>b.estimate}
      best = @open.shift
      @closed.push(best)
      @tried.push([best.x, best.y])
      if best.x == @target_x and best.y == @target_y
        break
      else
        for i in [0,1,-1]
          for j in [0,1,-1]
            next if ((i == j and i == 0) or (i+j).abs != 1)
            case i
            when 0
              case j
              when 1
                d = 2
              when -1
                d = 8
              end
            when 1
              d = 6
            when -1
              d = 4
             end

            if @event.passable?(best.x, best.y, d) and not @tried.include?([best.x+i, best.y+j])
              new_distance = Math.sqrt((best.x+i-@target_x)**2 + (best.y+j-@target_y)**2)+best.way
              wp = Waypoint.new(best.x+i, best.y+j, new_distance,best,best.way+1)
              if @open.include?(wp)
                if new_distance >= best.distance
                  @open.delete(wp)
                  @closed.push(wp)
                end
              elsif @closed.include?(wp)
                if new_distance < best.distance
                  @closed.delete(wp)
                  @open.push(wp)
                end
              else
                @open.push(wp)
              end
            end
          end
        end
      end
    end

    if @open != []
      @points = []
      route = RPG::MoveRoute.new
      node = best
      while node != nil
        @points.unshift([node.x, node.y])
        unless node.parent == nil
          if node.x > node.parent.x
            route.list.unshift(RPG::MoveCommand.new(3))
          elsif node.x < node.parent.x
            route.list.unshift(RPG::MoveCommand.new(2))
          elsif node.y > node.parent.y
            route.list.unshift(RPG::MoveCommand.new(1))
          else
            route.list.unshift(RPG::MoveCommand.new(4))
          end
        end
        node = node.parent
      end


      route.repeat = false
      @event.force_move_route(route)
      @event.target = [@target_x, @target_y]
      @event.path = @points
      return true
    else
      return false
    end
  end


  def fix_move(event, trgx, trgy)
    @open = []
    @closed = []
    @tried = []
    @event = event
    @target_x = trgx
    @target_y = trgy
    @start_x = @event.x
    @start_y = @event.y

    @now_x = @event.x
    @now_y = @event.y

    @distance = ((@target_x - @now_x)**2 + (@target_y - @now_y)**2)
    @open.push(Waypoint.new(@now_x, @now_y,@distance ,nil, 0))

    while @open != []
      @open.sort!{|a,b|a.estimate<=>b.estimate}
      best = @open.shift
      @closed.push(best)
      @tried.push([best.x, best.y])
      if best.x == @target_x and best.y == @target_y
        break
      else
        for i in [0,1,-1]
          for j in [0,1,-1]
            next if ((i == j and i == 0) or (i+j).abs != 1)
            case i
            when 0
              case j
              when 1
                d = 2
              when -1
                d = 8
              end
            when 1
              d = 6
            when -1
              d = 4
            end
  
            if @event.passable?(best.x, best.y, d) and not @tried.include?([best.x+i, best.y+j])
              new_distance = Math.sqrt((best.x+i-@target_x)**2 + (best.y+j-@target_y)**2)+best.way
              wp = Waypoint.new(best.x+i, best.y+j, new_distance,best,best.way+1)
              if @open.include?(wp)
                if new_distance >= best.distance
                  @open.delete(wp)
                  @closed.push(wp)
                end
              elsif @closed.include?(wp)
                if new_distance < best.distance
                  @closed.delete(wp)
                  @open.push(wp)
                end
              else
                @open.push(wp)
              end
            end
          end
        end
      end

    end
    @points = []
    if @open != []
      @path.shift

      node = best
      while node != nil
        @points.unshift([node.x, node.y])
      unless node.parent == nil
        if node.x > node.parent.x
          @route.list.unshift(RPG::MoveCommand.new(3))
        elsif node.x < node.parent.x
          @route.list.unshift(RPG::MoveCommand.new(2))
        elsif node.y > node.parent.y
          @route.list.unshift(RPG::MoveCommand.new(1))
        else
          @route.list.unshift(RPG::MoveCommand.new(4))
        end
      end
      node = node.parent
    end
    @event.path = @path
    @points.each{|a|@event.path.unshift(a)}
      return true
    else
      return false
    end

  end

  def fix(event)
    @route = event.move_route.deep_clone
    route2 = event.move_route
    event.move_route = nil
    @path = event.path.deep_clone
    path2 = event.path
    event.path = nil
    @x = event.x
    @y = event.y
    for i in 0...@path.size
      go= fix_move(event,@path[0][0], @path[0][1])
      if go
        return @route
      else
      @route.list.shift
      @path.shift

      end
    end
    event.stuck = true
    event.path = path2
    return route2
  end
end


class Waypoint
  attr_accessor :x, :y, :estimate, :parent, :way
  def initialize(x,y,estim,parent,way)
    @x = x
    @y = y
    @estimate = estim
    @parent = parent
    @way = way
  end
end

class Game_Character
  attr_accessor :move_route
  attr_accessor :move_route_index
  attr_accessor :target
  attr_accessor :path
  attr_accessor :stuck

  alias jimme_pf_passable? passable?
  def passable?(x,y,d)
    if jimme_pf_passable?(x,y,d)
      @stuck = false
      return true
    else
      if @path != nil and not @stuck
        ind = @move_route_index
        @move_route_index = 0
        for i in 0..ind
          @move_route.list.shift
          @path.shift
        end
        @move_route = $pathfinding.fix(self)
      end
    end
    return false
  end
end

class Object
  def deep_clone
    file = File.open('cloning.txt', "wb")
    Marshal.dump(self,file)
    file.close
    file = File.open('cloning.txt', "rb")
    data = Marshal.load(file)
    file.close
    return data
  end
end

There might be problems if you go in front of the NPC... Haven't tested, just a thought during writing this.

To use the script, call this script in any event:

Code:

$pathfinding.move(event no, destination x, destination y)

Also, put this in either a "Game Start" event, or in your scene_title:

Code:

$pathfinding = Pathfinding.new

~Jimmie

PS: For the sake of our computers, I will NOT make this script check all possible routes.
In a standard 15x20 map, with no blocked tiles (and disregarding borders), this would lead to
13689147905858837599132602738208831596646369562533743647148019007836899717749907
6593800206155688941388250484440597994042813512732765695774565400
loops!