Scripts:Pathfinding

Difficulty	Moderate
Skills	An understanding of NPC references
	Should know how to move NPCs around the map

This script allows an NPC to path-find around a map. It will move around obstacles and do its best to avoid other NPCs. A sample of it in action can be seen here.

It just moves directly towards the goal without looking ahead for problems, so will get stuck in deadends, just like the NPC "Chase You (Direct)" movetype. It supports making diagonal moves, but will squeeze through corners to make them!

#Path To
# Version 1.0 - July 09, 2013
# by BMR
#
# Feel free to use this anywhere, no credit is needed.
#
#  This is the main pathfinding code used for moving combatants around the combat field.  It is used by calling
#  the script (path to(target X, target Y)) and the script will find a way to get to those coordinates.  The starting position is called from a
#  a global variable which holds what combatant number is active.  The current X and Y coordinates of that combatant are retrieved, and then used
#  as the base for calculating the path.



script, path to, npcref, tarX, tarY, begin

	#Declare the variables
	#---------------------
	variable(
		curX #\The current position
		curY #/of the NPC
		
		chcX #\The best coordinate to go to
		chcY #/thus far, can be replaced
		
		tstX #\Used in the FOR LOOP
		tstY #/for testing
		
		oldX #\Old values for X and Y, to make
		oldY #/sure there's no backtracking
		
		minX #\The X bounds for testing the
		maxX #/best path to the target
		
		minY #\The Y bounds for testing the
		maxY #/best path to the target
		
		nd   #Test distance
		od   #Old Distance
		
		cr   #NPC Reference
		
		dne  #Whether or not the pathing is done
		
		ncst #The cost to move through an NPC.  The lower this is, the less other NPCs are avoided.  The higher, the more they are avoided.
	)
	#---------------------


	#Initialize the variables
	#------------------------
	cr  := npcref
	dne := FALSE      #dne starts out as FALSE so that the loop will keep running
	
	oldX := npc X(cr) #\The old coordinates are set to the starting position of the NPC that
	oldY := npc Y(cr) #/will be doing the pathfinding
	
	ncst := 20        #This sets the cost to move past NPCs
	#------------------------
	
	
	
	camera follows npc(cr) #Depending on what you want, you can have the camera follow the NPC or not.  Currently, it will follow the NPC.
	
	set npc ignores walls(cr, TRUE) #This prevents the NPC getting stuck on corners.
	
	
	
	
	#This is the main pathfinding loop
	#  This loop will continue running until the NPC gets to its target.
	#  This is done by turning the variable "dne" to TRUE
	#--------------------------------------------------------------------------------------------------------------------
	while(dne == FALSE) do(
	
	
	
		#Reset the variables to restart
		#pathfinding from the new position
		#---------------------------------
		curX := npc X(cr) #\This will set the current coordinates to the spot
		curY := npc Y(cr) #/that the npc has just moved to

		minX := curX -- 1 #\
		maxX := curX + 1  #	\This sets the bounds of where to search for the next closest
		minY := curY -- 1 # /spot to the 8 tiles surrounding the current coordinates
		maxY := curY + 1  #/
		
		od   := 1000000   #This value is reset to an extremely high number
		#---------------------------------
		

	
		#This block will check the 8 different positions around the NPC for the best one to move to
		#---------------------------------------------------------------------------------------------
		for(tstX, minX, maxX) do(
			for(tstY, minY, maxY) do(
				
				nd := distance(tstX * 100, tstY * 100, tarX * 100, tarY * 100)      #Everything is multiplied by 100, that gives more leeway
				if(read zone(zone:Invalid, tstX, tstY) == TRUE) then(nd := 1000000) #If there's an invalid tile, set the cost really high
				if(tstX == curX && tstY == curY) then(nd := 1000000)                #Make sure to leave the current square
				if(tstX == oldX && tstY == oldY) then(nd := 1000000)                #Prevent backtracking
				if(npc at spot(tstX, tstY)) then(nd += ncst)                        #Avoid NPCs if possible, but can still be passed

				
				#If the new distance tested is smaller than the old distance, then this is closer to the target
				#so the coordinates will be saved into tstX and tstY
				if(nd << od) then(
					chcX := tstX
					chcY := tstY
					od   := nd
				)
		
			)
		)
		#---------------------------------------------------------------------------------------------

		oldX := curX #\This will set the old coordinates to the current coordinates.  This is done for
		oldY := curY #/checking later on to prevent backtracking to the same tile
		
		
		
		#Now that the closest tile has been found, the NPC will move to it
		#-----------------------------------------------------------------
		walk npc to X(cr, chcX)
		#If you don't want the npc to move diagonally, add another "wait for npc" here
		walk npc to Y(cr, chcY)
		wait for npc(cr)
		#-----------------------------------------------------------------
		
		
		if(chcX == tarX && chcY == tarY) then(dne := TRUE) #If the NPC has arrived at the target, exit the loop
		

	)

	set npc ignores walls(cr, FALSE)  #This will turn collision with walls back on
	#--------------------------------------------------------------------------------------------------------------------


end

# Distance between two x,y positions. It affects whether the pathfinding makes diagonal moves .
script, distance, x1, y1, x2, y2, begin
	#return (abs(x1 -- x2) + abs(y1 -- y2))  # Moving diagonal costs 2 movement
	# Calculation where moving diagonally costs 1 movement
	variable (dx, dy)
	dx := abs(x1 -- x2)
	dy := abs(y1 -- y2)
	if (dx < dy) then (return (dy)) else (return (dx))  # max(dx, dy)
end