The thing that troubled me about my earlier solution was that it found the path with the least hops, not necessarily the least distance. This completely different version uses the A* (pronounced A Star) algorithm to take the travelling cost of each leg into account.
A* path finding algorithm
The general approach of the algorithm is to:
- Start with the starting town (call this the current town)
- Put the current town on the closed list (we won’t evaluate this one again)
- Find all towns leading from the current town (the destinations) and evaluate them. For each one:
- If the town is the target town, the algorithm is complete.
- If the town is on the “closed” list, ignore it.
- If the town is not on the “open” list, add it to the open list with its parent being the current town. The cost (G) of getting to this town is the cost of getting to the current town, plus the cost of this particular town (see below). The cost (H) of getting to the target is the distance to the target - in this case (since we aren't using compass directions) I don't know the cost to the target, and thus it is set to zero.
- If the town is on the “open” list already, and the cost (G) of getting to it is lower than before, change its cost to the lower cost, and change its parent to the current town. This represents the case where a better way has been found to reach the town in question that was previously found. For example, previously you might have reached a town by travelling one way, but now you can get there using a shorter way.
- Search all the towns in the “open” list and find the one with the lowest cost (F). If towns have the same F value choose the one with the lower H value (closer to the destination). If towns have the same F and H value, then choose any town (eg. the first one). Make that the current town. Remember that the F cost is the combined cost of getting there (G), and expected cost of getting from there to the destination (H). This effectively tends to force the algorithm to search towards the target rather than away from it.
- Go back to step 2 above, until the target is located, or the open list is exhausted, or some limit is reached (eg. 500 iterations)
Once the target is found we can work out the path by taking the town that reached it, then find its parent, then the parent of that parent, and so on, until we are back at the starting town. This path (in reverse) is the optimal way of reaching the target.
Cost of travel
As a simplification of travel costs I have assumed that your directions are a speedwalk, and that each number represents the cost. For example, 2n 3e 4s would be a cost of 9 (2 + 3 + 4). You can make this more complex if you want. This requires you to have numbers every time (ie. 1n rather than n).
Alternatively you could call EvaluateSpeedwalk on the speedwalk string (excluding the "do" part) and then count the number of lines that were generated.
Data:
travel = {}
travel.paris =
{
london = 'do 1n',
rome = 'do 2s'
}
travel.london =
{
paris = 'do 3s',
glasgow = 'do 4n'
}
travel.glasgow =
{
london = 'do 5s'
}
travel.rome =
{
paris = 'do 60n',
newyork = 'do 500e',
}
travel.newyork =
{
glasgow = 'do 5w'
}
Code:
DEBUGGING = false
MAX_SEARCHES = 100
-- -----------------------------------------------------------------
-- DEBUG helper function for debugging
-- -----------------------------------------------------------------
function DEBUG (...)
if DEBUGGING then
print ("DEBUG:", table.concat ( { ... }, " "))
end -- if
end -- DEBUG
function findPathsAstar (start, finish)
local NODE_OPEN = 1
local NODE_CLOSED = 2
local NODE_EXPLORED = 3
local finalCost = 0
-- open list and closed list
open, closed = {}, {}
-- for display
explored_towns = {}
-- add to open list
function makeOpen (which, g, parent)
explored_towns [which] = NODE_OPEN -- open
if open [which] then
-- X, Y won't change because the location doesn't change
-- update this if we got here with a lower G cost
if (g + open [which].h) < open [which].f then
DEBUG(string.format ("Amending %s to have G = %0.3f rather than %0.3f (F = %0.3f rather than %0.3f) and new parents %s",
which, g, open [which].g, g + open [which].h, open [which].f, parent))
open [which].g = g
open [which].f = g + open [which].h
open [which].parent = parent
end -- if
return open [which].f
end -- if already there
-- add it, compute H (unknown in this case)
local h = 0
open [which] = { loc = which, g = g, h = h , f = g + h, parent = parent }
DEBUG (string.format ("Adding node %s to the open list, g = %0.3f, h = %0.3f, f = %0.3f", which, g, h, g + h))
return open [which].f
end -- makeOpen
function isOpen (which)
return open [which]
end -- isOpen
-- add to closed list
function makeClosed (which)
closed [which] = open [which] -- copy values
open [which] = nil -- not in open list any more
explored_towns [which] = NODE_CLOSED -- closed
end -- makeClosed
function isClosed (which)
return closed [which]
end -- isOpen
function addNode (which, g, cost, parent)
assert (which ~= parent, "node cannot have itself as parent: " .. which)
if done then
return
end -- if done
-- see if we reached end
if which == finish then
done = true
paths = { }
table.insert (paths, { loc = finish } )
repeat
table.insert (paths, { loc = parent } )
parent = isClosed (parent) -- find its parent
if parent then
parent = parent.parent
end -- if
until parent == nil
return
end -- if
-- factor in land/water cost
makeOpen (which, cost, parent)
end -- addNode
local depth = 0
local count = 0
done = false
-- found path goes here
paths = {}
-- create particle for the initial town
addNode (start, 0, 0, nil) -- no g, no cost, no parent
while (not done) and next (open) and count < MAX_SEARCHES do
count = count + 1
-- find lowest scoring node in the open list
local fMin = 999999999
local gMin = 999999999
local minNode = nil
local openCount = 0
local closedCount = 0
for k, v in pairs (open) do
openCount = openCount + 1
if v.f < fMin then
fMin = v.f
minNode = v
gMin = v.g -- in case next one is equal, not less
elseif v.f == fMin then -- same f score, pick lower g score
if v.g < gMin then
gMin = v.g
minNode = v
end -- if
end -- if lower or same F score
end -- for
for k, v in pairs (closed) do
closedCount = closedCount + 1
end -- for
DEBUG (string.format ("%d nodes open, %d nodes closed", openCount, closedCount))
loc, g, h, f = minNode.loc, minNode.g, minNode.h, minNode.f
-- add this node to the closed list
makeClosed (loc)
DEBUG (string.rep ("-", 10))
DEBUG (string.format ("Selected node %s - put it on the closed list, g = %0.3f, h = %0.3f, f = %0.3f", loc, g, h, f))
DEBUG (string.rep ("-", 10))
for k, v in pairs (travel [loc]) do
-- calculate cost by adding in each speedwalk multiplier number (eg. 5n 6w would be a cost of 11)
cost = 0
for c in string.gmatch (v, "%d+") do
cost = cost + tonumber (c)
end -- for each number
DEBUG ("Adding", k, "path =", v, "cost =", cost)
if not isClosed (k) then
addNode (k, g, cost, loc, v)
end -- if
end -- for
DEBUG (string.format ("Iteration %d, cost = %0.1f", count, g))
end -- while more particles
if not next (paths) then
print ("No route from " .. start .. " to " .. finish .. " found.")
return nil
end -- it
ports = { }
routes = { }
-- calculate routes and ports
for i = #paths, 1, -1 do
local thisPort = paths [i].loc
table.insert (ports, thisPort)
if i > 1 then
table.insert (routes, travel [thisPort] [paths [i - 1].loc])
end -- if not destination
end -- for each route
return table.concat (routes, "; "), table.concat (ports, "/")
end -- function findPathsAstar
Test:
routes, ports = findPathsAstar ("rome", "glasgow")
print ("Routes = ", routes)
print ("Ports = ", ports)
Output:
Routes = do 60n; do 1n; do 4n
Ports = rome/paris/london/glasgow
However if you bump up the cost of travelling from rome to paris from 60 to 600, then the algorithm finds that going via newyork is faster:
Routes = do 500e; do 5w
Ports = rome/newyork/glasgow
And that is the improvement. It is taking the cost of each leg into account.
References
|