So I'm making a turn based game, it's in a 3D engine but it's really a 2D game I guess.

I need to be able to tell what characters are visible to other characters, but I calculate all the AI decisions for the turn before the enemy takes its turn.

The game has interrupts so it's important that the AI is smart enough to be aware of terrain. What I mean by this is imagine that they are running down a corridor. At each branching they need to be careful because if an enemy is there their turn might get interrupted. They also could choose to guard that spot for a turn before proceeding, just to see if someone is coming.

So if they just blindly run around it kind of kills the ability to have good AI, but I am not sure how I should do this. I guess I could precalculate the walkable areas into convex polygons. The problem here is on some maps there could be open levels. Imagine two walkways across from each other. The terrain and walkable areas are not contiguous but the areas are still visible. Also it's kind of a lot of work (though this will help with pathfinding as well).

Is there some other way to go about this? I have read a little here and there but mainly for FPSs or RTS not so much for a turn based tactical game.

Perhaps a little better explanation of the game?

Think Jagged Alliance 2, but in 3D, with single level 2D maps. If you don't know what that is explaining would take a great deal of time.

But the idea is I need to be able to do things like move to an areas I can fire at someone from, and have the enemy be able to figure out where cover is, and to be able to figure out areas to guard or be wary of crossing - they need to be able to tell if moving somewhere will possibly make them leave cover in case an enemy is around.

An interrupt means if the enemy has enough action points then if you come into vision they have a chance to interrupt their turn and use any remaining action points. So they can go into cover or more likely shoot you up.

If I can't figure that stuff out before the AI moves it will seriously cripple it as one mistep can mean death for a game like this. Of course most of the games like this have simplistic AI anyways, but I don't want to give up on it yet as I think it will make the game much better.

Every unit should plan for the worst ways in which its "ideal" turn can be affected by enemies:

• Could I be shot if I step into that square?
• If it isn't a safe square, what enemies could be able to shoot me? How likely are they to shoot me, instead of being obstructed or doing something more important?
• If lead starts flying, where can I retreat?
• Do I have enough movement points to get there, or I'm going to end my turn exposed?
• How hurt I'm going to be if I run for cover? (This is a very good way to choose between different places)
• Am I going to be hurt more or less than that if I stay in the open and shoot back? (Unlikely without superior firepower)Turns could be analyzed and executed without getting too clever with heuristics and statistical models and abstractions as a game tree, with position evaluation flexibly based on a combination of not getting hurt, killing enemies, reaching given destinations and so on, and moves consisting of walking, running, turning, stopping to listen etc. square by square, shooting different targets, and in the enemy's case showing up in different places.
  For every action point of the turn, pick the sub-move that guarantees the best worst-case state at the end of the turn (the traditional minimax criterion) and reevaluate as needed if new information is obtained: for example, if you step in front of a certain corridor and nobody is there, the whole subtree in which you stop for a shootout is dropped and the subtree in which you spend the rest of your action points to walk down that corridor becomes more attractive.

Why do you need to calculate the entire move first? Why not just use your movement points one at a time? That way, you really don't need to interrupt yourself... just make a decision based on information you've acquired throughout your move.

Why do you need to calculate the entire move first? Why not just use your movement points one at a time? That way, you really don't need to interrupt yourself... just make a decision based on information you've acquired throughout your move.

Because I want to have strong AI. I don't mean the AI term strong. I also want it to be fast. Everything is multithreaded and currently there's zero wait time. A similar game, Silent Storm, can churn on for 20 minutes to a single turn in some cases.

But this is not causing any real problems anyway, and it's nothing to do with interrupts. Interrupts are a game feature, not a programming thing. If you just have event driven AI it's going to totally suck. The AI for a game like this needs to be more like chess where there's planning ahead, though it doesn't need to be exhaustive and I don't want to make it throw out simulation aspect completely as it makes things seem too gamey. Meaning I want the enemies to behave realistically, sometimes smart, sometimes dumb, but always in a way that makes some sort of sense. Not just wandering aimlessly until I put a bullet in them. That works ok for FPS but not for a game like this.

Every unit should plan for the worst ways in which its "ideal" turn can be affected by enemies:

• Could I be shot if I step into that square?
• If it isn't a safe square, what enemies could be able to shoot me? How likely are they to shoot me, instead of being obstructed or doing something more important?
• If lead starts flying, where can I retreat?
• Do I have enough movement points to get there, or I'm going to end my turn exposed?
• How hurt I'm going to be if I run for cover? (This is a very good way to choose between different places)
• Am I going to be hurt more or less than that if I stay in the open and shoot back? (Unlikely without superior firepower)Turns could be analyzed and executed without getting too clever with heuristics and statistical models and abstractions as a game tree, with position evaluation flexibly based on a combination of not getting hurt, killing enemies, reaching given destinations and so on, and moves consisting of walking, running, turning, stopping to listen etc. square by square, shooting different targets, and in the enemy's case showing up in different places.
  For every action point of the turn, pick the sub-move that guarantees the best worst-case state at the end of the turn (the traditional minimax criterion) and reevaluate as needed if new information is obtained: for example, if you step in front of a certain corridor and nobody is there, the whole subtree in which you stop for a shootout is dropped and the subtree in which you spend the rest of your action points to walk down that corridor becomes more attractive.
  

I agree with this but the problem I have is mainly how to figure out what constitues these cases.

There's also no squares as such which makes it a more difficult problem. So somehow I need to be able to see not only every place people can see each other from, but to search out cover, and determine places where moving into them might expose you to enemy fire. But if I just shoot out a ton of collision detections as I analyzed each possibility then I know the performance is going to be disastrous.

So I'm hoping there's some data structure I can create to help with this.

It's a very difficult problem, unfortunately.

Influence Maps (unfortunately frequently regenerated in your case as the player units move).

An overlay grid of cells (with size small enought to have adaquate simulation of proper visibility, but large enough to be efficientlt processed) ontop of 3D terrain system.

Each enemy sweeps an angle range they can see around them with line segments marking cells they see (each line extending out before being blocked by terrain- stopped)
(set some maximum interaction range to minimize the length of sweep lines - a canned vector table of steps for all grid stepped lines can speed up processing)

Optimization is have seperate maps for each enemy and those not moving dont need to regenerate theirs.

The resulting maps mark the areas visible to the enemy unit(unmarked are areas of cover) for firing solutions (maps are summed for use against the player)
They (enemies) might try adjacent positions and see if they get better coverage/crossfire etc.. and adjust themselves once the player is known to be lurking.

Similar maps generated by the player avatar (and his allies) are generated - the enemies will try to avoid places they can be fired at (or multiiple fired/crossfire)


This method in a crude resolution may be used to cull further processing of more exact calculations (lazy evaluation)

---

Decisions of which places (cells) to move to is the real AI (A* path under the least enemy fire or general tactics after many options are evaluated)

When enemies positions are known, then the potential threat of where they may move to quickly and start firing calls for yet more 'future' influence maps
to be generated and evaluated (future utility of a position)

It would be even more fun (complicated) if there is 'fog of war' uncertainty of what the enemies can see (when itrs not certain where they will be)


You may notice that this still constitutes alot of processing for possibilities (most vealuated even though never used). Its the main reason that good AI
isnt done in so many games for so long. There usually is not real shortcut.

Thanks wodin, that gives me something to work with. I was hoping there was some easier way to do things but maybe that's not possible.

I looked into it a little more. I don't think I really need to make influence maps person by person or that it would help me.

For one I don't want to find cover from a specific character's current location, it's more to realize what areas are "danger" areas in general. So if stepping outside a building or into a corridor intersection, the AI needs to be able to realize it might be walking into a hostile location.

So I really need a data structure on top of the walkable node areas where I can query if 2 nodes are visible to each other that returns a fast result. But generating that out in brute force could be quite time consuming and require a lot of space. There's something like 100k nodes in a typical map I'm using.

Now I'm trying to think if there's some way to partition this into larger spaces then connect those or something.