pathfinding A* Algorythm compatable with OpenComputers robot movements

[cadergator10 1]

Hello, its me again... yes, I'm back... yes, I sure love filling up the feed...

I really wanted pathfinding for my program, so I found a simple LUA pathfinding script online and modified it to fit OpenComputers.

This is where I found the script https://github.com/wesleywerner/lua-star

This is the modified script: https://pastebin.com/5KsV3KuF

What's the difference and why is this good for robots:

1. The A* Algorythm works in 3D space!
2. Diagonals are disabled due to robots not moving in 3d space.
3. The algorythm takes in the Robot's facing into account (which you have to provide). It's using the sidesAPI format in integers.
4. Different movement weights based on facing direction. (straight ahead is a weight of 1 while turning around and moving is 2.9. turning right/left and moving is 2. Up and down is 1.1

Example code using it: 

local luastar = require("lua-star")

function positionIsOpenFunc(x, y, z)
    if x == 3 and y <= 4 and z == 4 then
      return false
    else 
      return true
    end
end

local path = luastar:find(15, 15, 15, {x=3,y=3,z=0,f=3}, {x=3,y=6,z=10}, positionIsOpenFunc, false, true)
for key,value in pairs(path) do
  print("--------")
  for key2,value2 in pairs(value) do
    print(key2 .. " : " .. value2)
  end
end --Facing 2=north, 3 = south, 4 = west, 5 = east

you can change the first false to true if wanted. It is set to false to not use cache, but tbh, cache isn't incredibly necessary i don't think. First 3 15's are the range that it will perform the algorythm, which means max X is -15,15, and same with other 2. first table is start and second is end. 

[cadergator10 1]

There are some issues with it I think that I might try and figure out

[AtomicPotato 0]

Hey this is pretty cool. I noticed some problems when using {x=0,y=0,z=0} as the starting position though, maybe because the parent of a node in that A* implementation is initialized at (0, 0, 0)?

I have some suggestions for improvement too:

• The calculateScore() function uses a heuristic based on the Euclidean distance to the goal, it should be the Manhattan distance for grid-based movement. For example, you could change line 55 from "local s = dx * dx + dy * dy + dz * dz" to "local s = math.abs(dx) + math.abs(dy) + math.abs(dz)". This should help increase efficiency and speed of the calculation.
• getAdjacent() isn't really necessary, you could just unroll that loop and inline the function. Since it's a 3D grid, each node has up to 6 neighbors with exceptions at the edges of the grid.
• Most implementations of A* use a priority queue to find the node with the lowest score in constant time, O(1). The code you have does a table.sort() across all the nodes, which I'm guessing will be O(n) average case. If you don't have any problems with the calculation taking a long time for larger areas, then you probably should keep it how it is. However if there are some performance issues then I would recommend taking a look at priority queues based on a binary heap, it's not hard to implement.

I've been working with A* quite a bit recently for a mining robot that needs to navigate in a cave. In my case, I'm considering the "hardness" of blocks when the robot plans a path it needs to dig through (meaning the robot may choose to mine through soft blocks like dirt instead of stone when possible). The hardness values can be obtained from the geolyzer hardware (see https://ocdoc.cil.li/component:geolyzer ), it scans a specified area in the world and returns the data in an array. Here is a demo implementation of my A* algorithm if you are curious: https://pastebin.com/K54Nkp1Z

[cadergator10 1]

On 9/29/2022 at 9:25 PM, AtomicPotato said:

Hey this is pretty cool. I noticed some problems when using {x=0,y=0,z=0} as the starting position though, maybe because the parent of a node in that A* implementation is initialized at (0, 0, 0)?

I have some suggestions for improvement too:

• The calculateScore() function uses a heuristic based on the Euclidean distance to the goal, it should be the Manhattan distance for grid-based movement. For example, you could change line 55 from "local s = dx * dx + dy * dy + dz * dz" to "local s = math.abs(dx) + math.abs(dy) + math.abs(dz)". This should help increase efficiency and speed of the calculation.
• getAdjacent() isn't really necessary, you could just unroll that loop and inline the function. Since it's a 3D grid, each node has up to 6 neighbors with exceptions at the edges of the grid.
• Most implementations of A* use a priority queue to find the node with the lowest score in constant time, O(1). The code you have does a table.sort() across all the nodes, which I'm guessing will be O(n) average case. If you don't have any problems with the calculation taking a long time for larger areas, then you probably should keep it how it is. However if there are some performance issues then I would recommend taking a look at priority queues based on a binary heap, it's not hard to implement.

I've been working with A* quite a bit recently for a mining robot that needs to navigate in a cave. In my case, I'm considering the "hardness" of blocks when the robot plans a path it needs to dig through (meaning the robot may choose to mine through soft blocks like dirt instead of stone when possible). The hardness values can be obtained from the geolyzer hardware (see https://ocdoc.cil.li/component:geolyzer ), it scans a specified area in the world and returns the data in an array. Here is a demo implementation of my A* algorithm if you are curious: https://pastebin.com/K54Nkp1Z

Thanks! If I get back into the A* stuff I'll take a look at all this