SHARE
TWEET

Untitled

a guest Apr 1st, 2017 65 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. pathfinder = {}
  3.  
  4.  
  5. --~ minetest.get_content_id(name)
  6. --~ minetest.registered_nodes
  7. --~ minetest.get_name_from_content_id(id)
  8. --~ local ivm = a:index(pos.x, pos.y, pos.z)
  9. --~ local ivm = a:indexp(pos)
  10.  
  11. print("loading pathfinder")
  12. --local walkable = {}
  13.  
  14. --for name, node in pairs(minetest.registered_nodes) do
  15.     ----~ if node.walkable then
  16.         --local id = minetest.get_content_id(name)
  17.         --print(id, name)
  18.         ----~ table.insert(walkable, id)
  19.         --walkable[id] = name
  20.     ----~ end
  21. --end
  22. ----~ table.sort(walkable)
  23. --print(dump(walkable))
  24. local openSet = {}
  25. local closedSet = {}
  26.  
  27. local vm
  28. local a
  29. local data
  30.  
  31.  
  32. local function get_distance(start_index, end_index)
  33.     local start_pos = a:position(start_index)
  34.     local end_pos = a:position(end_index)
  35.  
  36.     local distX = math.abs(start_pos.x - end_pos.x)
  37.     local distZ = math.abs(start_pos.z - end_pos.z)
  38.  
  39.     if distX > distZ then
  40.         return 14 * distZ + 10 * (distX - distZ)
  41.     else
  42.         return 14 * distX + 10 * (distZ - distX)
  43.     end
  44. end
  45.  
  46. local function walkable(id)
  47.     local name = minetest.get_name_from_content_id(id)
  48.     print(dump(minetest.registered_nodes[name]))
  49.     if minetest.registered_nodes[name].walkable == false then
  50.         return false
  51.     else
  52.         return true
  53.     end
  54. end
  55.  
  56. function pathfinder.find_path(endpos, pos)
  57.     --~ local file = io.open("debug.txt", "w")
  58.     --~ io.output(file)
  59.     local radius = vector.distance(pos, endpos)
  60.     vm = VoxelManip()
  61.     local minp, maxp = vm:read_from_map(
  62.             vector.subtract(pos, {x=radius, y=16, z=radius}),
  63.             vector.add(pos, {x=radius, y=16, z=radius})
  64.     )
  65.     a = VoxelArea:new({MinEdge = minp, MaxEdge = maxp})
  66.     data = vm:get_data()
  67.  
  68.     local starttime = minetest.get_us_time()
  69.  
  70.     local start_index = a:indexp(pos)
  71.     local target_index = a:indexp(endpos)
  72.     local count = 1
  73.  
  74.     openSet = {}
  75.     closedSet = {}
  76.  
  77.     openSet[start_index] = {hCost = 0, gCost = 0, fCost = 0, parent = 0, pos = pos}
  78.  
  79.     repeat
  80.         local current_index
  81.         local current_values
  82.         for i, v in pairs(openSet) do
  83.             current_index = i
  84.             current_values = v
  85.             break
  86.         end
  87.         for i, v in pairs(openSet) do
  88.             if v.fCost < openSet[current_index].fCost or v.fCost == current_values.fCost and v.hCost < current_values.hCost then
  89.                 current_index = i
  90.                 current_values = v
  91.             end
  92.         end
  93.  
  94.         openSet[current_index] = nil
  95.         closedSet[current_index] = current_values
  96.         count = count - 1
  97.     local mem = math.floor(collectgarbage("count")/1024)
  98.     if mem > 500 then
  99.         print("Manually collecting garbage...")
  100.         collectgarbage("collect")
  101.     end
  102.         if current_index == target_index then
  103.             print("Success")
  104.             local path = {}
  105.             local file = io.open("debug.txt", "w")
  106.             io.output(file)
  107.             io.write(start_index.." "..target_index)
  108.             io.write(dump(closedSet))
  109.             io.close(file)
  110.             repeat
  111.                 table.insert(path, a:position(closedSet[current_index].parent))
  112.                 current_index = closedSet[current_index].parent
  113.             until start_index == current_index
  114.  
  115.             print("Pathfinder: "..(minetest.get_us_time() - starttime) / 1000)
  116.             openSet = nil
  117.             closedSet = nil
  118.  
  119.  
  120.             return path
  121.         end
  122.  
  123.         local current_pos = a:position(current_index)
  124.         --~ minetest.set_node(current_pos, {name = "default:dry_shrub"})
  125.  
  126.  
  127.         for neighbor in a:iterp({x = current_pos.x - 1, y = current_pos.y, z = current_pos.z - 1},
  128.                 {x = current_pos.x + 1, y = current_pos.y, z = current_pos.z + 1}) do
  129.             local nodename = minetest.get_name_from_content_id(data[neighbor])
  130.             --~ print(nodename, data[neighbor])
  131.             if nodename == "default:dry_shrub" then
  132.                 print(walkable[data[neighbor]])
  133.             end
  134.             if neighbor ~= current_index and neighbor ~= closedSet[neighbor] and not walkable(data[neighbor]) then
  135.                 local move_cost_to_neighbor = current_values.gCost + get_distance(current_index, neighbor)
  136.                 local gCost = 0
  137.                 if openSet[neighbor] then
  138.                     gCost = openSet[neighbor].gCost
  139.                 end
  140.                 if move_cost_to_neighbor < gCost or not openSet[neighbor] then
  141.                     local hCost = get_distance(neighbor, target_index)
  142.                     openSet[neighbor] = {
  143.                             gCost = move_cost_to_neighbor,
  144.                             hCost = hCost,
  145.                             fCost = move_cost_to_neighbor + hCost,
  146.                             parent = current_index,
  147.                             pos = a:position(neighbor)
  148.                     }
  149.                     count = count + 1
  150.                 end
  151.             end
  152.             --~ io.write(neighbor, dump(a:position(neighbor)))
  153.         end
  154.         --~ io.write(dump(parent))
  155.         if count > 10000 then
  156.             print("fail")
  157.             return
  158.         end
  159.     until count < 1
  160.     --~ io.close(file)
  161.     return
  162. end
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top