Dealing with a dangerous world

By on November 12, 2011 8:19:49 PM from JoeUser Forums JoeUser Forums

Frogboy

Join Date 03/2001
+1470

One of the things that is giving me fits in Fallen Enchantress is getting delicate units to a dangerous place safely.

The classic case, sending a pioneer to claim a new area – but without getting killed on the way.

The hardest part of writing AI isn’t coming up with *A* away to solve a problem. It is solving the problem that doesn’t require a lot of coding time AND doesn’t doesn’t eat up a lot of CPU.

So, for instance, I don’t have the luxury that you humans have of looking at the path a unit generates between A and B and see what’s dangerous. That would be immensely expensive. 

Similarly, while providing a body guard for a unit is another path to take, the problem there is that you could really slow down your expansion and get wiped out by the human player who is able to make better decisions.

Locked Post 29 Replies
Search this post
Subscription Options


Reason for Karma (Optional)
Successfully updated karma reason!
November 12, 2011 8:28:17 PM from Elemental Forums Elemental Forums

Well, you could always simply say that the AI pioneers are masters of stealth & are able to move thru the land unseen.  Simply teleport them to within a couple of squares of their goal & problem solved.  Maybe have a time delay equal to the travel time the unit would have experienced.

Reason for Karma (Optional)
Successfully updated karma reason!
November 12, 2011 9:22:55 PM from Stardock Forums Stardock Forums

That would be the easy route but no real fair to humans.

Reason for Karma (Optional)
Successfully updated karma reason!
November 12, 2011 9:46:57 PM from Elemental Forums Elemental Forums

Hmm, possible solutions:

  1. Pioneer is agile - quick movement points, can easily flee battles if attacked (MOM settlers could flee and survive battles fairly easily. I remember some instances of attacking settlers, enemy leader casting some damage spells, and then fleeing. Sometimes the settler would surive turn after turn). AI in MOM would not escort.
  2. Pioneer is invisible unless enemy unit in adjacent square
  3. Pioneer recalcs waypoints each turn to asess threats and adjust path (humans would do so but not practical)
  4. Pioneer is escorted (humans would do so but not practical)
  5. Pioneer "death" may just represent scattering of settlers and chance to rally as a new Pioneer unit after tactical battle loss.

If you combined #1, #2, and #5 (or some combination thereof) it may make killing pioneers difficult as they have good survivability. Now, a human may just follow the pioneer and sack the new settlement when founded. However, #2 may make it difficult to follow if they can't be seen unless human unit is adjacent. If the pioneer is unescorted, it still raises an issue around initial garrison for a new settlement (maybe militias?)

In short, knowing #3 and #4 are difficult to implement, I think you need to make them durable without buffing attack and defense. Something that makes them agile, quick, and able to flee might do the trick.

Reason for Karma (Optional)
Successfully updated karma reason!
November 12, 2011 10:31:24 PM from Elemental Forums Elemental Forums

Quoting Frogboy,
That would be the easy route but no real fair to humans.

Well, sometimes fair isn't the point.  We humans have advantages that you can't easily program into the AI.  As you said -

Quoting Frogboy,
The hardest part of writing AI isn’t coming up with *A* away to solve a problem. It is solving the problem that doesn’t require a lot of coding time AND doesn’t doesn’t eat up a lot of CPU.

So, for instance, I don’t have the luxury that you humans have of looking at the path a unit generates between A and B and see what’s dangerous. That would be immensely expensive. 

Anything you come up with will be a cheat to some degree.  You just have to give the AI a little penalty for using it.

 

 

 

Reason for Karma (Optional)
Successfully updated karma reason!
November 13, 2011 3:36:33 AM from Elemental Forums Elemental Forums

Uhm... WHY is it expensive? It's simple pathfinding. Pick a route that doesn't bring the pioneer within 1 tile of an enemy unit (or 2, don't know FE rules). If wildlands or enemy territory then stay clear.

Reason for Karma (Optional)
Successfully updated karma reason!
November 13, 2011 7:00:36 AM from Elemental Forums Elemental Forums

I don't get why pioneer pathfinding is that CPU extensive either. Shouldn't it be quite simple to mark tiles that have a threat as no-go and then do a simple adjacency matrix power calculation weighted with movement costs for the shortest path without threats? In general you shouldn't move settlers by themselves that many tiles into the wild, so the matrices shouldn't grow that big before you need to have an escort and thus solving the problem.

When I play Civ, I don't use an unescorted settler to settle more than, say, 20 tiles from my nearest city. If I need to go further than that, I always get an escort that then starts guarding the city.

Since you can do the calculations on the human turn and the computer players probably won't have pioneers scrambling around constantly, there shouldn't be that much trouble calculating the paths. Then again I don't know how little resources you have for one task such as this when calculating the turns in parallel.

Reason for Karma (Optional)
Successfully updated karma reason!
November 13, 2011 8:58:02 AM from Elemental Forums Elemental Forums

I'm glad your willing to spend the time to do it right Frogboy. the whole monsters don't attack enemy pioneers thing in WoM was really annoying. A really good game can't have huge holes like that in the AI.

I'm not really a programmer but perhaps instead of preprograming a safe route you could take it a turn at at a time. So the pioneer goes out to try and settle and if a monster enters within his safety bubble he retreats to the nearest city or until the monster is out of sight, then he would try again. You could also then summon reinforcements to kill the monster. This would be much more organic instead of mechanical. The pioneers would thus have a chance to build a city without needing protection but would receive it if needed. However are cities going to be safe without soldiers in them anyway?

Reason for Karma (Optional)
Successfully updated karma reason!
November 13, 2011 9:13:46 AM from Elemental Forums Elemental Forums

This is another area where you're at an unfair disadvantage.

 

A human player will leave them unescorted, and reload if they're eaten.  It's just human nature: AI's have more fun losing then humans. 

 

One turn at a time and recalculating is probably the best chance, followed by giving pioneers good sight radius.  Pioneers are largely early game units, so AI times won't be that long in the start of a game.

 

That Pioneer death= respawns after a few turns idea is great though, and might be the best solution.  This would also keep humans from saving/reloading, and not cripple an AI in games where it loses and the player doesn't. 

 

I also like the pick a square, and have the town form a few turns later.  If the town is attacked while forming, it disappears, and monsters can attack, but the unit doesn't have to physically travel there.  You'd probably use your scout as a garrison until the town is formed.

 

Are either of those last two ideas viable on the game design front?  They sound really neat.

 

Reason for Karma (Optional)
Successfully updated karma reason!
November 13, 2011 10:24:42 AM from Elemental Forums Elemental Forums

To me those ideas sound pretty weird and gimmicky.

You shouldn't ever consider the saving/loading issue when creating AI. That's not part of the gameplay, that's just human cheating in the game. If winning / losing the game rests on whether or not your settler gets attacked by sheer chance, then that's a gameplay issue, not an AI one.

Bottom line is, you should be able to move the settler to where you want to create your next city with relative ease after you have assessed the threats around you. So either providing an escort should be easy enough or the settler should have enough move points/sight to steer away from most monsters. Civ does this pretty well by giving settlers two movement points when barbarians only have one.

Reason for Karma (Optional)
Successfully updated karma reason!
November 13, 2011 10:32:26 AM from Elemental Forums Elemental Forums

Here's an idea that would help the issue a little bit: make the settler unit a decent defensive unit that cannot attack or be grouped with anything else. Kind of like the mobile outposts in RTS games (command & conquer etc). Since a settler founds a whole town, it makes pretty good sense for it to have enough firepower to fight off a few bandits or the occasional beast, but not anything stronger like dragons or skags. It also makes sense for the settlers to not be able to pair up with anything else, since it's a convoy with loads of stuff to found a city and as such is too big a group to fit into an army. It automatically fills up whatever logistics quota you have for that unit.

This would pave way for an interesting addition to the Logistics tech: the better your logistics is, the better defended your settler units are automatically. However add some small penalty to the new city if the settler unit was damaged before founding the city. Perhaps 1-3 turns of no production in the new found city while they repair the damage.

Reason for Karma (Optional)
Successfully updated karma reason!
November 13, 2011 11:23:59 AM from Elemental Forums Elemental Forums

Frogboy - I really think you just need to bite the bullet and convoy your AI settlers.

My preferred strategy is to always send a settler out with at least 1 guard unit.  If it's a primo site I might even send 2 guards.

Nothing worse than losing a settler & then seeing your opponent build a city right where you wanted to.

And unless you're giving the AI an unfair advantage on new city 1st unit build times, that guard unit really comes in handy after the new city is founded.

 

Reason for Karma (Optional)
Successfully updated karma reason!
November 13, 2011 12:35:21 PM from Elemental Forums Elemental Forums

Quoting Sir_Linque,
I don't get why pioneer pathfinding is that CPU extensive either. Shouldn't it be quite simple to mark tiles that have a threat as no-go and then do a simple adjacency matrix power calculation weighted with movement costs for the shortest path without threats? In general you shouldn't move settlers by themselves that many tiles into the wild, so the matrices shouldn't grow that big before you need to have an escort and thus solving the problem.

When I play Civ, I don't use an unescorted settler to settle more than, say, 20 tiles from my nearest city. If I need to go further than that, I always get an escort that then starts guarding the city.

Since you can do the calculations on the human turn and the computer players probably won't have pioneers scrambling around constantly, there shouldn't be that much trouble calculating the paths. Then again I don't know how little resources you have for one task such as this when calculating the turns in parallel.

Wouldn't call myself a coding expert in any way shape of form but I'll take a shot at why this is so CPU intensive.

If all you want to do is find the shortest path from point A to point B for a unit, that is a fairly easy computational problem. The simplest implementation of Dijkstra's alogrithim (well known shortest path algorithm) operates in O(V^2) time (V is the number of vertices). Basically the time it takes to find a solution is proportional to the number of vertices squared. For instance if you were trying to figure out the shortest route that a truck could take between two towns, and had a map with a bunch of towns in between and knew the distances between all of them, you could find the optimal answer in some time that was proportional to the number of towns on the map squared. The problem you describe is similar to this, the paths just get different weightings based upon static threats that exist on the map. Instead of finding the shortest path you're finding the least dangerous and shortest path. The problem gets a little more complex, but its the same order of magnitude. In the grand scheme of things an algorithm like this that can operate in polynomial time is pretty fast.

The problem Brad is trying to tackle is on a very different level of complexity. You are now not just tying to find the shortest path between two points for a unit. You're trying to find the shortest path while also taking into account the possible actions of a number of other entities that can also move on the same map that you have to either avoid or counter in some way. The threats are no longer static constants, but rather other actors that are solving their own little constrained optimization problems. I can't just find the shortest/least dangerous path assuming that the threats all stay in the same place. I have to find the shortest/least dangerous path assuming the threats will make a counter move to every move that I make. Don't know for certain, but I imagine the time this takes rapidly blows up to exponential or even factorial time calculation. 

Reason for Karma (Optional)
Successfully updated karma reason!
November 13, 2011 1:33:47 PM from Elemental Forums Elemental Forums

Quoting scifi1950,
Frogboy - I really think you just need to bite the bullet and convoy your AI settlers.

My preferred strategy is to always send a settler out with at least 1 guard unit.  If it's a primo site I might even send 2 guards.

Nothing worse than losing a settler & then seeing your opponent build a city right where you wanted to.

And unless you're giving the AI an unfair advantage on new city 1st unit build times, that guard unit really comes in handy after the new city is founded.

 

 

Agreed. I also hope that the world is dangerous enough that the human player will have to escort their pioneers as well.

The best sites for settling should also have a strong monster presence anyway and sending the pioneer with even a weak escort should be suicide.

 

That way, the AI and human players will have to play by the same rules.

Reason for Karma (Optional)
Successfully updated karma reason!
November 13, 2011 2:07:04 PM from Elemental Forums Elemental Forums

Quoting jpmcconnell,

Quoting Sir_Linque, reply 6I don't get why pioneer pathfinding is that CPU extensive either. Shouldn't it be quite simple to mark tiles that have a threat as no-go and then do a simple adjacency matrix power calculation weighted with movement costs for the shortest path without threats? In general you shouldn't move settlers by themselves that many tiles into the wild, so the matrices shouldn't grow that big before you need to have an escort and thus solving the problem.

When I play Civ, I don't use an unescorted settler to settle more than, say, 20 tiles from my nearest city. If I need to go further than that, I always get an escort that then starts guarding the city.

Since you can do the calculations on the human turn and the computer players probably won't have pioneers scrambling around constantly, there shouldn't be that much trouble calculating the paths. Then again I don't know how little resources you have for one task such as this when calculating the turns in parallel.

Wouldn't call myself a coding expert in any way shape of form but I'll take a shot at why this is so CPU intensive.

If all you want to do is find the shortest path from point A to point B for a unit, that is a fairly easy computational problem. The simplest implementation of Dijkstra's alogrithim (well known shortest path algorithm) operates in O(V^2) time (V is the number of vertices). Basically the time it takes to find a solution is proportional to the number of vertices squared. For instance if you were trying to figure out the shortest route that a truck could take between two towns, and had a map with a bunch of towns in between and knew the distances between all of them, you could find the optimal answer in some time that was proportional to the number of towns on the map squared. The problem you describe is similar to this, the paths just get different weightings based upon static threats that exist on the map. Instead of finding the shortest path you're finding the least dangerous and shortest path. The problem gets a little more complex, but its the same order of magnitude. In the grand scheme of things an algorithm like this that can operate in polynomial time is pretty fast.

The problem Brad is trying to tackle is on a very different level of complexity. You are now not just tying to find the shortest path between two points for a unit. You're trying to find the shortest path while also taking into account the possible actions of a number of other entities that can also move on the same map that you have to either avoid or counter in some way. The threats are no longer static constants, but rather other actors that are solving their own little constrained optimization problems. I can't just find the shortest/least dangerous path assuming that the threats all stay in the same place. I have to find the shortest/least dangerous path assuming the threats will make a counter move to every move that I make. Don't know for certain, but I imagine the time this takes rapidly blows up to exponential or even factorial time calculation. 

But pathfinding shouldn't be that hard, even with moving threats. You have your basic grid, and you can just block out any tile as inaccessible if it has a monster within 1 tile (so a monster creates a 3x3 dead-loss). Add in wildlands and borders to factions that you are neutral or at war with.

My point is, even moving enemies should have very little impact on how you proceed. You just have to avoid them, which isn't very difficult.

Reason for Karma (Optional)
Successfully updated karma reason!
November 13, 2011 3:15:33 PM from Elemental Forums Elemental Forums

jpmcconnell, you don't need to calculate the movements of each threat. Just like Heavenfall said, you mark the squares that a monster can reach in the next turn as inaccessible; that's it. Just like a human player does, you actually CAN just find the shortest/least dangerous path assuming that the threats all stay in the same place. Each turn you re-calculate based on the new positions of the monsters. That's the way I do it when I play the game, so I think that's sufficient for an AI player.

Reason for Karma (Optional)
Successfully updated karma reason!
November 13, 2011 4:30:54 PM from Elemental Forums Elemental Forums

Would the easy way be to leave the AI dumb and just reduce the "threat radius" if there is such a thing for caravans?

and if there isn't such a mechanic it should be added. Large armies should scare away small groups of wild monsters and small armies should look like prey.

Reason for Karma (Optional)
Successfully updated karma reason!
November 13, 2011 4:34:21 PM from Elemental Forums Elemental Forums

Are we assuming that the AI is sending its pioneers out with guards? I don't think I have ever sent a lone pioneer out in all the times I have played WoM. 

Reason for Karma (Optional)
Successfully updated karma reason!
November 13, 2011 4:51:41 PM from Elemental Forums Elemental Forums

Quoting ,
One of the things that is giving me fits in Fallen Enchantress is getting delicate units to a dangerous place safely.

The classic case, sending a pioneer to claim a new area – but without getting killed on the way.
The hardest part of writing AI isn’t coming up with *A* away to solve a problem. It is solving the problem that doesn’t require a lot of coding time AND doesn’t doesn’t eat up a lot of CPU.
So, for instance, I don’t have the luxury that you humans have of looking at the path a unit generates between A and B and see what’s dangerous. That would be immensely expensive. 
Similarly, while providing a body guard for a unit is another path to take, the problem there is that you could really slow down your expansion and get wiped out by the human player who is able to make better decisions.

I'd be interested to know the exact problem that you're trying to solve. I'm sure you're aware of the solutions posted in this thread, since they're the solutions that are used in nearly every tile-based game.

Reason for Karma (Optional)
Successfully updated karma reason!
November 13, 2011 5:31:03 PM from Elemental Forums Elemental Forums
I guess I'm just giving brad the benefit of the doubt here. If it really was just a simple shortest path problem then the solution is pretty easy even with threats, and is also not incredibly computationally intensive. Thus there must be some complicating factor that makes it more than just a shortest path problem. I've thrown out one possibility, the fact that the threats are variable and not static. I'm curios to know what the complicating factor actually is. I also don't think just looking one turn in the future and basing a solution off that is a workable solution. You have to consider what other players ae going to do in subsequent turns. Being able to think ahead and plan, even something as simple as settler movement, seems to be what would separate a good ai from a crappy one. If the ai's really only looking at the next turns movement to identify dangerous areas then that opens up all sorts of exploits on the human side against the Ai that can't see beyond one turn in the future.
Reason for Karma (Optional)
Successfully updated karma reason!
November 13, 2011 5:32:13 PM from Elemental Forums Elemental Forums

There are lot of obvious solutions to these problems.

FE is quite a bit different than other tile based games in that the world is really REALLY dangerous. It's not like Civ or WOM or what have you where there's an occasional threat. It's more like an obstacle course of threats. The world is out to kill you hard.

And since I write the monster AI too, I am doing my best to make sure they're really good at killing stuff (without them being too unrealistic -- they won't chase you across the world or anything, they don't care about you that much).

Finding a delicate balance between caution and reckless is a non-trivial programming exercise.   If you ever watch champion strategy gamers (like Starcraft) you'll find that the bold win more often than the careful.

Reason for Karma (Optional)
Successfully updated karma reason!
November 13, 2011 6:29:17 PM from Elemental Forums Elemental Forums

Sounds like an escort should be pretty much mandatory, it is for the AI in Civ5 if for no other reason than the fact that the human player is likely to prey on new AI settlements.

Reason for Karma (Optional)
Successfully updated karma reason!
November 13, 2011 6:46:30 PM from Elemental Forums Elemental Forums

I agree.  If the world is an obstacle course of threats, the only decent way to get the pioneer through is by having a sufficient escort.

Reason for Karma (Optional)
Successfully updated karma reason!
November 13, 2011 8:42:06 PM from Elemental Forums Elemental Forums

Quoting Frogboy,
There are lot of obvious solutions to these problems.

FE is quite a bit different than other tile based games in that the world is really REALLY dangerous. It's not like Civ or WOM or what have you where there's an occasional threat. It's more like an obstacle course of threats. The world is out to kill you hard.

And since I write the monster AI too, I am doing my best to make sure they're really good at killing stuff (without them being too unrealistic -- they won't chase you across the world or anything, they don't care about you that much).

Finding a delicate balance between caution and reckless is a non-trivial programming exercise.   If you ever watch champion strategy gamers (like Starcraft) you'll find that the bold win more often than the careful.

 

What about letting the obstacle (monsters, etc) to ignore the AI settler?

If you make the AI to calculate a lot of things, there will be more... (and maybe) a long and annoying waiting time between turn.

Reason for Karma (Optional)
Successfully updated karma reason!
November 13, 2011 8:42:24 PM from Elemental Forums Elemental Forums

Flying units would be a good solution. 

Reason for Karma (Optional)
Successfully updated karma reason!
November 13, 2011 11:58:33 PM from Elemental Forums Elemental Forums

Quoting Frogboy,
There are lot of obvious solutions to these problems.

FE is quite a bit different than other tile based games in that the world is really REALLY dangerous. It's not like Civ or WOM or what have you where there's an occasional threat. It's more like an obstacle course of threats. The world is out to kill you hard.

And since I write the monster AI too, I am doing my best to make sure they're really good at killing stuff (without them being too unrealistic -- they won't chase you across the world or anything, they don't care about you that much).

Finding a delicate balance between caution and reckless is a non-trivial programming exercise.   If you ever watch champion strategy gamers (like Starcraft) you'll find that the bold win more often than the careful.

 

Games are often designed to encourage this, because games that do the reverse tend to stagnate into turtlefests.  This is what causes many fighting games to fail.

 

I still think that reducing the penalty for lost settlers in some fashion would be a good idea. 

Reason for Karma (Optional)
Successfully updated karma reason!
Stardock Forums v1.0.0.0    #108433  walnut3   Server Load Time: 00:00:00.0000485   Page Render Time: