Pathfinding Logic

I've been thinking about it for a while and I was wondering if someone with the knowledge could run though the logic for 2D and 3D pathfinding, assuming the computer working out the path had a map of the area,
eg
map1 = [[###xxx
##xxxx
#xx###
#x###x
#xxxxx
######]]

for a 2d map
(which would represent this:
# # # x x x
# # x x x x
# x x # # #
# x # # # x
# x x x x x
# # # # # #
)

the only way i could think of is having already mapped an area run a series of recursive path-finding algorithms to find the shortest way to get there

how i think of it is check if point A and point B can directly be accessed , if it cant, find an area that has the most open area to get closer , and then run itself to find a way to that point .

so you would need to recursively call a function that can get it closer to point B , and every time it runs point "B" is moving closer untill the path is found.
then theirs the return value , witch i think would best be created by a series of return a table of moves into a table or return the entire contents of that table using lua's ability to return multiple things at once

all in all its a huge thing to tackle , but not impossible.
though if u want them to auto map it gets exponentially harder lol.

edit :

just thought of another posible way
run the map though a loop finding all open areas with 2 or more space and return those positions for each direction then do a simmilar thing to what i mentioned above but on existing paths finding all that it can take , then find the shortest

A form of Dijkstra's algorithm would probably be the best and easiest way of doing this.
A* is a varient of the Dijkstra algorithm and is the one commonly used in game senses.

These are for the most part the quickest and most efficient, all you need is the map, and what is flagged as a "no go", then the algorithm would find the "cheapest" way, or the shortest way, to the target.

Have a read of the 2 links provided to get a greater understanding of them and I'm sure if you are unable to figure them out for yourself there should be an implementation somewhere that you can modify to work with a turtle. :)/>

This is the simplest example of pathfinding I know how to make. A* and dijkstra's algorithm are extensions of this basic model; this has been simplified based on the fact that the distance between "nodes" in a simple 2d map which does not allow diagonal movement is always 1.

--a simple map, 1s are walls/barriers and 0s are open space
local map={
  {  0,0,1,0,0,0, },
  {  0,0,1,0,1,1, },
  {  0,0,1,0,0,0, },
  {  0,0,1,1,1,0, },
  {  0,0,0,0,0,0, },
}
--dimensions of map
local mapWidth, mapHeight=6,5
 
--the starting position to find a path from
local start={x=1,y=1}
--the goal position you're trying to path to
local goal={x=6,y=1}
--an array of "open" nodes - these are nodes that have not been checked. We initialize it to include just the start position.
local open={start}
--this table will be a map of "closed" nodes - nodes that have already been checked. It is initially empty.
local closed={}
 
--function to take a position and turn it into a unique index
local function toindex(pos)
  --x+y*width gives a unique number for each x,y pair
  return pos.x+pos.y*mapWidth
end
 
--convenience table, directions we can go and the resulting offsets in the map
local directions={
  north = {x= 0, y=-1},
  south = {x= 0, y= 1},
  east =  {x= 1, y= 0},
  west =  {x=-1, y= 0},
}
--var to tell if we found the goal
local foundGoal=false
--loop while the open list is not empty
while #open>0 do
  --remove the first open node on the list and put it in curNode
  local curNode=table.remove(open,1)
  --build the index for this node, for use later
  local curIndex=toindex(curNode)
  --now go through each possible direction
  for dir,offset in pairs(directions) do
    --generate the position by adding offset to curNode
    local target={
	  x = curNode.x+offset.x,
	  y = curNode.y+offset.y
    }
   
    --is this our goal?
    if target.x==goal.x and target.y==goal.y then
	  --it is the goal! set foundGoal, add to closed, and break
	  foundGoal=true
	  closed[ toindex(target) ] = { dir=dir, prevIndex=curIndex }
	  break
    end
    --is this node valid, i.e., within the map bounds and not blocked?
    if target.x>0 and target.x<=mapWidth and
	   target.y>0 and target.y<=mapHeight and
	   map[target.y][target.x]==0 then
	  --generate the index for this position
	  local index=toindex(target)
   
	  --is it in the closed list already?
	  if closed[index]==nil then
	    --it is not. Add it to closed, key is index, for value we will store the direction that got it here and the index of the position we came from
	    closed[index]={dir=dir, prevIndex=curIndex}
	    --append it to the end of open
	    table.insert(open,target)
	  end
    end
  end
 
  --exited the for loop, did we find the goal?
  if foundGoal then
    --yawp, break out of the while loop too
    break
  end
end
 
--ok! did we find the goal?
if foundGoal then
  --we did! now we need to crawl back through our closed table to build the path
  --start at the end index
  local index=toindex(goal)
  --make our start index as well
  local startIndex=toindex(start)
  --make new table to hold the path
  local path={}
  --loop until we hit the goal
  repeat
    local node=closed[index]
    --move index to the node that led here
    index=node.prevIndex
    --add the direction to the START of our list
    table.insert(path,1,node.dir)
  --stop repeating when the next index is the start, as we're done
  until index==startIndex
  --now loop over that path!
  for i=1,#path do
    print(path[i])
  end 
else
  --didn't find the goal
  print("Path couldn't be found!")
end

pastebin: Zy466Kyy
Note that for very large maps, this algorithm may take a long time, and you may need to add a sleep() at the end of the main while() loop to prevent being terminated for not yielding. Turning the final list of directions or positions into an actual series of turtle movement commands will still take a bit of work, unless you're using a higher-level turtle api like turtlex that allows movement based on compass directions.

I'd like to note that using Dijkstra's algorithm or A* would be overkill here. Since turtles move over a 3D grid and all moves cost the same amout of fuel, the problem is reduced to finding the shortest path over a weighted graph with all weights being equal. That's efficiently solved using a breadth-first search of the map. The other algorithms would be more complicated to implement.

kamikazekiwi3: Generally correct, if you note my algorithm assumes fixed edge lengths and avoids dealing with distances by adding to the end of the open list and searching from the beginning, so it always searches the shortest path first, making it a variation of dijkstra that assumes constant edge length. Heuristics from a* could still be added, however, and the ordering of the open list altered to be sorted by the sum of the distance traveled so far and the minimum distance to target from there, which would be worthwhile if the maps being searched were much larger than 10x10, or if 3d maps were being searched. This would require also storing the distance cost of each node in both the open and closed lists, and when encountering a closed node, checking if the new cost is less than the old and, if so, re-opening the node with the new cost.

Looks really good, thanks for the help
But why does x*y*width give a unique value?
Surely (3,4) would be the same as (4,3) ?

kylergs, on 05 February 2013 - 07:30 AM said:

Looks really good, thanks for the help
But why does x*y*width give a unique value?
Surely (3,4) would be the same as (4,3) ?

That should probably be:

y*width + x

Which basically is the index if you would count every spot of every row in the raster until you're at that spot.

Edit: I actually looked at the code, it is that. You copied it wrong. But you have my explanation anyway. :P/>

what orwell said. Think it through, it'll make sense.

Suppose a 4x4 map:
0101
0000
0101
0000

1,1 is the top left, and gives 1*4+1==5
going right, we get
1,2 == 1*4+2 == 6
1,3 == 1*4+3 == 7
1,4 == 1*4+4 == 8
2,1 == 2*4+1 == 9

etc.

This is a very standard way to treat a one-dimensional array as if it were a 2-dimensional array. With arrays that begin with 0 instead of 1 (like in c or java, rather than lua), the indexes would go from 0 to width*height-1, rather than starting from width+1, but it didn't seem worth fixing since I was not actually making a 1d array, just a map of keys to values, I didn't bother correcting. To generate indices to a valid 1d lua array, you'd actually want to use x+(y-1)*width. </tmi>

Thanks, i misread it :)/>

Just got a chance to go through the code in detail, man that's some cool stuff, thanks for the help!

But the thing that gets me is this line:
closed[index]={dir=dir, prevIndex=curIndex}

Why the "dir=dir" and "prevIndex=curIndex" ?

Edit: I get it!

So closed[index].dir = dir and closed[index].prevIndex = curIndex

Is that right?

​Also, do you mind if I gut it and turn it into an API, (not for release of course!)

yes, that's right, and feel free to make it into an api. And by all means, release it too, if you want, I'm not bothered. Any code I post in AaP should be considered public domain :)/>

Haha, if I did I would improve it to handle 3D maps as well, thanks for the help, it was great seeing it in a language I understand

I saw this topic a while ago, I had looked into pathfinding in the past but I was a Lua n00b back then and gave up :)/> I have written my own since then and thought I would post it here. it is fairly messy and takes longer to run than the average pathfinder because it checks literally every possible path. I came and compared it to gophers and found it was very similar except every path had its own closed table

local function fPath(map)
local mt={__call=function(self,x,y)
  for k,v in pairs(self) do if v.x==x and v.y==y then return true end end
  return false
end}
local tDirs={{x=1,y=0,n="r"},{x=-1,y=0,n="l"},{x=0,y=1,n="d"},{x=0,y=-1,n="u"}}
local tPaths={{x=1,y=1,path="",checked=setmetatable({},mt)}}
local results={}
local function render(x,y)
  term.clear()
  for y,sLine in pairs(map) do
   term.setCursorPos(1,y)
   write(string.gsub(sLine," ","."))
  end
  term.setCursorPos(x,y)
  write("*")
end
local function tCopy(t)
  local res={}
  for k,v in pairs(t) do
   res[k]=v
  end
  return res
end
while tPaths[1] do
  if tPaths[1].x==10 and tPaths[1].y==1 then
   table.insert(results,tPaths[1].path)
  else
   for num,dir in pairs(tDirs) do
    if not tPaths[1].checked(tPaths[1].x+dir.x,tPaths[1].y+dir.y) and map(tPaths[1].x+dir.x,tPaths[1].y+dir.y)==" " then
	 table.insert(tPaths,2,{x=tPaths[1].x+dir.x,y=tPaths[1].y+dir.y,path=tPaths[1].path..dir.n,checked=setmetatable(tCopy(tPaths[1].checked),mt)})
	 table.insert(tPaths[2].checked,{x=tPaths[1].x+dir.x,y=tPaths[1].y+dir.y})
	 --print(tPaths[1].x+dir.x..", "..tPaths[1].y+dir.y)
	 render(tPaths[1].x+dir.x,tPaths[1].y+dir.y)
    end
   end
  end
  table.remove(tPaths,1)
  sleep(0)
end
local min=#results[1]
for k,v in pairs(results) do
  if #v<min then min=#v end
end
for i=1,#results do
  if #results[i]>min then
   results[i]=nil
  end
end
table.sort(results)
return results
end
local tMap=setmetatable({
" ######## ",
"	    # ",
" ## ##### ",
" ## #	 ",
" ## # ####",
" ## #	 ",
" ## ##### ",
"	    # ",
" ##### ## ",
"		  "
},{__call=function(self,x,y)
if self[y] and x<=#self[y] then
  return string.sub(self[y],x,x)
end
end})
local res=fPath(tMap)
term.clear()
term.setCursorPos(1,1)
for k,v in pairs(res) do
print(v)
end

well I came up with a much better method which finds the best path in the fastest way with the least code :)/>

the fastest system generally just tries to move towards the target but this can be easily fooled with a dead-end or even just a corner, you need a thorough system to get past these. I combined the two

basically it travels towards the target and if it cannot move towards the target then it tries all other directions, if it cannot move in those directions then it goes backward until it can go in another direction. pretty intelligent I think :)/>

now I just need a turtle mapper turtle :P/>

EDIT: I found a major bug in the pathfinder and have corrected it. here is the code

local tMap=setmetatable({
"01000000000000000101",
"01000000000000000101",
"01111100000000000101",
"00000111111111000101",
"11110110000001000101",
"00000110111101000101",
"01111110001101000101",
"01000011101101000101",
"01000000101101000101",
"01111111101101000101",
"00000000001101000101",
"11111111111101111101",
"00000000000100001101",
"00000000000101111101",
"00000000000101111101",
"00000000000100000001",
"00000000000111111111"
},{__call=function(self,x,y)
  if self[y] and x<=#self[y] then
   return string.sub(self[y],x,x)
  end
end})
local function fPath(map,targx,targy)
  --[VARS]
  local path={x=1,y=1,""}
  local target={x=targx or 1,y=targy or 1}
  local displacement=setmetatable({},{__index=function(self,index) if path[index] and target[index] then return path[index]-target[index] end end,__newindex=function() return nil end})
  local checked=setmetatable({{x=1,y=1}},{__call=function(self,x,y) for k,v in pairs(self) do if v.x==x and v.y==y then return true end end return false end})
  local directions_mt={__index=function(self,index) if index=="x" or index=="y" then return 0 end end}
  local directions=setmetatable({{x=1,"r"},{x=-1,"l"},{y=1,"d"},{y=-1,"u"}},{__call=function(self,direction)
   if direction then
	for k,v in pairs(self) do
	 if v[1]==direction then
	  return v
	 end
	end
   else
	local x
	local y
	for k,v in pairs(self) do
	 if (displacement.x>0 and v.x<0) or (displacement.x<0 and v.x>0) then
	  x=v
	 elseif (displacement.y>0 and v.y<0) or (displacement.y<0 and v.y>0) then
	  y=v
	 end
	end
	return x,y
   end
  end})
  for k,v in pairs(directions) do setmetatable(v,directions_mt) end
  --[FUNCTIONS]
  local render=function()
   term.clear()
   for k,v in pairs(map) do
	term.setCursorPos(1,k)
	print(string.gsub(string.gsub(v,"0","."),"1","#"))
   end
   print(path.x..", "..path.y)
   term.setCursorPos(path.x,path.y)
   write("*")
  end
  --[EXECUTION]
  while true do
   local x,y=directions()
   if x and map(path.x+x.x,path.y)=="0" and not checked(path.x+x.x,path.y) then
	path.x=path.x+x.x
	path[1]=path[1]..x[1]
	table.insert(checked,{x=path.x,y=path.y})
   elseif y and map(path.x,path.y+y.y)=="0" and not checked(path.x,path.y+y.y) then
	path.y=path.y+y.y
	path[1]=path[1]..y[1]
	table.insert(checked,{x=path.x,y=path.y})
   else
	local moved=false
	for k,v in pairs(directions) do
	 if v~=x and v~=y and map(path.x+v.x,path.y+v.y)=="0" and not checked(path.x+v.x,path.y+v.y) then
	  moved=true
	  path.x=path.x+v.x
	  path.y=path.y+v.y
	  path[1]=path[1]..v[1]
	  table.insert(checked,{x=path.x,y=path.y})
	  break
	 end
	end
	if not moved then
	 if path.x==1 and path.y==1 then
	  term.clear()
	  term.setCursorPos(1,1)
	  print("no way to get to target...")
	  break
	 end
	 path.x=path.x-directions(string.sub(path[1],-1)).x
	 path.y=path.y-directions(string.sub(path[1],-1)).y
	 path[1]=string.sub(path[1],1,-2)
	end
   end
   term.setCursorPos(1,12)
   if path.x==target.x and path.y==target.y then
	term.clear()
	term.setCursorPos(1,1)
	print("target found, path:")
	print(path[1])
	break
   end
   sleep(0)
   render()
  end
end
fPath(tMap,19,1)

EDIT2: I have made a 3d pathfinder as well, it is in my programs and utils post in my sig

kamikazekiwi3, on 05 February 2013 - 06:55 AM said:

I'd like to note that using Dijkstra's algorithm or A* would be overkill here. Since turtles move over a 3D grid and all moves cost the same amout of fuel, the problem is reduced to finding the shortest path over a weighted graph with all weights being equal. That's efficiently solved using a breadth-first search of the map. The other algorithms would be more complicated to implement.

If you were to have a large "highway" and some "streets" (aka, some tunnels and some larger tunnels) set up in your base, you could use A* or a similar pathfinding algorithm for it to help it decide which tunnel to go through to reach a certain place the fastest. In fact, I've already made one that I'm using for a program that I'm working on. It uses multiple files though, so here's a link to an installer for it:
http://pastebin.com/dcicx1yZ

Edit: Does anyone have a quick, non-recursive table copying function?

TehPers, on 07 February 2013 - 07:07 PM said:

kamikazekiwi3, on 05 February 2013 - 06:55 AM said:

I'd like to note that using Dijkstra's algorithm or A* would be overkill here. Since turtles move over a 3D grid and all moves cost the same amout of fuel, the problem is reduced to finding the shortest path over a weighted graph with all weights being equal. That's efficiently solved using a breadth-first search of the map. The other algorithms would be more complicated to implement.

If you were to have a large "highway" and some "streets" (aka, some tunnels and some larger tunnels) set up in your base, you could use A* or a similar pathfinding algorithm for it to help it decide which tunnel to go through to reach a certain place the fastest.

Exactly, that is a perfect example of where A* becomes VERY useful, sure kamikazekiwi3 it is pointless in an open area, and yes all nodes have the same costs with distance, BUT sometimes the paths effect the overall movement, which is where A* really comes in.

TehPers, on 07 February 2013 - 07:07 PM said:

Edit: Does anyone have a quick, non-recursive table copying function?

Is there tables inside the table? If so it can't be done properly without recursion.

sure it can.

local function deepCopy(old)
  local new={}
  local copyStack={ {old,new} }
  local tableCopies={}
  tableCopies[old]=new
 
  while #copyStack>0 do
    local copy=table.remove(copyStack,1)
    for k,v in pairs(copy[1]) do
	  if type(v)=="table" then
	    if tableCopies[v] then
		  copy[2][k]=tableCopies[v]
	    else
		  local t={}
		  copy[2][k]=t
		  copyStack[#copyStack+1]={v,t}
		  tableCopies[v]=t
	    end
	  else
	    copy[2][k]=v
	  end
    end
  end
  return new
end

note that this doesn't handle circular tables, though.
now it does.