09-24-2006, 01:00 PM
Dynamic Pathfinding
by Jimmie
Sep 24 2006
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.
To use the script, call this script in any event:
Also, put this in either a "Game Start" event, or in your scene_title:
~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!
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.
No support is given. If you are the owner of the thread, please contact administration.
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
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!