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):
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.
No Comments/Trackbacks/Pingbacks for this post yet...
|<< <||> >>|