Turn Based Strategy Movement

If you are using A*, then assign the water a different value if there is a transport available.

Under the A* Pathfinding, assigning different G values to the terrain, and keeping the H heuristic admissible, will find the perfect route every time. There's a couple of things to note about using transports: At the node where a transport can be invoked, each subsequent child node added to the open list should check if it was in the transport at the parent node, to alter the G values. Because they would have a better G value, these nodes have to displace any existing nodes for the location on the open list. This means you can't use a priority queue, and may have to find a better alternative, such as a hashmap.

One of the complicating factors in this is that, if the transport is not at a boardable location (e.g. the middle of the lake, etc.) at the time that the pathing is done, it may not be considered. The A* routine would somehow need to check to see if the transport can get to a rendezvous point either before the agent or within a reasonable amount of time, incorporate any delay that would result, etc. That starts to smack of a planning algorithm rather than a pathfinding one (despite them being similar, there is a significant difference).

I can remember how it was done in Red Alert with the transports. When you selected a set of units, the pathfinding system found a rendezvous point that the transport and the unit you selected could both reach.

This can be done, I imagine, by finding the shortest path from the transport to those boarding it, and then set the rendezvous point to one of the "shoreline" tiles, where both ships and land vehicles can go. (in Red Alert these were sandy beaches.)

As for the problem of finding the fastest route, simply give each type of vehicle a constant for its speed over different tiles, and allow the a* algorithm to scan right to the end of each path. This will be costly, but only necessary for amphibious vehicles.

I think the problem comes, however, in the units deciding that they need to "call" the available transport and say that they need to use it. As players, we would view that as two separate actions. 1) I need to move the unit, so 2) I need to move the transport. The AI needs to be able to include the possibility of the transport in the pathfinding calculation. In order to do that, it needs to include the movement of the transport without the unit as a parallel step to the initial movement (and/or waiting) of the unit. That's where the complexity comes in.

The easiest solution to that, I can think of, is labelling the nodes as transport available nodes. Alternatively, I suppose that the unit could scan for any transports available whenever the direct route is blocked by a body of water. A query to whatever system stores the list of units for any transports, followed by a scan of the result for any transport in the same body of water, possibly even followed by another query for how busy the transport is. The unit can they "weigh up" the different options for getting to its destination, with a bit of random data thrown in to simulate fuzzy logic.


btw, I've long considered a system where the level designer does the "object recognition" of landscape elements and each tile can belong to one or more of these "objects". The membership of the tiles to these objects can then be used within a finite state machine, to simulate object recognition within the game at little to no extra cost. the transport would then know which lake its "in", the land unit would know which lake it needs to "cross" and the only query needed woudl then be "whoes in this body of water and available to transport me"

Thanks for the help, guys. Sorry it took me so long to respond, my internet connection is spotty over Christmas break.