I'm one of the people who love your combat system. I think this system is part of your vision, and I don't want that to change.



But there are still irritations, largely due to strange pathfinding by units. I think that if you dealt with these pathfinding oddities, combat would be much more intuitive. And I think a lot of people who think that they don't like your combat system would discover that, in fact, it's a pretty cool system.



First, the problems. I'm going to number them so I can list solutions later.

• 1) You line your units up and give them some attack orders on the enemy line, with some focused attacks. They should run forward and attack, maintaining their line, but one of the units runs diagonally across the field to his target, and everybody's orders get screwed up.
• 2) You've got a nice little war going on at a chokepoint. You want your units to maintain the line or advance if there are any casualties, so you give attack orders to your units that are behind the line. But, instead of lending morale support when nobody dies, those units race halfway across the map to the other chokepoint, where nothing much is happening, in an attempt to get behind the enemy. If we wanted them to race to that chokepoint, we would have given a move order.
• 3) You give an attack order, on aggressive stance. You figure, "Even if my target dies, my unit will attack something, right?" But your target gets surrounded by enemy troops and impassible terrain. Your unit just sits there twiddling its thumbs.
• 4) You're focusing fire to take out a particular enemy unit, and he dies! Callooh callay, oh frabjous day! But your next unit, denied his ordered target, charges through the opening deep behind enemy lines, pursuing some distant target that he can't reach, that leaves him stranded behind enemy lines.
• 5) You want to move a small distance to a particular tile, then attack a particular enemy, to take advantage of terrain. But your enemy moves. Your unit moves-- then stands there, even though it has remaining movement.
  
  

All of these problems can be fixed by small changes to your code. The especially good news is that fixing these problems doesn't affect your vision or any particulars of combat.



I'm assuming that you're using A* pathfinding, because it's well examined and works great. There's only one problem with it: it doesn't do a good job of delivering every path. It stops when it finds the first good path.



But you don't have to change your pathfinding algorithm to find all good paths. You just have to run it more often. Instead of pathfinding to the enemy, you pathfind to every hex adjacent to the enemy (that can, itself, be pathed through to the enemy.) Running pathfinding more than once is fine, for your game, because pathfinding over 77 (sometimes a few more) nodes is a relatively quick, easy job. You don't have to worry much about the computation involved.



Which is good, because to fix some of these problems, you'll need to run your pathfinding with different parameters. Currently, it appears as if Endless Legend runs pathfinding once for each unit each phase, treating enemy units as impassible terrain. But to fix some of these problems, you need to run it again, treating enemy units as passable terrain.



The final change is to let your units' facing influence their final path. We know that facing has nothing to do with combat (although it exists for the sake of your models). But facing is an intuitive concept to players. We think a unit ought to move in the direction its facing, and we expect it to move forward rather than sideways if both would achieve the same end. That's why we get a little irritated when our lines run diagonally across the field.



(There are also several problems that strike me as unintentional bugs-- movement in Hold Ground stance, reassignment of target in new phase, stuff like that. Those needsto be addressed, but since they seem like code bugs, I wouldn't know how to address them myself.)



So the solutions:

• 1) Make units prefer paths that move in the direction of their facing.
• 2) and 3) When the path is larger than the unit is capable of in a single turn, run path again, ignoring friendly and enemy units, and follow that path until you can follow it no longer.
• 4) When the original target is no longer valid, prefer new targets close to both your position and the position of the original target.
• 5) When a unit has been given a move+attack order, consider the attack order exactly as if a basic attack order had been given, just with fewer movement points available due to the initial movement.
  
  

Here's a detailed flowchart:

[code]

I) If unit has only attack/support orders:

A) If target is within range

1) Attack (or support) target

B) Else if target is alive: create a list of hexes that lie within range of the target

1) If any of these hexes are reachable in this turn

a) Sort the list by theta (angle between unit's facing and target tile) and move to the most forward tile. In case of ties (or close values, consider giving 30 degrees leeway), pick the closest tile (in terms of distance, not in terms of pathfinding cost). Move there and attack/support target.

2) Else if none of these hexes are reachable this turn, create a new list of tiles that lie within range of the target and are reachable this turn when ignoring friendly and enemy units blocking path

a) If any of these new hexes are reachable this turn, move as in IB1a until path is blocked

b) Else if no hexes from either list are reachable this turn, use the path generated by the first pathfinding run, preferring the path with the least cost in MP (remember, we've got up to six paths in each list)

i) If any target is within range, attack/support. Prefer targets lying in the same direction the unit is facing, then prefer close units, then prefer whatever (your current algorithm).

ii) Else if no target is within range and the unit is support, try again on the other player (either attack or support depending on unit's original orders)

C) Else if target is dead: make a list of alive targets

1) Sort that list in terms of (distance to unit)+(distance to original target at start of phase) and pick the one with the lowest value. (We want the unit moving in the same general direction as originally ordered.)

2) Run according to I above on new target

II) If unit has move orders or compound move-attack/support orders:

A) If no path to target hex exists

1) Rerun path to target hex, ignoring friendly and enemy units

a) If no path exists, do not move. (The tile cannot be pathed to, ever.) If any targets lie within range, pick the closest, frontmost one and attack/support it.

b) If new path exists, follow it until blocked by a friendly or enemy unit. If any targets lie within range, pick the closest, frontmost one and attack/support it.

B) Else path to target exists, move to that hex

C) If no compound attack/support order has been given, make a list of targets within range, pick the closest, frontmost one and attack/support it.

D) Else a compound order has been given.

1) If unit has hold ground or defensive orders, make a list of targets within range, pick the closest, frontmost one and attack/support it.

2) Else unit has aggressive orders. Move to (with remaining movement points) and attack/support target as in I above.

III) If unit has no orders

A) If unit is in aggressive stance, pick the closest, frontmost target and attack/support it as in I above.

B) If unit is in hold ground stance, pick the closest, frontmost target. If it is within range attack/support it.

C) If unit is in defensive stance, make a list of all hexes reachable by that unit.

1) Run pathfinding from each enemy to each hex. Sort this list by the lowest cost of any unit to each hex, then pick the hex with the highest of these costs. In case of ties, prefer the closest, frontmost hex.

2) If any targets lie within range, pick the closest, frontmost target and attack/support it.

[/code]

natev wrote:
But you don't have to change your pathfinding algorithm to find all good paths. You just have to run it more often. Instead of pathfinding to the enemy, you pathfind to every hex adjacent to the enemy (that can, itself, be pathed through to the enemy.)

This sounds great to me. In most battles, I just want my units to do damage to someone if they can't reach their target. I don't want them trying to make a 3 or 4 turn trek through forests and around cliffs to reach the target they're aiming for, who will have moved by the time they get to where they were originally going. I try to use "hold position" to achieve this goal, but it obviously doesn't always work out.

Hi Natev,



Thank you for your great feedback. We might sum up the issue by saying:

The player expects a specific behavior for a targeting unit, but this unit has a different behavior.

When a unit doesn’t go straight for their target but attacks from another adjacent tile, it’s because this tile is considered by the AI as more interesting than the tile between the unit and the target.

We could solve this issue in two ways:

• By reducing the AI’s smartness (only for the player). With simpler decisions, the player will be more able to anticipate their units’ behavior.
• By increasing the feedback. For example, we could add a marker to show the player where the unit is going to go before attacking its unit.
  
  

Which solution seems the best to you? Personally, I prefer the second one even if it comes with new issues.



Right now, we could add two improvements without even working on what has been previously said:

• We could make the unit go straight for their target even if the target is totally surrounded by other units (instead of not moving).
• It’s perhaps possible to make the unit take in consideration their allies’ paths. Currently, a unit individually computes their path without taking into consideration how many allies are targeting the same target.
  
  

What is your opinion?

Wow, thanks for reading!

Manu wrote:
Hi Natev,

When a unit doesn’t go straight for their target but attacks from another adjacent tile, it’s because this tile is considered by the AI as more interesting than the tile between the unit and the target.

We could solve this issue in two ways:

• By reducing the AI’s smartness (only for the player). With simpler decisions, the player will be more able to anticipate their units’ behavior.
• By increasing the feedback. For example, we could add a marker to show the player where the unit is going to go before attacking its unit.
  
  

Which solution seems the best to you? Personally, I prefer the second one even if it comes with new issues.

I prefer the first solution. I don't think that we, as players, expect much intelligence from our units. We expect them to follow our orders simply. We expect them to not do anything "crazy" (from our human point of view) when they don't have valid orders. Any attempt to make individual unit AI "smart" is going to make their behavior less intuitive to the player. (That said, it takes a certain intelligence to replicate behavior that we humans would see as simple and dumb.) When we need complicated behavior from our units, we are able to deliver it in the form of compound move+attack orders.



There are two problems with the second solution. One is that it adds visual clutter to a screen that's already teetering close to visual overload. The other problem is that it does nothing to improve situations where the AI has orders that it can no longer follow. I think that "strange" behavior by units in the absence of valid orders is responsible for more frustration than strangely executed valid orders, although both are important.

Right now, we could add two improvements without even working on what has been previously said:

• We could make the unit go straight for their target even if the target is totally surrounded by other units (instead of not moving).
• It’s perhaps possible to make the unit take in consideration their allies’ paths. Currently, a unit individually computes their path without taking into consideration how many allies are targeting the same target.
  
  

What is your opinion?

I think the first (aggressive behavior in the absence of unblocked path to target) is very important to implement. Your battle system shines when dealing with formations, chokepoints, and variety in damage/life ratios, and that means that the problems associated with this occur frequently.



I don't think the second is important, and might not be a good idea to implement ever (for the player's unit-based AI-- army-wide AI definitely needs to take allies' paths and positions into account). It leads to behavior unpredictable to the player. It's a little like a new electronic device that thinks its smart enough to know what you want and when you want it, yet never is, if you can forgive the simile



I appreciate the great effort you've put into making a game that has occupied my mind like few before it. Again, thank you so much for taking the time to consider my suggestions.

natev wrote:
I prefer the first solution. I don't think that we, as players, expect much intelligence from our units. We expect them to follow our orders simply. We expect them to not do anything "crazy" (from our human point of view) when they don't have valid orders.

The problem with this solution is the subjectivity. How can we guess what the player is expecting of their unit? Even if the global behavior gets simpler, there is still the risk to make the player unable to anticipate a unit’s reaction to an enemy movement. And what could be logical for someone could be crazy for someone else.



With an upstream feedback, we can at least tell the player where their unit is going. If they disagree, they can use the manual position order (right click) then the target order (ctrl + right click). But new problems come with this solution. Since it is an upstream feedback, we cannot guarantee the final position will be the showed one. We can only tell the player: "The unit will try to attack this target and will try to go to this position (which you can change by a manual order). If they cannot follow this behavior, they will improvise something (which should be smart)."

just give me some indication of which 36 initiative dude is going to move first and i'd be happy. =)

Manu wrote:
And what could be logical for someone could be crazy for someone else.

It could be, but I don't think it will be. I think most people will agree on logical behavior.



I think that the way to test this is to print out a few battlefield positions with orders. Say, "Here are your units. Here are the orders you gave them. Where do you expect them to go?" Hand them around the office. See how much variation exists in the answers you receive. It's better if the people being tested have a familiarity with the game, but are not experts, or else they'll be biased by their knowledge of how units actually do behave. Make sure people know it's just to gather their feelings or they'll overthink it



You're right that the behavior of units that are acting after another unit will always be capable of something the player wasn't expecting. That's an important part of the challenge and fun of the system. But not all unanticipated actions are equal. When circumstances change, humans expect behavior similar to the orders given. The rules behind your battle system are simple enough that something like similarity can be achieved fairly easily. Again, this is something you can research by handing out "puzzles" at the office. Here are your orders. Here is the new position of enemy units. Where do you expect your units to go? I listed above the factors that I believe lead humans to consider certain moves similar, basically just similar distance and similar direction, but you might want to see what other people believe before acting on that.

With an upstream feedback, we can at least tell the player where their unit is going. If they disagree, they can use the manual position order (right click) then the target order (ctrl + right click). But new problems come with this solution. Since it is an upstream feedback, we cannot guarantee the final position will be the showed one. We can only tell the player: "The unit will try to attack this target and will try to go to this position (which you can change by a manual order). If they cannot follow this behavior, they will improvise something (which should be smart)."

I think, that with your upstream feedback, you are talking about a particular situation: a player-controlled unit, on aggressive stance, is given a simple attack order to attack a unit in range. There is a more "interesting" tile from which it can launch the attack than the one on which it is standing. Should the unit move to the interesting tile before attacking? If so, should that predicted behavior be shown on the orders screen so that the player will be able to halt it (in this case, by switching the unit's stance to "hold")? And you're saying that the answer to the second question is Yes! But I believe the answer to the first question is No! so the second question doesn't even matter.



If the AI can make the decision that a tile is more interesting and should be moved to, then the player can make that decision as well-- move here, then attack. And that maps more intuitively, more directly, to the player's mind: the fewer orders the player gives, the less complicated the unit's behavior. As opposed to with the smart unit: the fewer orders the player gives, the more complicated the unit's behavior; the more orders the player gives, the less complicated the unit's behavior. Even if you somehow make unit AI smarter than the player, the player doesn't like feeling second-guessed by his or her own units. During my games, I find myself saying, "If I wanted you to move there, I would have told you to move there."



But I'm getting the feeling that part of the difficulty in this is that unit-based AI and army-wide AI are not fully decoupled. Is that the case? Does army-AI give compound move+attack orders, or is it operating in a different mode than the player?

First off, thanks a lot natev, for providing some great suggestions.



A couple thoughts...



Facing: Unless facing means something and the game allows players to have some control, it absolutely shouldn't influence any AI decisions. In effect you are taking something that the player has no control over and making it important, which is frustrating to players.



Shortest Distance vs. Best Position : Your suggestions do not consider Morale and Terrain bonuses, just distance. These things should factor into the equations. I'm not suggesting that the AI should always select the hex with the best attack bonus (which I suspect it currently does) but it should be a factor.



Selecting Targets Near Original Target : I agree that if a target is unreachable, the AI should give weight to targets near the original goal.



Wasted Actions : One problem (I'm sure the devs struggle with) is units wasting actions. If a unit cannot fulfil it's orders, does a player prefer that the unit:



[LIST=1]

Take initiative and do something (Attack/Heal) and potentially heavily deviate from the original orders

Not attack/support for the round but stick to the letter of the order.

[/LIST]

The answer is always "it depends", but generally I prefer #1. Combat is on a clock and losing an action is a big setback. The problem is more pronounced for Melee units as a Move & Target order with Hold Position, which works for Ranged, can result in a lot of non-attacks for Melee units.

natev wrote:
I think, that with your upstream feedback, you are talking about a particular situation: a player-controlled unit, on aggressive stance, is given a simple attack order to attack a unit in range. There is a more "interesting" tile from which it can launch the attack than the one on which it is standing. Should the unit move to the interesting tile before attacking? If so, should that predicted behavior be shown on the orders screen so that the player will be able to halt it (in this case, by switching the unit's stance to "hold")? And you're saying that the answer to the second question is Yes! But I believe the answer to the first question is No! so the second question doesn't even matter.

I think you may be misleading yourself by failing to consider more complex situations.



If I give a unit an attack order but no move order, and its target is outside its attack range, should it move closer so that it can attack, or should it stay where it is because I didn't give it a move order? I think most people would overwhelmingly prefer that it move so that it can make the requested attack. That means that the absence of a move order cannot be interpreted as an order to not move.



Giving your units explicit move orders can sometimes be very helpful, but it can also be very risky if the enemy has higher initiative than you. You think he's going to move to location X, which means you want your archer to move into the forested city tile at location Y for attack and defense bonuses and make a ranged attack against him. But it turns out your target moved to location Z instead, and now if your archer goes to location Y it won't be able to attack anything at all. Even if you anticipate this problem, you can't give contingent orders that change based on what the higher-initiative enemy does. Units need to react flexibly because you don't know what the battlefield is going to look like when it gets around to their turn.



Other than the strange issues with units simply not attacking even when they obviously can, I think the most frustrating issue I've seen is units blocking each other. You order units A and B both to attack unit E. Unit A can only attack unit E if it moves to tile X. Unit B can attack unit E if it moves either to tile X or to tile Y. "Obviously" A should move to X and B should move to Y so they can both attack E. But unit B happens to have higher initiative, and it happens to move to tile X, unnecessarily blocking unit A and thereby wasting unit A's turn.



I think this is what you're getting at with this complaint:

natev wrote:
1) You line your units up and give them some attack orders on the enemy line, with some focused attacks. They should run forward and attack, maintaining their line, but one of the units runs diagonally across the field to his target, and everybody's orders get screwed up.

Unfortunately, figuring out in advance that unit B is going to block unit A if it moves to tile X but not if it moves to tile Y is computationally complicated in the general case. The standard way of doing that would be a tree search of all possible future moves (through, in this case, the end of the current round), but I'm guessing that's too expensive to be a reasonable solution in EL (at least in large battles)--a single unit could plausibly have 10 movement options, a large battle with reinforcements could include 20+ units, 10^20 = way more combinations than you can search in a reasonable time.



I suppose you could tell the units to always run straight towards their target, and that would solve the specific example you gave, but probably at the cost of making them behave even worse in virtually all other situations. You're functionally saying that a lone archer should charge into melee even when it could kite, which I think many players would regard as an insane default strategy.

Antistone wrote:
If I give a unit an attack order but no move order, and its target is outside its attack range, should it move closer so that it can attack, or should it stay where it is because I didn't give it a move order?

If it is on aggressive stance, it absolutely should move. I don't see anywhere where I said anything to suggest that it shouldn't.

Giving your units explicit move orders can sometimes be very helpful, but it can also be very risky if the enemy has higher initiative than you.

Which is part of why I made recommendation 5 in the opening post, which would go a long way toward alleviating that risk. It would still allow higher initiative, equal movement units to sometimes escape the fray from a unit given a compound order, but that seems appropriate to me.

Other than the strange issues with units simply not attacking even when they obviously can, I think the most frustrating issue I've seen is units blocking each other. You order units A and B both to attack unit E. Unit A can only attack unit E if it moves to tile X. Unit B can attack unit E if it moves either to tile X or to tile Y. "Obviously" A should move to X and B should move to Y so they can both attack E. But unit B happens to have higher initiative, and it happens to move to tile X, unnecessarily blocking unit A and thereby wasting unit A's turn.

I personally don't have a problem with this. I mean, it occurs, but I consider an extra turn to join the fray to be an appropriate cost to running tight formations.

You're functionally saying that a lone archer should charge into melee even when it could kite, which I think many players would regard as an insane default strategy.

No, I think you may have misunderstood me somewhere. A ranged unit on aggressive stance would close until its target is within range. A ranged unit on defensive stance would retreat to a position furthest from all enemies, and then fire if it had range to any enemies.

So this may be impossible.... but could you have an option where you removed the majority of need for pathfinding?

Instead of issuing orders at the beginning of battle, you issue orders for each unit as its turn comes up?



This could be a separate option, so if people wanted to play the old way they still could.

Thank you for all your contributions. We’re going to think about this and try a few things. To answer your questions:

natev wrote:
But I'm getting the feeling that part of the difficulty in this is that unit-based AI and army-wide AI are not fully decoupled. Is that the case? Does army-AI give compound move+attack orders, or is it operating in a different mode than the player?

The army-wide AI only exists at the beginning of each turn when it needs to choose a strategy for each unit. Please note that this part is still a work in progress. For now, 99.9% of the AI’s smartness is into the unit-based AI (but this may change in the future).



The unit-based AI can do two main tasks: choose the best target in a set of targets (let’s call it the Targeting Algorithm), and choose the best position in a set of tiles (let’s call it the Tile Algorithm).



The Targeting Algorithm is based on many factors (remaining life, comparison between both units’ attributes…) including how many allies are around or targeting a specific enemy. If the targeting unit is the first one to play, they cannot know how many of their allies will follow.



The Tile Algorithm is quite similar. It is called each time the unit has to move. It searches for the best tile close enough to the target according to the altitude, the terrain type and, amongst other stuff, the neighbors. This means the first unit to choose cannot evaluate the neighbor factor because nobody has moved yet.



So when you see all the units running and targeting a same enemy, this is not because of an army-wide AI developing a Machiavellian strategy; this is thanks to an emergent behavior from all the unit-based AIs.

Antistone wrote:
Unfortunately, figuring out in advance that unit B is going to block unit A if it moves to tile X but not if it moves to tile Y is computationally complicated in the general case. The standard way of doing that would be a tree search of all possible future moves (through, in this case, the end of the current round), but I'm guessing that's too expensive to be a reasonable solution in EL (at least in large battles)--a single unit could plausibly have 10 movement options, a large battle with reinforcements could include 20+ units, 10^20 = way more combinations than you can search in a reasonable time.

This is exactly why we have to stay on a unit-based AI when computing a movement and a target. If we try to anticipate all the units’ behaviors and compute the most optimized one, we are going to have serious performance issues.

Caotico09 wrote:
Instead of issuing orders at the beginning of battle, you issue orders for each unit as its turn comes up?

This option would come with new issues. Sure, this would be easier for the player, but we’d lose a very unique side of our gameplay. And issues of movements would remain when playing against an AI’s empire.

It's plain to me that unit-based AI best suits orders issued for each unit as its turn comes up (a turn-based combat system). This is the industry standard, and I imagine the AI would behave much better. It seems a shame that turn-based combat is not supported, considering how important terrain and unit placement are to combat, and therefore how important unit control is.



As far as round-based combat goes, as human players we give all of our units orders that make them work together in order to maximise effectiveness, and we should expect that the AI would do the same. That's one issue - army-wide combat AI. These orders we give are, of course, imperfect, as they are changed by changing circumstances (what tiles remain free and accessible, what targets remain alive and in reach) - and so the AI often takes command. If the AI is to take command here, then predictability, simplicity and action are the most important things. The AI must never do something stupid like chase a unit behind a cliff, and it must never sit still doing nothing - either it advances, retreats or holds ground based on the back-up order. This entire issue would be solved by turn-based combat, of course, but you could fix round-based combat by ensuring that either 1) no units ever counterattack so as not to spend an action, 2) counterattacks can occur once but are free i.e. they do not spend an action, 3) counterattacks are 'infinite' and do not spend an action. The important thing is that units do not spend their actions counterattacking, so as to give each unit the opportunity to follow either the player's orders or the backup orders. Trust me, that will go a long way to alleviating many of the frustrations of lack of unit control in combat. My honest opinion is that turn-based combat is the way to go, but addressing counter-attacks is a start at least.

Tigregalis wrote:
As far as round-based combat goes, as human players we give all of our units orders that make them work together in order to maximise effectiveness, and we should expect that the AI would do the same...This entire issue would be solved by turn-based combat, of course

No, turn-based combat wouldn't help this particular issue at all. Even if you issue the orders one at a time as the units' turns come up, it's still useful to plan ahead so that your units can work together effectively, human players are still going to do that, and the AI is still going to be blocked from doing that by computational barriers.

Tigregalis wrote:
but you could fix round-based combat by ensuring that either 1) no units ever counterattack so as not to spend an action, 2) counterattacks can occur once but are free i.e. they do not spend an action, 3) counterattacks are 'infinite' and do not spend an action. The important thing is that units do not spend their actions counterattacking, so as to give each unit the opportunity to follow either the player's orders or the backup orders.

Wait, what?! Where did this counterattack thing come from? How is that related to anything else that's been discussed in the thread?

Manu wrote:
The unit-based AI can do two main tasks: choose the best target in a set of targets (let’s call it the Targeting Algorithm), and choose the best position in a set of tiles (let’s call it the Tile Algorithm).

Thanks for the explanations, Manu.



The targeting algorithm seems much improved in 1.0.12 (still needs a bit of work when it gives a target unlikely to be in range, and it's exploitable when you start understanding how it works). The tile algorithm, however, isn't very good. While I would prefer to see simple unit AI and complex army AI, the tile algorithm needs examination if you continue to use it.



Even with single-unit armies, poor tiles (unforested, lower altitude than other potential tiles from which to attack, same or worse vulnerability to counter-attack by additional enemies) are being chosen. Edit: This behavior is why, in the top post, I assumed that you were just running path to target using A* and following it until you reached range.



I was assuming you were aware of this problem, but I'll collect some screen shots the next time it happens.

natev wrote:
I was assuming you were aware of this problem, but I'll collect some screen shots the next time it happens.

Please do! Any information about weird situations is welcomed. If you want to share a save (which is highly recommended), you can refer to this thread: /#/endless-legend/forum/13-tech-support/thread/5393-reporting-an-issue

Thank you!