Problem with my pathfinder

Started by Epherex, May 09, 2017, 11:01:34 pm

Previous topic - Next topic

Epherex

I was messing around with pathfinding and I came up with a script that works, but not as expected. It uses the A* algorithm and binary heaps, but for some reason it's really slow on complex paths unless I consider the score of each node as only the heuristic (not considering the cost), and it still works perfectly, and so much faster. Could someone try it out and tell me why this is happening?
To use it, call a script:
PathFinder.new(character, x_target, y_target)

The character must be an actual Game_Character class.
It's still very incomplete because I can't figure out what is going on. Here is the script that considers the score of each node as the movement cost + the heuristic:
class Game_Character
attr_accessor :move_route
attr_accessor :move_route_index
def pos_with_dir(x, y, d)
new_x = x + (d == 6 ? 1 : d == 4 ? -1 : 0)
new_y = y + (d == 2 ? 1 : d == 8 ? -1 : 0)
return [new_x, new_y]
end
end

class Node
attr_reader   :x
attr_reader   :y
attr_reader   :heuristic
attr_accessor :parent
attr_accessor :cost
attr_accessor :open
def initialize(x, y, cost, heuristic, parent = nil)
@open = true
@x, @y, @cost, @heuristic, @visited, @parent = x, y, cost, heuristic, false, parent
end

def score
return @heuristic + @cost
end

def visit
@visited = true
end

def visited?
return @visited
end

def pos
return [@x, @y]
end
end

class PathFinder
attr_accessor :open
attr_accessor :closed
def initialize(char, tx, ty)
@char = char
heuristic = (tx - char.x).abs + (ty - char.y).abs
first_node = Node.new(char.x, char.y, 0, heuristic)
@open = [nil, first_node]
@open_tiles = {[char.x, char.y] => first_node}
@target = Node.new(tx, ty, 0, 0)
@closed = {}
@last_node = nil
find_path
end
 
def find_path
count = 0
while @open.size > 1
#print @open[1].inspect
close(1)
count += 1
if @closed.keys.include?(@target.pos)
@last_node = @closed[@target.pos]
break
end
if count % 200 == 0
Graphics.update
end
end
#print count
backtrack if @last_node != nil
end

def backtrack
list = []
current_node = @last_node
while current_node.parent
difx = current_node.x - current_node.parent.x
dify = current_node.y - current_node.parent.y
move_code = difx == -1 ? 2 : difx == 1 ? 3 : 0
move_code = dify == -1 ? 4 : dify == 1 ? 1 : move_code
command = RPG::MoveCommand.new
command.code = move_code
list.unshift(command)
current_node = current_node.parent
end
route = RPG::MoveRoute.new
route.list = list
route.repeat = false
@char.force_move_route(route)
  end
 
def close(index)
node = @open[index]
node.open = false
remove_heap(index)
@open_tiles.delete([node.x, node.y])
@closed[[node.x, node.y]] = node
expand(node)
end

def expand(node)
return if node.visited?
nodes = []
[2, 4, 6, 8].each do |dir|
new_pos = @char.pos_with_dir(node.x, node.y, dir)
if @char.passable?(new_pos[0], new_pos[1], 0) && !@closed.keys.include?(new_pos)
heuristic = (@target.x - new_pos[0]).abs + (@target.y - new_pos[1]).abs
if @open_tiles.keys.include?(new_pos)
if @open_tiles[new_pos].cost > node.cost + 1
@open_tiles[new_pos].parent = node
@open_tiles[new_pos].cost = node.cost + 1
update_heap(@open_tiles[new_pos])
end
else
nde = Node.new(new_pos[0], new_pos[1], node.cost + 1, heuristic, node)
if nodes[0] != nil && nde.score < nodes[0].score
temp = nodes[0]
nodes[0] = nde
nodes.push(temp)
else
nodes.push(nde)
end
end
end
end
nodes.reverse.each do |nde|
add_heap(nde)
#$scene.spriteset.insert_sprite(nde)
end
node.visit
end
 
def update_heap(item)
position = @open.rindex(item)
while position != 1 && @open[position].score <= @open[position/2].score
temp = @open[position/2]
@open[position/2] = @open[position]
@open[position] = temp
position /= 2
end
end

def add_heap(item)
position = @open.size
@open[position] = item
@open_tiles[item.pos] = item
while position != 1 && @open[position].score <= @open[position/2].score
temp = @open[position/2]
@open[position/2] = @open[position]
@open[position] = temp
position /= 2
end
end

def remove_heap(item)
last = @open[@open.size-1]
@open_tiles.delete(@open[item].pos)
@open[item] = last
@open.delete_at(@open.size-1)
position = item
while position != @open.size-1 && ((@open[position*2] &&
   @open[position].score > @open[position*2].score) ||
   (@open[position*2+1] && @open[position].score >
   @open[position*2+1].score))
if !@open[position*2+1]
score2 = @open[position*2].score + 1
else
score2 = @open[position*2+1].score
end
if @open[position*2].score < score2
temp = @open[position*2]
@open[position*2] = @open[position]
@open[position] = temp
position *= 2
else
temp = @open[position*2+1]
@open[position*2+1] = @open[position]
@open[position] = temp
position = position * 2 + 1
end
end
end
end


To remove the movement cost from the score of each node, remove the "+ @cost" at line 24.
I know there are a lot of good pathfinders out there, but I just want to make my own for experience purposes.

Blizzard

Actually looking up a different path finder might be a good idea since you can figure out how the other one is implemented.
That being said, I vaguely remember that you're supposed to use heuristic cost to the new node from the current plus the movement cost to the current node. I haven't taken a good look at your code yet though.
Check out Daygames and our games:

King of Booze 2      King of Booze: Never Ever
Drinking Game for Android      Never have I ever for Android
Drinking Game for iOS      Never have I ever for iOS


Quote from: winkioI do not speak to bricks, either as individuals or in wall form.

Quote from: Barney StinsonWhen I get sad, I stop being sad and be awesome instead. True story.

Epherex

May 10, 2017, 01:28:56 am #2 Last Edit: May 10, 2017, 01:30:29 am by Epherex
Quote from: Blizzard on May 10, 2017, 12:50:17 am
Actually looking up a different path finder might be a good idea since you can figure out how the other one is implemented.
That being said, I vaguely remember that you're supposed to use heuristic cost to the new node from the current plus the movement cost to the current node. I haven't taken a good look at your code yet though.


I based some of my code on other scripts, but I can't see what I'm doing wrong here.

https://www.dropbox.com/s/8gm87ndydj4zkiv/pathfind.exe?dl=0
I uploaded a demo with a script that shows sprites of the nodes on the map (I also set a ridiculous resolution to see better). Green squares are open nodes, red squares are closed ones. From the example on the demo, you can see it checked the whole map. Seems to be because the desired ones actually have higher scores, but on your script the path gets found very fast.

Blizzard

I'd have to go in-depth with your algorithm to figure out what's wrong. xD

A* is actually just a modified Dijkstra's algorithm. Instead of going through all nodes, an x,y coordinate heuristic is used to check possibly favorable nodes first.
Check out Daygames and our games:

King of Booze 2      King of Booze: Never Ever
Drinking Game for Android      Never have I ever for Android
Drinking Game for iOS      Never have I ever for iOS


Quote from: winkioI do not speak to bricks, either as individuals or in wall form.

Quote from: Barney StinsonWhen I get sad, I stop being sad and be awesome instead. True story.

KK20

I don't see anything wrong with the code. The simple act of removing @cost from your total node cost just makes the algorithm greedy--it evaluates nodes that look like they are close to finding the path while disregarding optimization (i.e. the shortest path). By putting @cost in, the algorithm first favors nodes that are close to the goal then those that have not been evaluated a lot. At some point, the length of the current path (which might be the correct one) has a larger cost than a node that is close to the beginning.

Wikipedia has a good visualization on what you're experiencing:
Spoiler: ShowHide



Other Projects
RPG Maker XP Ace  Upgrade RMXP to RMVXA performance!
XPA Tilemap  Tilemap rewrite with many features, including custom resolution!

Nintendo Switch Friend Code: 8310-1917-5318
Discord: KK20 Tyler#8901

Join the CP Discord Server!

Epherex

Quote from: KK20 on May 10, 2017, 02:43:03 am
I don't see anything wrong with the code. The simple act of removing @cost from your total node cost just makes the algorithm greedy--it evaluates nodes that look like they are close to finding the path while disregarding optimization (i.e. the shortest path). By putting @cost in, the algorithm first favors nodes that are close to the goal then those that have not been evaluated a lot. At some point, the length of the current path (which might be the correct one) has a larger cost than a node that is close to the beginning.

Wikipedia has a good visualization on what you're experiencing:
Spoiler: ShowHide





That seems to be the case. But try to use Blizz's pathfinder on my demo. Still gets found pretty fast. Isn't it supposed to check the whole map as well? Unless it doesn't use the same algorithm. I didn't take a deep look into its code.

KK20

I've studied Blizzard's and your scripts. Your script evaluates about half as many tiles as Blizzard's on the demo map, but Blizzard's finishes in about a quarter of a second while your's takes about 1.75 seconds.

I believe the main offender to this time difference are your heap methods and chosen data types. You are constantly swapping items around in hashes and arrays that, when they become very large in size, get very slow very quickly. I also don't see how it is guaranteeing that you will be evaluating the lowest cost node on the next loop iteration as your update_heap skips over potential good candidates (newly inserted node checks halfway through the open list to see if it is a better cost--if yes, then swap; repeat until no longer the better cost). I really don't know why you have both an open nodes array and an open nodes hash; just choose one.

Blizzard sticks with a open nodes hash where the key-value pairing is
[x, y, cost] => direction

He then chooses a node from the hash that has the lowest cost in its key; otherwise, the node closest to the goal is chosen. This isn't really A*, but more of a modified Dijkstra. There are no heuristics really being done here. If I choose a location that is like 5 tiles away, it evaluates well over 5 tiles to find the best path (refer to my previous post's animated image where it makes a beeline to the goal in the beginning). Your script functions exactly as how I expect it to.

The TL;DR version = Your heaping is slowing everything down unnecessarily. Please take a step back and think of a better way to sort your nodes.

Other Projects
RPG Maker XP Ace  Upgrade RMXP to RMVXA performance!
XPA Tilemap  Tilemap rewrite with many features, including custom resolution!

Nintendo Switch Friend Code: 8310-1917-5318
Discord: KK20 Tyler#8901

Join the CP Discord Server!

Blizzard

That's true, I did optimize my script in such a way.

I think you're wrong about Dijsktra. The thing with a Cartesian coordinate system is that coordinate distances are consistent throughout the whole grid so technically the heuristic of the xy coordinate difference is actually not just an cost estimation, but a consistent cost. I used that fact to make the Dijkstra's algorithm implementation faster and that's basically what A* is. It just uses a heuristic like that to decide which nodes to check first.
Check out Daygames and our games:

King of Booze 2      King of Booze: Never Ever
Drinking Game for Android      Never have I ever for Android
Drinking Game for iOS      Never have I ever for iOS


Quote from: winkioI do not speak to bricks, either as individuals or in wall form.

Quote from: Barney StinsonWhen I get sad, I stop being sad and be awesome instead. True story.

KK20

It still doesn't explain why it doesn't perform how A* should ideally. If you change the part where it checks for distance from the current node to the target and THEN check for path cost, then it will definitely behave more like A*, but, as I mentioned in my first post, it becomes greedy. A* needs to factor in both the path cost and a heuristic together to get the absolute lowest cost. You're using two values separately with a bias (which is not that much faster than Dijkstra to be honest).

I don't know what you mean about me being wrong about Dijsktra when I never talked about it.

Other Projects
RPG Maker XP Ace  Upgrade RMXP to RMVXA performance!
XPA Tilemap  Tilemap rewrite with many features, including custom resolution!

Nintendo Switch Friend Code: 8310-1917-5318
Discord: KK20 Tyler#8901

Join the CP Discord Server!

Blizzard

Quote from: KK20 on May 10, 2017, 11:05:45 pm
This isn't really A*, but more of a modified Dijkstra.


That's what I meant.

You mean because of this?


key = request.open.keys.min {|a, b|
        a[2] > b[2] ? 1 : (a[2] < b[2] ? -1 :
        (Math.hypot_squared(a[0] - request.target.x, a[1] - request.target.y) <=>
        Math.hypot_squared(b[0] - request.target.x, b[1] - request.target.y)))}


I'm first checking the already known cost before checking the heuristic cost. So you think I should check them together?
Check out Daygames and our games:

King of Booze 2      King of Booze: Never Ever
Drinking Game for Android      Never have I ever for Android
Drinking Game for iOS      Never have I ever for iOS


Quote from: winkioI do not speak to bricks, either as individuals or in wall form.

Quote from: Barney StinsonWhen I get sad, I stop being sad and be awesome instead. True story.

KK20

May 11, 2017, 09:46:31 pm #10 Last Edit: May 11, 2017, 09:49:42 pm by KK20
I guess my sentence can be interpreted many ways. What I really wanted to say was something along the lines of "a square is a rectangle but a rectangle is not a square"--your script is more Dijkstra than it is A*.

F0's pathfinder script is a true implementation of A* in that the heuristics are incorporated into the node costs. It doesn't perform as fast as your script though (~0.44 seconds) due to the sorting it does to find the lowest cost (kinda similar to Epherex's heaping methods), but it does evaluate less nodes.

Funny thing though is that if I remove the Math.hypot_squared in your script (and make it pure Dijkstra), it actually performs faster, at least in regards to the demo project Epherex provided (~0.177 sec). Of course, in terms of straight line path requests, it still pales in comparison. The data types you used are key to its speed.

I tried taking a stab at the problem in making my own pathfinder. It's very rough since I was mainly experimenting, but it does get the job done. Print statements commented out.
Spoiler: ShowHide

# Script call: Pathfinder.find($game_player, X, Y)

class Node
  attr_reader   :x, :y, :parent, :direction
  attr_accessor :cost, :heur
 
  def initialize(x, y, parent, direction)
    @x, @y, @parent, @direction = x, y, parent, direction
    @cost = @heur = 0
  end
 
  def total_cost; @cost + @heur; end
  def pos; [@x, @y]; end
end

#--------------------------------------------------------------------------

module PathFinder
  attr_accessor :open
  attr_accessor :closed
 
  class << self
   
  def find(char, tx, ty)
    @char = char
    first_node = Node.new(char.x, char.y, nil, 0)
    @open = {}
    @open[0] = [first_node]
    @closed = {}
    @closed[[char.x, char.y]] = true
    @target = [tx, ty]
   
    #t = Time.now
    move_route = find_path
    #p @count
    #p Time.now - t
   
    if move_route
      @char.force_move_route(move_route)
    else
      p "No path could be found!"
    end
   
    @open.clear
    @closed.clear
  end
 
  def find_path
    @count = 1
    while @open.size > 0
      #s = ""
      #@open.each{ |key, val|
      #  s += "[#{key}] = "
      #  val.each {|v| s += "[#{v.x},#{v.y}] " }
      #  s += "; "
      #}
      #p s
      # Get the lowest cost tile
      lowest_cost = @open.keys.sort.shift
      open_node   = @open[lowest_cost].shift
      # Found target node? Make the move route path!
      return make_move_route(open_node) if open_node.pos == @target
     
      # Check in each direction
      [2,4,6,8].each{ |dir|
        nx = open_node.x + (dir == 4 ? -1 : dir == 6 ? 1 : 0)
        ny = open_node.y + (dir == 8 ? -1 : dir == 2 ? 1 : 0)
        # If can move in this direction and node hasn't been evaluated yet
        if @char.passable?(open_node.x, open_node.y, dir) && !@closed[[nx, ny]]
          # Add to open list
          @count += 1
          new_node = Node.new(nx, ny, open_node, dir)
          new_node.cost = open_node.cost + 1
          new_node.heur = distance(nx, ny, *@target)
          cost = new_node.total_cost
          @open[cost] ? @open[cost].push(new_node) : @open[cost] = [new_node]
          @closed[[nx, ny]] = true
        end
      }
      # There are no more open tiles with a cost lower than this
      if @open[lowest_cost].empty?
        @open.delete(lowest_cost)
      end
     
    end
    # If we reach here, no path could be found
    return nil
  end
 
  def make_move_route(last_node)
    list = []
    while last_node.parent
      move_code = last_node.direction / 2
      command = RPG::MoveCommand.new
      command.code = move_code
      list.unshift(command)
      last_node = last_node.parent
    end
    route = RPG::MoveRoute.new
    route.list = list
    route.repeat = false
    route
  end
 
  def distance(x1, y1, x2, y2)
    dist = (x1 - x2).abs + (y1 - y2).abs
    dist == 0 ? -1.0/0.0 : dist
  end
 
  end
end

It performs somewhat faster than your default script (~0.22 vs ~0.27), but not as fast with the Math.hypot_squared removed.

And yeah, tests are performed assuming all tiles on a Cartesian coordinate system have an equal cost--my script would break otherwise. I'll keep looking into improving this.

Other Projects
RPG Maker XP Ace  Upgrade RMXP to RMVXA performance!
XPA Tilemap  Tilemap rewrite with many features, including custom resolution!

Nintendo Switch Friend Code: 8310-1917-5318
Discord: KK20 Tyler#8901

Join the CP Discord Server!

Blizzard

Yeah, it performs faster because of its greedy nature. xD When it works like that, some paths will be faster, some will be slower depending on how straightforward they are.

I think that you shouldn't make it more general. Algorithms and generalizations are fine, but your should use the specifics of a problem to optimize the shit out of it. Since we have a Cartesian coordinate system and it's not likely to change, we should use that fact to make the implementation faster.
Check out Daygames and our games:

King of Booze 2      King of Booze: Never Ever
Drinking Game for Android      Never have I ever for Android
Drinking Game for iOS      Never have I ever for iOS


Quote from: winkioI do not speak to bricks, either as individuals or in wall form.

Quote from: Barney StinsonWhen I get sad, I stop being sad and be awesome instead. True story.