Heya all! I'd like to discuss some issues regarding the development of the AI for my Bomberman clone. Now I should fill everyone in on the concept for the game, as it does vary slightly from the standard Bomberman game and this is relevant to the AI requirements. As usual, the game will pit a number of opponents against one another in an arena. The arena will feature an arrangement of blocks, some indestructible and others destructible. The players will use bombs to destroy obstacles and to harm one another. Along the way, players will encounter powerups and mana. Mana will appear at random positions in the arena and will be used to power certain abilities and possibly the bombs themselves. Powerups will sometimes appear in the position of destroyed obstacles and will grant temporary special abilities or penalties. As this clone is to be a fantasy genre tilt on the game, we are also giving players access to 2 special abilities each, one for ranged use, and one for melee use, though I do not mean to imply that abilities are solely different forms of attack, like powerups, they could also be used as a form of defence or utility, though this is dependant upon the class of the player. Anyway, with that explained, I'll explain my AI requirements. I need the computer player to be able to find a route to a given point, and have already fully implemented A* pathfinding to accomplish this. I also need the character to be able to realise when an obstacle is blocking their path, and to be able to destroy the obstacle with a bomb, which means the character must move up to the obstacle, drop a bomb and retreat to cover. The character should realise when it is blocked in by an obstacle, so as not to drop a bomb at the obstacle and then try to run around accomplishing other objectives, only to end up running into the bomb he just dropped! When the character is not blocked in, it must make use of the fact that it may have a powerup allowing it to drop more bombs simultaneously, and choose a new objective such as bombing the player from another angle, if it is safe to do so. The AI must also be able to maneuver up towards the player and realise when and where it is best to drop a bomb. The AI must also know when it is appropriate to hunt for powerups/mana and when/how to avoid the player if it is at a disadvantage. The AI should not play every situation in the same manner, or it will probably be too predictable and easy to explout. The AI must be controlled so we can make it more or less easy to defeat. Finally the AI must know how best to utilise powerups/abilities, as it is no good using a defensive ability where an attacking or utility ability should have been used! So, I think that sums up everything I require of my AI, and I think I've worked out how to optimally achieve what I want, but I've begun to wonder if it should really involve so much hard work for what seems such a simple game! I've gone into Lambert-Jones(IIRC)models, fuzzy logic, finite state machines and all sorts of other areas just to get a reasonably intelligent enemy, and after planning I realise it is quite a huge task to implement everything. I have recently managed to simplify everything to a level I'm happier with, where the planned code is not as 'optimal' but still achieves roughly the same effect, but I still wonder if I could be making do with something much simpler.... I'm using this as portfolio work that I'd like to have finished in a strict deadline, so simplicty really ticks the boxes for this project. So I'll explain my rough concept for my new model, and I would much appreciate any suggestions for improvement, or general discussion on any of the areas I cover. First of all, I'm going to give the AI a list of possible states as follows: STATE_DROPBOMB STATE_FINDROUTETOPLAYER STATE_EVADEBOMBS STATE_DESTROYOBSTACLE STATE_HUNTPOWERUPS STATE_HUNTMANA Now initially we must choose a state. I'd like to have the state altered by a personality of the AI, and will probably implement a random element towards choosing the state along with a priority based system. On starting a level, the AI may decide to find a route to the player, or they may try to gain an advantage by grabbing a powerup. In the case of finding a route to the player, we simply feed the player position into the A* algorithm and let the pathfinder do its job. In the case of the destroyobstacle state, we have to plug in the location of an undestroyed obstacle to destroy in an attempt to gain a powerup, this could either be the closest obstacle, or a random obstacle and should achieve a fairly intelligent appearance. What happens next is really dictated by events that occur during the previous state, if we are hit by a bomb or in any way damaged, we may want to seek a powerup. If we have expended any mana, we may need to hunt for mana, and so on. If we encounter an obstacle along any route we wish to traverse, it should be destroyed. We simply keep check of any nodes blocked by an obstacle and if there is an obstacle make note of the fact and move towards it by feeding its position into the pathfinder. If we have reached the position of an obstacle, we should then drop a bomb (STATE_DROPBOMB). This would then trigger STATE_AVOIDBOMB. This state works by taking all the pathfinding nodes the player can reach without going through an obstacle, and calculating two distances for each and every node. The first distance is the distance from the player to the node, the second distance is from the bomb to the node. We then choose the node that is the shortest distance from the player, but the longest distance from the bomb. This effectively will make the player try to move diagonally from the bomb if at all possible but will still move the player directly away if there is no side tunnel, which will more than likely put the player out of line of sight of the bomb as is intended. STATE_AVOIDBOMB will be triggered any time the character comes into the same node as a bomb. The avoid player state will probably do something like taking 3 random nodes and trying to find a route to the one furthest away from the player. So all in all, that's my intended system, I'd like to hope it will work quite well, but I still wonder if I'm making things more complicated than they really need to be?! Anyhoo, if you're still with me and have not fallen asleep yet, I'd like to thank you for reading this far and invite you to comment or make suggestions on anything discussed! Thanks, Steve

a production system using a few heuristics might just do the job. You certainly already half way there with your thinking - you have several goal states and have identified several tests that you can use to choose your action.

Basically just give a score to each action move left, right, up, down, stationary, drop bomb.

Go through your tests and rules, gives each action a score. Whatever has the highest score you go do.

To give ai different personalities you just adjust the score weight given for a particular action. A cowardly one would always have a higher score given to a direction opposite to a player, etc, etc. When there's a bomb on the next square scores are added to any direction that leads away from the bomb.

I've worked a few monthes ago on a bomberman IA, I didn't use any A* pathfinding. One way is to find all the places the bot can go, storing the distance (easy recursive algorithm), and then "evaluate" the place (bonus it need, good place to set a bomb cos lot of destroyable walls around, bad place because a bomb will explode near soon...).

To find the place it will be easy too, we know the distance to the target, let's say 7, then we have to find a '6', then a '5'... in order to make an "inverse-path".

The algorithm is quick, and the AI is quite challenging.

You can dl my game, i think the sources are included in the zip, when not and when you're interested i can send them.

here a shot :
http://seb.sevilla.free.fr/sxdl/bomber/bomber_shot.jpg
and here the dl :
http://seb.sevilla.free.fr/sxdl/bomber/Magic%20Bomber.zip

hey all,

Thanks for all the input, it is much appreciated! I don't have time to reply to all I would like to right now, but one common thing I should have mentioned that is relevant to most of the posts is that I am not operating on fixed movement where the player can only move up down left or right, in my clone, I'm allowing the player to move freely in any direction (so long as walls do not interfere!). This actually rules out some parts of some of your suggestions, but I guess that was my mistake for not mentioning the fact.

This does complicate matters somewhat, and is why I use A* pathfinding rather than a more simplistic algorithm. Also, as suggested in the last post, it would be fine to use an algorithm like you suggest, but unfortunately my maps could feature blocks in any position, not just in a standard grid, so my maps may feature dead-ends that I don't think your algorithm would cope with.

Saying that though, I did mention that perhaps I'm being too idealistic, and should simplify things to make life easier, maybe that is just the kind of thing I need to do. Although saying that, as of last night, I finished about 75% of the AI that I originally suggested and it actually works quite well, but doesn't quite produce the level of difficulty I had hoped for, so I need to work on it a little more, perhaps introduce fuzzy logic as has been suggested and see if I can't make it a little more unpredicatable and a little more skilled.

I must say though, that although graphics are usually one of the first things you produce in a project, and one of the most impressive things to see in action, seeing the computer character go about its business without any interaction from me is a joy to behold and it has been well worth the small amount of effort required to get it working!

Any further comments are still welcome!

Cheers,

Steve

*EDIT* As for the heuristics method, I had originally intended to go down that route, but I have found that it introduces several problems. I find it hard to ensure that the influential factors are well balanced in adding to the score of the heuristic, and there are pitfalls to avoid, such as making it impossible for a given state to ever come into effect because another state always outscores it, and having to deal with situations where more than one state get the samee score, this is of course also further complicated when you add in modifiers for behavioural influence. I am of course open to suggestion as to how to avoid such problems, though for the time being I am operating as follows:

I first determine which goals are acceptable given the situation, I then add them into a vector of goals. I then choose a random goal from the posible goals. This goal is then carried out to completion and can only be interrupted by a priority goal. The priority goals are dealt with in exactly the same way as normal goals except for the fact that they can come into play at any time, rather than only coming into play after the last objective is complete. Priority goals do however have to wait for other priority goals to complete (Avoiding bombs, reacting to large changes in player position, etc).