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.

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.