generic image
Processing...
  • Games
  • Catalog
  • Develop
  • Robux
  • Search in Players
  • Search in Games
  • Search in Catalog
  • Search in Groups
  • Search in Library
  • Log In
  • Sign Up
  • Games
  • Catalog
  • Develop
  • Robux
   
ROBLOX Forum » Game Creation and Development » Scripters
Home Search
 

Re: Heuristics

Previous Thread :: Next Thread 
StealthKing95 is not online. StealthKing95
Joined: 13 Dec 2008
Total Posts: 4263
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 is not online. 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
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
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
StealthKing95 is not online. StealthKing95
Joined: 13 Dec 2008
Total Posts: 4263
16 Feb 2014 10:00 AM
[ Content Deleted ]
Report Abuse
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
16 Feb 2014 10:02 AM
Then you are doing it wrong.
Report Abuse
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
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
StealthKing95 is not online. StealthKing95
Joined: 13 Dec 2008
Total Posts: 4263
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
StealthKing95 is not online. StealthKing95
Joined: 13 Dec 2008
Total Posts: 4263
16 Feb 2014 10:07 AM
And the connections are stored, and I do iterate through them.
Report Abuse
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
16 Feb 2014 10:07 AM
So why does it try to go through the wall?
Report Abuse
StealthKing95 is not online. StealthKing95
Joined: 13 Dec 2008
Total Posts: 4263
16 Feb 2014 10:08 AM
It doesn't, it just gets confused and errors
Report Abuse
MrNicNac is not online. 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
Radioaktiivinen is not online. Radioaktiivinen
Joined: 25 Apr 2009
Total Posts: 18629
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
StealthKing95 is not online. StealthKing95
Joined: 13 Dec 2008
Total Posts: 4263
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
Brandonhare is not online. Brandonhare
Joined: 02 May 2007
Total Posts: 11005
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
StealthKing95 is not online. StealthKing95
Joined: 13 Dec 2008
Total Posts: 4263
16 Feb 2014 12:46 PM
This is what happens

http://www.youtube.com/watch?v=YbI11eEvtPo&feature=youtu.be
Report Abuse
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
16 Feb 2014 01:09 PM
Do you add all connected nodes to the open list?
Report Abuse
Gorake is not online. 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
StealthKing95 is not online. StealthKing95
Joined: 13 Dec 2008
Total Posts: 4263
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
Brandonhare is not online. Brandonhare
Joined: 02 May 2007
Total Posts: 11005
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
StealthKing95 is not online. StealthKing95
Joined: 13 Dec 2008
Total Posts: 4263
16 Feb 2014 01:11 PM
oh, on the video it only colors the path ^
Report Abuse
StealthKing95 is not online. StealthKing95
Joined: 13 Dec 2008
Total Posts: 4263
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
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
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
StealthKing95 is not online. StealthKing95
Joined: 13 Dec 2008
Total Posts: 4263
16 Feb 2014 01:16 PM
Please read my latest post about improving the heuristic. This is getting out of hands
Report Abuse
Radioaktiivinen is not online. Radioaktiivinen
Joined: 25 Apr 2009
Total Posts: 18629
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
Brandonhare is not online. Brandonhare
Joined: 02 May 2007
Total Posts: 11005
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
Previous Thread :: Next Thread 
Page 1 of 1
 
 
ROBLOX Forum » Game Creation and Development » Scripters
   
 
   
  • About Us
  • Jobs
  • Blog
  • Parents
  • Help
  • Terms
  • Privacy

©2017 Roblox Corporation. Roblox, the Roblox logo, Robux, Bloxy, and Powering Imagination are among our registered and unregistered trademarks in the U.S. and other countries.



Progress
Starting Roblox...
Connecting to Players...
R R

Roblox is now loading. Get ready to play!

R R

You're moments away from getting into the game!

Click here for help

Check Remember my choice and click Launch Application in the dialog box above to join games faster in the future!

Gameplay sponsored by:
Loading 0% - Starting game...
Get more with Builders Club! Join Builders Club
Choose Your Avatar
I have an account
generic image