artificial potential fields

Game Mechanics Artificial Intelligence
#1

Hi, currently I’m working on a simple 2d space shooter called towship (http://towship.sourceforge.net). Since it basically is a top down scroller with beefed up physics, the AI doesn’t have to be really complicated. However I am not willing to accept AIs flying fixed paths, that would be just a little too boring imho. While real pathfinding algorithms like a space-time A* seem a bit overkill, I thought so called artificial potential fields might just do the trick.

Since the big name might scare people off unnecessarily, I’ll explain a little:
Suppose the direction of the AI is determined by a number of artificial forces coming from various objects in the game. Typically the AI’s goal will attract the object and obstacles ilke walls and other ships will repel it. These forces, will guide the AI through the playing field. You can visualise this as a landscape where the goal is a deep valley and all the obstacles are hills, in this landscape the AI will slide towards it’s goal. This visualization also makes some problems apparant like local minima, which basically is a valley from which the ai cannot slide towards its goal without going uphill.

Anyways, while this seems like a pretty straightforward issue, it can get pretty complicated (try a google search and see all the scientific papers on the subject). I was hoping someone here would have some valuable insight into this, perhaps previous experiences? Maybe I’m aiming to high and should employ simpler methods, but I’m out of ideas in that respect.

Thanks in advance!

#2

I used a much simplified version of this for a racing game. I used an overmap grid with ‘hints’ in each square such as ‘go left a bit’ or ‘go left a lot’, ‘slow down’, ‘speed up’ &c. Each bot took account of it’s current square’s hint and also those ahead and on either side. Combined with the locations of enemies this gave a cheap but realistic variation in the drive paths of the bots and also allowed them to predict the behaviour of opponents (by reading their hints too). It worked really well, but took a fair bit of individual hint tuning for each map.
Point-source and line-source potential fields would have been better but it depends on your processor power - if you’re going for mobile devices maybe the grid option is better…

#3

Very interesting way to achieve driving paths.

Currently I have roads with directions (not hints) and the driver
looks for them to decide where to go next(lines the car with
the direction). Also reads ahead to find corners and look for
other cars to make collision avoidance.

Do you have a demo of your racer or some kind of pseudo-code
of your algorithm??

#4

Can’t find the code I’m afraid…
Sounds like you’re pretty nearly there though, but why not add power as well as directions to the roads? This can help with cornering (ie slow down for corner ahead, speed up after corner) and also for collision avoidance - a car in front is more likely to go for faster squares and if a collision is likely then the AI car can choose left or right avoidance swerve depending the on the ‘power’ of road ahead. You might also think about adding a ‘safety-factor’ for locations (ie the road near a hazard is more ‘costly’ than open road).
If you wanted to be really flash you could get the cars to ‘learn’ the track and build up their own maps based on experience, then use the maps they generated in your game…

#5

Good idea, power in the road. It even could be variable (to use semaphores). In the end the car’s drivers are the ones that control the car using its inputs (accel, steering, brake) And they can learn good ways to cross the city (this hasn’t been implemented yet)…

Rafael.-

#6

The reason why there are lots of papers on potential fields is because its difficult to get working. The local minima is the hard problem.
Solution one is add random noise to your resolved vector, this ensures that theoretically it can never get stuck in a local minima but it make take along time to climb out.
The popular alternative method is to let your AIs leave a trail of repulsive fields where they go, which prevents them for staying in the same place too long. I think everyone agrees thats the most elagent way.

Tom

#7

Thanks for the suggestions, I’ll definately try dropping repulsive fields on the way. My first exploration of the subject actually was quite promising. Even the most basic versions seem to do well enough for this game, this is mostly because I’m not desparately trying to avoid collisions, as long as it looks remotely ‘realistic’ (not totally brainless) it’s okay.

Another advantage of these artificial potential fields is that I get some tweaking parameters for free. For example, it’s fairly easy to make an AI behave more reckless or very afraid. An AI can also evade specific objects in different ways, for example, a seeking missile shouldn’t be evaded in the same ways we would evade a rock. There are some more things I plan to experiment with like flying preplanned paths, dynamic path flying (eg. circle around the player), flocking like behaviour and formation flying.

I’m going to combine the potential fields with path finding for the static environment. Hopefully this will also resolve some of the local minima. I was hoping I could use the potential fields to evade moving objects.

Keep the suggestions going and I will keep you posted! :wink:

–gideon