Can you spot the logic error in this? I sure can't :'(
(Ignore the terrible code; this stuff is like pre-alpha alpha).
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
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:
(https://rmrk.net/proxy.php?request=http%3A%2F%2Fi56.tinypic.com%2Fwup7uo.png&hash=c6aadf14293594e8a6737d10991d7afe4585e3f3)
(Movement Range is 4)
(https://rmrk.net/proxy.php?request=http%3A%2F%2Fi51.tinypic.com%2Feg6bg3.png&hash=ae0a1cf872d62f716019c3a9072a25436b2ad5cd)
(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.
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 .