AI and shapes in 2D Grid

I'm working on a grid- and turn-based strategy rpg. My problem is concerning finding best position for my AI to use a skill. But lets start at the beginning.

My plan is to make each skill an action for my AI. It checks for each action how effective it would be, chooses the best and does it.

Each skill has a usage and a affect area that can be circular or shapes like

[
[1,1,1,1,1],
[0,1,1,1,0],
[0,0,1,0,0]
]


which can be used in 4 directions.

The most simple solution would be to just check the affect area for each position and direction of the movable and usage area. But as these checks can get quite intensive I want to minimize them as far as possible.

One approach would be to combine the circular movement area with the skills usage and affect areas and find all target entities in it. So I have a list of all entities that could be targeted by the skill. The next step would be to group these entities by the skills affect area to rate it higher when the skill hits multiple targets. And as the new position and direction should get into that rating as well I have to check all possible positions for each group. And I've no idea on how to effectively do that.

1) Does this AI approach makes sense?

2) Is there a better way to define such grid-shapes and apply them to the checks later on?

3) Any ideas on how to group the targets by the skills usage area or minimize the positions and directions to check by the knowledge of where the target entities are?

EDIT: After this is not going to get answered I have to ask another question: Am I bad in asking for help? In the 10 year's I'm developing now there were like five times were I really couldn't get further without a tip. But unless which way I try to ask for help (in the internet, asking the few developers I know or someone outside of the industry for understanding problems) I've never got any. To be fair I'm only coming with real problems after being stuck for days. But as I see the internet full of perfectly answered questions I begin to think: Is that my fault? What makes this question not worthy for an answer?

• You are not bad at asking I just doubt most of us have an answer, this type of opimalizations is rather mathematical. Jun 23, 2014 at 11:52
• Really thanks for saying that. This thought put me in a bad mood, you've saved my day!
– fery
Jun 23, 2014 at 12:10
• It's typical for people who ask for questions to have questions that very hard, you say you only have turned to the Internet 5 times. That means you think about your problems yourself which is good, you are also likely to be searching for your answer, also very good. However if neither find a solution then we on the internet have to find a solution to that has not been solved on the internet before and isn't trivially easy which can take a while. Jun 23, 2014 at 12:17

Is it really fun to play against an AI that is "perfect"? Perhaps better is to randomly sample N configurations, and choose the best one out of those N. Here, choose N such that the computation is not too intensive.

You can of course make a hybrid solution: For every skill, try N random choices, or something like that. You can make the choices "better" by perhaps making it more likely that you are close to something you want to hit (but this depends of course on what information you have available).

This is a quite complex problem, are you sure you need to optimize this (how big are the areas?), One options is to generate a 2d array for each power (note different orientations = different powers)and use it to store how many chars you can hit if you target that position. You can calculate this by picking each character and then increasing each position that could hit that character by one. You then keep track of the best square and target that when you have checked each position.

So

int[][] hit
for each char
for each power
for each tile hit by power
hit[tilex][tiley]++
if(biggest(hit[tilex][tiley]))
temphighest=tile
target temphighest

• No, I'm not sure. As it's round based the AI can take a few seconds and that was my last hope. I'm not sure on the areas now, but it wont be to much. I'm going to try to check all positions and see how long it takes.
– fery
Jun 23, 2014 at 12:11
• I think itś the most effective method but you could otherwise ask at math.stackexchange Jun 23, 2014 at 12:12
• and are these few seconds with the algorithm I posed or by just looping through everything? Jun 23, 2014 at 12:22
• I'll try both ways.
– fery
Jun 23, 2014 at 12:33