Simple "Can get there from here" function

[troycheek]

Can Unit X get from Point A to Point B? Or, at least, close enough to Point B to accomplish its assigned task?

If there was a function to easily determine that, my Central Build AI wouldn't try to send construction vehicles off to build on distant islands, or construction subs to build far inland. I think I've finally figured out the Lua Pathfinder enough to code a function to determine that.

Edit: I was wrong, of course. The code I initially posted didn't function properly, and some of the conclusions in the discussion that followed were incorrect. I removed them to keep from confusing anyone else. Check newer posts.

Anyway, the point of the whole exercise is to create some kind of small, simple drop-in function for any time a unit under widget control needs to know "can I get there from here?" Suggestions? Comments?

[CarRepairer]

Tada! http://springrts.com/wiki/Lua_PathFinder

[jK]

local i = #waypoint
local x,y,z = waypoint[1],waypoint[2],waypoint[3]
While the wiki speaks of levels of details and whatnot, the waypoint table appears to mostly be a progression from origin to destination. The last waypoint is the closest one to the destination. If there is a path, this waypoint will be very close to the destination. If not, then this waypoint will be far away from the destination, probably back at the edge of whatever terrain or water which the unit finds impassible.

return x,y,z
Why return the coordinates of the last waypoint instead of a simple true/false? To make a true/false decision, you have to specify how close is close enough. The path does not always end exactly at the destination. If you want a unit to go to or through a particular position, you may want to get it very close. On the other hand, if you're trying to attack an enemy unit or build a structure at a particular position, it may be sufficient to know that you could get within a certain range.

Incorrect if the target can't be reached it returns nil. As the wiki says the resolutions of the waypoints decreases (there are 3 different levels of resolutions), so the final waypoint has a very low resolution and so it can somewhat off the desired spot. By using path:Next() the path gets updated and so the resolution will increase the more you come up to final pos.
Use the `radius` argument if you want to use different margins.

PS: Cause of the low resolution it can happen that it seems first that a spot is reachable, but the more you come up to it the resolution increases and so it can happen that the spots isn't reachable anymore. But that has nothing to do with the distance of the first assumption from the wanted target spot.

[troycheek]

Tada! http://springrts.com/wiki/Lua_PathFinder

I'm aware of that page and have already corrected a couple of minor mistakes on it (a couple more to go). If that page has all the information I'm supposed to need, then I need a remedial class or something. I've learned more from my own experimentation and jK's comments than that page. Speaking of which...

Incorrect if the target can't be reached it returns nil.

Assuming you're referring to Spring.RequestPath, I've seen two cases where this isn't true. First, when the destination is the same as or very close to the starting point, the path may be nil even though the unit is already there or literally one step away. Secondly, now that I've rewritten to use path:Next(), I've seen cases where a path is returned when the target isn't reachable. The log shows something like this:

Code: Select all

Construction KBot from 1144, 1164 to 1552, 2144:
1128, 1144
1120, 1160
1112, 1176
1112, 1192
1112, 1208
[...about 100 lines snipped..]
1512, 1840
1528, 1848
1544, 1848
1552, 2144
Done!

Note the discontinuity in the last two steps there. In this case, there was a sheer cliff between the unit and where I wanted it to build. The unit walked along the cliff until it was as close to the target as possible, then decided it couldn't move anymore. (Note: The target probably was technically reachable, but only if the unit backtracked halfway across the map first. But since the pathfinder didn't send it that way...)

If not for cases like these two, Spring.RequestPath could be used all by itself to tell if a unit could reach a destination.

As the wiki says the resolutions of the waypoints decreases (there are 3 different levels of resolutions), so the final waypoint has a very low resolution and so it can somewhat off the desired spot.

I think I finally understand all that. Thanks. Too bad that it invalidates pretty much everything I was doing, but I think I can still do what I wanted to do.

Updated, and still probably useless, "Can I get there from here" check. This one just returns true/false.

Code: Select all

function CanGetThere(unitID,ox,oy,oz,dx,dy,dz)
	local udid = Spring.GetUnitDefID(unitID)
	local moveID = UnitDefs[udid].moveData.id
	if not moveID then return dx,dy,dz end
	if Distance(ox,oz,dx,dz) < 32 then return true end
	local path = Spring.RequestPath( moveID,ox,oy,oz,dx,dy,dz )
	if path then
		local cnt = 0
		local x,y,z = 0,0,0
		local nx,ny,nz = path:Next(ox,oy,oz)
		while (nx) and cnt < 1000 do	-- sanity check
			x,y,z = nx,ny,nz
			nx,ny,nz = path:Next(x,y,z)
			if (nx == dx) and (nz == dz) then return true end
			cnt = cnt + 1
		end
		return false
	else
		return false
	end
end

I still need to add some kind of discontinuity check.

[troycheek]

Code: Select all

Path:GetEstimatedPath

 ( ) -> nil | {
    [1] = { x,y,z }, ...
  },{
    [1] = startIdxOfDetailedPath,
    [2] = startIdxOfDetailedEstimatedPath1,
    [3] = startIdxOfDetailedEstimatedPath2,
  }

GetEstimatedPath() returns 2 tables: 1 table with the waypoints and 1 table with 3 indices (in the waypoint table) when a new (more lazy) pathfinding algorithm begins. So the waypoint table contains 3 different levels of details.

Part of my confusion, which I'll mention here in case anyone else is likewise confused, is that I read this and thought it meant that the waypoint table contains three complete paths from point A to point B with three different levels of details. I was wrong, of course.

In actuality, the waypoint table charts out the path starting with pretty small steps, and if the path is long enough switches to medium steps at that point of the path, then after a while switches to huge steps.

Also, if the path is short enough, it may reach the end before the waypoints switch to medium or huge steps. In that case, startIdxOfDetailedEstimatedPath1 or 2 point to nil entries of the waypoint table.

Edit: Probably need to add some of that into the wiki.