I had planned to work more on the game during the Christmas holidays, but I did not start until a few days ago. But I made some clear progress these last few days.
The algorithm that calculates the set of hexagons a unit can reach now takes terrain into account. For instance, crossing a forested hexagon costs more movement points than passing through a hexagon representing farm land.
The screenshot shows the hexagons the blueish tank near the bottom-left corner can move to. The forest hexes at the top were previously reachable.
At first, I thought all I had to do was associate costs with every edge and sum them up as I traversed the graph, but after a while I realized that breadth-first search (which is what I used before) cannot be used with weighted graphs to solve this problem (unless all edges have the same weight). So I had to throw away the old search code and implement Dijkstra’s algorithm instead. Took me longer than I expected, but now the code is cleaner and handles weighted graphs properly.
I also simplified the rules for how close to an enemy a unit is allowed to move without having to stop. The new rule is simply that you cannot pass through a hex that is adjacent to an enemy unit. That is all that is needed, really. Thanks Peter E. for making a comment that made me realize how pointless the (relative) complexity of the old method was!
Tags: dijkstra, path finding
