Fastest Route to Tile with Restrictions

[Gubid]

Ok.. i am running into a block and I cannot think of an easy way to get around it. 

I am trying to re-write the movement section of GTBS to use tile movement restrictions.  By this I mean that this tile may be -2 move and the next -1 and hence forth.  So here is a situation.

You have an actor on a log, and they want to get to this other log just a stones throw away.  The problem is that in order to cross to that log easily they must walk around, or go through the bushes separating them.  So with this in mind.

1=Require 1 move to enter tile
2=Requires 2 move to enter tile
3=Requires 3 move to enter tile
4...
5...


-MAP -
1 1 
4 1 
X 1

The actor is the X... they are trying to get to the first 1 listed on the top row.  To get there they could go through the 4(requiring 5 move) or around it(requiring 4 move).  I want it to find the fastest route.  The current path finding forces it to pass through the 4 tile while if they walked around it would require less overall move. 

The code that is currently figuring this stuff out is this...

Spoiler: calc_pos

		case range_max
		when 0 
		  positions.push([actor.x, actor.y])	   
		else
		  positions.push([actor.x, actor.y])
		  route = [[]]
		  more_step = [0]
		  for i in more_step
			x = positions[i][0]
			y = positions[i][1]
			
			if !positions.include?([x, y + 1]) and actor.passable?(x, y, 2)
			  positions.push([x, y + 1])
			  route.push(route[i] + [2])
			  if route[i].size + 1 < range_max
				more_step.push(route.index(route[i] + [2]))
			  end
			end
			
			if !positions.include?([x - 1, y]) and actor.passable?(x, y, 4)
			  positions.push([x - 1, y])
			  route.push(route[i] + [4])
			  if route[i].size + 1 < range_max
				more_step.push(route.index(route[i] + [4]))
			  end
			end
			
			if !positions.include?([x + 1, y]) and actor.passable?(x, y, 6)
			  positions.push([x + 1, y])
			  route.push(route[i] + [6])
			  if route[i].size + 1 < range_max
				more_step.push(route.index(route[i] + [6]))
			  end
			end
			
			if !positions.include?([x, y - 1]) and actor.passable?(x, y, 8)
			  positions.push([x, y - 1])
			  route.push(route[i] + [8])
			  if route[i].size + 1 < range_max
				more_step.push(route.index(route[i] + [8]))
			  end
			end
		  end
		end
		need_del = []
		for pos in positions
		  if occupied?(pos[0], pos[1])
			r = route[positions.index(pos)]
			need_del.push([pos, r])
		  end		  
		end
		if need_del.size > 0
		  loop do 
			p = need_del[0][0]
			r = need_del[0][1]
			route.delete(r)
			positions.delete(p)
			need_del.delete([p,r])
			if need_del.size == 0
			  break
			end
		  end
		end
		@route = route

The above script allows it to find the fastest route to a tile, but doesnt consider the amount of move it requires to get there, other than it is less that the actors move amount.  I would like this to also figure if it was the fastest way to get there, and thus uses the least move required. 

Anyone want to help offer their skills?  I was thinking of using the terrain_tag to figure this out.    I am already using the terrain tag as part of def passable? for flying characters and other special abilities.  Any help would be appreciated.

 

[Moogleking]

It sounds like you're looking for this:
http://en.wikipedia.org/wiki/Dijkstra's_algorithm
Basically each tile will be a vertex, and you'll want to run Dijkstra's algorithm.  You'll probably want to set a max path length to whatever the maximum amount a character can move.  Each vertex weight will be based on the tile's movement value.  You'll want to set it up so the source is the tile you're on, and the destination is the target vertex.

Sorry I can't offer coding advice for this in Ruby, but this is definitely the algorithm you're looking for.

 

[Cowlol]

Yeah you could use an algorithm like Dijkstra or A* while taking cost into account. I think terrain tag is a good way to handle costs or restrictions, I'm using them for the same purpose in the next version of my pathfinder. Each tile is associated with a cost (and a heuristic in the case of A*) and the tile with the lowest cost is considered first. So while searching for a path in your example, the tiles with 1s will be considered first because they cost less. You could alternatively integrate a cost system into your current script but you'll end with something like the aforementioned algorithms anyway.

 

[Gubid]

I would love to use A* over my current Dijkstra method.  It gives more flexibility I think especially with the use of Terrain Tags to get what I am looking for. 
I tried adjusting the current script to replace the path to a particular node, if a less costly route was found, but then it doesnt go to the next "step", because it has already explored some of that area.  Sides having it check an area more than once is kinda a waste of CPU.  I would like it to suggest 2 best paths, and choose which one is the least costly to reach that position.  A* as you said would follow the ones, which is correct in the example I gave, but what if the 4 was as 2 or 3.  Technically if it was a 2 then the move required would only be 3 while going around would be 4, and if it was 3 the cost would be the same for going through or around.  If that is the case, i would prefer the shorter route if cost is the same, but if its less it should be used regardless of length.

I have an idea and perhaps you can tell me if I should look at doing it some other way. 
I am thinking of using the existing method to locate each movable position(but then use the A* script to find the best path to it using what was described above.  If a tile that was designated movable earlier but A* cannot find a path to it when taking TT's into consideration, then it would be removed from the positions list. This way it uses the TT's to figure where you can move, but in a backwords sort of way.  So technically i would be using both the Dijkstra method along with A*. 

Anyway, looking forward to your update Cowlol.  Thanks for the response.  Hopefully I can get something worked out before too long. 


EDIT: Actually here is another idea.. instead of using the Dijkstra method to locate where they can move, I just great the overall move area(using the method I use for skills) then just check each of those positions as described above.  then it doesnt have to check movability etc, more than once.  It just uses a formula to get the "movable area" then examines it with A*.  Tell me what you think.

 

[Cowlol]

I would love to use A* over my current Dijkstra method.  It gives more flexibility I think especially with the use of Terrain Tags to get what I am looking for. 
I tried adjusting the current script to replace the path to a particular node, if a less costly route was found, but then it doesnt go to the next "step", because it has already explored some of that area.  Sides having it check an area more than once is kinda a waste of CPU.  I would like it to suggest 2 best paths, and choose which one is the least costly to reach that position.  A* as you said would follow the ones, which is correct in the example I gave, but what if the 4 was as 2 or 3.  Technically if it was a 2 then the move required would only be 3 while going around would be 4, and if it was 3 the cost would be the same for going through or around.  If that is the case, i would prefer the shorter route if cost is the same, but if its less it should be used regardless of length.

For the two best routes things (the case with the 4 tile being 3 instead), what you could do is add something into the cost function in A* (or Dijkstra) to take into account the actual length of the path or to penalize paths that aren't straight (involve turns). That way more straight or shorter paths are preferred to more complex paths while also taking the tile restriction into account.

I have an idea and perhaps you can tell me if I should look at doing it some other way.
I am thinking of using the existing method to locate each movable position(but then use the A* script to find the best path to it using what was described above.  If a tile that was designated movable earlier but A* cannot find a path to it when taking TT's into consideration, then it would be removed from the positions list. This way it uses the TT's to figure where you can move, but in a backwords sort of way.  So technically i would be using both the Dijkstra method along with A*.

I'm still not sure why use both while you could just use one. All you need to do is to include tile tag as a factor in the existing method, instead of doing an expensive search twice.

EDIT: Actually here is another idea.. instead of using the Dijkstra method to locate where they can move, I just great the overall move area(using the method I use for skills) then just check each of those positions as described above.  then it doesnt have to check movability etc, more than once.  It just uses a formula to get the "movable area" then examines it with A*.  Tell me what you think.

Yeah that sounds better, there's no need to find a path twice. I think you could just get away with something like...

if (within_move_range?(target_tile))
find_path 
else 
find_path_closest # or do nothing, depends on what you want
end

So what you have is a function or a lookup table that knows what tiles the character can move to, and it checks it before pathfinding. You could even have it as part of your pathfinding algorithm (checking for range and such).

 

[Gubid]

I like the idea of already having the pass table available, but I see a flaw in the way you did it in your A* script.  That is

 for x in 0...$game_map.width
  for y in 0...$game_map.height
    map_pass[x,y] = actor.passable?(x,y,0) ? 1 : 0
  end
 end

There is no major problem, but what happens when the tile is pasable but only from a specified direction? your method doesnt account for that.  It just looks for mainstream passability. 

I would like to either use my existing method or yours to account for Terrian tags, but I cannot think of how to implement it.  I wrote something out, but when a path to a tile is "replaced" with a faster one, it doesnt continue the route because nothing new was added, but something was replaced.  I dunno, I will keep playing with it, but I think your A* method may be faster than this.  If its faster, I may want to use that instead.

Thanks again for your help on this matter.

 

[Cowlol]

You're right about tiles with specific passable directions, but it's actually a bit complex to account for that because it depends on which direction the characters enters it from which is something I can't calculate in advance. One way around it is to use the pre-generated table as a base and to perform another simple passibility check during pathfinding which just checks for the ability to enter the tile from the direction of the tile's parent.

It's hard to help you with your replacement problem when I don't know much about the code in question, but as for implementation it is simply the matter of assigning costs to tiles as you consider them during the search. For example, in my script I currently assign a static cost of 1 to all tiles (plus the cost of 'getting there'), so what I'd do is add the terrain tag value of the tile to the cost. Your method is different but it'd still boil down to assigning costs to tiles and finding paths with minimal costs. Maybe if you show what you have so far I could be more helpful.

You shouldn't be terribly concerned with speed as characters generally have limited movement ranges in tactical RPGs  and any decent path finding algorithm will compute a path in little time.

Thanks for giving me things to think about for my own implementation!

 

[Gubid]

It was as if the hand of god sprang forth from the heavens and smacked me up side the head and said..
"You idiot!  Its right there!"

At least that is how it felt when I realized that my replacement problem is not a problem at all!  My method... quoted above in the first post actually checks all 4 directions before continuing to the next.  This means that it can replace as it goes and doesnt break the existing method.  I think I have what I need to finish getting this in place and can keep the basic existing script without adding anying that would affect performance heavily.  (such as calculating it twice) 

Anyway, thanks again for your input Cowlol and good luck with your script.  I have what I need to finish mine.. at least this part of it

Thanks again all!

 

[Gubid]

Just so everyone knows, if they cared.  Here is the code I ended up with, and it works perfectly!

Spoiler: def calc_pos

		case range_max
		when 0 
		  positions.push([actor.x, actor.y])	   
		else
		  positions.push([actor.x, actor.y])			  #push starting position
		  route = [[]]									#initialize route
		  cost = [0]									  #start position cost = 0
		  more_step = [0]								 #initialize array
		  for i in more_step							  #each step in position
			x = positions[i][0]						   #set x for index
			y = positions[i][1]						   #set y for index
			c = cost[i]								   #set cost for current postion index
			
			if actor.passable?(x, y, 2)				   #if can pass down?
			  tt = $game_map.terrain_tag(x, y + 1)		 #get terrain tag
			  if tt > 4								   #is terrain tag less than 4?
				tt = 0									#else, tt = o
			  end
			  if c+1+tt <= range_max					  #if current route cost + 1 + terrain tag value <= move_range
				if positions.include?([x, y + 1])		 #if up already found? (yes)
				  index = positions.index([x, y + 1])	 #set index for position
				  if cost[index] > c+1+tt				 #is new route found less costly?
					route[index].clear					#reset existing route
					route[index] = route[i] + [2]		 #set new route
					cost[index] = c+1+tt				  #replace cost table for pos
				  elsif cost[index] == c+1+tt			 #is new route just as costly?
					if rand(2) == 0					   #randomly replace, 1/3 chance
					  route[index].clear
					  route[index] = route[i] + [2]	   #replace route
					  cost[index] = c+1+tt				#replace cost table for pos
					end
				  end
				else									  #up not found..
				  positions.push([x, y + 1])			  #add position to positions array
				  route.push(route[i] + [2])			  #add route for position
				  cost.push(c+1+tt)					   #add cost required for position
				  if route[i].size + 1 < range_max		 #can one more step?
					more_step.push(route.index(route[i] + [2])) #push more step for position
				  end
				end
			  end
			end
			 
			#comments repeat for each direction
			if actor.passable?(x, y, 4) #left
			  tt = $game_map.terrain_tag(x - 1,y)
			  if tt > 4
				tt = 0
			  end
			  if c+1+tt <= range_max
				if positions.include?([x - 1, y])
				  index = positions.index([x - 1, y])
				  if cost[index] > c+1+tt
					route[index].clear
					route[index] = route[i] + [4]
					cost[index] = c+1+tt
				  elsif cost[index] == c+1+tt
					if rand(2) == 0
					  route[index].clear
					  route[index] = route[i] + [4]
					  cost[index] = c+1+tt
					end
				  end
				else
				  positions.push([x - 1, y])
				  route.push(route[i] + [4])
				  cost.push(c+1+tt)
				  if c+1+tt < range_max
					more_step.push(route.index(route[i] + [4]))
				  end
				end
			  end
			end
			
			if actor.passable?(x, y, 6) #right
			  tt = $game_map.terrain_tag(x + 1,y)
			  if tt > 4
				tt = 0
			  end
			  if c+1+tt <= range_max
				if positions.include?([x + 1, y])
				  index = positions.index([x + 1, y])
				  if cost[index] > c+1+tt
					route[index].clear
					route[index] = route[i] + [6]
					cost[index] = c+1+tt
				  elsif cost[index] == c+1+tt
					if rand(2) == 0
					  route[index].clear
					  route[index] = route[i] + [6]
					  cost[index] = c+1+tt
					end
				  end
				else
				  positions.push([x + 1, y])
				  route.push(route[i] + [6])
				  cost.push(c+1+tt)
				  if c+1+tt < range_max
					more_step.push(route.index(route[i] + [6]))
				  end
				end
			  end
			end
			
			if actor.passable?(x, y, 8) #Up
			  tt = $game_map.terrain_tag(x,y - 1) #get terrain tag
			  if tt > 4 #is terrain tag less than 4?
				tt = 0 #else, tt = o
			  end
			  if c+1+tt <= range_max #if current route cost + 1 + terrain tag value <= move_range
				if positions.include?([x, y - 1]) #if up already found? (yes)
				 index = positions.index([x, y - 1])
				  if cost[index] > c+1+tt #is new route found less costly?
					route[index].clear
					route[index] = route[i] + [8] #replace route
					cost[index] = c+1+tt	   #update cost table for pos
				  elsif cost[index] == c+1+tt #is new route just as costly?
					if rand(3) == 0 #randomly replace, 1/3 chance
					  route[index].clear
					  route[index] = route[i] + [8] #replace route
					  cost[index] = c+1+tt	 #replace cost table for pos
					end
				  end
				else	#up not found..
				  positions.push([x, y - 1]) #add position to positions array
				  route.push(route[i] + [8]) #add route for position
				  cost.push(c+1+tt) #add cost required for position
				  if c+1+tt < range_max #can one more step?
					more_step.push(route.index(route[i] + [8])) #push more step for position
				  end
				end
			  end
			end
		  end
		end
		need_del = [] #initialize need_del array
		for pos in positions #check all positions
		  if occupied?(pos[0], pos[1]) #position occupied?
			r = route[positions.index(pos)] #read route for position
			need_del.push([pos, r]) #add position and route to array for deletion
		  end		  
		end
		if need_del.size > 0 #if array size > 0
		  loop do #run loop
			p = need_del[0][0] #read path
			r = need_del[0][1] #read route
			route.delete(r) #delete route
			positions.delete(p) #delete path
			need_del.delete([p,r]) #update need_del array
			if need_del.size == 0 #if need_del == 0
			  break  #break loop
			end
		  end
		end
		@route = route #set route as instance variable instead of local only.

I tried to comment the crap out of it so that you can see why I do something and so on.