Well, since my last post there have been many changes. Here's the long story.

First of all, the screenshots I showed you didn't come from a program I coded. Actually, the program comes from here.

My pathfinding algorithm wasn't working as expected so I decided to search for one that would work as I wanted. Unfortunately, I didn't find anything for isometric tile maps with 8 directions possible. I then decided to modify the program I linked above to make it work with isometric tiles and with 8 directions. It was actually a bad idea because it took me time to understand how the pathfinding was implemented and the modifications I made were... quite messy (on top of that I'm not a Java programmer and it's written in Java ).

Ok, so I decided to take back MY algorithm (implemented in C++) and try (one more time) to make it work.

[...] Also, it sounds like you're not actually implementing A* correctly, or don't fully understand the algorithm. There are two costs: the heuristic (which as Alvaro said is generally not the problem provided it is admissible) and the actual traversal cost. Chances are your problem is in your A* implementation in how you compute the actual traversal cost versus the values provided by your heuristic.

Yes there are 2 costs, thanks for reminding me! All this time, I don't know why but I never considered the "G" (known) cost. I focused on the "H" (heuristic) cost. Your answer, ferrous, helped me as well:

After reading your post, I modified my heuristic function to a simple one (diffX + diffY):

int Pathfinder::calculateHeuristicCost(PathNode *node)
{
    Point cellPt = this->getCoordsFromCellId(node->CellId);
    Point goalPt = this->getCoordsFromCellId(m_goalCellId);

    int dx = std::abs(cellPt.X - goalPt.X);
    int dy = std::abs(cellPt.Y - goalPt.Y);

    return dx + dy;
}

and I worked on the function which calculates the G cost. I decided to penalize orthogonal moves by adding an extra cost. But then the question is: what cost should I add to orthogonal moves?

• If the cost it too high, the algorithm will always prefer diagonal moves and it will result in longer paths sometimes.
• If the cost is too low, the algorithm will always prefer orthogonal moves (as shown in the screenshots above) and it will result in longer paths as well.

After a few tries, I ended up with the values +10 for diagonal moves and +14 for orthogonal moves (which are common values for pathfinding, don't really know why, I read some things about distances and Pythagorean theorem).

const int ORTHOGONAL_COST = 14;
const int DIAGONAL_COST = 10;

int Pathfinder::calculateMoveCost(PathNode *parent, PathNode *node)
{
    const CellData &parentCellData = m_mapGrid.getCellDataFromId(parent->CellId);
    const CellData &nodeCellData = m_mapGrid.getCellDataFromId(node->CellId);

    if (this->getDiagonalAlignment(parentCellData, nodeCellData) != Direction::None)
        return parent->G + DIAGONAL_COST;
    else
        return parent->G + ORTHOGONAL_COST;

    return 0;
}

Result:

As you can see, it works pretty well.

What do you think? Good/bad method?

Good work!

The reason you wound up with 10 and 14 is because of Pythagoras, as you noted: if a straight line costs 10 units, then the triangle formed by taking two straight moves also offers you a third move, the diagonal. By the Pythagorean theorem, the diagonal cost = sqrt(a*a + b*b) = sqrt(10*10 + 10*10) = sqrt(200) ~= 14.142.

Thank you for this explanation and for all your answers.

Thanks to everybody who posted in this thread too.

I can move on to the next part of my game now .