|
| 16 Feb 2014 09:33 AM |
For my A* algorithm this is what I use for heuristics:
function heuristic(id1, id2) local p1 = master_node_table[id1].Brick.Position local p2 = master_node_table[id2].Brick.Position return (p1 - p2).magnitude end
HOWEVER! There are cases when the goal is closer than the next node on the path to goal(its behind a wall though), so then the entire path gets messed up and never gets to the goal.
Any better ways to for heuristic? |
|
|
| Report Abuse |
|
|
digpoe
|
  |
| Joined: 02 Nov 2008 |
| Total Posts: 9092 |
|
|
| 16 Feb 2014 09:35 AM |
| Check if a valid path exists between the two. In the image you linked, you had parts demonstrating these paths. You could check if such 'paths' existed before travelling down them. |
|
|
| Report Abuse |
|
|
|
| 16 Feb 2014 09:38 AM |
Should it not know that the next path is invalid, and thus ignore it until later?
That's how it is SUPPOSED to work right? Only make these calculations for valid connections? |
|
|
| Report Abuse |
|
|
| |
|
|
| 16 Feb 2014 10:02 AM |
| Then you are doing it wrong. |
|
|
| Report Abuse |
|
|
|
| 16 Feb 2014 10:03 AM |
Just store the connections in a table, then iterate through the table to get the connected nodes.
It would be even less laggy than what you are doing :P |
|
|
| Report Abuse |
|
|
|
| 16 Feb 2014 10:06 AM |
Let me explain.
puu.sh/6Ys9j.PNG
It should go around the wall, but it confuses the A-star because the goal is already "close" (though its really behind a wall) and it would increase the distance taken to go around, so it never gets to its goal |
|
|
| Report Abuse |
|
|
|
| 16 Feb 2014 10:07 AM |
| And the connections are stored, and I do iterate through them. |
|
|
| Report Abuse |
|
|
|
| 16 Feb 2014 10:07 AM |
| So why does it try to go through the wall? |
|
|
| Report Abuse |
|
|
|
| 16 Feb 2014 10:08 AM |
| It doesn't, it just gets confused and errors |
|
|
| Report Abuse |
|
|
MrNicNac
|
  |
| Joined: 29 Aug 2008 |
| Total Posts: 26567 |
|
|
| 16 Feb 2014 10:20 AM |
A* has three cost checks. Are you including the other two? One is the current heuristic you have, then there is another which is the distance between the place you started and the next choice you're about to check. Finally, you add those two checks together and compare the final result (called the F cost).
What may be happening is that you aren't using a "closed" list correctly. It shouldn't get "confused" and never reach there. It should add that path to a set of "closed" or "unreachable" adjacents and never use them again - only choosing the other available paths. As long as a path exists, A* will always find it. This is how you know it's implemented correctly.
|
|
|
| Report Abuse |
|
|
|
| 16 Feb 2014 10:51 AM |
Lets say you have a path like
OOO OXO OXO OXO OXO OXO GXS (goal, start, O=open, X=wall)
There will be 1 node in the open list (S) so adjacents will be taken (there is only one, the O above S).
S will be set closed.
Again only 1 node in open list, and only one direction to go (since S is closed and cant be re-entered) so that will be picked.
This continues until you reach G. Note that at no point costs are involved. This is because costs are only used to prioritize between nodes, which cannot be done when there is only one way to go.
Costs are used to determine which node from the open list to explore next (always taking the one with lowest dist+heuristic)
In your case with a room and then a long path to goal that is nearby, A* will likely explore the room first and then be forced to follow the long path when no other options exist.
|
|
|
| Report Abuse |
|
|
|
| 16 Feb 2014 11:22 AM |
"In your case with a room and then a long path to goal that is nearby, A* will likely explore the room first and then be forced to follow the long path when no other options exist."
This is correct and exactly the reason why it errors.
You see, it explores the room first, but it cant afterwards go to the hallway because the nodes leading to it are already set in closed |
|
|
| Report Abuse |
|
|
|
| 16 Feb 2014 12:32 PM |
| Why can't it reach the hallway? It should have been added to the open set when you first visited those closed neighboring nodes. |
|
|
| Report Abuse |
|
|
|
| 16 Feb 2014 12:46 PM |
This is what happens
http://www.youtube.com/watch?v=YbI11eEvtPo&feature=youtu.be |
|
|
| Report Abuse |
|
|
|
| 16 Feb 2014 01:09 PM |
| Do you add all connected nodes to the open list? |
|
|
| Report Abuse |
|
|
Gorake
|
  |
| Joined: 10 Feb 2014 |
| Total Posts: 219 |
|
|
| 16 Feb 2014 01:09 PM |
| Yeah, it looks like you're just adding one at a time in the video. |
|
|
| Report Abuse |
|
|
|
| 16 Feb 2014 01:11 PM |
yes except for nodes that are on the closed list already, theyre ignored
basically the fix is convincing the algorithm that the F score is lower down the hallway
I basically need to improve the heuristic so it takes into account possible paths and not just euclidean distance(magnitude between start and goal)
I just have no idea how to improve the heuristic
|
|
|
| Report Abuse |
|
|
|
| 16 Feb 2014 01:11 PM |
It looks as if you've implemented A* incorrectly. Yours appears to only be able to visit a cell adjacent to the previously checked one. What you're supposed to do is choose the cell in the open set with the best score, regardless of its position in the world.
I suggest reading up on the algorithm a little more, the wikipedia page is pretty good. Here is a version I made if you prefer learning by example, I believe it's well commented: http://www.roblox.com/A-item?id=71066974 |
|
|
| Report Abuse |
|
|
|
| 16 Feb 2014 01:11 PM |
| oh, on the video it only colors the path ^ |
|
|
| Report Abuse |
|
|
|
| 16 Feb 2014 01:15 PM |
"What you're supposed to do is choose the cell in the open set with the best score, regardless of its position in the world."
"Regardless of its position in the world"
What. At first i mistakenly did this and the result was completely random behaviour where it jumped across the map, leading to paths that made no sense.
This implementation Im using right now works perfectly if there are no cases like now that the goal is closer than the next node on the path |
|
|
| Report Abuse |
|
|
|
| 16 Feb 2014 01:16 PM |
In the correct implementation of the algorithm this is not a problem.
However, my explanation skills fail so some better person should explain. |
|
|
| Report Abuse |
|
|
|
| 16 Feb 2014 01:16 PM |
| Please read my latest post about improving the heuristic. This is getting out of hands |
|
|
| Report Abuse |
|
|
|
| 16 Feb 2014 01:19 PM |
It is impossible to have a closed node next to an unvisited node.
It will always be CLOSED-OPEN-UNVISITED
Think of pathfinding as a goo, where you mark the inside of the goo closed, and keep track of the bordering nodes.
Then you decide where you should expand the goo next, move its "border" one cell further. This is what the heuristic helps you optimize, to prefer expending from open cells that are closer to the goal. |
|
|
| Report Abuse |
|
|
|
| 16 Feb 2014 01:27 PM |
The problem isn't in the heuristic, you could set it to function heuristic() return math.random(-1000,1000) end and it'd still find a (suboptimal) solution.
I think you've implemented A* incorrectly. Here's an overview:
1. Pick the node in the open (to be visited) set with the lowest FScore. 2. Calculate the score of all surrounding unvisited nodes and add them to the open set HScore = heuristic() GScore = (distance to previous node) + (previous node's GScore) FScore = HScore + GScore 3. Store a reference to the previous node (to find your way back once you finish) and mark the node as closed.
With this method, it is possible to explore all nodes even if they're "blocked off" by closed nodes, because by visiting those closed nodes they would have been added to the open set. |
|
|
| Report Abuse |
|
|