Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (497)
Games in Android Showcase (114)
games submitted by our members
Games in WIP (563)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  artificial potential fields  (Read 4134 times)
0 Members and 1 Guest are viewing this topic.
Offline gideon

Senior Newbie





« Posted 2007-02-14 00:23:42 »

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!

The towship's adventures
Offline SimonH
« Reply #1 - Posted 2007-02-14 04:12:07 »

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...

People make games and games make people
Offline rdcarvallo

Senior Member


Projects: 5
Exp: 15 years


2D Java games forever!


« Reply #2 - Posted 2007-02-14 04:41:19 »

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??

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline SimonH
« Reply #3 - Posted 2007-02-14 05:17:01 »

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...

People make games and games make people
Offline rdcarvallo

Senior Member


Projects: 5
Exp: 15 years


2D Java games forever!


« Reply #4 - Posted 2007-02-18 20:41:36 »

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.-
Offline t_larkworthy

Senior Member


Medals: 1
Projects: 1


Google App Engine Rocks!


« Reply #5 - Posted 2007-02-19 01:01:22 »

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

Runesketch: an Online CCG built on Google App Engine where players draw their cards and trade. Fight, draw or trade yourself to success.
Offline gideon

Senior Newbie





« Reply #6 - Posted 2007-02-19 09:02:14 »

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

The towship's adventures
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

BurntPizza (22 views)
2014-09-19 03:14:18

Dwinin (35 views)
2014-09-12 09:08:26

Norakomi (62 views)
2014-09-10 13:57:51

TehJavaDev (89 views)
2014-09-10 06:39:09

Tekkerue (44 views)
2014-09-09 02:24:56

mitcheeb (65 views)
2014-09-08 06:06:29

BurntPizza (47 views)
2014-09-07 01:13:42

Longarmx (35 views)
2014-09-07 01:12:14

Longarmx (40 views)
2014-09-07 01:11:22

Longarmx (36 views)
2014-09-07 01:10:19
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!