Wish List: Routing

[Psientist]

I've played other turn-based strategy games like Civilization, Call to Power, and Warlords that have had one nice feature that reduces micromanagement: army routing.

1. select an army / commander.
2. click / drag a route to a destination, which may take numerous turns to traverse.
3. The army follows that path on its own without the player having to babysit them every turn.
4. When the army arrives, the player gets a message.


Wouldn't that be a nice feature?

[merlinme]

Yes, a very nice feature. Anything which reduces micro management is a good thing, in my opinion. However it would require building some route finding into the program (taking into account the speed of the army, any difficult terrain, whether the army has flying or sailing, etc.)

Also the programmers have to decide what should happen if the route gets blocked for some reason (i.e. a province changes hands). Personally I'd be happiest for the unit to stop moving and tell you why, rather than attempting to find another route, let alone launching an attack!

Conversely a much quicker route may open up if you capture a province, but in that case I think it's up to the player to realise and change the moving unit's orders.

Maybe we'll get something for Dominions 4...

[Graeme Dice]

merlinme said:
However it would require building some route finding into the program (taking into account the speed of the army, any difficult terrain, whether the army has flying or sailing, etc.)

This is a trivial programming problem for a system where your units don't block each other. An A* search is simple to implement, and takes into account all of these factors.

[Gandalf Parker]

That would be alot of thinking on a pbem system. Anything that carries beyond one turn would be pretty involved to put in since its just not setup for multiple turn actions. It took us forever to get simple "memory" things that just carries it over to the next turn and treats it as the same command given again with no extra thinking (like monthly casting or build queues beyond one turn).

I wouldnt mind that much thinking and file handling on an MP game. I dont care how long the hosting takes since Im usually in a "one turn a day" game. But on a solo game with lots of provinces and AIs, or a blitz game with lots of players, I think that would be too long a hosting for even me to put up with.

[Graeme Dice]

Gandalf Parker said:
That would be alot of thinking on a pbem system. Anything that carries beyond one turn would be pretty involved to put in since its just not setup for multiple turn actions.

Why on earth would you worry about saving path information between turns? You run the pathfinding algorithm every turn for every unit. Pathfinding in a system like Dominions is simple, since the best path is not affected dynamically by the current position of other units. This is especially true for a sparsely populated graph like a typical Dominions map. I'll use a concrete example to illustrate how you don't understand the issues involved. Civilization 3 & 4 are games which have similar numbers of individual units to Dominions, and which have far more densely populated graphs (8 possible movements for every single square). In a single turn of either of these games (Or just about any other strategy game), every single unit can be told to find a path to any legal destination anywhere on the entire map, with no noticeable slowdown.

Further, the real blow to your claim that pathfinding for human players would somehow add overwhelming computational time, is that the AI already performs these calculations every turn. As any player of Dom3 would be able to tell you, the "AI thinking" phase of turn generation is by far the shortest phase.

[Gandalf Parker]

I dont think civ 3 and 4 are written as pbem. Much of those games involves multi-turn actions. But I didnt say it wasnt possible. Just that its not something that the game has support for.

So you are recommending that each unit have a variable stored for a target-province (as in "I want to go to province 498") and then each turn refigure the next move to get it closer to province 498 (if its still possible that turn). And of course a message for any unit which becomes unable to complete its movement such as something taking out the connecting provinces it would have to move thru.

That would work of course. And if multi-turn tracking was instituted then there would be many many suggestions that we could get into the game. Turn recognition for map and mod commands for one thing, which would be fantastic for scenario creation.

[Taqwus]

You might also store the number of turns required based on the previous province ownership values to reach the destination. If based on a new turn's ownership values there does -not- exist a path through friendly (or flyable) provinces that takes one or more fewer turns then that estimate, then one of the following must be true:

* The army has slowed down; possible if the player has assigned slower troops to it, or if it was flying and a global storm is in effect, or so forth.

* Previously efficient paths are no longer passable; perhaps the previous route included a province which is now hostile and the army can't fly, or an underwater province and Thetis just got dispelled.

In either of these cases, warning and canceling might be reasonable.

Actually, we already know that the movement order could store an associated destination in the turn file because it already does in the event that the movement takes just one turn. The only differences, if we ignore the above suggestion about times, are that the destination be interpreted as take the fastest route to this province even if we can't reach it in one turn instead of move to this province; and that the movement order be preserved for the next turn if not preserved. *shrug*

[Gandalf Parker]

Taqwus said:
Actually, we already know that the movement order could store an associated destination in the turn file because it already does in the event that the movement takes just one turn. The only differences, if we ignore the above suggestion about times, are that the destination be interpreted as take the fastest route to this province even if we can't reach it in one turn instead of move to this province; and that the movement order be preserved for the next turn if not preserved. *shrug*

That makes sense. At the moment it does things in a pbem way. I put my "I want to" into a .2h file (to host file) which is then absorbed, processed, and the results are kicked out to a .trn file (turn file). Any changes to the map are written to the fthrlnd file (fatherland) on the host server. Alot of that is invisible to any that isnt running a server but it defines the pbem starting basis of the game.

So far we have gotten some nice benefits from the game being changed to save an order that it got in the .2h file and send it back as a pre-set order of the same unit or province in the .trn file (monthly casting, queues, etc). I suppose the "where I move next" might be restored to the same unit as the default "where I move next" if the game is set to refigure the path each time. It might even turn off the "if move is possible" check which would allow me to say "move to 495" even if no route is available when I give the command. The army would continually try to go there until eventually it becomes available.

Id LOVE to see real multi-turn memory be written into the game. Many of my dreams are involved with the game being able to store a command for the future. At the moment the maps and mods commands are all "set it up at the beginning of the game" stuff. It would be a blast if we could get turn recognition or time-passed recognition into some of the commands. Such as "on turn 30" or "after 10 turns".

[Graeme Dice]

Gandalf Parker said:
I dont think civ 3 and 4 are written as pbem.

Which is relevant, why, exactly? There is absolutely no fundamental difference in how you would store a unit's destination just because you happen to transmit orders via a file rather than directly into the hosting computer. Every unit in Dominions already stores which province it is attempting to move to next turn out of necessity, which is all that's needed for a pathfinding algorithm to send the unit on a long term trip.

[PaoloZ]

I agree with Graeme. It is not a hard task. A* should solve the problem quickly as the adjacency graph of the map is quite simple. The destination of an army is already stored, so it has to be changed the way the value is used and kept between turns (at the moment it is wasted every turn).

How the AI plans an attack?
I mean: if the AI has to attack your lands with an army assembled at their home province (assuming a distance greater than 1 between their home land and your lands), doesn't it plan a course?
Is this not pathfinding (maybe it's a greedy algorithm)?

The AI does not seem to push its armies around in a random pattern.