Path Finding

0 Members and 1 Guest are viewing this topic.

*
Rep:
Level 97
2014 Best RPG Maker User - Engine2014 Most Unsung Member2013 Best RPG Maker User (Scripting)2012 Favorite Staff Member2012 Most Mature Member2012 Best RPG Maker User (Scripting)2012 Best MemberSecret Santa 2012 ParticipantProject of the Month winner for July 20092011 Best RPG Maker User (Scripting)2011 Best Veteran2011 Favourite Staff Member2011 Most Mature Member2011 Best Use of Avatar and Signature Space2010 Favourite Staff Member2010 Most Mature Member
When I write a new version of this script, I will allow for it. As it is, you would need to alter the script so that it retains the size of the path and the old command, and then just reset the move event command.

**
Rep:
Level 83
I just wanted to let you know that this is a very great and important VX script ;)

You have all my compliments :)

*
Rep:
Level 97
2014 Best RPG Maker User - Engine2014 Most Unsung Member2013 Best RPG Maker User (Scripting)2012 Favorite Staff Member2012 Most Mature Member2012 Best RPG Maker User (Scripting)2012 Best MemberSecret Santa 2012 ParticipantProject of the Month winner for July 20092011 Best RPG Maker User (Scripting)2011 Best Veteran2011 Favourite Staff Member2011 Most Mature Member2011 Best Use of Avatar and Signature Space2010 Favourite Staff Member2010 Most Mature Member
Thank you for that. It is still quite flawed though. I do intend to work on making a better version once my schedule clears up.

********
Resource Artist
Rep:
Level 94
\\\\\
Project of the Month winner for June 2009
Still a great script MA.

Just cleaning some spam.
~Fix'd spam junkie Shandy333~ He needs to keep his shit shut.
« Last Edit: August 19, 2009, 09:29:07 PM by grafikal »

**
Rep: +0/-0Level 90
Necro for the sake of support:
I have this http://www.rpgmakervx.net/index.php?showtopic=17774&st=0&p=153712&#entry153712 script - how would the pathfinding work, assuming I set one tile paths to look like, vertically and in order, ceiling wall wall ceiling?
Would it recognize a path there?
"Lightning is like a troll, you don't know what hit you till you smell it!"

*
Rep:
Level 97
2014 Best RPG Maker User - Engine2014 Most Unsung Member2013 Best RPG Maker User (Scripting)2012 Favorite Staff Member2012 Most Mature Member2012 Best RPG Maker User (Scripting)2012 Best MemberSecret Santa 2012 ParticipantProject of the Month winner for July 20092011 Best RPG Maker User (Scripting)2011 Best Veteran2011 Favourite Staff Member2011 Most Mature Member2011 Best Use of Avatar and Signature Space2010 Favourite Staff Member2010 Most Mature Member
Umm, not sure. I have not really looked at the coding for that script before. Have you tested it?

**
Rep: +0/-0Level 90
Did test, not sure what caused it, but something more than this script mucked it up. Not sure what so can't provide a straight test conclusion.
I know path finding worked in a room with no obstacles but not from one room to another. Odd that, really.
"Lightning is like a troll, you don't know what hit you till you smell it!"

*
Rep:
Level 81
How easy would it be to allow this to create a path to get to the position (but one) of the player? Looking at the script and running some tests, it doesn't seem to like you specify a position that VX determines as impassable.

I tried to do something with it without going into anything too heavy for the GIAW contest, but didn't get too far with it at the time. Thinking about it though, I'd also need something along the lines of what you had planned for V3 of this script, in particular the recalculation of the route part due to the game including many moments in which the situation of the game and the player could change (in both subtle and dramatic ways).

Really, it'd just be nice to be able to move towards the player's location. Unless it'd just be simpler for me to work on my own version of the script so that I can make it work easier with the other idea(s) that I have planned.

I have no issues with scripting path finding algorithms (having based my uni dissertation on said algorithms), but seeing as this script already exists, I figured I'd see what you could do before I start the researching and planning that I'll have to do. Even some good ideas for me to look into/work on would be appreciated.

Thanks in advance, for whatever you can provide me with.
(Why do I always feel like it's the end of the world and I'm the last man standing?)

*
Rep: +0/-0Level 67
RMRK Junior
Hey MA, any news on a V3 of this script? We're trying to get a stable mouse system going, and we're running into problems with the current version of this script, which we're using for the script. It's actually just lag stuff, which we're trying to fix in other means, but we're getting some problems. I read that you have a better, faster version of this coming.. Is this still in development?

Or heck, what would be even easier, if you could maybe explain how we could set two different counts. One to keep track of the iterations, and one to keep track of the steps between the paths, and I think we could fix the problems we're having.
« Last Edit: June 17, 2011, 01:47:39 AM by Beleren »

***
Rep:
Level 84
---> LOL <---
Sorry for necro posting but I found a bug:

The script  allows me to make a npc (or character) walk to a specific x and y coordinate on a map. It will determine the shortest path and walk there. How ever I found in maps with heavy obstacles that npc will not move.

For example, Suppose you have a pub with lots of NPC's, chairs, tables and obstacles. now make an NPC walk from point A to b, wait, walk from point b to the exit (disappear - wait re-apear) and walk to point C (some other place in the pub). Depending on how obstacle heavy your pub is (and this one is obstacle heavy) that NPC will disappear (it will essentially skip to the "leave the pub" section) and then after some frames re-apear and try to walk across the pub. This should not happen. the NPC should follow the command given by:

 find_path (target_x, target_y, diagonal, max_iterations)

in this instance max-iterations is set to 0 (tested it with a number like 10 still doesn't change anything). Now maps that are not obstacle heavy like plains or a small forest the character can walk to the location given by this command. How ever if the map were to have lots of barrels or trees and lots of ways that the character could get to there destination it will skip that step or not move at all or in this case, the case of the pub example, leave and come back - essentially skipping to some other part of the movement commands given.

Hope this helps. I believe its an issue with your antilogarithm.

***
Rep:
Level 84
---> LOL <---

*
Rep: +0/-0Level 54
Kan
Are you still planning to make V3 of this script? I'm just curious because I can't use it, since routes aren't being recalculated. It would be great if anyone could fix this, as my scripting skills aren't good enough to alter this script by myself. And sorry for necropost.
I'm sorry for my bad English

**
Rep: +0/-0Level 27
RMRK Junior
Is there a way to make an event go directly to the player ? This sounds like a gnar-gnar script, but it'd be even better if you could do that.
I've tried setting the script in the move route to "find_path($game_player.x, $game_player.y)" on repeat, but it doesn't seem to work. The event stays in place. And the pathfinding on the default "approach" is really iffy... when the events are too far away from the player, they get stuck in walls or don't move at all.

*
Rep: +0/-0Level 23
Music Addict
This is the only viable pathfinding script I can find for VX, unfortunately I'm having the same problem as slayer.

Would really appreciate it if you could do something about that recalculation (maybe a line that reloads the event page?). Script doesn't need to be any more efficient IMO, it just needs to be able to recalculate.

If it helps as reference, I have an ACE pathfinding script which does recalculate:

Spoiler for:
Code: [Select]
#===============================================================================
# Pathfinding & Event formations
# By Jet10985(Jet) & Venima
#===============================================================================
# This script will allow you to use a pathfinder to move players or events.
# Modification: This script will also allow you to use a pathfinder which
# incorporates formation handling.
# This script has: 2 customization options.
#
# Modifications:
# Pathfinder:
# Goal location may now be inpassable, pathfinder will still reach it.
# Pathfinder still works "as intended" when the move route is set to repeat.
# Added parameter: distance (explained below).
# Added parameter: jump (set to true if the moves should be jumps instead of
# walking).
# Added parameter: commonEvent (provide the common event id for the pathfinder
# to run the event before each move (useful for adding sound or effects to
# movements)
# Added parameters:
# catchup (provide a value to indicate how far from the target the event
#   should be before it speeds up its movement)
# catchupSpeed (provide a value for the speed when catching up)
# normalSpeed (provide a value for the speed after its caught up)
# Note: Pathfinder is a bit more processor heavy when used with a repeating
# move route (it was useless before, so this is only a benefit)
# Formations:
# Added find_formation_path function
# Added turn_with_player function
#
#===============================================================================
# Overwritten Methods:
# None
#-------------------------------------------------------------------------------
# Aliased methods:
# None
#===============================================================================
=begin

===============================================================================
 Instructions:

===============================================================================
 Standard pathfinder:
-------------------------------------------------------------------------------

To move a player or event, use this in a move route's "Script..." command:

find_path(x, y, distance = 0, jump = false, commonEvent = 0, catchup = 0,
      catchupSpeed = 5, normalSpeed = 4)

x is the target x

y is the targey y

distance is set to 0 by default and can be omitted to keep the default value.
While x and y represent the target location, the event will only be moved
up to the specified distance from the target. This makes it easier to have
an event follow the player, without getting in the player's way. This could
be used as an alternative to following, except it works on any events,
not just party members.

jump is set to false by default and can be omitted. Jump specifies that
instead of the event "moving" to the target, the event will make small "jumps"
to the target. If you specify jump, you cannot omit any previous parameters.

commonEvent is set to 0 by default and can be omitted. This specifies the
id of a common event that you want executed before each move step. Currently
this only applies to repeating paths. When set to 0, no common event is called.
If you specify commonEvent you cannot omit any previous parameters.

catchup is set to 0 by default and can be omitted. Catchup specifies that if
the event is equal to or past the catchup distance, they will move faster to
"catch up". Their speed becomes the catchUp speed. Once caught up, they will
return to the normalSpeed. If you specify catchup you cannot omit any previous
parameters.

catchupSpeed is set to 5 by default and can be omitted. It is used when catchup
is specified to a value above 0. (see catchup for details). If you specify
catchupSpeed you cannot omit any previous parameters.

normalSpeed is set to 5 by default and can be omitted. It is used when catchup
is specified to a value above 0. (see catchup for details). If you specify
normalSpeed you cannot omit any previous parameters.



Running the script outside of a move route (as a standalone script call)
has two extra parameters after x and y called "ev" and "wait" but has no
commonEvent or catcup parameters.

find_path(x, y, ev = 0, wait = false, distance = 0, jump = false)

ev is set to 0 by default and can be omitted like so: find_path(9, 4).
Ev represents which character is to be moved. -1 is the player, 0 is the
calling event, and anything above is an event on the map whose ID is the ev.

wait is set to false by default and can be omitted like so:
find_path(9, 4) or find_path(9, 4, -1)
find_path(x, y) or find_path(x, y, ev)
wait specifies if the player will have to wait for the move route to finish
to start moving again.

-------------------------------------------------------------------------------
 Examples:

Example of following the player at a distance:

In event's custom move route or specified move route (on repeat):
  find_path($game_player.x, $game_player.y, 3)
 
Example of an event following an event with id 2 and catching up:
  find_path($game_events[2].x, $game_events[2].y, 0, false, 0, 3)

===============================================================================
 Formation handling:
-------------------------------------------------------------------------------

To move an event using a formation use this in a move route:

find_formation_path(followId, shiftX, shiftY, catchup = FORM_CATCHUP_DIST,
      catchupSpeed = 5, normalSpeed = 4)
     
followId is the character that this event is in formation with. -1 = player,
0 = current event (although this is pointless) and above 0 is the event id.

shiftX is the relational x position from the followId character WHEN that
character faces "down". If you enter -1, this event will move to the left if
its facing down, or right if its facing up.

shiftY is the relational y position from the followId character WHEN that
character faces "down". If you enter -1, this event will move above if its
facing down, or below if it's facing up.

catchup's default value is specified by the parameter FORM_CATCHUP_DIST and
can be omitted. This specifies how far behind this event can get before it
speeds up to catch up.

catchupSpeed's default value is 5 and can be omitted. This specifies how fast
this event will move when it's "catching up". If you specify catchupSpeed, you
cannot omit any previous parameters.

normalSpeed's default value is 4 and can be omitted. This specifies how fast
this event will move when it isn't "catching up". If you specify normalSpeed,
you cannot omit any previous parameters.


You also have another command for formations:
Entering "turn_with_leader" as a separate script after find_formation_path
will cause the event to turn the same way the player is turned after arriving
at their formation position.
Entering "turn_with_leader(1)" will turn the same way as event with id 1.
Turn_with_leader also has a second optional parameter. Entering "left" or -1
will turn this event left of the leader's direction, entering "right" or 1
will turn this event right of the leader's direction, and entering "back" or 2
will turn this event opposite of the leader's direction. Again, if you specify
this parameter, you cannot omit the previous one.

-------------------------------------------------------------------------------
 Examples:

Example of 2 events acting similar to followers behind the player:
In a repeating move-route for Event 01:
find_formation_path(-1,0,-1)
In a repeating move_route for Event 02:
find_formation_path(1,0,-1)

Example of an event covering the player's back 2 spaces away:
In a repeating move-route:
find_formation_path(-1,0,-2)
turn_with_leader(-1,"back")

Example of an event with a formation determined by in-game variables:
In a repeating move-route:
find_formation_path(-1, $game_variables[1], $game_variables[2])

=end

#===============================================================================
# Customisation options below:
#===============================================================================
module Venima
  module Formations
    #
    FORM_CATCHUP_DIST = 3
  end
end

module Jet
  module Pathfinder
   
    # While mainly for coders, you may change this value to allow the
    # pathfinder more time to find a path. 1000 is default, as it is enough for
    # a 100x100 MAZE so, yeah.
    # Note from Venima, you probably don't want to change this value too much
    MAXIMUM_ITERATIONS = 500
   
  end
end
#===============================================================================
# Customisation end
#===============================================================================

class Node
 
  include Comparable

  attr_accessor :point, :parent, :cost, :cost_estimated

  def initialize(point)
    @point = point
    @cost = 0
    @cost_estimated = 0
    @on_path = false
    @parent = nil
  end

  def mark_path
    @on_path = true
    @parent.mark_path if @parent
  end
   
  def total_cost
    cost + cost_estimated
  end

  def <=>(other)
    total_cost <=> other.total_cost
  end
   
  def ==(other)
    point == other.point
  end
end

class Point
 
  attr_accessor :x, :y
 
  def initialize(x, y)
    @x, @y = x, y
  end

  def ==(other)
    return false unless Point === other
    @x == other.x && @y == other.y
  end

  def distance(other)
    (@x - other.x).abs + (@y - other.y).abs
  end

  def relative(xr, yr)
    Point.new(x + xr, y + yr)
  end
end

class Game_Map
 
  def each_neighbor(node, char = $game_player)
    x = node.point.x
    y = node.point.y
    nodes = []
    4.times {|i|
      i += 1
      new_x = round_x_with_direction(x, i * 2)
      new_y = round_y_with_direction(y, i * 2)
      next unless char.passable?(x, y, i * 2)
      #removed line below (technically, if your goal is an inpassable block,
      # e.g. an event, you can still reach it)
      #next unless char.passable?(new_x, new_y, 10 - i * 2)
      nodes.push(Node.new(Point.new(new_x, new_y)))
    }
    nodes
  end
 
  def find_path(tx, ty, sx, sy, dist, jump, char = $game_player)
    start = Node.new(Point.new(sx, sy))
    goal = Node.new(Point.new(tx, ty))
    return [] if start == goal or (dist > 0 and start.point.distance(goal.point) <= dist)
    return [] if ![2, 4, 6, 8].any? {|i| char.passable?(tx, ty, i) }
    open_set = [start]
    closed_set = []
    path = []
    iterations = 0
    loop do
      return [] if iterations == Jet::Pathfinder::MAXIMUM_ITERATIONS
      iterations += 1
      current = open_set.min
      return [] unless current
      each_neighbor(current, char).each {|node|
        if node == goal or (dist > 0 and node.point.distance(goal.point) <= dist)
          node.parent = current
          node.mark_path
          return recreate_path(node, jump)
        end
        next if closed_set.include?(node)
        cost = current.cost + 1
        if open_set.include?(node)
          if cost < node.cost
            node.parent = current
            node.cost = cost
          end
        else
          open_set << node
          node.parent = current
          node.cost = cost
          node.cost_estimated = node.point.distance(goal.point)
        end
      }
      closed_set << open_set.delete(current)
    end
  end
 
  def recreate_path(node, jump)
    path = []
    hash = {[1, 0] => 6, [-1, 0] => 4, [0, 1] => 2, [0, -1] => 8}
    until node.nil?
      pos = node.point
      node = node.parent
      next if node.nil?
      ar = [pos.x <=> node.point.x, pos.y <=> node.point.y]
      if jump
        path.push(RPG::MoveCommand.new(14,ar))
      else
        path.push(RPG::MoveCommand.new(hash[ar] / 2))
      end
    end
    return path
  end
end

class Game_Character
 
  #modified function (added handling for repeated move route (recalculates path
  # each step so it doesn't just loop it's old path route and will revalidate 
  # if x or y changes, will follow variable value if x and y are set to it)
  def find_path(x, y, dist = 0, jump = false, commonEvent = 0, catchup = 0, catchupSpeed = 5, normalSpeed = 4)
    path = $game_map.find_path(x, y, self.x, self.y, dist, jump).reverse
    if !@move_route.repeat
      @move_route.list.delete_at(@move_route_index)
      @move_route.list.insert(@move_route_index, *path)
      @move_route_index -= 1
    elsif path.length > 0
      if commonEvent > 0
        $game_temp.reserve_common_event(commonEvent)
      end
      if catchup > 0
        if @move_speed < catchupSpeed && path.length >= catchup
          process_move_command(RPG::MoveCommand.new(29,[catchupSpeed]))
        elsif @move_speed >= catchupSpeed && path.length < 2
          process_move_command(RPG::MoveCommand.new(29,[normalSpeed]))
        end
      end
      process_move_command(path[0])
      @move_route_index -= 1
    end
    return path.length
  end

  def get_character(i)
    if i == -1
      return $game_player
    end
    if i == 0
      return $game_map.events[@event_id]
    end
    if i > 0
      return $game_map.events[i]
    end
  end
 
  def find_formation_path(followId, shiftX, shiftY, catchup = Venima::Formations::FORM_CATCHUP_DIST, catchupSpeed = 5, normalSpeed = 4)
    x = shift_follow_x(followId, shiftX, shiftY)
    y = shift_follow_y(followId, shiftX, shiftY)
    if find_path(x,y,0,false,0,catchup,catchupSpeed,normalSpeed) == 0
      char = get_character(followId)
      find_path(char.x,char.y,3,false,0,catchup,catchupSpeed,normalSpeed)
    end
  end
 
  def shift_follow_x(followId, shiftX, shiftY)
    char = get_character(followId)
    case char.direction
    when 2
      return char.x + shiftX
    when 4
      return char.x - shiftY
    when 6
      return char.x + shiftY
    when 8
      return char.x - shiftX
    end
    return char.x
  end
 
  def shift_follow_y(followId, shiftX, shiftY)
    char = get_character(followId)
    case char.direction
    when 2
      return char.y + shiftY
    when 4
      return char.y - shiftX
    when 6
      return char.y + shiftX
    when 8
      return char.y - shiftY
    end
    return char.y
  end
 
  def turn_with_leader(eventId = -1, dirmod = "")
    dir = get_character(eventId).direction
    mod = 0
    if dirmod == "left" || dirmod == -1
      case dir
      when 2
        set_direction(4)
      when 4
        set_direction(2)
      when 6
        set_direction(8)
      when 8
        set_direction(6)
      end
    elsif dirmod == "right" || dirmod == 1
      case dir
      when 2
        set_direction(6)
      when 4
        set_direction(8)
      when 6
        set_direction(2)
      when 8
        set_direction(4)
      end
    elsif dirmod == "back" || dirmod == 2
      case dir
      when 2
        set_direction(8)
      when 4
        set_direction(6)
      when 6
        set_direction(4)
      when 8
        set_direction(2)
      end
    else
      set_direction(dir)
    end
  end
end

class Game_Interpreter
 
  #modified line below (added distance parameter)
  def find_path(x, y, ev = 0, wait = false, dist = 0, jump = false)
    char = get_character(ev)
    #modified line below (added distance parameter)
    path = $game_map.find_path(x, y, char.x, char.y, dist, jump)
    path.reverse!
    path.push(RPG::MoveCommand.new(0))
    route = RPG::MoveRoute.new
    route.list = path
    route.wait = wait
    route.skippable = true
    route.repeat = false
    char.force_move_route(route)
  end
end

I would convert it but, I only know RGSS3, I don't know the differences between that and RGSS2.