A* will work just fine, you cannot use a good heuristic but that is ok. The A* algorithm is meant to work when you dont know where the goal is. In essence this is what you have. Consider you base all your locations as the distance from where you started, then your start is always (0,0). Now it is the end you do not know as far as the algorithm is concerned. You can still check to see if you have found the end, however, which is the important point.