Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 20 Sep 2010
Offline Last Active Mar 15 2012 07:48 AM

Topics I've Started

RTS-AI built on potentialfields

23 February 2012 - 07:28 AM

Hi there,

we are currently developing an RTS-game and working on the fight-implementation. Of course you come to the field of AI immediately, so we thought how to realise the AI implementation. We looked for a straightforward technic and finally chose the potential(field)-approach. Let me point out what this means:

All moving depends on potentials. So if you want to move some unit from A to B, we have a layer for the static world, that is the heightmap. So you make a regular A-star algorithm execution which is a bit different to what you use normally. We start at the target and go from there to find our start-position. The class path_potential_admin supplies the static layer, so obstacles are not considered. It also has some caching-functionality, so if this path is already known (specified by pos A and B), we can save time and supply our previously found path. This is possible as the static world never changes. The dynamic world is also based on potentials, that is e. g. a repulsive one for units or buildings so that we do not collide. We offer a few different potentials, just have a look at the code ( http://sourceforge.net/p/potentialfield/code/ci/b9930a37bc114a64601d976d0c2d774fa919789d/tree/ - it comes with a VS-project which is ready to compile and will create some pictures which illustrate how it works - be aware, might take a long time to finish).

When it comes to the moving process, we need some force which tells us where to go. You can imagine that like a 3D-potential-field and some bullet. The bullet will always move downwards (due to the earth's gravitational pull). Downwards means the lowest potential in this context.

So far to the theoretical idea and method, now we come to the real world and the problems we currently face with our implementation. We have some requirements:
* do not rely on external libraries
* be as performant as possible

So we would like to discuss the following questions:
* What do you think about this idea at all?
* What improvements do you see in the implementation?
* We are working with a hex-grid currently, what do you think about this approach?
* There is an issue when it comes to mapping a quadratic heightmap to a hex-grid (you know radius of the inner circle and the side length are not equivalent, just see http://upload.wikimedia.org/wikipedia/commons/e/e2/Sechseck-Zeichnung.svg ). This is a known issue and will be fixed soon
* The A-star implementation is somehow not really efficient when it comes to a changed start-position. Are there any improvements?
* Anything else you want to say.

Thanks a lot for your contributions.