Options

Dynamic Pathfinding

• Dynamic Pathfinding
• Dynamic Pathfinding
by Jimmie
Sep 24 2006

This is a locked, single-post thread from Creation Asylum. Archived here to prevent its loss.

Warning from JimmieZeriab 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: 1)

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, @path)       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```

Zeriab Wrote: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!
Thanks given by: