Riding the Fitness Curve!

As a continuation from my previous rant about the obsession with A*, I decided to maybe talk about a concept for a new pathfinding algorithm/method that I've been wondering about.

For those familiar with hill-climbers, you should know that they have a nasty tendency to get stuck at a local optimal. This is uasually not a great idea, which is why Morris came up with the BreakOut method, which is great because what it does is modify the fitness plane such that a local optimal is "filled" in with penalty and the hill-climber just kind of spills out and move on to the next optimal. Thus, you will eventually reach an absolute optimal. This was a really neat little idea since it only required a breakout list that kept track of all the places you've been. The down-side, however, is that the list can get quite storage intensive in the memory if you run it for a long time, or you have a large fitness space.

Tabu search and ant colony optimization had some nice ideas dealing with memory issues. For tabu search, the lists are of fixed length and entries expire. In ant colony, the entries just lose weight and eventually disappear. So, combining these two ideas with the breakout method, you get a breakout method with a decaying penalty that eventually disappears.

So, what does this have to do with pathfinding? Well, pathfinding is just one of those funky problems that contains a few assumption that nicely helps us make the problem simpler.

In discrete pathfinding, where you have a fixed number of "nodes," you get the advantage of A* search, which is nice and optimal, until your number of nodes kind of blow up in your face and then you have to settle with sub-optimal solutions with fixed iterations of iterative deepening A* or just A* that goes n steps deep. Those, I guess we can call the n-A*. The problem gets a little nastier with continuous space, which is where games are usually going nowadays. With real space, you can't really have "nodes" to run an A* unless you assign them yourself, which really reduces the realism, not to mention the flexibility of motion. Well, you can consider shifting way-points dynamically, but still, how many people actually travel along straight lines and splines in an unknown region anyways. Even if you know where you are, there's always a small tad of randomness to your motion.

So, what about path discovery on the fly? Nothing pre-planned with a touch of randomness. Now, the assumption, of course, is that the agent has no knowledge of the terrain, only based on what is within visible range. So, combining tabu search and breakout methods, we can look at the field of play as one big fitness plane where in the beginning, the goal is the lowest point and that the agent is trying to get to it. So, with some randomness, we start moving in the direction of the goal, while leaving a traile of breakouts behind, which raises the fitness plane behind us . This will prevent the agent from actually back tracking. Then, let's say the agent sees a wall with no entrance, it then randomly chooses to travel along the wall in some direction. All this time leaving breakouts. As the agent moves farther from the initial point, the initial breakouts start to decay and disappear.. So, we will basically circles around the wall untill we find a path towards the goal to go past the wall. In a sense, we sort of just surf the fitness wave we leave behind, until we maybe hit a dead-in and turn around and backtrack . Its a little hard to fully describe this concept, but it is a pretty nice real-time pathfinding idea, which is something we use in real life anyways.

As for the other nice thing about it, all visible obstacles can easily be seen as spikes or raised areas on the fitness plane. Since the goal is the minimal, this will automatically drive the agent away from the walls for a certain distance, or follow the walls, depending on the effect.

---------------------------------------------------------------------------------

There is another simpler way too. :p

This just came to mind while thinking about evacuation modelling. If evacuation models can be used to simulate people exitting an area, why can't it be used to simulate pathfinding behaviors in real time?

So, given a goal, obstacles, and other dynamic things along the way, the agent will be attracted to the goal, but repelled by the obstacles. If say in a waze of area with rooms, we can then use the scenegraph to duplicate the attraction of the goal onto entry-ways towards it. It doesn't have to be exact, but the agent will then be able to follow these attractions and move towards the goal. The cost is almost free, and the results are dynamic.