Peculiar Pathfinding in Design Philosophy

ID:152018
 
May 22 2008, 4:55 am
I am designing a turn-based ship battle system, and the A.I aspect of it has me a little discombobulated. The main problem I have is that movement is limited; they can only turn X amount of turns per Phase, and only by 45 degrees each turn. Also they are limited to Y forward steps.

Another problem is that ships fire sideways, so turning the A.I to face the enemy isn't an option; the A.I has to move as if to pass the enemy and line up its side with said enemy.

Also there are three types of ammunition; Grapeshot (which can only be fired into squares in the immediate vicinity of the A.I (or two squares away if the A.I is of a certain Skill Level) - Cannonball (which can fire in a straight line from the side of the ship up to 3 or 4 squares away) - and Longballs (which cannot be fired closer than 3 squares away or nearer than 5) - this means the A.I has to work out how far to one side it needs to go.

I'm just having some trouble working out the maths. If it helps, the average A.I can turn 3 times per Phase, and move forward 5 times. Any help would be greatly appreciated.

~Ease~
#1 May 22 2008, 5:04 am
Before getting into the math and such, may I suggest taking a look at jt_vectors?
There's a lot of functionality there that would likely be of
help to you, such as getting the angle between two points.
#2 May 22 2008, 6:41 am
Part of the answer to this depends on if the ship can fire as one of its turns, or if firing ends its turn, or both. To me the ship's AI has a few priorities:

  • Don't run into any land masses.
  • Fire on enemy ships.
  • Don't end a turn in a place where an enemy can get to you unless this is unavoidable or the first goals demand it; wherever possible minimize the number of enemies who can get to you.

    Because movement and firing are a limited set of options, you can probably plot out all of a ship's possible endpoints for a turn, and all of the possible points it could hit. Calculate this for your own ship, and then calculate it for the enemies; I'd just use a simple list of turfs with an associated count on each one to say how many turfs are in danger of firing or ramming. The count should only be 1 per ship regardless of how many moves threaten that spot, unless the enemy ship can fire twice, or fire and ram, etc. causing more damage. (Another way to do this is to count the maximum damage a ship could inflict on any spot.)

    In the end you should have one or more "optimal" choices where you maximize your potential to damage other ships but minimize your own danger. If for each spot you encode the move/fire sequence that can get you there, then it's just a matter of following that sequence.

    Lummox JR