Movement Range Logic Help

Can you spot the logic error in this? I sure can't :'(

(Ignore the terrible code; this stuff is like pre-alpha alpha).

Code: [Select]


def create_movement_range
   
    x = cursor_event[0].x
    y = cursor_event[0].y
    movement = cursor_event[0].battler[3]
   
    open = []
    closed = []
    parent_x = Table.new($game_map.width, $game_map.height)
    parent_y = Table.new($game_map.width, $game_map.height)
   
    for i in 0...$game_map.width
      for j in 0...$game_map.height
        parent_x[i, j] = -1
        parent_y[i, j] = -1
      end
    end
   
    open.push([x, y])
    closed = open.clone
    open.delete([x, y])
    open.push([x, y + 1]) if $game_map.passable?(x, y + 1)
    open.push([x, y - 1]) if $game_map.passable?(x, y - 1)
    open.push([x + 1, y]) if $game_map.passable?(x + 1, y)
    open.push([x - 1, y]) if $game_map.passable?(x - 1, y)
   
    for point in open
      parent_x[point[0], point[1]] = x
      parent_y[point[0], point[1]] = y
    end
   
    loop do
     
      lowest = 9999
     
      for point in open
       
        dist = ((point[0] - x).abs + (point[1] - y).abs) * 10
        next if dist > lowest
        iterations = 0
        point_x = point[0]
        point_y = point[1]
       
        loop do
         
          if not (point_x - parent_x[point_x, point_y]) == 0
            if not parent_x[point_x, point_y] == -1
              point_x -= (point_x - parent_x[point_x, point_y])
              iterations += 1
            end
          elsif not (point_y - parent_y[point_x, point_y]) == 0
            if not parent_y[point_x, point_y] == -1
              point_y -= (point_y - parent_y[point_x, point_y])
              iterations += 1
            end
          else
            break
          end
         
          break if parent_x[point_x, point_y] == -1 and parent_y[point_x, point_y] == -1
         
        end       
       
        lowest = dist
        lowest_point = point
       
      end
     
      break if iterations > movement
       
      open.delete(lowest_point)
      closed.push(lowest_point)
     
      ax = lowest_point[0]
      ay = lowest_point[1]
     
      for i in 0..3
        case i
        when 0; key = [ax, ay + 1]
        when 1; key = [ax, ay - 1]
        when 2; key = [ax + 1, ay]
        when 3; key = [ax - 1, ay]
        end
        next unless $game_map.passable?(key[0], key[1])
        next if closed.include?(key)
        open.push(key)
       
        parent_x[key[0], key[1]] = lowest_point[0]
        parent_y[key[0], key[1]] = lowest_point[1]
      end
     
    end
   
    @points = closed

  end


Background: I was playing around with a turn based tactics like movement system, where your movement is limited by steps (iterations in this algorithm). I was attempting to use Dijkstra's pathfinding algorithm by spliltting the map into the standard 32 * 32 grid, and checking the amount of iterations to create my movement range. I can't see what's wrong with this, but RPG Maker begs to differ:

(Movement Range is 4)

(Movement Range is 3) This works fine.

Demo attached if you don't want to work blind. Thanks for your help, guys.

Pardon the double post but I took out the heuristic (not sure why it was there in the first place), and it seems to be working fine now.

Code: [Select]

def create_movement_range
   
    x = cursor_event[0].x
    y = cursor_event[0].y
    movement = cursor_event[0].battler[3]
   
    open = []
    closed = []
    parent_x = Table.new($game_map.width, $game_map.height)
    parent_y = Table.new($game_map.width, $game_map.height)
   
    for i in 0...$game_map.width
      for j in 0...$game_map.height
        parent_x[i, j] = -1
        parent_y[i, j] = -1
      end
    end
   
    open.push([x, y])
    closed = open.clone
    open.delete([x, y])
    open.push([x, y + 1]) if $game_map.passable?(x, y + 1)
    open.push([x, y - 1]) if $game_map.passable?(x, y - 1)
    open.push([x + 1, y]) if $game_map.passable?(x + 1, y)
    open.push([x - 1, y]) if $game_map.passable?(x - 1, y)
   
    for point in open
      parent_x[point[0], point[1]] = x
      parent_y[point[0], point[1]] = y
    end
   
    loop do
     
      lowest = 9999
     
      for point in open
       
        iterations = 0
        point_x = point[0]
        point_y = point[1]
       
        loop do
         
          if not (point_x - parent_x[point_x, point_y]) == 0
            if not parent_x[point_x, point_y] == -1
              point_x -= (point_x - parent_x[point_x, point_y])
              iterations += 1
            end
          elsif not (point_y - parent_y[point_x, point_y]) == 0
            if not parent_y[point_x, point_y] == -1
              point_y -= (point_y - parent_y[point_x, point_y])
              iterations += 1
            end
          else
            break
          end
         
          break if parent_x[point_x, point_y] == -1 and parent_y[point_x, point_y] == -1
         
        end 
       
        next if iterations > lowest
       
        lowest = iterations
        lowest_point = point
       
      end
     
      break if lowest > movement
       
      open.delete(lowest_point)
      closed.push(lowest_point)
     
      ax = lowest_point[0]
      ay = lowest_point[1]
     
      for i in 0..3
        case i
        when 0; key = [ax, ay + 1]
        when 1; key = [ax, ay - 1]
        when 2; key = [ax + 1, ay]
        when 3; key = [ax - 1, ay]
        end
        next unless $game_map.passable?(key[0], key[1])
        next if closed.include?(key)
        open.push(key)
       
        parent_x[key[0], key[1]] = lowest_point[0]
        parent_y[key[0], key[1]] = lowest_point[1]
      end
     
    end
   
    @points = closed
   
  end


Gonna leave this open just in case anyone comes up with a better algorithm.

Wait ... you're working on a TBS
2 TBS are already existing but you probably know it . both aren't perfect and can be improved .
What are the differences with your project ?

I'd say the most obvious difference is that he's making this one.

yep , of course
But what i mean is that a lot of makers are complaining about the GTBS . it's a monster script with a lot of setup (and quite mysterious for some of them) and yes , some bugs .
So making another TBS as a sense ... especially if it's a most simple one .