I am creating a turn based top down game and looking to make my AI a bit smarter. I have implemented A* for my game and currently if a entity is blocking the way to my player the pathfinder does not return a path since I simply don't add the node. I could just add the node so the entity will line up but I imagine this could end up in a long queue while there might be other paths available.

To tackle this I could increment the cost of the tile when this is occupied by something. Let's say I want the entity to circle around by four blocks, I could multiply the tilecost by 4. When there are two entities blocking it will look for another path 8 tiles around. Perhaps I could increment it depending on the life of the creature and average damage the player does. What are some good numbers here?

And what about calculating these "chokepoints" in advance? This would really add to the inteligence of the ai when there are multiple enemies incoming and the player decides to enter a room these enemies will anticipate a path to another door into this room. I guess this means I need another graph that has altered connection cost relative to enemy position vs player position. Is there any good read about doing this since I cannot wrap my head around how ti implement this properly.

I'm looking for any other tricks that makes pathfinding for my AI a bit smarter.

If you are able to mess with the costs of your edges then just disable them instead. It sounds like a really bad thing to do this with costs. That said I think you want the AI to still try to go there but discourage them from doing so slightly which sounds like a good idea and I wouldn't be against what you suggest if that's your intention. You could instead of having fixed weights have it as a function, you'd still have fixed movement costs but then it could drag in other things like if it's a choke point, if the path is occupied etc. Something like:

cost = fixedMovementCost+occupiedCost*IsOccupied+chokePointCost*IsChokePoint

The idea being that some parts you calculate before hand and some parts are dynamic. I haven't used this myself and there is probably a more standard way top deal with it.

No worries I made my edge cost final/constant. What I meant was something having something similar as you suggested. A cost multiplier which ads to the G value of the node when it's occupied.

if (occupied)

{

multiplier = 4;

}

node.setG(currentNode,getG() + (connection.getCost() * multiplier));

Working like a charm but I like to have more influence on it as to when it should stand in line and when it should circle around. For a beginning the multiplier can be derived from the creatures current health. Maybe even switch with another enemy on appropriate times but I guess the latter should be handled by my FSM.

I wonder if you can predict where the player is going.

The simplest I can think of is to compute

A = distance 'previous position -> destination';
B = distance 'previous position -> current position';
C = distance 'current position -> destination';
D = A - (B + C);

If the player travels to the destination, D should be close to 0. If he/she moves away from the destination, it becomes negative.

Computing these values for many destinations is quite expensive though.

I'm looking for any other tricks that makes pathfinding for my AI a bit smarter.

the first obvious trick is to consider tiles occupied by an entity as impassable, and run A* often enough to account for moving objects. but that may be too slow (even with round-robin updates) if your search area is too large or you must do pathing for many entities or a combo thereof.

the only other real A* related option is to try to fool A* as you're doing now. but results can be incorrect.

often times, A* is used for pathing thru static obstacles, and other methods are used for pathing around dynamic objects. for example, A* with heuristic collision avoidance of dynamic objects might be one possible approach.

remember, A* is always correct, its just slow, and must be redone whenever the search area changes to maintain current correct results. so A*'ing everything every update will always work - but may take too long.

I was thinking about that too, but OP is turn based, so doesn't have to worry about A*ing every frame. Is the game Tile based? If it is, then dynamic avoidance won't really work either. Depending on the game, clustering the AI/having the AI line up could be bad, for example, if the player has area of effect attacks, so you may want to have anti-clustering as part of the choice in location. Not modifying the heuristic, but in modifying the choice of destination.

No worries I made my edge cost final/constant. What I meant was something having something similar as you suggested. A cost multiplier which ads to the G value of the node when it's occupied.

if (occupied)

{

multiplier = 4;

}

node.setG(currentNode,getG() + (connection.getCost() * multiplier));

Working like a charm but I like to have more influence on it as to when it should stand in line and when it should circle around. For a beginning the multiplier can be derived from the creatures current health. Maybe even switch with another enemy on appropriate times but I guess the latter should be handled by my FSM.

I do something like that in my game. Different types of units have different weights. The overall targets are set by a higher level AI.

but OP is turn based

in that case, just start with brute force by A*'ing each unit just before they move each turn, and count other units as impassable. sure you solve a whole path just to get the next few tiles you'll traverse this turn, but they are the right tiles. if you have the clock cycles, use them. and units will automatically path around other units that way - in an optimal manner.

I remember seeing an article in one of the AI Game Programming Wisdom books where everyone was pathfinding together and reserving the blocks they would be standing in at each increment of time. So if at now + 3 I was going to be in x,y, no one else could use x,y at now + 3.