Smartroute: rework to use result of rs_cache instead of duplicating, use bread-first-search and incremental search further with formspec

3 files changed, 184 insertions, 122 deletions

diff --git a/advtrains_interlocking/database.lua b/advtrains_interlocking/database.lua
index f84f60b..38b1bc8 100644
--- a/advtrains_interlocking/database.lua
+++ b/advtrains_interlocking/database.lua
@@ -718,6 +718,7 @@ local function recursively_find_routes(s_pos, s_connid, locks_found, result_tabl
 				return
 			end
 			local out_conns = ildb.get_possible_out_connids(node.name, bconnid)
+			-- note 2025-01-06: get_possible_out_connids contains some logic so that the correct switch state is selected even if the turnout is entered from the branch side (see "have_back_conn")
 			for oconnid, state in pairs(out_conns) do
 				--atdebug("Going in direction",oconnid,"state",state)
 				locks_found[pts] = state
diff --git a/advtrains_interlocking/smartroute.lua b/advtrains_interlocking/smartroute.lua
index a26f2d1..f697d7b 100644
--- a/advtrains_interlocking/smartroute.lua
+++ b/advtrains_interlocking/smartroute.lua
@@ -19,7 +19,7 @@ function sr.start(pname, sigd)
 			end
 		end
 	end
-	sr.propose_next(pname, sigd, 10, is_startsignal_shunt) -- TODO set tscnt_limit to 2 initially and then increase it. Do this when form is implemented
+	sr.propose_next(pname, sigd, 0, is_startsignal_shunt)
 end
 
 
@@ -28,88 +28,10 @@ local function otherside(s)
 end
 
 --route search implementation
--- Note this is similar to recursively_find_routes in database.lua, there used for the rscache
-
-local function recursively_find_routes(s_pos, s_connid, searching_shunt, tcbseq, mark_pos, result_table, scan_limit, tscnt_limit, cur_ts_id, notify_pname)
-	atdebug("(SmartRoute) Recursively restarting at ",s_pos, s_connid, "limit left", scan_limit,"tscnt",tscnt_limit)
-	local ti = advtrains.get_track_iterator(s_pos, s_connid, scan_limit, false)
-	local pos, connid, bconnid = ti:next_branch()
-	pos, connid, bconnid = ti:next_track()-- step once to get ahead of previous turnout
-	local last_pos
-	repeat
-		-- record position in mark_pos
-		local pts = advtrains.encode_pos(pos)
-		mark_pos[pts] = true
-		
-		local node = advtrains.ndb.get_node_or_nil(pos)
-		--atdebug("(SmartRoute) Walk ",pos, "nodename", node.name, "entering at conn",bconnid)
-		local ndef = minetest.registered_nodes[node.name]
-		if ndef.advtrains and ndef.advtrains.node_state_map then
-			-- Stop, this is a switchable node. Find out which conns we can go at
-			atdebug("(SmartRoute) Found turnout ",pos, "nodename", node.name, "entering at conn",bconnid)
-			local out_conns = ildb.get_possible_out_connids(node.name, bconnid)
-			for oconnid, state in pairs(out_conns) do
-				--atdebug("Going in direction",oconnid,"state",state)
-				recursively_find_routes(pos, oconnid, searching_shunt,
-					table.copy(tcbseq), table.copy(mark_pos),
-					result_table, ti.limit, tscnt_limit, cur_ts_id, notify_pname)
-			end
-			return
-		end
-		--otherwise, this might be a tcb
-		local tcb = ildb.get_tcb(pos)
-		if tcb then
-			local fsigd = { p = pos, s = connid }
-			atdebug("(SmartRoute) Encounter TCB ",fsigd)
-			tcbseq[#tcbseq+1] = fsigd
-			-- TS validity check: ensure that the TS the back connid refers to is the same as the one at the start
-			local re_ts_id = tcb[bconnid].ts_id
-			if re_ts_id ~= cur_ts_id then
-				atwarn("(SmartRoute) Found TS Inconsistency: entered in section",cur_ts_id,"but TCB backref is section",re_ts_id)
-				ildb.check_and_repair_ts_at_pos(pos, bconnid, notify_pname)
-				-- nothing needs to be updated on our side
-			end
-			-- check if this is a possible route endpoint
-			local tcbs = tcb[connid]
-			if tcbs.signal then
-				local ndef = advtrains.ndb.get_ndef(tcbs.signal)
-				if ndef and ndef.advtrains then
-					if ndef.advtrains.route_role == "main" or ndef.advtrains.route_role == "main_distant"
-							or ndef.advtrains.route_role == "end" or ndef.advtrains.route_role == "shunt" then
-						-- signal is suitable target
-						local is_mainsignal = ndef.advtrains.route_role ~= "shunt"
-						-- record the found route in the results
-						result_table[#result_table+1] = {
-							tcbseq = table.copy(tcbseq),
-							mark_pos = table.copy(mark_pos),
-							shunt_route = not is_mainsignal,
-							to_end_of_track = false,
-							name = tcbs.signal_name or atil.sigd_to_string(fsigd)
-						}
-						-- if this is a main signal and/or we are only searching shunt routes, stop the search here
-						if is_mainsignal or searching_shunt then
-							atdebug("(SmartRoute) Terminating here because it is main or only shunt routes searched")
-							return
-						end
-					end
-				end
-			end
-			-- decrease tscnt
-			tscnt_limit = tscnt_limit - 1
-			atdebug("(SmartRoute) Remaining TS Count:",tscnt_limit)
-			if tscnt_limit <= 0 then
-				break
-			end
-			-- update the cur_ts_id
-			cur_ts_id = tcb[connid].ts_id
-			atdebug("(SmartRoute) Now in section:",cur_ts_id)
-		end
-		-- Go forward
-		last_pos = pos
-		pos, connid, bconnid = ti:next_track()
-	until not pos -- this stops the loop when either the track end is reached or the limit is hit
-	atdebug("(SmartRoute) Reached track end or limit at", last_pos, ". This path is not saved, returning")
-end
+-- new 2025-01-06: rely on the already present info from rscache to traverse sections
+-- this allows to implement a breadth first search
+-- format of foundroute:
+-- { name = "the name", tcbseq = { list of sigds in sequence, not containing the start sigd }}
 
 local function build_route_from_foundroute(froute, name)
 	local route = {
@@ -123,17 +45,99 @@ local function build_route_from_foundroute(froute, name)
 	return route
 end
 
--- Maximum scan length for track iterator
-local TS_MAX_SCAN = 1000
+-- Maximum num of sections for routes to be found
+local RTE_MAX_SECS = 16
 
-function sr.rescan(pname, sigd, tcbs, tscnt_limit, searching_shunt, pname)
-	local result_table = {}
-	recursively_find_routes(sigd.p, sigd.s, searching_shunt, {}, {}, result_table, TS_MAX_SCAN, tscnt_limit, tcbs.ts_id, pname)
-	return result_table
+-- scan for possible routes from the start tcb in a bread-first-search manner
+-- find_more_than: search is aborted only if more than the specified number of routes are found
+function sr.rescan(pname, sigd, tcbs, find_more_than, searching_shunt, pname)
+	local found_routes = {}
+	local restart_tcbs = { {sigd = sigd, tcbseq = {} } }
+	local last_len = 0
+	while true do
+		-- take first entry out of restart_tcbs (due to the way it is inserted the first entry will always be the one with the lowest length
+		local cur_restart
+		for idx, rst in ipairs(restart_tcbs) do
+			cur_restart = rst
+			table.remove(restart_tcbs, idx)
+			break
+		end
+		if not cur_restart then
+			-- we have no candidates left. Give up and return what we have
+			atdebug("(SR) No Candidates left, end rescan")
+			return found_routes
+		end
+		-- check if we need to stop due to having found enough routes
+		local cur_len = #cur_restart.tcbseq
+		if cur_len > last_len then
+			-- one level is finished, check if enoufh routes are found
+			if #found_routes > find_more_than then
+				atdebug("(SR) Layer finished and enough routes found, end rescan")
+				return found_routes
+			end
+			last_len = cur_len
+		end
+		-- our current restart point is nouw in cur_restart
+		local c_sigd = cur_restart.sigd
+		atdebug("(SR) Search continues at",c_sigd,"seqlen",#cur_restart.tcbseq)
+		-- do a TS repair, this also updates the RS cache should it be out of date
+		local c_ts_id = ildb.check_and_repair_ts_at_pos(c_sigd.p, c_sigd.s, pname, false)
+		if c_ts_id then
+			local c_ts = ildb.get_ts(c_ts_id)
+			local bgn_pts = advtrains.encode_pos(c_sigd.p)
+			local rsout = c_ts.rs_cache[bgn_pts]
+			if rsout then
+				for _, end_sigd in ipairs(c_ts.tc_breaks) do
+					end_pkey = advtrains.encode_pos(end_sigd.p)
+					if rsout[end_pkey] then
+						atdebug("(SR) Section",c_ts_id,c_ts.name,"has way",c_sigd,"->",end_sigd)
+						local nsigd = {p=end_sigd.p, s = end_sigd.s==1 and 2 or 1} -- invert to other side
+						-- record nsigd in the tcbseq
+						local ntcbseq = table.copy(cur_restart.tcbseq)
+						ntcbseq[#ntcbseq+1] = nsigd
+						local shall_continue = true
+						-- check if that sigd is a route target
+						local tcbs = ildb.get_tcbs(nsigd)
+                        if tcbs.signal then
+							local ndef = advtrains.ndb.get_ndef(tcbs.signal)
+							if ndef and ndef.advtrains then
+								if ndef.advtrains.route_role == "main" or ndef.advtrains.route_role == "main_distant"
+											or ndef.advtrains.route_role == "end" or ndef.advtrains.route_role == "shunt" then
+									-- signal is suitable target
+									local is_mainsignal = ndef.advtrains.route_role ~= "shunt"
+									atdebug("(SR) Suitable end signal at",nsigd,", recording route!")
+									-- record the found route in the results
+									found_routes[#found_routes+1] = {
+											tcbseq = ntcbseq,
+											shunt_route = not is_mainsignal,
+											name = tcbs.signal_name or atil.sigd_to_string(fsigd)
+									}
+									-- if this is a main signal and/or we are only searching shunt routes, stop the search here
+									if is_mainsignal or searching_shunt then
+											atdebug("(SR) Not continuing this branch!")
+											shall_continue = false
+									end
+								end
+							end
+                        end
+						-- unless overridden, insert the next restart point
+						if shall_continue then
+							restart_tcbs[#restart_tcbs+1] =  {sigd = nsigd, tcbseq = ntcbseq } 
+						end
+					end
+				end
+			else
+				atdebug("(SR) Section",c_ts_id,c_ts.name,"found no rscache entry for start ",bgn_pts)
+			end
+		else
+			atdebug("(SR) Stop at",c_sigd,"because no sec ahead")
+		end
+	end
 end
 
+local players_smartroute_actions = {}
 -- Propose to pname the smartroute actions in a form, with the current settings as passed to this function
-function sr.propose_next(pname, sigd, tscnt_limit, searching_shunt)
+function sr.propose_next(pname, sigd, find_more_than, searching_shunt)
 	local tcbs = ildb.get_tcbs(sigd)
 	if not tcbs or not tcbs.routes then
 		minetest.chat_send_player(pname, "Smartroute: TCBS or routes don't exist here!")
@@ -143,40 +147,93 @@ function sr.propose_next(pname, sigd, tscnt_limit, searching_shunt)
 		return
 	end
 	-- Step 1: search for routes using the current settings
-	local found_routes = sr.rescan(pname, sigd, tcbs, tscnt_limit, searching_shunt, pname)
-	-- Step 2: remove routes for endpoints for which routes already exist
-	local ex_endpts = {} -- key = sigd_to_string
-	for rtid, route in ipairs(tcbs.routes) do
-		local valid = advtrains.interlocking.check_route_valid(route, sigd)
-		local endpoint = route[#route].next -- 'next' field of the last route segment (the segment with index==len)
-		if valid and endpoint then
+	local found_routes = sr.rescan(pname, sigd, tcbs, find_more_than, searching_shunt, pname)
+	-- Step 2: store in actions table
+	players_smartroute_actions[pname] = {
+		sigd = sigd,
+		searching_shunt = searching_shunt,
+		found_routes = found_routes
+	}
+	-- step 3: build form
+	local form = "size[5,5]label[0,0;Route search: "..#found_routes.." found]"
+	local tab = {}
+	for idx, froute in ipairs(found_routes) do
+		tab[idx] = minetest.formspec_escape(froute.name.." (Len="..#froute.tcbseq..")")
+	end
+	form=form.."textlist[0.5,1;4,3;rtelist;"..table.concat(tab, ",").."]"
+	form=form.."button[0.5,4;2,1;continue;Search further]"
+	form=form.."button[2.5,4;2,1;apply;Apply]"
+	
+	minetest.show_formspec(pname, "at_il_smartroute_propose", form)
+end
+
+minetest.register_on_player_receive_fields(function(player, formname, fields)
+	local pname = player:get_player_name()
+	if not minetest.check_player_privs(pname, "interlocking") then
+		return
+	end
+	if formname ~= "at_il_smartroute_propose" then
+		return
+	end
+	-- retrieve from the storage the current search result
+	local srtab = players_smartroute_actions[pname]
+	if not srtab then
+		return
+	end
+	local sigd = srtab.sigd
+	local found_routes = srtab.found_routes
+	
+	if fields.continue then
+		-- search on, but find at least one route more
+		sr.propose_next(pname, sigd, #found_routes, srtab.searching_shunt)
+		return
+	end
+	
+	if fields.apply then
+		-- user is happy with the found routes. Proceed to save them in the signal
+		local tcbs = ildb.get_tcbs(sigd)
+		if not tcbs then return end
+		-- remove routes for endpoints for which routes already exist
+		local ex_endpts = {} -- key = sigd_to_string
+		for rtid, route in ipairs(tcbs.routes) do
+			local valid = advtrains.interlocking.check_route_valid(route, sigd)
+			local endpoint = route[#route].next -- 'next' field of the last route segment (the segment with index==len)
+			if valid and endpoint then
+				local endstr = advtrains.interlocking.sigd_to_string(endpoint)
+				atdebug("(Smartroute) Find existing endpoint:",route.name,"ends at",endstr)
+				ex_endpts[endstr] = route.name
+			else
+				atdebug("(Smartroute) Find existing endpoint:",route.name," not considered, endpoint",endpoint,"valid",valid)
+			end
+		end
+		local new_frte = {}
+		for _,froute in ipairs(found_routes) do
+			local endpoint = froute.tcbseq[#froute.tcbseq]
 			local endstr = advtrains.interlocking.sigd_to_string(endpoint)
-			atdebug("(Smartroute) Find existing endpoint:",route.name,"ends at",endstr)
-			ex_endpts[endstr] = route.name
-		else
-			atdebug("(Smartroute) Find existing endpoint:",route.name," not considered, endpoint",endpoint,"valid",valid)
+			if not ex_endpts[endstr] then
+				new_frte[#new_frte+1] = froute
+			else
+				atdebug("(Smartroute) Throwing away",froute.name,"because endpoint",endstr,"already reached by route",ex_endpts[endstr])
+			end
 		end
-	end
-	local new_frte = {}
-	for _,froute in ipairs(found_routes) do
-		local endpoint = froute.tcbseq[#froute.tcbseq]
-		local endstr = advtrains.interlocking.sigd_to_string(endpoint)
-		if not ex_endpts[endstr] then
-			new_frte[#new_frte+1] = froute
-		else
-			atdebug("(Smartroute) Throwing away",froute.name,"because endpoint",endstr,"already reached by route",ex_endpts[endstr])
+		
+		-- All remaining routes will be applied to the signal
+		local sel_rte = #tcbs.routes+1
+		for idx, froute in ipairs(new_frte) do
+			tcbs.routes[#tcbs.routes+1] = build_route_from_foundroute(froute)
 		end
+		-- if only one route present and it is newly created (there was no route before, thus sel_rte==1), make default
+		if sel_rte == 1 and #tcbs.routes == 1 then
+			tcbs.routes[1].ars = {default=true}
+		end
+		atdebug("Smartroute done!")
+		advtrains.interlocking.show_signalling_form(sigd, pname, sel_rte)
+		players_smartroute_actions[pname] = nil
 	end
-	
-	-- All remaining routes will be shown to user now.
-	-- TODO: show a form. Right now still shortcircuit
-	local sel_rte = #tcbs.routes+1
-	for idx, froute in ipairs(new_frte) do
-		tcbs.routes[#tcbs.routes+1] = build_route_from_foundroute(froute)
+	if fields.quit then
+		players_smartroute_actions[pname] = nil
 	end
-	atdebug("Smartroute done!")
-	advtrains.interlocking.show_signalling_form(sigd, pname, sel_rte)
-end
+end)
 
 
 advtrains.interlocking.smartroute = sr
diff --git a/advtrains_interlocking/tcb_ts_ui.lua b/advtrains_interlocking/tcb_ts_ui.lua
index 4f755af..edc6921 100755
--- a/advtrains_interlocking/tcb_ts_ui.lua
+++ b/advtrains_interlocking/tcb_ts_ui.lua
@@ -871,14 +871,15 @@ function advtrains.interlocking.show_signalling_form(sigd, pname, sel_rte, calle
 					form = form.."button[0.5,6;  5,1;setroute;Set Route]"
 					form = form.."button[0.5,7;2,1;dsproute;Show]"
 					if hasprivs then
-						form = form.."button[2.5,7;1,1;setarsdefault;Set Def.]"
+						form = form.."button[5.5,3.3;1,0.3;setarsdefault;D]tooltip[setarsdefault;Set ARS default route]"
 						form = form.."button[3.5,7;2,1;editroute;Edit]"
 						if sel_rte > 1 then
-							form = form .. "button[5.5,4;0.5,0.3;moveup;↑]"
+							form = form .. "button[5.5,4;1,0.3;moveup;↑]"
 						end
 						if sel_rte < #strtab then
-							form = form .. "button[5.5,4.7;0.5,0.3;movedown;↓]"
+							form = form .. "button[5.5,4.7;1,0.3;movedown;↓]"
 						end
+						form = form.."button[5.5,5.4;1,0.3;delroute;X]tooltip[delroute;Delete this route]"
 					end
 				else
 					form = form .. "]"
@@ -1097,6 +1098,9 @@ minetest.register_on_player_receive_fields(function(player, formname, fields)
 						end
 					end
 				end
+				if fields.delroute and hasprivs then
+					table.remove(tcbs.routes,sel_rte)
+				end
 			end
 		end