Game Development Status 12/20/04

Monthly total 24.5 hours; yearly total 366.5 hours.

I had to remind myself tonight that the goal of heuristic search is to quickly reduce the search space by means in order to complete the search at least somewhat faster than an other (brute force) approach.

I was implementing a version of A* limited by the movement points available to a slow unit, the assumption being that a unit might not have sufficient MP to reach the destination hex. This lead me to give some thought to the road heuristic function, which I had avoided implementing to this point. I was reviewing my previos train of thought on the subject: when I have an opportunity to path into a road hex, I change the unit's formation to road and move faster along the road. I had always got stuck when it came time to leave the road again...I couldn't come up with a way to estimate H for a path that entered the road and later left the road.

Here's the thing that occurred to me: the heuristic doesn't have to be perfect, it just has to be admissable (i.e. less than or equal to the actual cost of the possible move). OK, my heuristic will be to assume that the unit will move all subsequent hexes at the road movement rate. This will tend to underestimate the actual cost and it will bias movement in favor of road marches. I'm willing to live with that for now. I can reduce excessive bias later, but for now, I move on.