A* Pathfinding project as Decition Tree


I’m writing a turn based game and I need a decision tree system for my AI. The idea is to make AI player create a tree by chaning all his possible actions for a current turn and then search through this tree for the most optimal route. That’s how basic turn-based AI is written.

Naturally, all I need is a point graph with custom nodes, based on action types and A* algorithm to find the most productive route. What I want to know is how performance demmanding the A* Pathfinding Project is for this kind of job? As I imagine, it’s just your ordinary graph and search algorithm. It is not necessary intended for spatial navigation and I can use it for other purpouses? Or is it intended only for path finding and I should search for more generic options?

Thank you!


Well, you can use the A* Pathfinding Project for this. However since you are already going to have to construct all the possible actions for the AI at each turn, then using A* to search through them will not make it much faster compared to a simpler technique such as BFS or Dijkstra as it is likely to be bottlenecked by constructing the tree.
If you already have a way of constructing the tree, dijkstra can be implemented from scratch in 20 lines of code or something like that.
If your tree is very large you might not even want to generate the whole tree at once, but only generate the parts that the search visits on the fly. If you need this, then unfortunately this package cannot help you as it requires the whole graph to be constructed up front (as with most things, it is technically possible to get around this, but it is a bit hacky).