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.

#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