One of the factors that affect the success of Evolutionary Robotics (ER) is the way fitness functions are designed to operate. While needs-based custom fitness functions have been developed, most of the time they have been defined in simpler mathematical functions to reduce the computation time. In this paper, we hypothesize that an incremental fitness function based on established techniques in specific task domains in robotics will aid the evolution process. An A-star algorithm-based fitness function for path planning is designed and implemented for evolving the body plans and controllers of robots for navigation and obstacle avoidance tasks. It has been shown that using this concept, fitter robots have evolved in most cases when compared to simple distance-only based fitness functions. However, due to variable performance of the evolver with the A-star fitness function, the results are inconclusive. We also identify problems associated with the fitness function and make recommendations for designing future fitness functions based on observations of the experiments.