Dear All, In the interest of boosting community spirit and getting people to share ideas more freely. I have started this thread in order to discover the variety of Pathfinding algorithms that people are using (or just plain thinking up). I'm going to cheat and save some of mine 'till I get some responses (no use exposing ones hand before the game has begun)... but just for those who may not know much about the basics of pathfinding (like what the bleep is it?), here is a quick primer (its late/early so it might not be particularly clear)... I'll try and keep it in plain english. One of the many problems faced in games today is the Pathfinding problem. How do you get from place A to place B. Clearly if you have no obstacles and the terrain is uniform - you simple draw a straight line. But if you are trying to find a good route through treacherous terrain, the problem is made more complex. Before I can give any meaningfull examples we need a theoretical environment for this pathfinding algorithm to work in. So we'll keep it simple for the sake of example: You have a map comprised of a grid of squares, each square has a cost associated with moving through it. How do you find the lowest cost route from any point A to any point B. Simple enough... We'll start with the basics. I won't go into too much detail since there is good documentation elsewhere (but feel free to email me if you want me to give you more information or suggest further reading material). THE BREADTH FIRST SEARCH Simple enough. You form a tree, where the root of the tree is where you are and somewhere higher up in the tree is where you wish to go. Each branching point in this tree represents a location, each branch represents a journey between locations. You want to find the branching point (or node) that matches the location you wish to find. I don't know how this diagram will come out but here goes... Root (I know its upside down, humour me...) / / \ \ First layer /\/\ /\/\ Second layer Ok. That is a very simple tree. In a bredth first search you check each of the first layer branches first, then each of the second layer branches, then so on. Childs play. Whats good about this? Well, the breadth first search will always find what its looking for if it exists. It is the basic standard. And you can do funky things with a breadth first search to make it work much faster. Whats wrong with it? Well - its too damn slow, it finds every damn thing, it doesn't filter out any chaff and it doesn't do hardly anything to maximise it searching speed. If your map is very large then it will take ages, but it works fine for very small maps. What about movement costs? Well, we're now stepping away from pure breadth first searches into something slightly different... We have our grid of squares, each with an associated cost. This will be a nightmare to understand if I bollox it up in my drunken state, but here goes: You have your starting square, you look in each direction (lets assume you can move in 8 directions) and see what the cost of moving in to each of the adjacent squares is. Then you place a counter on that square which is equal to the cost of moving into it. Also place a pointer that points back at the square you started at. Once you've done that to each of the adjacent squares we get into the main loop: Go to each of the squares you have a counter in and reduce the counter by one. Now go back through those counters and see if any of them have reached zero, if they have: First, check if this is the target square, if so you've done it (see later on). Next, look into all of the squares adjacent to this particular square. If any of them don't have a counter on them, put one down (just like before) and place a pointer that points back to the current square. (yawn...) Keep going until you have no squares with counters of zero or more - or you have found the target square. In the first case, there is no solution. In the second case, you have found an optimal solution. Trace the back arrows (breadcrumb trail) you left behind and you will have the lowest cost route possible. If you kept on going after finding the first (just until you finish one cycle) you will find all the other routes that have the equivalent (still optimum) cost. You can limit the processing time spent easily, because by limiting the number of cycles you spend conducting this search, you limit the amount of processing and you do so in a way that is equivalent to saying I will not bother with this journey if it will cost me more than X (where X is the limit imposed on the number of cycles, which due to the way the search works is the same as the total cost of your optimum solution). Anyway, I've got work to do - I will continue this later... Sorry if that was a clear as mud and sorry if its buggy as hell. It's only a simplistic start, there are lists of improvements and alternatives. But that is what I want to encourage - discussion about different ways of solving this problem. Must dash, Ben Chapman (I'm on call so I don't have time to check this submission through - I'm going to have a heart attack when I read this again in the morning...)

Some I know of Breadth First: Expand the node least recently expanded (i.e. traverse the tree across before stepping down a level). This is more complete than depth first because depth first can get stuck if a branch is infinite. Uniform Cost: I think this is what you described last, always expand the node with the cheapest cost. Best-First: Assign a hueristic to each node, that is an estimate of the distance to the goal. The hueristic should never over-estimate the distance. Expand the node with the lowest heuristic. A*: Combination of Uniform Cost and Best-First. Expand the node with the lowest cost+hueristic. This will always find the shortest distance. There is also Hill Climbing where you pick the direction that seems to be going in the right direction (i.e. uphill if you want to climb a hill). [Edited by RSmithies on 24th March 2001 at 11:19 AM]

Excellent, The game is on. Now those are all listed (with excellent discriptions) in Russel & Norvig's Artificial Intelligence: A Modern Approach. Plus a few you missed. They are textbook solutions. Lets see some more cutting edge stuff (any chance of being graced with Lionheads opinion?). Btw RSmithies, although I hadn't mentioned uniform cost or best first in my first mail if you look carefully you'll see a dodgy version of it in the examples. More textbook solutions: 1. Iterative Deepening 2. Bi-direction searches (excellent when you know the start AND end point of a search already - so quite saucy for pathfinding AI) 3. You can also use CSP methods, R&N has some information on this but Edward Tsang's Foundations Of Constraint Satisfaction takes it far further. 4. Genetic Algorithm style searches. (Groovy...) 5. You can even go for more behavioural methods to using Distributed AI Techniques. 6. Plug macros into you search for optimisation a la Machine Learning (I have some excellent texts on this I could possibly scan in if someone asked very nicely). I'm sorry for the lack of detail, but I'm very tired after being on call all night. Consult the texts or send me email queries and I will help who I can. Ben Chapman

Another point, I think you may want to look again at your definition of depth first search. Its not quite pukka is it? Ben Chapman

Yeah, swap depth and breadth round - sorry, I have a rather large hangover at the moment I've edited it now [Edited by RSmithies on 24th March 2001 at 11:20 AM]

Come on lads, I know its saturday and we're all hung over from last night but lets get our brains in gear. I've had three hours sleep having worked through the night, I've filled an ashtray and drunk my last bottle of Cobra. Time for wide ranging discussions. We need to use our freedom of though while we still have it We must have enough talent spread over this discussion group to create games that push things even further than black and white. We just need to put our brains together. Ben Chapman

Look up "Branch & Bound" searches. They're really good for Decision Tree learning. It's late and I can barely spell straight, so I may have to leave it up to you to find out about it. Hope I made some semblence of sense.

Yup, Branch and bound was one of the strategies I learned in 1st year AI. We're getting into heuristics now, which is positive. There's also: Iterative Broadening, Backtracking, Lookahead searching (Forward checking), Theres the CSP ones: Directional arc-consistancy lookahead (DAC-L) Arc-consistancy lookahead (AC-L) I've got quite a lot of texts concerning all of these. A few research papers and a shed load of course notes. But at the moment we're just spouting names (I'm trying my best to provide references and if asked nicely I'll even show you how to do them). I think for all the wannabe games programmers that are dealing with this kind of problem as they build a game, it would be usefull to know what the profesionals are using in their games. Its not a really big thing, most of the techniques can be found in research papers and can be figured out from first principles. But I'd like to know how Lionhead et al have solved the problem and how they managed to save processor power and memory consumption while still retaining accuracy (not that all did). And what of the behaviour aspect, do real people solve this problem in the same way? Is there a split between the game AI and real human behaviour here? Does that harm the realism of the games? How do you get around this? I've know some tricks but I'm not so stupid as to think I know everything. Ben

Behaviour based ant colony system style. Each ant wanders stochastically, so it generally heads for a point attractor (the destination) but with some random element. Each ant (bot, creature, agent, tank, person, whatever) drops a pheromone in each space they go to and the effect of this pheromone is to increase the chance of an ant stepping into this square. So you step into a square based on it being closer to the target, having more pheromone in it and with a random element. Pheromone slowly dissipates btw, so after a while it'll be all gone if no other ant walks through that square, meaning that unused paths dissappear. The first few critters may take an age to get to the target if it's a complex route, but the more creatures walking from A to B, the more optimised the path becomes with almost no computational overhead. Not optimised for time or effeciency _but_ it's another to do it. For more info look up "Ant colony system" or "Ant colony optimisation" by Eric Bonabeau or Marco Dorigo. Mike

Excellent, I'll look up that article. I've also got a load of uni material on various researchers efforts in this area related to MAS using gradient fields and pheremone/token trails. This moves towards natural movement, but I have my doubts about its speed and resource requirements if you where going to use this method for optimum path finding. A similar idea has been used to solve travelling salesman style problems - particularly in reference to the movements of oil tankers. In fact, I did a similar thing as my third year AI project (Distributing Resources With A Multiple Agent System). I'm sure you could also come up with (or maybe I'm remembering an article I've read) a contract net protocol method of solving pathfinding. And it would be interesting to formulate it as a constraint satisfaction problem. So many ideas, so little time... Soon I should put a whole block of material on the web. Ben

A* gets my vote most of the time. Interestingly, what I've found to be more tricky (in complex 3d environments) is avoiding the dynamically moving obstacles (especially other characters), rather than getting pathfinding to work for a single character (which is pretty well documented). There are often special situations which need to be taken account of. For instance, if there is a tunnel with multiple waypoints in, but only enough room to fit one character, and two characters want to go through it in opposite directions. Other situations include characters potentially getting 'jammed' in between e.g. door frames, so that they cannot free themselves, and only move if a character further up in a chain moves.

Yes, unpredictable moving obstacles can be tough. The most elementary way of getting round this is to continuously revise your route in the light of changing conditions. If you can check for events which invalidate your planned route you can then generate revised plans. Deadlocks can be a pain, but you can come up with an order of precendence and let the 'dominant' agent move while the 'submissive' agent backs out. Any other clever methods you know of? Ben

Okay, this is a general theoretical suggestion rather than something I've personally tried and tested. However, try having two layers of path finding AI, one using A* type general pathfinding for planning and a second using reactive, flocking (though not flocking but based on the position of local obects around you, their speed and trajectories, perhaps evolved) style behaviours. Use the planning layer to give a direction of general travel which translates into a local attractor in the behaviour based level, then the reactive side deals with the dynamic object avoidance. Sound reasonable? I thought so. Mike

I've been thinking along similar lines of late, because I am looking into pathfinding in a world of continuous co-ordinates (rather than squares) with movement that occurs at any angle rather than at compass directions, involving turning radii, acceleration and deceleration. The idea of planning a general route then using a more behaviour based mechanism to execute that plan is very attractive. I'm fairly sure I've read a paper on a similar system, maybe something to do with subsumption architectures in robotics. I particularly like this because I think it will tend toward more fluid and natural movement. There are some fairly good articles to be found at http://www.gamasutra.com, one includes some good ideas for smoothing pathfinding and adding realistic turning. Ben

For a little pet project I recently evolved a wee beastie to run around a world collecting food. The GA was based on "the more food you get the fitter you are", then I bred from a random triplet, the fittest two being the parents, the least fit being replaced with the new child. The creature had 10 inputs from the world in front of it, telling it the amount of food in each of 10 circular areas forming a triangle of inputs to its front (two in the first layer, 3 in the second layer, 5 in the third layer). Using this as an input to a neural network with 2 outputs to forward/back movement and left/right turning angle the creature became very good at hoovering up food, to the point it really looked fairly intelligent for that behaviour. If you reversed the idea, so that it's inputs were the number of creatures in each circle in the world around it and the fitness function was to move towards a specific point (also an input into the net) from its current point (another input) without hitting any of the observed obstacles then I imagine it should work equally well. The final network I used for my experiment worked just fine with no hidden layers or recurrence, so just 20 connections. Not a huge overhead unless you have thousands of creatures in the world. Mike