How to resolve this game problem

I have a simple game problem using A*:

We have several nodes in a tree, one node contains:

1. monster with power and it's element
2. the way link to other nodes.
3. The plus point we get after we kill this monster.

There开发者_如何学运维 are five elements: Metal, Wood, Water, Fire, Land.

Our character can only kill a monster if our element's encounter score is more than or equal monster's.

And after kill a monster we must plus all the bonus point to one element's score, we can't split them up to several elements.

goal: Find the shortest way to a specific node.

My solution: I will use A*:

heuristic: Dijkstra

find(mainCharacter,node,plusPoint) {
  // node here is the node has smallest f
  shortestWay[5] ways;
  foreach(element in elements) {
       mainCharacter->element += plusPoint;
       if (mainCharacter can beat the monster in node) {
           bestNode is node has the smallest f in node->neighbourNodes
           *ways[element] ++ << the steps, we plus point to the first element at very first path. it can be -1 if we can't go.
           find(mainCharacter,bestNode,node->plusPoint)
       }
}
Our goal will be the *ways[element] with the smallest step.

My question:

Are my solution right and good enough ?

Are there any better solution for this game ?

Thanks first :)

---

I'm not sure A* is going to allow you to do this.

The main issue here is that your available nodes change as you explore new nodes. This means it might be worthwhile to backtrack sometimes.

Example: You are at node A, which opens to B and C. B opens to E. E opens to F, which opens to G, which opens to D. C opens to D which is your destination.

B is guarded by a power 2 elemental, and C guarded by a power 4 elemental. You are at power 3. E F and G all have power 2 elementals.

From A you can only go to B and C. C is too powerful so you go to B. You could keep going around to yield A B E F G D, or you could backtrack: A B A C D. (After you take out B, C is no longer too powerful.)

So, you are going to end up doing a lot of re-evaulation in whatever algorithm you come up with. This isn't even bounded by O(n!) because of the potential back tracking.

The approach I would take is to look at the shortest route without backtracking. This is your upper bound, and should be easy to do with A* (I think...) or something like it. Then you can find the geographical paths (ignoring power levels) that are shorter than this distance. From there, you can start eliminating blocks in power until 1) you get them all down, or 2) your geographic distance required to acquire the additional power to get through the blocks pushes the distance over the upper bound.