A-star algorithm. Should the following happen ?

[Slastraf]

The following is printed in the console if i call the self:path() method :

 

>> Step 1 >> 1

>> Step 2 >> 5

 

Is this supposed to happen ? , If yes,

I taught the algorithm returns each node of path, not only the first and the last one.

Attached are the .lua versions of the script needed if you want to try it out yourself.

Heres a pastebin version http://pastebin.com/Zag8entv

 

heres where I fot the original lua file from: https://github.com/lattejed/a-star-lua

 

I am sorry if is this too much research for helping me, but I would very appreciate it.

controllerPivotScript.lua

3rdPersonFollow.lua

[Rick]

The thing I found with that algo is that if there are straight lines in the path it skips the nodes in the middle and returns the start and end point. So you will have to find those middle nodes to move to from the information it gives you.

[Slastraf]

The thing I found with that algo is that if there are straight lines in the path it skips the nodes in the middle and returns the start and end point. So you will have to find those middle nodes to move to from the information it gives you.

I tried it with very different values, always there are 2 lines returned.

if you go from the top right corner for example, to the top left corner its a straight line , and I wouldnt worry

but when theres diagonal paths does it count as "straight" , too ?

That would mean it calculates a path only if theres "ignored" nodes in the nodes[] table.

I would test that out but how do you make "ignored" nodes ?

[Rick]

Yeah, if I recall diagonal would be straight also. If it's returning the correct straight lines (even diagonal) then I'd say it's working?

 

 

If you look at the documentation there is a callback function that gets called. If it returns true the node is passable if false it's not. I think what you would have to do is check your marked field in that node table to see if it's taken. So nodes can be a table that has at least an x an y member but you can add any other members in that. So for example you would add an .open field that is boolean. In this callback function you make check if node.open == false then return false end to signify that node isn't valid.

 

I think that's how it works.

 

 

[edit] You probably check the neighbor for open not the node itself when inside that callback function.

 

 

If you don't define this callback function there is a default one in the library that just returns true which makes all nodes valid to move.

 

You should be able to find a path that would return some straight lines and some diagonal even without unpassable nodes right? That can tell you if it's working too.

[Rick]

ok, the biggest thing you were missing is checking if the neighbor was actually a valid neighbor given the 2D grid layout you have. This means you have to see if neighbor and node's row/col are actually 1 value from either other. If they are > 1 value then it's not a valid neighbor because it's too far away to be a valid neighbor in a 2D grid. Below is how I setup the is valid function and it worked. It also gave me each node from start to end like you were expecting.

 

local valid_node_func = function (node, neighbor)
-- not a valid neighbor if we can't walk on this "tile"
if neighbor.walkable == false then return false end

-- only neighbors that are right next to the node are valid neighbors in our 2d grid setup
if math.abs(neighbor.row - node.row) > 1 then return false end
if math.abs(neighbor.col - node.col) > 1 then return false end

-- don't allow diagonal movement
if neighbor.x ~= node.x  then 
if neighbor.y ~=node.y then
return false 
end
end
if neighbor.y ~= node.y  then 
if neighbor.x ~=node.x then
return false 
end
end

-- we made it passed all the checks, yay! we are a valid neighbor!
return true
end