/loaded pathfinder.tf

;; utility to find the shortest/cheapest path from point a to point b

;; Antti Pietikäinen (Heidel@bat) 2004

;; usage:
;; /path_find <source> <dest>

;; info about creating the linklist

;; /purgevar is needed
/require -q misc.tf

/require -q help_list.tf
/help_add /help_pathfinder find the cheapest path from a to b

/def -i help_pathfinder=\
	/echo -aB Pathfinder help:%;\
	/echo /path_find <start> <destination>      Find the path from <start> to <destination>%;\
	/echo ( see the file for help about creating the paths )%;\
	/echo

;; method: pick a node, put its links into a list with ascending costs, follow the first link, 
;; add that node's links into the list, and follow the first link again, until we either run 
;; out of links (not found) or meet our target

;; ----------
;; variables:
;; ----------
;; node_<name>_where				which node has the cheapest link to this node (temp)
;; node_<name>_cost				cost to reach this node from ..._where (temp)
;; node_<name>_links				number of links from this node 
;; node_count					number of links, misleading name, sorry
;; forbidden node names: not_found, starting_node, count
;; link_<name>_<#>_cost				cost of following this link
;; link_<name>_<#>_target			target of this link
;; link_<name>_<#>_command			commands used to follow this link
;; link numbering starts from 1
;; linklist					list of links to follow, same order as linklist_costs (temp)
;; (babylon_1 babylon_2 ...)
;; linklist_costs				list of costs, ascending order (temp)
;; (20 30 ...)
;; linklist_route				result of the search
;; (ocp_3 orion_2 ...)
;; linklist_route_cost				cost of the route
;; various temporary variables, all named t_*
;; all are global, and purged after search, some are used to replace function parameters/return values



;; -----------
;; all commands expect valid input, strange things will happen if invalid input is encountered!
;; should use "pre-compiled" variable list to speed up the load process, the effect is same
;/load pathfinder_paths.tf



;; -----------
;; clean some temp variables, used for init and closing
/def -i path_clean_nodes_and_lists=\
	/purgevar node_*_cost%;\
	/purgevar node_*_where%;\
	/unset linklist%;\
	/unset linklist_costs
;; ----------


;; -----------
;; add to linklist, {1} name, {2} cost (cost is the currentnode+link cost)
/def -i path_push_linklist=\
;	/echo !%{linklist}!%;\
	/set t_name %{1}%;\
	/test t_cost := %{2}%;\
	/path_add_costlist %{linklist_costs}%;\
	/path_add_linklist %{linklist}%;\
;	/echo added node %{t_name} at cost %{t_cost}%;\
;	/echo !%{linklist_costs}!%;\
;	/echo !%{linklist}!
;; ----------

;; ----------
;; move through list until we find something bigger than current cost
;; then, add the cost to the right place, store the place in t_count for add_linklist
/def -i path_add_costlist=\
	/test t_slen := strlen({*})%;\
	/test t_count := 0%;\
	/while ({#}) \
		/if ({1} > {t_cost}) \
			/break%;\
		/else \
			/test ++t_count%;\
			/shift%;\
		/endif%;\
	/done%;\
	/test t_elen := strlen({*})%;\
	/test linklist_costs := strcat( substr( linklist_costs,0,t_slen-t_elen),\
						  t_elen==0&t_slen!=0?" ":"",\
						  t_cost,\
						  {*}?" ":"",\
						  {*})
;; ----------

;; ----------
;; add the name to the list, the place is in t_count, name is in t_name
/def -i path_add_linklist=\
	/test t_slen := strlen("%{*}")%;\
	/shift %{t_count}%;\
	/test t_elen := strlen("%{*}")%;\
	/if (t_count==0) \
		/test linklist := strcat(t_name,linklist=~""?"":" ",linklist)%;\
	/elseif (!{*}) \
		/test linklist := strcat(linklist,linklist=~""?"":" ",t_name)%;\
	/else \
		/test linklist := strcat(substr( linklist,0,t_slen-t_elen),\
						  " ",t_name,\
						  {*})%;\
	/endif
;; ----------


;; ------------
;; get the first item on linklist, save it to t_linkname, then remove the first item on both lists
;; if list is empty, t_linkname is set to "not_found"
/def -i path_pop_linklist=\
	/path_get_linklist %{linklist}%;\
	/path_get_costlist %{linklist_costs}
;; ----------

;; ----------
/def -i path_get_costlist=\
	/shift%;\
	/test linklist_costs :={*}
;; ----------

;; ----------
/def -i path_get_linklist=\
	/if ({#} == 0) \
		/test t_linkname := "not_found"%;\
	/else \
		/test t_linkname := {1}%;\
	/endif%;\
	/shift%;\
	/test linklist :={*}
;; ----------


;; ------------
;; follow the links in {1} and possibly add the links to linklist 
;; (if this is a cheaper way to reach that node, that is)
/def -i path_follow_node=\
	/eval /test t_num := node_%{1}_links%;\
	/eval /test t_basecost := node_%{1}_cost%;\
;	/echo now at %{1}, basecost %{t_basecost}, has %{t_num} links%;\
	/while (t_num) \
		/eval /test t_ltarget := link_%{1}_%{t_num}_target%;\
		/eval /test t_lcost := link_%{1}_%{t_num}_cost%;\
		/eval /test t_ncost := node_%{t_ltarget}_cost%;\
		/if ( (t_ncost =~ "") | ( (t_basecost + t_lcost) < t_ncost) )\
;			/eval /echo > marking node %{t_ltarget} for search at cost $[t_basecost+t_lcost]%;\
			/eval /test node_%{t_ltarget}_cost := t_basecost + t_lcost%;\
			/eval /test node_%{t_ltarget}_where := {1}%;\
			/eval /path_push_linklist %{t_ltarget} $[t_basecost + t_lcost]%;\
		/endif%;\
		/test --t_num%;\
	/done
;; ----------


;; -------------
;; do the search
;; {1} is the startpoint, {2} is the endpoint
;; max number of nodes searched is node_count, variable "managed" by path_create_link
;; store the result in linklist_route, total cost is in linklist_route_cost
;; purge the temp variables when done
/def -i path_find=\
	/path_clean_nodes_and_lists%;\
	/unset linklist_route%;\
	/unset linklist_route_cost%;\
	/eval /test node_%{1}_where := "starting_node"%;\
	/eval /test node_%{1}_cost := 0%;\
	/path_push_linklist %{1} 0%;\
	/test t_checkup := 0%;\
	/while ( (t_linkname !~ {2}) & (++t_checkup < node_count) ) \
		/path_pop_linklist%;\
		/if (t_linkname =~ "not_found") \
			/break%;\
		/endif%;\
		/path_follow_node %{t_linkname}%;\
	/done%;\
	/if ( (t_linkname =~ "not_found") | (t_checkup == node_count) ) \
		/echo -aCred % pathfinder: couldn't find route from '%{1}' to '%{2}.'%;\
	/else \
		/path_backtrack %{1} %{2}%;\
		/test linklist_route := t_list%;\
		/test linklist_route_cost := t_total%;\
		/echo -aCgreen % pathfinder: found route from '%{1}' to '%{2}', cost %{t_total}.%;\
		/echo -aCgreen % Start movement with /path_go%;\
	/endif%;\
	/purgevar t_*%;\
	/path_clean_nodes_and_lists
;; ----------


;; --------------
;; trace the way back from {2} to {1} following ..._where's
/def -i path_backtrack=\
	/unset t_list%;\
	/eval /test t_from := node_%{2}_where%;\
	/test t_to := {2}%;\
	/eval /test t_total := node_%{2}_cost%;\
;	/echo starting backtrack by finding link from node %{t_from} to node %{t_to}%;\
	/while (t_from !~ "starting_node") \
		/path_find_link%;\
		/test t_list :=strcat(t_link," ",t_list)%;\
		/test t_to := t_from%;\
		/eval /test t_from := node_%{t_from}_where%;\
;		/echo continuing backtrack by finding link from node %{t_from} to node %{t_to}%;\
	/done%;\
;	/echo got the route: %{t_list}
;; ----------
	

;; ----------
;; check the links from t_from, find the one leading to t_to, store the link name to t_link
/def -i path_find_link=\
	/eval /test t_n := node_%{t_from}_links%;\
	/while (t_n) \
		/eval /test t_t := link_%{t_from}_%{t_n}_target%;\
		/if (t_t =~ t_to) \
			/break%;\
		/endif%;\
		/test --t_n%;\
	/done%;\
	/if (t_n==0) \
		/echo ERROR! no link from %{t_from} to %{t_to}, there was one earlier...%;\
	/else \
		/test t_link := "%{t_from}_%{t_n}"%;\
	/endif
;; ----------

;; ---------------
;; create a command from input links
;; delim is ;, do a replace if that's not ok
;; also, replace 40 s with 20 s;20 s
/def -i path_create_command=\
	/unset t_com%;\
	/while ({#}) \
		/eval /test t_com := strcat(t_com,link_%{1}_command,";")%;\
		/shift%;\
	/done%;\
	/test t_mod := t_com%;\
	/test t_big := regmatch("(([0-9][0-9]+) (n|ne|nw|s|se|sw|w|e));",t_mod)%;\
	/while (t_big) \
;		/echo found: %{P1} from: %{t_mod}%;\
;		/echo t_big !%{t_big}! P1 !%{P1}! P2 !%{P2}! P3 !%{P3}!%;\
		/path_split_numdir %{P1}%;\
		/test t_new := ""%;\
		/while (t_dirnum > 20) \
			/test t_new := strcat("20 ",t_dir,";",t_new)%;\
			/test t_dirnum := t_dirnum-20%;\
		/done%;\
		/test t_start := strstr(t_mod,{P1})%;\
		/test t_mod := substr(t_mod,t_start+strlen({P1}))%;\
		/test t_new := strcat(t_new,t_dirnum," ",t_dir)%;\
		/test t_com := replace({P1},t_new,t_com)%;\
		/test t_big := regmatch("([0-9][0-9]+ (?:n|ne|nw|s|se|sw|w|e));",t_mod)%;\
;		/echo command now: %{t_com}%;\
	/done%;\
	/test t_com := replace(";1 ",";",t_com)%;\
	/test t_com := substr(t_com,0,strlen(t_com)-1)%;\
	/result t_com
;; ----------

;; ----------
;; regmatch fails to return P2 and P3 from (()()) after the first, so, need this
/def -i path_split_numdir=\
	/test t_dirnum := {1}%;\
	/test t_dir := {2}
;; ----------

;; ----------
;; adding links
;; twoway link command usable only with commands with basic directions
;; cost calculation works only with commands with basic direction
;; hence: ALWAYS give cost for links with non-standard directions
;;        NEVER use twoway with non-standard directions
;; cost 0 counts the cost with path_count_cost
;; to force cost of 0, use 0.0 instead (might work)
;; avoid creating links with cost of 0, they may explode
;; negative costs are very likely to create endless loops
;; ----------

;; ----------
;; create a link
;; {1} from, {2} to, {3} cost, {4+} commands
/def -i path_create_link=\
;	/echo from: %{1} to: %{2} at cost: %{3} using command: %{-3}%;\
	/eval /test t_index := ++node_%{1}_links%;\
	/if ({3}=~"0") \
		/path_count_cost %{-3}%;\
	/else \
		/test t_cost := {3}%;\
	/endif%;\
	/eval /test link_%{1}_%{t_index}_cost := t_cost%;\
	/eval /test link_%{1}_%{t_index}_target :="%{2}"%;\
	/eval /test link_%{1}_%{t_index}_command :="%{-3}"%;\
	/test ++node_count
;; ----------

;; ----------
;; count the link cost from the command
;; cost is 1 per room
;; turns the command into an expression ;)
/def -i path_count_cost=\
	/test t_result := replace(" ","*",{*})%;\
	/test t_result := replace("ne","1",t_result)%;\
	/test t_result := replace("se","1",t_result)%;\
	/test t_result := replace("nw","1",t_result)%;\
	/test t_result := replace("sw","1",t_result)%;\
	/test t_result := replace("n","1",t_result)%;\
	/test t_result := replace("s","1",t_result)%;\
	/test t_result := replace("e","1",t_result)%;\
	/test t_result := replace("w","1",t_result)%;\
	/test t_result := replace(";","+",t_result)%;\
	/if (regmatch("[^0-9+*]",t_result)) \
		/echo % warning: using default cost (1) because failed to get the cost from: %{t_result}%;\
		/set t_cost=1%;\
	/else \
		/eval /test t_cost := %{t_result}%;\
	/endif
;; ----------

;; ----------
;; create link from a to b and link from b to a
;; consider doing most of the links with this
/def -i path_create_twoway_link=\
	/path_create_link %{*}%;\
	/path_create_link %{2} %{1} %{3} $(/path_reverse_commands %{-3})
;; ----------

;; ----------
;; turns e to w and so on
/def -i path_reverse_commands=\
	/test t_result := replace("e","q",{*})%;\
	/test t_result := replace("w","e",t_result)%;\
	/test t_result := replace("q","w",t_result)%;\
	/test t_result := replace("n","q",t_result)%;\
	/test t_result := replace("s","n",t_result)%;\
	/test t_result := replace("q","s",t_result)%;\
	/result %{t_result}
;; ----------

;; ----------------
;; load slobber's paths
/load slobberpaths.tf



/echo -aCyellow % Pathfinder loaded.