I've implemented the basic A* algorithm (learning from Patrick Lester's A* tutorial http://www.policyalmanac.org/games/aStarTutorial.htm which was quite frankly excellent) at the moment however i'm wanting to enable the AI entities to follow a target which is being moved by the player i've seen mention of such things as RTA* and LRTA* and MTS (though only briefly) but can't find any tutorials showing how these are achieved or the theory behind them (it doesn't help that google uses the '*' as a wildcard) can anyone help me out here with any good tutorials you've seen? cheers

Quote: Original post by Mantrid
at the moment however i'm wanting to enable the AI entities to follow a target which is being moved by the player

What exactly do you want the AI entities to do? If you can formaly specify your goals, you can also find an algorithm that fulfills them (sometimes even one that runs fast enough).

Three simple ways to implement following a moving target:
a) always move to the current position of the target

b) repeat this a few times:
1) calculate time to reach target position
2) assume the player doesn't change anything and calculate where the target will be at the calculated time
3) replace target position with the calculated position and go to 1)

c) binary search over a timespan in the future: calculate target position after x seconds and minimize time to reach that position

well at the moment it's an app just for me to learn with, so it'll be a pacman-esque affrair, with the player controlling an entity on a 2d grid while the enemy AI tries to land on the square the player is on to "kill" it.

Quote: Original post by Mantrid
well at the moment it's an app just for me to learn with, so it'll be a pacman-esque affrair, with the player controlling an entity on a 2d grid while the enemy AI tries to land on the square the player is on to "kill" it.

Another possible approach for that is discretizing time and use a chess-AI way of dealing with that (it's probably a bit unfair on the player): chess ai techniques on wikipedia

i'm having a look at this at the moment, since it seems pretty suited to the task (moving target search: ishida and korf) since i've heard quite a lot of good things about it

Quote: Original post by Mantrid
i've seen mention of such things as RTA* and LRTA* and MTS (though only briefly) but can't find any tutorials showing how these are achieved or the theory behind them (it doesn't help that google uses the '*' as a wildcard)

Look up Sven Koenig's website. He has several publications regarding RTA* etc and a good review paper covering all of these associated methods.

Cheers,

Timkin