sumimakito/a-star

A*(A-star) pathfinding algorithm in C++

^{^}Makito^{^← Cat ears}

I'm a self-motivated developer. I love learning by doing.

About Me

• A Go, Java(Type)Script, Lua, Ruast, Python, and (... more languages) user
• Work as a Full-stack Software Engineer
• Used to be an iOS and Android Developer
• Actually I hold a bachelor's degree in English Language and Linguistics

a-star's Issues

Inaccurate heuristic function makes the search slow

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

hi

can you teach me how to open the file because it is always showing 0x00007FFA0E134008 中 (於 Project5.exe) 發生未處理的例外狀況: Microsoft C++ 發生例外狀況: cv::Exception (記憶體位置 0x0000007EC97FF000)。