A* Logic Problem

First, Thank you to dan200 and the openCCSensors team for the great mods. About 8 weeks ago I was playing Tekkit Legends with my son, working our way through each mod when we got to computercraft. I have been engrossed ever since.

Here I am 2K lines of code and 8 weeks later with my first post for help. I’ve made it a point to exhaust all the computercraft and lua forums to the extent possible. Every time I started to type a question I would go double check everything and each time I found the error and cancelled the post.

Now I’m sitting here on day three trying to find a logic problem and could use a fresh set of eyes.

I’ve never considered myself a programmer so this will probably look unorthodox. I’ve also tried a bunch of new things to learn more about functions, tables and the like so it may be overly complicated in places.

I would appreciate any feedback to find the problem and understand where the error(s) are.

This is a seek function that is part of a larger program. I’m attempting to implement A* to somewhat intelligently get my turtle to a set of supply chests. My offset is going up each turn until it does not return a best node around turn 4.

My approach is:
1) Specify destination location for the inventory chest (Captured in another function)
2) Get current location from GPS
3) Get facing direction so that I know which way to move
4) Inspect all neighbor blocks and close the ones that are not “Air”
5) Close the current/parent block.
6) Calculate g (distance from start) for each neighbor
7) Calculate h (distance to end) for each neighbor
8) Calculate f (overall move cost) to each neighbor
9) Make up/down moves cost slightly more
10) Select the lowest cost open node from the list
11) Use absolute distance to end as a tie breaker
12) Move to that node
13) Repeat 2 – 12 while current location does not equal target location

A little over 500 lines. Here is the pastebin:

http://pastebin.com/J4qXNPkp

Well, I can't really follow your code, but I can give you some tips on formatting and such which may make your life easier.

1 - In a few places, your indentation is a bit off. For example, lines 12 and 13 are indented too far, and lines 148-162 aren't indented enough.
2 - You also define functions inside functions - I would not do that. If you want to use it with only that function, I would use a do ... end

local func
do
  local function thatonefunction()
    --#do stuff
  end
  func = function()
   thatonefunction()
   --#other stuff
  end
end

Another thing, I would keep away from string.format. Several features of it are broken in computercraft / LuaJ. You can still, of course, use it's non-broken features - I'd just get used to using the alternatives, in case you need them at some point.

Thank you. I fixed the indention / readability and reworked the functions as you suggested. I'm not sure I fully understand the reason behind the do..end loop as it seems like a sub-function would limit scope also. Going with your conventions.

While working through your suggestions I found a couple other issues that I'm working on and will re-post a revised version in a couple days.

I found that I was using the g values to tie-break instead of the h values and my math for calculating the h value was returning negative values instead of absolute values.

These issues also masked a couple issues with the move function where I had the forward and backward moves reversed.

Essentially, it's an extremely small increase in the execution speed of the function, because the inner function isn't defined ever time you call it.

I'll do a quick description of each function:

Spoiler

function thing()
  local function otherthing()
    --do things
  end
  otherthing()
end
thing()
thing()

——-
1. define thing
2. call thing
a. define otherthing
b. call otherthing
3. call thing
a. define otherthing
b. call otherthing

Spoiler

local thing
do
  local function otherthing()
    --do things
  end
  thing = function()
    otherthing()
  end
end
thing()
thing()

——-
1. localize thing
2. define otherthing local to the scope of the do…end block (it's not a loop)
3. define thing
4. call thing
a. call otherthing
4. call thing
b. call otherthing

I completely messed up my code trying to implement KingofGamesYami's do…end recommendations. I ended up rewriting the whole thing without nesting the functions and eliminating the Node function I was using to build the node list.

The root cause of my increasing offset issue was a calculation error in step 6. I was calculating g from the currentNode instead of carrying forward the value from the parent node. I found it by logging each pass through populating the node table and recalculating each step on paper then in a spreadsheet to find it like this:

Spoiler

The rewritten code is here (Still has errors closing some nodes described below) :

http://pastebin.com/GbFMdjzG

Just thought I would share my progress and how I'm working though the issues if anyone else comes along trying to do this.

Next problem to solve is that my code to detect a block and close it is not working as expected. Lines 413 - 446 are supposed to inspect the adjacent blocks and close any block that returns data upon inspection. It is not always closing occupied blocks; like when encountering a chest.

Spoiler

The node is added to the table but not closed because turtle.inspect() is returning false for some reason.

Spoiler

Because the node is not closed it keeps trying to move to the chest location. I'll post a more specific question if I cannot figure it out.

My first thought is a mod-interaction issue; "copper chests" aren't a vanilla Minecraft thing.

If turtle.inspect() returns false when entered directly into the Lua console (in which case it should also provide a string explaining why), does turtle.detect() work?

It was not a problem with turtle.inspect(). I broke out that section of code to test if inspect was working with the iron chests mod and it works fine.

The problem was with my node logic. Even though we can only "see" six blocks from any position with a turtle all 26 neighboring blocks must be considered and recalculated on each move. This is because one of the 26 blocks could have been an up/down/front/back/left/right block considered in a previous move. Without recalculating f & g from the new parent position block from previous turns have artificially low costs.

The block I choose was legitimately open but should have had a higher cost since I would have had to travel back through the parent to get there. I've over-corrected in the way I'm re-calculating g now but it seems to yield the expected results. Might be causing my y problem though.

I've coded for recalculating all the blocks and I seem to be successfully navigating obstacles on the same y axis to the destination from any starting position an any starting direction

There is still a problem choosing a new y that is next on my list and my while loop stops too soon.

while currentVector.x ~= targetVector.x and currentVector.z ~= targetVector.z and moveCount < 21 do

The intent is to stop when the current X and Current Y is equal to the Target X and Target Y.

I see that as its written when any of the conditions becomes false the loop ends. I want to write it so that it continues until all the conditions evaluate false

Here is Rev 3 that re-calculates all 26 neighbors and fixes some of the directional math I had messed up.
http://pastebin.com/QdrwPeeR

Last update on this post. I'm done with the A* / seek function for now. Thanks for the suggestions; they got me to think about some of the problems and debugging differently.

I fixed the loop issue by switching from while..do loop to a repeat..until loop after reviewing the Loop Tutorial again. This way I'm explicitly checking if the current coordinates are equal to the target coordinates rather than looping while the offsets are not zero.

I've tested all facing directions on all sided sides of the target location and with randomly placed blocks in the way. So far it seems to do what I wanted. I even placed the turtle behind a mountain and it found it's way to the target about 6 chunks away.

Still need to test in all positive coordinates and in split coordinates.

Here is the final version with the logging and comments removed.

http://pastebin.com/ZFLsr9MX