Inaccurate heuristic function makes the search slow

[HjalteBested]

Hi Sumi

Good work !

But I found a problem:
The heuristic is not in the same units as the cost function which makes the search far slower than it should be.

The following change makes the code much faster as it only searches where it needs to. You might also add a tie-breaker.

inline int computeH(MapNode *node1, MapNode *node2){
    if (ALLOW_VERTEX_PASSTHROUGH) {
        return diagonal_distance(node1, node2)*G_SKEW;
    } else {
        return manhattan_distance(node1, node2)*G_DIRECT;
    }
}

/**	The standard heuristic is the Manhattan distance. 
 *	Look at your cost function and see what the least cost is 
 *	for moving from one space to another. 
 *	The heuristic should be cost times manhattan distance: */
inline int manhattan_distance(MapNode* node1, MapNode* node2){
	return abs(node2->x - node1->x) + abs(node2->y - node1->y);
}

/**	If on your map you allow diagonal movement, then you need a different heuristic. 
 *	The Manhattan distance for (4 east, 4 north) will be 8. 
 *	However, you could simply move (4 northeast) instead, so the heuristic should be 4. 
 *	This function handles diagonals: */
inline int diagonal_distance(MapNode* node1, MapNode* node2){
	return max(abs(node2->x - node1->x),abs(node2->y - node1->y));
}

www.dropbox.com/s/vnsl4hkceuy5pyw/Map50_1_Path.png
www.dropbox.com/s/lag03s9i18rqira/Map50_2_Path.png
www.dropbox.com/s/teipm39dd5kqwqc/Map50_3_Path.png

[sumimakito]

Hello Hjalte, Thanks for your review! I’ll take a look. :-) Cheers Makito iPhoneから送信 2018/04/04 午後6:25、HjalteBested <notifications@github.com<mailto:notifications@github.com>>のメール: Hi Sumi Good work ! But I found a problem: The heuristic is not in the same units as the cost function which makes the search far slower than it should be. The following change makes the code much faster as it only searches where it needs to. You might also add a tie-breaker. `inline int computeH(MapNode *node1, MapNode *node2){ if (ALLOW_VERTEX_PASSTHROUGH) { return diagonal_distance(node1, node2)*G_SKEW; } else { return manhattan_distance(node1, node2)*G_DIRECT; } } /** The standard heuristic is the Manhattan distance. * Look at your cost function and see what the least cost is * for moving from one space to another. * The heuristic should be cost times manhattan distance: / inline int manhattan_distance(MapNode node1, MapNode* node2){ return abs(node2->x - node1->x) + abs(node2->y - node1->y); } /** If on your map you allow diagonal movement, then you need a different heuristic. * The Manhattan distance for (4 east, 4 north) will be 8. * However, you could simply move (4 northeast) instead, so the heuristic should be 4. * This function handles diagonals: / inline int diagonal_distance(MapNode node1, MapNode* node2){ return max(abs(node2->x - node1->x),abs(node2->y - node1->y)); } ` — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub<#1>, or mute the thread<https://github.com/notifications/unsubscribe-auth/AFCGVO2xN9pb00jqWudXoTXPjrIXIxSDks5tlJ-mgaJpZM4TGi12>.

[sumimakito]

Hello Hjalte,

I have tested out your advice and it works like a charm!
The code has been updated. Also, I'm sorry for the late reply.

Thanks
Makito

[HjalteBested]

Hi Makito

Glad to help :)

Thank you for the work - I am using it in my own project for path planning for a mobile robot ;)

Cheers,
Hjalte