So I have been getting into coding for a little while now and am currently making an A* search algorithm as a side project. I used the manhattan distance for my heuristic, and calculated the cost by finding the length of the path taken from the source to the node being explored. It seemed to be doing pretty well once I got it working and tried it out a few times, but then I tried the grid in the image below and ran into a problem.
(Ignore the blacked out 16 and 17 in the optimal path, I did that after it ran)
As you can see, the path that my algorithm took was not optimal, as there was a shorter path available by going to the right. However, I manually calculated f(n) = g(n) + h(n) for all nodes in the algorithm's path as well as the first node in the more optimal path and found that f(n)algorithm < f(1)optimal always:
(f(n)algorithm goes back up to 92 if you keep going, but no further than that)
So, I am curious if my algorithm is flawed, or if A* is not always optimal. I have heard in multiple places that it is optimal, so I am inclined to believe the former, but I can't wrap my head around how I would get the algorithm to check the optimal path, since it is always supposed to check the node with the lowest f. Any help would be appreciated.
I can also include my code if need be, but I feel like this is a more conceptual question, so I am leaving it out for now.