dumb notes on finding more pathier paths

Hi I don't know. Some pathfinding thing has been on my mind. This might be mostly dumb, or at least it's dumb enough that I can kind of understand each part of it. Anyway some notes in case I wanna remember it later...

"""problem statement"""

Maybe think of a turn based strategy game or something. If we're using something like Dijkstra's algorithm on something like a tilemap we tend to get one of the good paths between two positions. (Good meaning it has the lowest possible total movement cost.)

In these examples the movement cost rules are fairly simple:

It can be the case that a lot of different paths from one position to another are equally good. E.g. we could be moving to the east and a little to the northeast like this:

            o
           o
          o
oooooooooo
10 moves to the west followed by 3 moves to the northwest

And another path might cost the same:

          ooo
       ooo
   oooo
ooo
3 west, 1 northwest, 4 west, 1 northwest, 3 west, 1 northwest, 3 west

In my experience, if I code something up I'm likely to end up with code that picks paths more like the first one. Like maybe it tries directions in a certain order when searching so it does either all the orthogonal movement or all the diagonal movement first. Anyway what's been on my mind has to do with how to choose paths that look more like the second one. I guess that one looks less "artifical" or something to me, maybe more like how I'd go if I was making the moves by hand.

filling a map

The more dijkstrian code is at the bottom of the post. I won't get into details here, but it's similar to the stuff in the Advent of Dijkstra post.

Here are some maps:

oneroom =
[[
###############################################
#                             E               #
#                                             #
#                                             #
# S                                           #
###############################################
]]

largerooms =
[[
###############################################
#                                             #
# #####################                       #
#                     #                       #
#                     #                       #
#                     #                     E #
####################  #########################
#                                             #
#                                             #
#                                             #
# S                                           #
###############################################
]]

complicated = [[
###################################
#  #     #         #        #     #
####     #########   ######   #   #
#    #    #      #####    ######  #
# S  #        #        ##         #
########## ##### ##################
#   #      #   #        #   #     #
# ###      # # #        # # # #   #
# #        # # #          # E #   #
###        ### ################   #
#                                 #
###################################
]]

We can kind of Dikjstra-flood-fill a map from its S and then show the result in a kind of heatmappy way:

function reachable(str)
  local map = mappy(str)
  local q = flood(map, next(map.S))
  local function heat(c, p)
    local seen = q.seen[p]
    if not seen then return c end
    c = c == " " and "." or c
    return span(c, heatstyle(seen.cost, q.highest))
  end
  web.html(maphtml(map, heat))
end
reachable(oneroom)
reachable(largerooms)
reachable(complicated)

Every reachable position gets a colour :)

It'd also be possible to stop filling when reaching a certain movement cost or something? But here we're just filling the entire map.

finding just any old path

The data structure we get from the flood function also has information about how we got to each position. The result from looking up a reachable position will contain a from table with directions and positions. A way to find a path to a position is to start with that position and then use those from tables to step back toward the start position:

function stepback(p, fill)
    local seen = fill[p]
    if not seen then return nil end
    for _, d in ipairs(dirs) do
      if seen.from[d] then return seen.from[d] end
    end
    return nil
end

function steppy(str, stepback)
  local map = mappy(str)
  local start, stop = next(map.S), next(map.E)
  local q = flood(map, start)
  local path = { [stop] = true }
  local p = stepback(stop, q.seen, start)
  while p do
    path[p] = true
    p = stepback(p, q.seen, start)
  end
  local function drawpath(c, p)
    return path[p] and c == " " and "o" or c
  end
  web.html(maphtml(map, drawpath))
end

We can find a path for each map:

steppy(oneroom, stepback)
steppy(largerooms, stepback)
steppy(complicated, stepback)

This does the thing where it attempts orthogonal movement before diagonal movement. It's more noticable in the less complicated maps. Okay.

rectangles

Given a start and a stop position, we can find all the positions we can possibly visit by following one of the good paths. After flood filling and choosing a stop position, we can kind of flood fill back to the start position through all the from values:

function fillback(fill, p)
  local set, visited = { [p] = true }, { [p] = true }
  while next(set) do
    local p = next(set)
    set[p] = nil
    local seen = fill[p]
    for _, d in ipairs(dirs) do
      local from = seen.from[d]
      if from and not visited[from] then
        set[from] = true
        visited[from] = true
      end
    end
  end
  return visited
end

function possiblepositions(str)
  local map = mappy(str)
  local start, stop = next(map.S), next(map.E)
  local q = flood(map, start)
  local back = fillback(q.seen, stop)
  local function heat(c, p)
    if not back[p] then return c end
    local seen = q.seen[p]
    c = c == " " and "." or c
    return span(c, heatstyle(seen.cost, q.highest))
  end
  web.html(maphtml(map, heat))
end

Let's take a look:

possiblepositions(oneroom)
possiblepositions(largerooms)
possiblepositions(complicated)

So we get these almost-rectangular areas where each position is visited by at least one good path. Those are the areas where I'd maybe like to choose paths differently. Like within such a rectangle, maybe have the path be more like a line between opposite corners.

lines

From the Wikipedia article on Bresenham's line algorithm:

y1 - y0 y = (x - x0) + y0 x1 - x0
An equation: y = ((y1 - y0) / (x1 - x0)) (x - x0) + y0

Here's a function that calculates how far off we are:

function off(from, to, p)
  local fx, fy, tx, ty, x, y, dx, dy
  local d = to - from
  if math.abs(d.x) >= math.abs(d.y) then
    fx, fy, tx, ty, x, y, dx, dy = from.x, from.y, to.x, to.y, p.x, p.y, d.x, d.y
  else
    fx, fy, tx, ty, x, y, dx, dy = from.y, from.x, to.y, to.x, p.y, p.x, d.y, d.x
  end
  local target
  if dx == 0 then target = fy
  elseif fx == x then target = fy
  else target = fy + (((x - fx) * dy + (dx // 2)) // dx)
  end
  return math.abs(y - target)
end

Uh, um, uuh, if we imagine a line between two points, from and to, then this should give us the number of steps away from the line a position is. It rotates some numbers around a bit to account for lines that are more vertical vs. lines that are more horizontal. Like if the line is more horizontal the steps will be along the y-axis but if it's more vertical they will be along the x-axis. Uuuh, I'm not very good at this, but it does seem to work I think?

local from, to = vec(0, 0), vec(8, 3)
for y = 0, 3 do
  for x = 0, 8 do
    io.write(off(from, to, vec(x, y)))
  end
  io.write("\n")
end

That's like a line of zeroes.

Anyway the idea is something like: If we're trying to move along some line and we have some possible positions for the next step, we can choose the one with the lowest off-number.

super-low-effort rectangle detection

I don't wanna deal with stuff. Let's just shoot a ray in each of the 4 main directions, maybe that's good enough.

local function shoot(p, dir, back)
  local prev = p
  while back[p] do
    prev = p
    p = p + dir
  end
  return prev
end

function rect(p, back)
  return
    shoot(p, N, back).y,
    shoot(p, E, back).x,
    shoot(p, S, back).y,
    shoot(p, W, back).x
end

function showrect(str, pos)
  local map = mappy(str)
  local start, stop = next(map.S), next(map.E)
  local q = flood(map, start)
  local back = fillback(q.seen, stop)
  local n, e, s, w = rect(pos, back)
  local function within(p)
    return p.y >= n and p.y <= s and p.x >= w and p.x <= e
  end
  local function heat(c, p)
    if not within(p) then return p == pos and "X" or c end
    local cost = (p == pos or not q.seen[p]) and q.highest or q.seen[p].cost
    c =
      (p == pos and "X")
      or (c == " " and ".")
      or c
    return span(c, heatstyle(cost, q.highest))
  end
  web.html(maphtml(map, heat))
end

Let's take a look:

possiblepositions(largerooms)
showrect(largerooms, vec(4, 11))
showrect(largerooms, vec(7, 10))
showrect(largerooms, vec(10, 2))
showrect(largerooms, vec(30, 2))
showrect(largerooms, vec(30, 3))

In some positions the rectangles seem pretty okay but in others they aren't exactly the ones we're after. We're only using them to choose between paths that are all good though. So it's not like using a weird rectangle for a few steps will make us choose a bad path. I dunno, it's maybe okay.

uh, let's go

Okay so: We use the fillback function from earlier to get like a pretend map that might have rectangles in it. And then when we're constructing the path and are stepping from one position to the next (or previous, I guess), we look into some things:

The rectback function puts the stuff together. It's a large function because it does a bunch of direction checking in a repetitive and maybe kind of dumb way.

function rectback()
  local back
  return function(p, fill)
    if not back then back = fillback(fill, p) end
    local seen = fill[p]
    if not seen then return nil end
    local from = seen.from
    if seen.dirs ~= 2 then return stepback(p, fill) end
    local n, e, s, w = rect(p, back)
    local start, stop
    local d1, d2
    if from[W] and from[NW] then
      d1, d2 = W, NW
      start, stop = vec(e, s), vec(w, n)
    elseif from[N] and from[NW] then
      d1, d2 = N, NW
      start, stop = vec(e, s), vec(w, n)
    elseif from[N] and from[NE] then
      d1, d2 = N, NE
      start, stop = vec(w, s), vec(e, n)
    elseif from[E] and from[NE] then
      d1, d2 = E, NE
      start, stop = vec(w, s), vec(e, n)
    elseif from[E] and from[SE] then
      d1, d2 = E, SE
      start, stop = vec(w, n), vec(e, s)
    elseif from[S] and from[SE] then
      d1, d2 = S, SE
      start, stop = vec(w, n), vec(e, s)
    elseif from[S] and from[SW] then
      d1, d2 = S, SW
      start, stop = vec(e, n), vec(w, s)
    elseif from[E] and from[SW] then
      d1, d2 = E, SW
      start, stop = vec(e, n), vec(w, s)
    else return stepback(p, fill)
    end
    local p1, p2 = from[d1], from[d2]
    return (off(start, stop, p1) <= off(start, stop, p2)) and p1 or p2
  end
end
steppy(oneroom, rectback())
steppy(largerooms, rectback())
steppy(complicated, rectback())

Bla blah. I think those paths are okay :)

Final REPL for playing around with the map and comparing the paths:

local str = [[
###############################################
#                                             #
# ############# #######                       #
#                     #                       #
#                     #                       #
#                     #                       #
#                     #                       #
#                     #                       #
#                     #                       #
#                     #                       #
#                     #                       #
#                     #    E                  #
####################  #########################
#                                             #
#                                             #
#                                             #
# S                                           #
###############################################
]]
steppy(str, rectback())
steppy(str, stepback)

appendix: the dijkstrarian flood fill and stuf

function memo(key, new)
  local all = setmetatable({}, { __mode = "v" })
  return function(...)
    local k = key(...)
    local found = all[k]
    if found then return found end
    local v = new(...)
    all[k] = v
    return v
  end
end

Vec = {}
vec = memo(
  function(x, y) return x .. "," .. y end,
  function(x, y) return setmetatable({ x = x, y = y }, Vec) end)

function Vec.__add(a, b) return vec(a.x + b.x, a.y + b.y) end
function Vec.__sub(a, b) return vec(a.x - b.x, a.y - b.y) end
N, E, S, W = vec(0, -1), vec(1, 0), vec(0, 1), vec(-1, 0)
NW, NE, SE, SW = N + W, N + E, S + E, S + W
function Vec.__tostring(v) return v.x .. "," .. v.y end
dirs = { NW, NE, SE, SW, N, E, S, W }

Lazy = {}
function Lazy.__index(t, k)
  local list = {}
  t[k] = list
  return list
end

Queue = {}
Queue.__index = Queue
function Queue.new()
    local q = {
        highest = 0,
        lowest = 0,
        seen = {},
        lists = setmetatable({}, Lazy)
    }
    setmetatable(q, Queue)
    return q
end

function Queue.put(q, pos, cost, dir, from)
  local seen = q.seen[pos]
  if seen then
    if seen.cost == cost then
      seen.from[dir] = from
      seen.dirs = seen.dirs + 1
      return
    elseif seen.cost < cost then
      return
    end
    local prev = q.lists[seen.cost]
    local current = prev.next
    while current do
      if current.pos == pos then
        prev.next = current.next
        break
      end
      local next = current.next
      prev = current
      current = next
    end
  end
  q.seen[pos] = { cost = cost, from = dir and { [dir] = from } or {}, dirs = dir and 1 or 0 }
  q.lists[cost].next = { pos = pos, next = q.lists[cost].next }
  q.highest = math.max(q.highest, cost)
end

function Queue.get(q)
  local i = q.lowest
  for i = q.lowest, q.highest do
    local list = q.lists[i]
    if list.next then
      local entry = list.next
       list.next = entry.next
       local pos = entry.pos
       q.lowest = i
       return pos, i
    end
  end
end

function mappy(str)
  local lines = str:gmatch("[^\n]+")
  local map = {}
  local y = 0
  local w = 0
  for line in lines do
    y = y + 1
    local x = 0
    for c in line:gmatch(".") do
      x = x + 1
      local v = vec(x, y)
      if c == "#" then
        map[v] = c
      end
      local set = map[c] or {}
      set[v] = true
      map[c] = set
    end
    w = math.max(w, x)
  end
  map.size = vec(w, y)
  return map
end

function maphtml(map, f)
  local html = { '<pre><code>' }
  for y = 1, map.size.y do
    for x = 1, map.size.x do
      local p = vec(x, y)
      local c =
        (map.S[p] and 'S')
        or (map.E[p] and 'E')
        or map[p] or ' '
      html[#html + 1] = f and f(c, p) or c
    end
    html[#html + 1] = '\n'
  end
  return table.concat(html)
end

function neighbours(p, map)
  local i = 1
  local cost = 3
  return function()
    while i <= 8 do
      local dir = dirs[i]
      local np = p + dir
      if i == 5 then cost = 2 end
      i = i + 1
      if
        np.x > 0 and np.x <= map.size.x
        and np.y > 0 and np.y <= map.size.y
        and not map[np]
      then return np, cost, dir
      end
    end
    return nil
  end
end

function step(map, q)
  local p, cost = q:get()
  if not p then return false end
  for np, c, dir in neighbours(p, map) do
    q:put(np, cost + c, dir, p)
  end
  return true
end

function flood(map, start)
  local q = Queue.new()
  q:put(start, 0)
  local current = true
  while current do current = step(map, q, stop) end
  return q
end

function span(str, style)
  return '<span style="' .. style .. '">' .. str .. '</span>'
end

function heatstyle(n, max)
  local h = (1 - (n / max)) * 240
  return 'background-color: hsl(' .. h .. ', 100%, 50%)'
end