Leonardo RD's blog

In order to implement the hierarchical pathfinding algorithm (hpf), I needed to create a graph representing the portals in a map, and then find shortest paths between pairs of points in this graph. Since CEL already has a graph implementation that meets these requirements, I decided to use it. However, I did find a few points where some changes had to be made to the code, as well as some bugs. Here is a list of all the changes (besides bugfixes):

• Added a weight element to iCelEdge - Since the graph implementation was used for navigation, it was safe to assume the weight (or cost) between two nodes would always be the euclidean distance between then. This is not the case for hpf, however.
  The weight can be set using the edge's setter method, or using the new overloaded version of iCelNode::AddSuccessor(), which takes the weight as a parameter. The old version will still consider the weight to be the euclidean distance between the nodes.
• Added a way to remove edges and nodes from the graph - Nodes can be removed using iCelGraph::RemoveNode(), while edges can be removed by either using iCelGraph::RemoveEdge() or iCelNode::RemoveEdge(). The methods used to create nodes and
  edges were also changed to return the index of the added element.
• Added a way to create a new node for the graph - Nodes in a graph can now be created using the method iCelGraph::CreateEmptyNode().

Besides those changes, I also made an alternative implementation of the A* algorithm, since the one found in iCelGraph::ShortestPath() looked unfamiliar to me (meaning I don't belive its correct, but I'm not sure). It's possible the differences are due to some optimization I don't know about, but hpf already had a lot of issues to check, so I decided to be on the safe side. This new version of A* was based on this article and wikipedia. I believe it is the most general version of the algorithm, and it should present no problems. For now, I left this new implementation of the A* algorithm in iCelGraph::ShortestPath2(), as an alternative to the old one.

One important difference about the old A* implementation and the new one is that the path returned by the former doesn't contain the starting (current) position, while the later contains both the starting and ending position. I decided this was important, since the path could be inverted, in which case the destination could be missing.

Do note that none of these changes will break existing code that uses the graph plugin.