Wednesday, September 5, 2007

AI Pathing system

My AI path finding works like this. Bear in mind I read about A* and thought it sounded too complicated when it's all precompiled anyway.

Preparation:
Open editor and click out a bunch of separate paths around buildings - you should try and make as many paths that lead to other location as possible.

Algorithm:
1. When running AI search find closest path to destination.

2. Start COST at 0

3. While traversing nodes on current path, can any nodes on this path see a path to player OR Is node to next path obstructed? (add 1 to COST per node traversed) Store x,y as you go - the idea is to make a path using nodes of existing paths, the paths are just helpers.

4. If failed on either in 3, continue to end of path (summing COST)

5. When at end of current path, look for next path along "rough" vector toward player - tick FAILED counter - pick next path - log JUNCTION(x) ( and COST to here )

6. If FAILED counter < n, pick a new path from destination and goto 3.

7. When FAILED reaches n record COST for *this solution is stored.

8. Next solution, go to JUNCTION(x) until all paths exhausted.

9. Pick lowest cost path.Presumably, when laying the paths down you should have given the algorithm enough chances to get to the player.

So in this pick (black lines are placed by user/programmer) at each junction only nodes "roughly" heading toward the player (even though obstructed) where chosen.

What do you think? Too complex? Not efficient perhaps? Full of errors ?


No comments: