Jump to content
  • Sky
  • Blueberry
  • Slate
  • Blackcurrant
  • Watermelon
  • Strawberry
  • Orange
  • Banana
  • Apple
  • Emerald
  • Chocolate
  • Charcoal
cadergator10

A* Algorythm compatable with OpenComputers robot movements

Recommended Posts

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. 

Link to post
Share on other sites

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

Link to post
Share on other sites
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

Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...

×
×
  • Create New...

Important Information

By using this site, you agree to our Terms of Use and Privacy Policy.