Previous Blog Next Blog
Prev/Next Blog
by date

AI Pathing system for BRAVE

AI Pathing system for BRAVE
Name:Andy Hawkins
Date Posted:Sep 05, 2007
Rating:2.0 out of 5
Public:YES
Comments:YES
RSS Feed:GarageGames Blog feedor Subscribe with .
Profile Page:View profile page for Andy Hawkins

Blog post
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 pic (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 ?

Recent Blog Posts
List:07/28/08 - Lightwave Tut and BRAVE progress
05/31/08 - BRAVE Troop Deploy Code and Modelling
05/15/08 - BRAVE Base Camp
05/04/08 - BRAVE Beta Release
04/27/08 - BRAVE - London 4
04/21/08 - BRAVE - London 3
04/13/08 - BRAVE - Awwwright! - London 2
04/09/08 - BRAVE Update - London 1

Submit ResourceSubmit your own resources!

Tom Cassiotis   (Sep 05, 2007 at 17:09 GMT)
I think you should take a look at Dijkstra's shortest path algorithm. You are basically building a network with identical weighted edges (you can change that to have the weights reflect the distance between nodes) and running a shortest path algorithm.

Stand on the shoulders of gaints :)
http://en.wikipedia.org/wiki/Dijkstra's_algorithm

Phil Carlisle   (Sep 05, 2007 at 17:38 GMT)
I'd read about A* again. The reason why everyone uses it is that it is pretty much the best solution. What youre talking about is a heuristic that chooses links that "move towards the goal", which is exactly what A* is, its a heuristic based flood fill.

Seriously, think about it again.

Andy Hawkins   (Sep 06, 2007 at 00:30 GMT)
Thanks for the advice. I'll read up on those again.

You must be a member and be logged in to either append comments or rate this resource.