This forum is a read-only archive of the Gammon Software forum (2000–2026). No new posts can be made. Search the archive.

Linking tables.

Posted by Falgor on Thu 30 Apr 2020 01:30 PM — 8 posts, 34,065 views.

Falgor #0
Hi,

I've hit a wall trying to link tables together in order to chain aliases. I've managed to link table entries "2 deep" but it is a messy fix. I'm trying to create something that will run as deep as it needs to.

First, the table:


travel = {}

travel.paris =
{
 london = 'do 10n',
 rome = 'do 10s'
}

travel.london =
{
 paris = 'do 10s',
 glasgow = 'do 10n'
}

travel.glasgow =
{
 london = 'do 10s'
}

travel.rome =
{
paris = 'do 10n'
}


Looking at the table above, I want to be able to link two together to provide a chain of aliases.

Here is my code to figure out directions between two places.


  function get_dirs (start, finish)

        for k, v in pairs (travel[start]) do 
        if k == finish then return v end
        end   

    end -- end get_dirs

print(get_dirs("rome", "paris"))
--- do 10n




I've bastardised the code above to try and 'reach out' to find further directions, but i'm struggling to fathom the logic. What I want to achieve:

Glasgow - London = do 10s

Glasgow - Paris = do 10s ; do 10s

Rome - Glasgow = do 10n ; do 10n ; do 10n

Here is my code for getting deeper:


function get_dirs(start,finish)
  multi_path = {}
      for k, v in pairs (travel[start]) do
        if k == finish then table.insert(multi_path, v) end -- if
      end -- for
  if next(multi_path) == nil then multi_dirs(start,finish)
  else
  for k, v in pairs (multi_path) do
    print(v)
  end
  end
end -- get dirs

function multi_dirs (start, finish)
      for k, v in pairs (travel[start]) do
        local stop_off = k
          for k, v in pairs (travel[k]) do
            if k == finish then
            get_dirs(start, stop_off)
            get_dirs(stop_off, finish)
            end
          end
      end  
end -- multi_dirs


It's messy and only goes to the next location. What I would like to do is somehow search the whole 'travel' table and link values together based on the key names.

I have no idea where to start!

Thanks,

Falg.
Amended on Thu 30 Apr 2020 09:01 PM by Nick Gammon
Falgor #1
Update.

I've got some of the way, however I'd like to run this with a reccuring loop, rather than relying on if functions.

get_route - Runs some nested if functions to find the 'linking' values and returns them as values in a table.

convert_route - Interrogates route = {} and sends the correct names to get_dirs

get_dirs - Returns the directions required to link location.

My current issue is it's now working too well! Glasgow is next to London, but it is giving me the following get_dir(glasgow, london) -- glasgow-london-paris-rome-paris-london.... A bit of a long way round. Trying to figure out how to end the function from inside the loops. So far no luck with break, return, os.exit or goto.


function get_dirs (start, finish)

    for k, v in pairs (travel) do 
      -- Match start location
      if k == start then
        for k, v in pairs (travel[k]) do 
        -- Match end location
        if k == finish then return v end
        end   
      end
      current_area = finish
    end

    end -- end get_dirs

function convert_route ()
 i = 1

  for k, v in pairs (route) do
    local start = route[i]
    i = i + 1
    local finish = route[i]
    if get_dirs(start,finish) == nil then
    break
    else
    print(get_dirs(start,finish))
    end
  end
end -- end convert_route

function get_route(start,finish)

  route = {}

  for k, v in pairs (travel[start]) do

    if k == finish then
    route = {start, finish}
    print("STAGE ONE")
    convert_route()
    break
    else

      name = k
      for k, v in pairs (travel[name]) do

        if k == finish then
        route = {start, name, finish}
        print("STAGE TWO")
        convert_route()
        break
        else

          name_two = k
          for k, v in pairs (travel[name_two]) do

            if k == finish then
            route = {start, name, name_two, finish}
            print("STAGE THREE")
            convert_route()
            break
            else

              name_three = k
              for k, v in pairs (travel[name_three]) do

                if k == finish then 
                route = {start, name, name_two, name_three, finish}
                print("STAGE FOUR")
                convert_route()
                break
                else
                print("DIRECTIONS NOT FOUND")
                end
              end
            end
          end
        end
      end
    end
  end
end -- end get_route
Amended on Thu 30 Apr 2020 10:11 PM by Nick Gammon
Nick Gammon Australia Forum Administrator #2
Please use code tags, not quote tags for code. I amended your post.

Your method of finding the direction is kind-of strange. Lua tables are keyed, you don't have to search them for the key. Instead of:


  function get_dirs (start, finish)

    for k, v in pairs (travel[start]) do
      if k == finish then return v end
    end
  end -- end get_dirs


You can do this:


  function get_dirs (start, finish)
    return travel [start] [finish]
  end -- end get_dirs


In fact that is so short you hardly need a function call at all.

Anyway, to solve your larger problem, I adapted the room-finding algorithm in the mapper.

Maybe it's overkill but it seems to work.

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 6n'
}


Finding code:



require "copytable"

SCAN_DEPTH = 100

function find_paths (start, finish)

  local function make_particle (curr_loc, prev_path)
    local prev_path = prev_path or {}
    return {current_town=curr_loc, path=prev_path}
  end

  local depth = 0
  local done = false
  local explored_towns, particles = {}, {}

  -- this is where we collect found paths
  -- the table is keyed by destination, with paths as values
  local paths = {}

  -- create particle for the initial place
  table.insert (particles, make_particle (start))

  while (not done) and #particles > 0 and depth < SCAN_DEPTH do

    -- create a new generation of particles
    new_generation = {}
    depth = depth + 1

    -- process each active particle
    for i, part in ipairs (particles) do

      -- if town doesn't exist, forget it
      if travel [part.current_town] then

        -- get a list of destinations from the current town
        destinations = travel [part.current_town]

        -- create one new particle for each destination
        for dest, dir in pairs(destinations) do

          -- if we've been in this town before, drop it
          if not explored_towns[dest] then
            explored_towns[dest] = true
            if travel [dest] then
              new_path = copytable.deep (part.path)
              table.insert(new_path, { dir = dir, dest = dest } )

              -- if this town is wanted then save its path

              if dest == finish then
                done = true
                paths[dest] = new_path
              end -- if end town found

              -- make a new particle in the new town
              table.insert(new_generation, make_particle(dest, new_path))
            end -- if town exists
          end -- not explored this town
          if done then
            break
          end

        end  -- for each destination

      end -- if town exists

      if done then
        break
      end
    end  -- for each particle

    particles = new_generation
  end   -- while more particles

  if not next (paths) then
    print ("No route to", finish, "from", start, "found")
    return nil
  end -- it

  ports = { }
  routes = { }
  for k, v in ipairs (paths [finish]) do
    table.insert (ports, v.dest)
    table.insert (routes, v.dir)
  end -- for each route

  return table.concat (routes, "; "), table.concat (ports, "/")
end -- function find_paths


I changed your directions in the initial table to make it more obvious if it found the right route (eg. 1n, 2n, 3n and so on)

Basically what this code does is iterate out from the starting town, building up a route to the finishing town. Once the finishing town is found it stops, and reports the places you visit and the directions to get there. So for rome to glasgow I got:



routes, ports = find_paths ("rome", "glasgow")

print ("Routes = ", routes)
print ("Ports  = ", ports)


Result:


Routes = 	do 6n; do 1n; do 4n
Ports  = 	paris/london/glasgow


It returns nil if it can't find a route.
Amended on Thu 30 Apr 2020 10:22 PM by Nick Gammon
Nick Gammon Australia Forum Administrator #3
For glasgow to london I got:


routes, ports = find_paths ("glasgow", "london")

print ("Routes = ", routes)
print ("Ports  = ", ports)


Result:


Routes = 	do 5s
Ports  = 	london
Falgor #4
Nick, you are a genius!

Thank you so much, works perfectly.

Glad I was on totally the wrong track!

Nested if functions is never a good way to go.

Thank you.
Nick Gammon Australia Forum Administrator #5
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:

  1. Start with the starting town (call this the current town)
  2. Put the current town on the closed list (we won’t evaluate this one again)
  3. 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.

  4. 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.
  5. 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


Amended on Sat 02 May 2020 12:32 AM by Nick Gammon
Nick Gammon Australia Forum Administrator #6

You can see a rather cool demonstration of the A* algorithm in action, in a MUSHclient miniwindow, by downloading the Gist from GitHub: nickgammon/Path_Finder.xml.

Place all 3 files into your worlds/plugins folder. The file Path_Finder.xml is a plugin which you install using the plugins menu. The other two files are Lua files with the code in them.

Once installed it draws a random “map” with obstacles. The black boxes are “impassable land” and the blue ones are water, which takes longer to traverse.

It then selects a random starting and ending point and calculates a path, drawing each step.

In some cases if the start or ending point is inside impassable land, then no path will be drawn.

Type “draw” (in the command window) to draw a new random map. Then press Ctrl+R to repeat the last command and keep drawing new paths.

There is some configuration stuff in the code, you can get a larger window by playing with these variables, for example:

GRID_SIZE = 14
X_SIZE = 50
Y_SIZE = 50

Optimal values will depend on how big your screen is.

Amended on Sat 02 May 2020 06:38 AM by Nick Gammon
Falgor #7
Nick, you never cease to amaze me.

I'm going to have a play with it later tonight.

The A* method makes perfect sense in my head. It is what I was trying to articulate! I get two tables deep and my brain has a meltdown... I'm not smart enough for this coding lark!

Thanks!