[VXA] Pathfinding

Pathfinding
Version: 1.0
Author: cozziekuns
Date: New Years Eve, 2011

Version History

• <Version 1.0> 2011.12.31 - Original Release

Planned Future Versions

• <Version 1.1> Allow for dynamic recalculation if one wants to repeat the path-finding process for any reason.

Description

This script allows you to move any character to another tile using the shortest path possible. It takes a significantly longer time on large maps.

Features

• Incredibly fast and accurate pathfinding
• Easy script calls
• Almost no configuration

Screenshots

Not really applicable for this type of thing.

Instructions

To use, create a move route event and as a script command use:

find_path(target_x, target_y)

Additionally, one can force a path through a script using the following call:
 
force_path(target_x, target_y)

There is a known bug that is present in Modern Algebra's script regarding the recalculation of a path once found. Since some of this script is simply a convert from his VX version (only the algorithm is different by being slightly slower and sloppier ), the bug is also found in this script.

Script

Code: [Select]

#===============================================================================
# [VXA] Pathfinding
#-------------------------------------------------------------------------------
# Version: 1.0
# Author: cozziekuns (rmrk)
# Last Date Updated: 12/31/2011 (MM/DD/YYYY)
#===============================================================================
# Description:
#-------------------------------------------------------------------------------
# This script allows you to move any character to another tile using the 
# shortest path possible. It takes a significantly longer time on large maps.
#===============================================================================
# Updates
# ------------------------------------------------------------------------------
# o 12/31/2011 - Started Script
#===============================================================================
# To-do List
#-------------------------------------------------------------------------------
# o Allow for dynamic recalculation if one wants to repeat the pathfinding
#   process for any reason.
#===============================================================================
# Instructions
#-------------------------------------------------------------------------------
# To use, create a move route event and as a script command use:
#
# find_path(target_x, target_y)
#
# Additionally, one can force a path through a script using the following call:
#
# force_path(target_x, target_y)
#
# There is a known bug that is present in Modern Algebra's script regarding the
# recalculation of a path once found. Since some of this script is simply
# a convert from his VX version (only the algorithm is different by being
# slightly slower and sloppier :P), the bug is also found in this script.
#===============================================================================

#==============================================================================
# ** Game_Map
#==============================================================================

class Game_Map
 
  def find_path(target_x, target_y, sx, sy, passable, char)
    path = []
    max_elements = width * height + 2
    checked_items = 0
    @open_list_items = 0
    @open_list = Table.new(max_elements)
    @nodes = Table.new(max_elements, 2)
    open = Table.new(width, height)
    closed = Table.new(width, height)
    parent = Table.new(width, height, 3)
    @f_cost = Table.new(width, height)
    @open_list[0] = 0
    @nodes[0, 0] = sx
    @nodes[0, 1] = sy
    next_point = [sx, sy]
    closed[sx, sy] = 1
    loop do
      next_point = delete_from_heap if not next_point == [sx, sy]
      return path if next_point.nil?
      open[next_point[0], next_point[1]] = 0
      closed[next_point[0], next_point[1]] = 2 if not next_point == [sx, sy]
      parent_x, parent_y = next_point[0], next_point[1]
      for i in 1..4
        x, y = case i * 2
        when 2; [parent_x, parent_y + 1]
        when 4; [parent_x - 1, parent_y]
        when 6; [parent_x + 1, parent_y]
        when 8; [parent_x, parent_y - 1]
        end
        next if closed[x, y] == 2
        next unless char.passable?(parent_x, parent_y, i * 2)
        if not open[x, y] == 1
          open[x, y] = 1
          parent[x, y, 0] = parent_x
          parent[x, y, 1] = parent_y
          parent[x, y, 2] = parent[parent_x, parent_y, 2] + 10
          g = parent[x, y, 2] + 10
          h = ((target_x - x).abs + (target_y - y).abs) * 10
          @f_cost[x, y] = g
          checked_items += 1
          @open_list_items += 1
          @nodes[checked_items, 0] = x
          @nodes[checked_items, 1] = y
          add_to_heap(checked_items)
        else
          old_g = parent[x, y, 2] + 10
          new_g = parent[parent_x, parent_y, 2] + 20
          next if old_g < new_g
          parent[x, y, 0] = parent_x
          parent[x, y, 1] = parent_y
          parent[x, y, 2] = new_g
          g = parent[x, y, 2] + 10
          h = ((target_x - x).abs + (target_y - y).abs) * 10
          @f_cost[x, y] = g
        end
      end
      next_point = nil
      break if closed[target_x, target_y] == 2
    end   
    path_x, path_y = target_x, target_y   
    loop do   
      parent_x = parent[path_x, path_y, 0]
      parent_y = parent[path_x, path_y, 1]
      if path_x < parent_x
        code = 2
      elsif path_x > parent_x
        code = 3
      else
        code = path_y < parent_y ? 4 : 1
      end     
      path.push(RPG::MoveCommand.new(code))
      path_x, path_y = parent_x, parent_y     
      break if path_x == sx and path_y == sy
    end
    return path
  end
 
  def add_to_heap(value)
    m = @open_list_items
    @open_list[m] = value
    while m != 1
      if fcost(@open_list[m]) < fcost(@open_list[m / 2])
        temp = @open_list[m / 2]
        @open_list[m / 2] = @open_list[m]
        @open_list[m] = temp
        m /= 2
      else
        break
      end
    end
  end
 
  def delete_from_heap
    next_point = @open_list[0]
    @open_list[0] = @open_list[@open_list_items]
    @open_list_items -= 1
    v = 1
    loop do
      u = v
      w = 2 * u
      if w + 1 <= @open_list_items
        v = w if fcost(@open_list[u - 1]) >= fcost(@open_list[w - 1])
        v = w + 1 if fcost(@open_list[v - 1]) >= fcost(@open_list[w])
      elsif w <= @open_list_items
        v = w if fcost(@open_list[u - 1]) >= fcost(@open_list[w - 1])
      end
      if u != v
        temp = @open_list[u - 1]
        @open_list[u - 1] = @open_list[v - 1]
        @open_list[v - 1] = temp
      else
        break
      end
    end
    return @nodes[next_point, 0], @nodes[next_point, 1]
  end
 
  def fcost(point)
    x = @nodes[point, 0]
    y = @nodes[point, 1]
    return @f_cost[x, y]
  end
 
end

#==============================================================================
# ** Game_CharacterBase
#==============================================================================

class Game_CharacterBase

  def find_path(target_x, target_y)
    path = $game_map.find_path(target_x, target_y, @x, @y, false, self)
    @move_route.list.delete_at(@move_route_index)
    path.each { |i| @move_route.list.insert(@move_route_index, i) }
    @move_route_index -= 1
  end
 
  def force_path(target_x, target_y)
    path = $game_map.find_path(target_x, target_y, @x, @y, false, self)
    path.reverse!
    path.push (RPG::MoveCommand.new(0))
    move_route = RPG::MoveRoute.new
    move_route.list = path
    move_route.repeat = false
    force_move_route(move_route)
  end
 
  def count_iterations(target_x, target_y)
    path = $game_map.find_path(target_x, target_y, @x, @y, true, self)
    return path.size
  end
 
end


Credit

• cozziekuns
• Modern Algebra, for his VX version of the script

Thanks

• Patrick Lester, and his well known A* Tutorials which were immensely helpful.

Author's Notes

Happy New Years Eve! I'm in America right now so I don't get an early New Years

The other side of the world looks forward to your return, and would like to inform you that it's January 1st already.

Also, nice port.

I think I love you! I am still messing around with the demo version of VXA and I was like "there's got to be a way to just tell a character to go to a point without having to count all the little boxes manually." And now there is!

I'm just using it to make cutscenes easier, but i could see it being used to having a character that accompany you into a dungeon and progresses the game whether you figure out the puzzles or not. When you say,

 "It takes a significantly longer time on large maps."

Do you mean there would be a lot of lag if other stuff was going on? I created a big maze using the default sample map in VX Ace for the World tree, and I removed all the little branches and opened up one hole so it was like a big circular maze, dropped in a little girl (hey, don't question my ethics here) and waited at the exit, and she found her way to me perfectly and it didn't take any time. I redid it again and followed her every step of the way and she didn't stop or lag at all, actually she didn't even go down any of the dead ends.

Kudos to you and modern algebra for the amazing script!

Do you mean there would be a lot of lag if other stuff was going on? I created a big maze using the default sample map in VX Ace for the World tree, and I removed all the little branches and opened up one hole so it was like a big circular maze, dropped in a little girl (hey, don't question my ethics here) and waited at the exit, and she found her way to me perfectly and it didn't take any time. I redid it again and followed her every step of the way and she didn't stop or lag at all, actually she didn't even go down any of the dead ends.

Attempting to pathfind with multiple events will create a lot of lag, as well as 400x400+ Maps.

Is there a way to find a path with only one movement because I want an event to go on a tile using only 5 moves and if it has not reached the destination, it stop itself.

Hello again, this is nothing wrong with the script, but a stupid User error that I wanted to share so nobody else wastes their time with this. I kept getting this error and I couldn't for the life of me figure out why:

Code: [Select]

Script 'Game_Character' line 179: TypeError occurred.

no implicit conversion from nil to integer

The reason was passability was not possible. I was on a blank map simply trying to get a guy to walk into the screen.

You just have to add passability to the event you are trying to path find with and you'll be good. Just wanted to share in case anyone else has this "problem". As they say, most problems fall between the keyboard and chair!

Thanks again for porting this awesome script!

Whenever I try and use this script it says + is not a valid method or something...

EDIT: It's on line 180 rather than 179 for some reason.

Great script! It's quite fast too. Good job for both Modern Algebra and cozziekuns!

Hello again, this is nothing wrong with the script, but a stupid User error that I wanted to share so nobody else wastes their time with this. I kept getting this error and I couldn't for the life of me figure out why:

Code: [Select]

Script 'Game_Character' line 179: TypeError occurred.

no implicit conversion from nil to integer

The reason was passability was not possible. I was on a blank map simply trying to get a guy to walk into the screen.

You just have to add passability to the event you are trying to path find with and you'll be good. Just wanted to share in case anyone else has this "problem". As they say, most problems fall between the keyboard and chair!

Thanks again for porting this awesome script!

^ Indeed, I spent eons till I found out I also had a passability problem and fixed it. When an error like that occurs, usually you think that something is wrong, like incompatibility or syntax errors.
Not existing a path between two points is a possible (and in some, circunstances, acceptable) outcome. Bursting an error like that is sort of confusing. I'd suggest some sort of error treatment in the script when this happens (like returning a value indicating that no path was found).
Maybe this error treatment can be optional. If the user thinks it's better to him to have an error popup (for debug purposes, probably), then the script could also do it.

That error is a bit annoying when two events just happened to block one another (I used them as alternate for move route for really big cutscenes). It'd be nice if that error is optional.

I don't think Cozziekuns is supporting this anymore, so reluctantly I will attempt a solution for him.


Go to line 136 of the script and add this code just one line after 'def delete_from_heap'

Code: [Select]

unless @open_list[0] && @open_list_items > -1
      msgbox_p("This Event Cannot Find A Path To The Specified Location") if $TEST
      return nil
    end


This will add a pop-up if an event cannot find a path, but only when testing. During Release Mode it won't show up.
If you don't want the pop-up just remove the msgbox_p line.

Thank you very much!

Is there any way to make an event find path based on two variables (an x and y variable of the player)?

Is there any way to make an event find path based on two variables (an x and y variable of the player)?

$game_map.events[ID].find_path($game_player.x,$game_player.y)