Hello! Recently I started programming a bomberman-clone game in Java. I've got all stuff working, except enemy AI. What I am currently trying to achieve, is(assuming my terrain is grid-based(just like in bomberman game)) : if the enemy is standing on a tile which is not safe(there's some bomb nearby which will explode and kill the enemy), find the closest safe tile, find the safe path to that tile(if there's no safe path, find another closest tile and another safe path..). And finally, get to that tile. The biggest problem is keeping the path safe.

(Everytime, when player places a bomb, all tiles which are going to be hit by an explosion are marked as "unsafe")

Here's what my bot does right now(pseudo code):

void update() { // being called every frame
if (tileIamStandingOn.safe == false) { //if tile that enemy is standing on is unsafe
calculatePath();
}

if (wayPoints.size != 0) { // if we have some path to follow to 
followThePath();
}
}

void calculatePath() {  // A* pathfinding 
Tile closestSafeTile = getClosestSafeTile(); // So now we have the targetTile(tile that enemy should reach) 
getPath(closestSafeTile); // using A* alghorithm

}

Tile getClosestSafeTile() {
Tile closestTile = null;

openNodes.add(tileIamStandingOn);  //

		while (openNodes.size > 0) {
			final Tile lowestTile = getNodeWithLowestFValueIn(openNodes); //I loop through openNodes list and return the node(tile) with smalles F value (just basic A* pathfinding)

			openNodes.removeValue(lowestTile, false);
			closedNodes.add(lowestTile);

			Tile tileDown, tileUp, tileRight, tileLeft; // I create references for Tiles which are next to the tileWithLowestFCost

			tileLeft = map.getTileAt(lowestTile.column - 1, lowestTile.row);
			if (tileLeft != null && tileLeft.walkable) { // if I can walk on the tile and it is not null
				if (!closedNodes.contains(tileLeft, false)) { // if tile is not in the closedNodes list (these are A* things, which I am not going to explain deeply)
					if (!openNodes.contains(tileLeft, false)) {
						tileLeft.F = (short) (lowestTile.F + 10); // as right now we do not calculate path, but we are finding closestSafeTile, no G or H value calculations

						openNodes.add(tileLeft);
						
						if (tileLeft.safe) { // if tile is safe
							 closestTile = tileLeft;
							resetPathResources(); // clear stuff like openNode list and reset F values of all Tiles
							break;
						}
					} else { // if tile is in openNodes, we do a special check(reparenting)
						if (lowestTile.F + 10 < tileLeft.F) {
							tileLeft.F = (short) (lowestTile.F + 10);
						}
					}
                                        
                                        now I just repeat all calculations I did for tileLeft to TileDown,Tile Right...
				}
			}
		}

return closestTile;
}

void getPath(Tile targetTile) {
openNodes.add(tile);
		
		while (openNodes.size > 0) {
			final Tile lowestTile = getLowestNodeIn(openNodes); // again the same principal as described in getclosestSafeTile method

			openNodes.removeValue(lowestTile, false);
			closedNodes.add(lowestTile);
			
			if (lowestTile.equals(targetTile)) break; //if we have reached the targetTile(our Goal) stop the loop

			Tile tileDown, tileUp, tileRight, tileLeft;

			tileLeft = map.getTileAt(lowestTile.column - 1, lowestTile.row);
			if (tileLeft != null && tileLeft.Walkable) {
				if (!closedNodes.contains(tileLeft, false)) { 
					if (!openNodes.contains(tileLeft, false)) {
						tileLeft.H = getHeuristicValue(tileLeft); // as we are now finding closest path, we calculate H, G values, too.
						tileLeft.G = (byte) (lowestTile.G + 10);
						tileLeft.F = (byte) (tileLeft.H + tileLeft.G); 
						tileLeft.parent = lowestTile;

						openNodes.add(tileLeft); 
					} else {
						if (lowestTile.G + 10 < tileLeft.G) {
							tileLeft.G = (byte) (lowestTile.G + 10);
							tileLeft.F = (byte) (tileLeft.H + tileLeft.G); // reparenting
							tileLeft.parent = lowestTile;
						}
					}
				}
			}

			do the same calculations for TileRight, TileTop...
		}
		
		Tile currentNode = targetTile; // now, the path is in our closedNodes list, along with some other Tiles, so we "extract" only the right ones(the shortest path)
		while (currentNode != tile) {
			wayPoints.add(currentNode);
			currentNode = currentNode.parent;
		}
		
		wayPoints.reverse(); // so now our WayPoints list contains all Tiles in shortest Path to cloesestSafeTile
	}
}

So this means I have fully working A* alghorithm, but have no idea how to calculate whether the path is safe. I could just say that if I find unsafe Tile while calculating the path, path is not safe. But this may not be ideal solution. I could also calculate that: if some tile in path is not safe, but while I am walking over it it won't explode, take it as safe tile. But you know, sometimes the bots in bomberman game stop when they are before tile which is exploading and then continue moving(after the explosion). I need some way to handle all that and make the path nice and safe. I'm kinda lost here. Any way would be appreciated.

Instead of just storing whether a tile is safe or not, store the nearest time at which an explosion will occur in that tile. Then you can use that when calculating G in your pathfinder. Right now you're using a fixed cost of 10 for moving from any tile to any adjacent tile. You might try adding an additional someConstant / (nextExplosionTime - (currentTime + pathTime)) to that cost whenever that calculated denominator is greater than zero. (someConstant will be dependent upon the scale of your time values and the importance you want to place on this effect relative to the fixed cost of 10; pathTime is the duration of time it will take for the enemy to follow the path and get to the tile in question from its starting position)

The result is that the enemy will only worry a little bit about tiles that are unsafe but whose explosions aren't imminent. But they'll be more aggressive about avoiding tiles whose explosions are about to happen. And they won't care at all about tiles that will explode before they even get there (that's what the pathTime component of the formula is for).

That last bit is flawed in that a tile might have two overlapping explosions queued up at different future times, and the enemy might ignore the first explosion because it'll happen sooner than the enemy can reach the tile. But without extra logic to store the second explosion's time and factor that into the path finding, the enemy will happily walk right into the second explosion. Though if the enemy recalculates its path every turn, it might be able to save itself from most embarrassment.

For better path calculation you may want to check-out cooperative path finding like http://www.gamedev.net/topic/669996-cooperative-pathfinding-agents-get-stuck-at-choke-point/

Whoa! Thanks for such a useful informations! I guess I may be able to construct some nice working AI with this.

Thanks again!

You may want to allow your agents to backtrack into tiles they've already visited, in case the only safe path involves stepping back into a tile that you previously visited.

This would be easily represented by adding "time" layers to your pathfinding graph, where each layer represents what the bombs will be doing in the future. Instead of using A*, you would just use a breadth-first traversal where each step advances one time layer as well (including paths where the agent stands still!). Nodes in future layers where bombs explode would be marked non-traversable. Each time a bomb is planted, prediction layers are added up until the time at which that bomb explodes, and each agent recalculates all safe nodes through all layers.

You may also decide to place potential-hazard information in all of the cells a competing player could move to and place a bomb in the future.

This might make the AI play the game too well for a player to compete, though...

Thanks! I'll definitly use this, even though I am probably not going to get rid of all A* calculations... I'll see what I can come up with.

Right; You'll still need A* for other things, such as planning how to get to a tile when you've decided where you want to place a bomb, or how to get to a player if you're a physical-contact-attack type of monster.