Are there any pathfinding algorithms that would handle different movement types?

I'm developing a bot for a BattleTech board game simulator http://en.wikipedia.org/wiki/BattleTech, it is turn based.

The board is divided into hexagons, each one has a different terrain type and elevation. You drive a robot which moves over them, to destroy other robots.

I only know Dijkstra and A* pathfinding algorithms, but the problem is that there are 3 types of movements: walk, run and jump several hexagons (each of them have their own rules). Walk and run are almost the same.

The best path could be a combination or each movement type. Here is an example of map http://megamek.info/sites/default/files/isometric_view.png

Do you know a good algorithm for this complex pathfinding or a way to combine A* results for each movement type?

• I think this is often handled by some clever manipulation of a weighted path with A* (weight being the cost of that path/square). For example, if jumping is preferable, it gets a lower weight (eg. 5) than walking (eg. 10). Aug 26, 2013 at 11:34
• How exactly do the three types of movement differ? Can they be combined (walk to tile A, then run to B and then jump to C in the same turn)? When yes, what are the rules which prevent the player form always using the cheapest method to get from tile A to tile B? Aug 26, 2013 at 11:59
• @Philipp Yes they can be, when using A*. You can add every tile you can move to with every movement type to the open list, then based on the price of each one + a good heuristic you can determine which one to progress further on. Aug 26, 2013 at 12:03
• @Philipp No, you can use only one type of move each turn. Aug 26, 2013 at 15:52
• Walk: move through the hexagons with little difference in elevation. Run: the same but you can go far, although you will generate heat and lose accuracy shooting (so it's not always the best). Jump: you can jump obstacles (a wall or river) instead of around them walking. Aug 26, 2013 at 16:01

Both Dijkstra and A* can add different costs to the edges (=connections) from one tile to another. They also allow to connect two nodes (=tiles) with more than one edge, each one with a different cost.

The alternative jump-mode would mean that there is an alternative direct edge from each tile to each tile in jump distance. But because a mech can either walk or jump in a turn, the cost for using this edge would be the move points of a whole turn, plus the remaining points of the current turn when there already was a move this turn.

According to your description, the decision for walking vs. running does not make much of a difference regarding path choice, but it rather seem to be a strategic decisions to make. The actor definitely can walk when the destination can be reached in the current turn without resorting to running. But otherwise there are many factors to factor in, like:

• current heat level and likeliness of being involved in combat before being able to cool down
• difficulty of any shots which need to be fired this round
• how strategically important it is to reach the destination quickly

There is no hard rule for making this decision. The best you can do is to use a heuristic approach. Assign positive or negative point values to all circumstances, add them up, and see if the result is positive or negative.

There is also another factor in pathfinding you should account for: Under some conditions it could make sense for a mech to avoid ending its turn at certain locations. When in a danger area, using three turns to get from A to B but ending each one in cover might be better than using only two, but being exposed at the end of each. Or maybe not. It depends on the circumstances and the exact game mechanics. This, again, is a strategic decision you have to make based on heuristics. You could represent this by adding an additional cost to edges which end the turn on a dangerous tile to discourage the AI from making this move.