Hello everybody I have been writing the AI for a 2D game, it uses a stepping engine so for each step on the game clock every unit has a chance to move to a direction, the total direction are the following: public final static int MOVE_NONE = 0; // do nothing (used to cancel a move) public final static int MOVE_N = 1; // north public final static int MOVE_NE = 2; // northeast public final static int MOVE_E = 3; // east public final static int MOVE_SE = 4; // south east public final static int MOVE_S = 5; // south public final static int MOVE_SW = 6; // south west public final static int MOVE_W = 7; // west public final static int MOVE_NW = 8; // north west I have been trying to create an algorithm so my weaker units run away from nearby enemies, a one step distance would be perfect, if I have only one enemy then the problem turns simple I just make my unit move in the same direction than the unit.. The problem arises each time the unit is being chased by more than 2 units, I have been trying to find an algorithm so the unit moves avoiding all enemies thought they seem to go straight to them.. A portion of my code is here: public boolean task_Protect(Unit myUnit,int maxProximity) { boolean danger=false; int enemycount=0, directionsum=0; for(Knight enemyknight : enemyKnights) { if(myUnit.getDistanceTo(enemyknight.getX(),enemyknight.getY())<=maxProximity) { directionsum+=enemyknight.getDirectionTo(myUnit.getX(),myUnit.getX()); enemycount++; danger=true; } } if(!danger){ return false; } switch(enemycount) { case 1: move(myUnit,directionsum); break; case 2: move(myUnit,((directionsum/enemycount)+4+(directionsum%2)%8)); break; } return true; } Is there any known algorithm for these kind of situations, make my unit getting uncatchable by enemy units? Thanks in advance ____ Ruben

Your thought process is conceptually correct (move away from the average direction of the enemies), but you are failing because of using integers to specify directions. You need to use a vector average and then pick the 8-direction direction to move in that is closest to that.

I also recommend that you use a weight based on the inverse of the distance to each enemy, so you run away from the nearest enemy most strongly.

Best bet is to use an influence map. Process the map with radiation out from each enemy. Once you have processed all the enemies, each agent then selects one of the eight directions that is the lowest value. This will be, by necessity, the one that is away from the bulk of the enemies.

This works whether the enemies are bunched or spread, near or far. In fact, if the enemies circle around the agent, he will retreat to the center. If there is a weak spot in the circle, he will try to break through that point.

I'd just add a little something that allows choosing a direction if the result is 0 (but there are ennemies).

Quote: Original post by InnocuousFox
Best bet is to use an influence map. Process the map with radiation out from each enemy. Once you have processed all the enemies, each agent then selects one of the eight directions that is the lowest value. This will be, by necessity, the one that is away from the bulk of the enemies.

But the direction that is locally optimal may not lead to the global safe spot that the agent should be seeking. The agent may be running into the arms of even stronger enemies.
In my own game, instead of selecting a locally optimal direction, I use Dijkstra's algorithm to search for the nearest safe spot (a spot that is not being influenced by enemies.) This gives me both the closest safe spot to use as a destination, as well as the safest path for the agent to follow. So while the agent is in the danger zone, he can still navigate around local high-danger areas to get to his destination.
Because the environment is dynamic, I throw away the last half of the path, and repath when the agent gets there. This also lets two friendly agents find safety with each other - they radiate negative influence - instead of running past each other.
I also repath if the agent hits a high-danger, or panic level spot that has suddenly appeared.

I have just noticed that the OP asks for one-step lookahead, so in that case this method cannot be used. But the units will probably look a bit dumber as a result...


[Edited by - captain_crunch on April 7, 2009 4:24:45 AM]

Thanks everybody for the tips, after a hard time I have made my own influence map, I had to simulate a border on the map so my units aren't trapped against the map limits too, even though sometimes they don't resist...
The objective of my peasants is to capture land, is there anyway I can extend the influence map so that my peasants beside escaping also capture the highest number of enemy territory or unexplored territory?
I have added points to each stage of the terrain as follows, though they don't seem to like it and ignore it :/

/////////////////////////////////////////////
///////Terrain influence variable set////////
/////////////////////////////////////////////

static final byte INFLUENCE_OF_ENEMY_TERRAIN=8;
static final byte INFLUENCE_OF_UNEXPLORED_TERRAIN= 4;
static final byte INFLUENCE_OF_MY_TERRAIN=-4;
static final byte INFLUENCE_OF_MAP_BORDER=-16;

A few thoughts on how I might try to come at this...

Treat this as an optimal control problem with terminal cost.

The terminal cost is the minimum, over all the enemy units, of the time that it would take for that enemy to reach that tile if he moved at top speed directly there.

The per-tile cost is 0 for most tiles, and -K for enemy tiles; i.e., you reward the player for moving over enemy terrain. K is just some constant. If it's huge that's all the villager cares about; if it's small all he cares about is fleeing from enemies.

You can solve this with dynamic programming. Start with an array over all your tiles filled with the terminal costs for the tiles. Then, from this, generate a new array by, for each tile, setting its value to be the minimum value from the set {old_array[this_tile], old_array[neighbor_1] + per_tile_cost[neighbor1], old_array[neighbor_2] + per_tile_cost[neighbor2], ...}. Then replace the old array by the new array and repeat. Do this until old_array = new_array.

Once you have this array, the best thing for your villager to do is to move to whichever of his adjacent tiles has the lowest value in this array.

You could keep the computational cost of this low by
1 - only generating these values for a small region around the villager (e.g., 20x20 tiles) instead of the entire map; this is an approximation.
2 - only generating these values every few AI "cycles" (or spreading the computation out over a few cycles), under the assumption that the values you compute are valid for a while.

[EDIT: I notice this is similar to what captain_crunch does.]

[EDIT: the per-tile cost should actually depend on time, and so on the iteration number on the algorithm I outlined above. It should be -K or 0 most of the time, as I said, but if the iteration number is larger than the terminal cost for that tile than the per tile cost should be infinity. Basically, not only do you need to get to a tile that is far away from enemies, but you also need to avoid enemies as you do so.]

[Edited by - Emergent on April 7, 2009 8:58:29 AM]

Quote: Original post by RubenRamalho
The objective of my peasants is to capture land, is there anyway I can extend the influence map so that my peasants beside escaping also capture the highest number of enemy territory or unexplored territory?

While I didn't look at your implementation, the quick answer is yes. You can layer influence maps in multiple ways in order to create a variety of effects. They are very powerful if used correctly.