Impoved pathing algorithm

Brainstorm ideas of possible additions to the game. Read this before posting!

Moderators: Forum Moderators, Developers

Forum rules
Before posting a new idea, you must read the following:
Post Reply
WizardMagus
Posts: 34
Joined: September 10th, 2006, 11:06 pm

Impoved pathing algorithm

Post by WizardMagus » June 14th, 2007, 7:15 am

There are many times I find myself with a large army that is very far from where it needs to be. For instance, I have just finished off one enemy, but my next enemy is across the map. In these cases, I would like to have my army be able to move intelligently over long distances without me having to worry about them, so I can focus on other areas of the map.

However, I have noticed a couple problems with the current pathing implementation:

I) There does not appear to be a logical order in which the computer will move your units. I do not know how it is currently decided now, but it is not optimal by any means. Oftentimes I will have a unit way in the back move a couple hexes until it hits someone in front of it - then the person in front will move afterwards, and the rear unit is left with unused unit points (even though its crystal ball shows up as red) while it still has many free hexes to go. A similar problem crops up when units with 6 move get stuck behind units with 5 move forever, for example. Every turn the 6-move unit wastes one move, while the 5-move unit could waste one move for one turn and never impede the 6-move unit again.

II) The units select the most efficient possible line from point A to B, and refuse to deviate from this path. This becomes a problem when you are moving any significant number of units. They begin to form a single-column line - and given the above problem, this results in it being unable to move very quickly at all. If they would instead be able to consider a slightly-less-efficient path, and branch out into two or three columns, the whole army could move more quickly.

Right now, the pathing is so bad that I have given up trying to let the computer move my units. I take so long double-checking and correcting the computer that I save time moving them myself.

Is there any particular reason why it works the way it does now? I know that we want to keep the AI simple enough that it does not begin to bog down the computer, and I have not programmed in years and never in Python, but it should not be too taxing on the computer. Here is my general idea for some heuristics that I do not believe would be too taxing:

1) First, units with the highest movement move before slower ones - this means that quick units will rapidly get in front of the slower units causing the roadblocks, and reach their objective the fastest. If you want your army to move as one block, you can always slow down the fast units, you can't speed up the slow ones.

2) Second, units closer to their objective move before distant ones - this prevents a lot of wasted movement points, when the rear units only move a couple of spaces, before the vanguard gets to move at all. With this in place, the whole column would be able to move intelligently instead of the current stutter-step.

Pitfall: With higher movement units coming before closer units, you can wind up where a high-move unit in the back of the column will not be able to advance as much as it could otherwise hypothetically move, wasting movement points. The third step below partially mitigates this, although I think something creative could be done beforehand... The computer could check and see if any other unit were standing on the current unit's eventual destination and move that unit first, but I think that is beginning to increase the complexity since that would necessitate an entire movement tree.

3) Travel along the most efficient path as already defined - until you hit another unit cluster, and you still have movement points left. At this point, search adjacent hexes for alternative routes (this does not have to be extremely intelligent or complicated, just enough to make the units file into multiple columns). Even if you only have a single movement point left, you can still move to the side and allow the unit behind that one to move one space closer to its destination. This will always help the entire column's movement, even if it will sometimes break even for individual units.



I think that this could greatly improve the capacity for the computer to move large armies across long distances. Any thoughts/suggestions/improvements? Any obvious flaw I am missing that completely destroys the idea? Do the coders out there think that this could be reasonably implemented?

rrenaud
Posts: 34
Joined: February 8th, 2006, 5:43 am
Contact:

Post by rrenaud » June 14th, 2007, 1:45 pm

I agree with you. I think your heuristics are nice. I brought the multiple unit path finding problems up in IRC a few months ago. The general sentiment was that when you need to move a large army uncontested through a big area, it likely represents a flaw the the underlying scenario. If you take a step back from the path finding problem think about it, in general it's just not fun to be moving your army around without any enemies to battle. My particular grief was about the HTTT map where you are in a big, long randomly generated cave. I heard this map be fixed, but I haven't played it since.

BTW, I am pretty sure all the path finding code is in C++. I don't know if that makes you any more willing to try to patch it :).

Darth Fool
Retired Developer
Posts: 2633
Joined: March 22nd, 2004, 11:22 pm
Location: An Earl's Roadstead

Post by Darth Fool » June 14th, 2007, 3:46 pm

The current algorithm is very simple. In the future, there will be an AI that will have various WML configurable ways to adjust how it chooses to move units and so should be able to do some more sophisticated path finding than is currently possible. That said, I don't have any intention on making the more sophisticated path finding available to players. They can already micro-manage their units paths if they want to, and the User Interface for all the options would be an ungodly mess.

deoxy
Posts: 208
Joined: May 16th, 2007, 5:22 pm
Location: Texas

Post by deoxy » June 14th, 2007, 4:34 pm

Another solution would be to have the computer move all units 1 space at a time, starting with the closest one.

That is, as a player, I can move a unit one space, move a different unit, then move th first unit AGAIN. Allowing the computer to do this might be helpful.
Insert nifty witticism here... if only I had one.

rrenaud
Posts: 34
Joined: February 8th, 2006, 5:43 am
Contact:

Post by rrenaud » June 14th, 2007, 4:50 pm

What is the concern with the UI? Is the concern that you can't now promise to show crazy long path to a user, because you may change it slightly to accommodate a hoard of units?

The problem is forcing the player to make boring micromanagement path finding decisions to route a large army over a long distance. This is a tedious burden on the player which can be improved algorithmically.

WizardMagus
Posts: 34
Joined: September 10th, 2006, 11:06 pm

Post by WizardMagus » June 14th, 2007, 6:58 pm

Darth Fool wrote:The current algorithm is very simple. In the future, there will be an AI that will have various WML configurable ways to adjust how it chooses to move units and so should be able to do some more sophisticated path finding than is currently possible. That said, I don't have any intention on making the more sophisticated path finding available to players. They can already micro-manage their units paths if they want to, and the User Interface for all the options would be an ungodly mess.
I am definitely not proposing to allow the user to define AI movement by any means. I am asking for a couple simple heuristics that allow it to move units with vastly improved efficiency. The player would never even know they were there.
rrenaud wrote:The general sentiment was that when you need to move a large army uncontested through a big area, it likely represents a flaw the the underlying scenario.

BTW, I am pretty sure all the path finding code is in C++. I don't know if that makes you any more willing to try to patch it :).
I agree that could be a flaw in the scenario in many of the cases, but at the same time I don't think that is always the case. Right now I am playing Northern Rebirth, which has some of the best level ideas I've seen. The second map is great because you can travel between the left trolls and middle skeletons by means of "hidden passages" you find, allowing your units to instantly become relevant again. But think of the fourth mission, where you send people down several different pathways, and only half of them wind back around towards your ultimate objective. The rest have to play catch-up for several turns. Another time I experience this is a large MP map, where you kill one player but have to travel several turns to get to the next.

I heard that the AI was in Python, so I just assumed the pathing was part of AI. C++ is more encouraging, but I haven't programmed a game in C++ in at least five years. I don't think I have the time to pick it back up on that level. :?
deoxy wrote:Another solution would be to have the computer move all units 1 space at a time, starting with the closest one.
First of all, faster units must move before closer ones, and I think I laid out the justification for that above. Second of all, to move the units one at a time seems to be a little bit futile and time-consuming. If we are going to use that much CPU power, then we should just use my movement tree above. I could lay out some general heuristics for that as well if people are interested...

Post Reply