By the way, TILES is now the name for the framework, since this is for a tile based game. “Grecian Urn” describes a particular aesthetic I want to achieve someday in a game, but the more I explore this tile based game, the less I think it is appropriate for the original vision. At this point, I think it would be better to design Grecian Urn as a side scroller showing characters in profile rather than a top down grid. But since I am already creating a framework for a tile based game, I might as well finish it.
It is amazing to me that I got A* wrong the first time around since I have read explanations about it before. Its implementation is quite simple, but since I misunderstood how it worked my attempt was overly complicated. I think I made the mistakes I did because I had started thinking about sub-processes before considering how the whole thing would fit together.
My initial understanding of the A* heuristic was that to explore the shortest path between point a and point b you followed this process:
- at each node assemble a list of possible next steps to take
- rank these next steps according to their distance from the goal
- choose the node nearest your goal and then repeat step 1 at the new node
There are two problems with that application. One problem is that there are more steps in the actual process which I only vaguely considered. I should have thought it all through before writing any code. The big problem however is that while you do gather a list of next steps from each explored node, you then insert this list into a master list of untried steps. This is a fundamental difference, and requires that the ranking of each possibility be based on the sum of potential distance to target from that node, and the distance traversed to reach the node. Also you don’t limit the decision making in step 3 to the most recently explored possibilities, but reconsider all remaining untried possibilities in light of what you just discovered.
In other words I had visualized the process like that of a frog crossing a pond one lily pad at a time, when actually the process is more like a tree growing roots in search of water. At each moment (each iteration of the A* process), the tree considers all of the root tips before choosing a root tip in which it will invest its energy. A frog by comparison is only able to choose between lily pads adjacent its current position as opposed to all the lily pads floating on the pond. If in the midst of its exploration the frog discovers that it made a wrong choice earlier based on information it now has, it would have to backtrack to the point where it made the wrong choice, and then try again. The tree on the other hand simply switches its focus to another root tip.
At first, to solve my problem, I copied Ondřej’s pathfinding code and integrated it with my other code. But curiously I noticed that he builds his path from the goal toward the starting point whereas I think I will need it to build from the starting point. So I rewrote his routines, and they are currently ugly, but each step in the path identifies the previous step and the next step in the chain which is useful, and I also have stored the starting point, and the goal.
I question the value of one of the changes I made to Ondřej’s code. Ondřej created a path object by feeding a function with parameters for the destination, and then when he wants to find a particular path toward that destination he feeds the path’s compute method with a starting point. This means that he could theoretically find paths to the same destination which originate from different starting points without creating a new path object for each search.
Rather than stick with his design I wrote one function which receives two points and finds a path between them. In other words, I combined the compute function and the object making function. I did this because I would rather have one function call than two, and I do not understand the circumstances in which I would want to reuse the path object. Presumably if I had several creatures each with different starting points yet all targeting the player, I would compute a path for each of them using the player’s position as their goal, but I don’t know if this improves efficiency enough to be worth it. I may discover in time that I made a bad decision, but I’ll deal with that when the time comes.