Pathfinding as Better AI

When most people think of pathfinding algorithms, such as A Star, they think of simply finding the shortest distance between two locations on a map. Although this was it's original purpose, it can be so much more then that. A lot of implementations of pathfinding take advantage of the movement cost to make the paths more realistic. Such as avoiding wall-crawling, or preferring to walk on the sidewalk instead of grass unless necessary. These are very simple operations, but yet have already rocketed the simple find-the-shortest-path to a more natural, actual walking pattern.

But why do we have to stop there?

Let's build onto this a little bit. Instead of messing with solely the cost to move to a specific node, let's add more nodes. In addition to nodes like "move north," "move south," etc. Let's add "sprint forward," and "jump forward." Then adjust the cost to include time taken, and energy consumed, and demand to get to the end as quickly as possible. By doing this, more complex paths are available. Enemies will walk around normally, but when a player starts to walk by, they will rush towards you. Possibility breaking into full sprint to get to the player if they need. Adding a maximum energy could even persuade the enemy to give up, if it becomes too difficult to reach the player. Imagine how realistic monster movement would be now!

We can go even deeper.

What if we add even more complex functions. Such as "wait," "swing sword, " "shoot bow, " "drink healing potion." At this point, imagine how much more complex the creature's intelligence will become. It could actually hide behind a pillar out of the player's sight, and shoot a bow when they're not looking. Or charge up and hit you with a sword, then run. The possibilities quickly become immense. Simple enemies are become something to fear, and computer controlled pets become the most important companions.

Pros and Cons?

Well, there are a few of each. For pros, it adds a very high intelligence simulations. And it's highly flexible.

Cons, wells, balancing the point values can be a little tricky. I'll explain how to work with scoring, below. But the biggest issues are calculating heuristics, if applicable, and performance.

Performance is something that becomes a huge resource on this. As so many more dimensions are being explored. Working even on a simple grid instantly becomes a massive chore for the CPU. In addition, if heuristics, which are already very difficult to calculate, are done incorrectly, the computer could be wondering around for quite a while before finding an acceptable path. As for heuristics, it's much harder to calculate, as now multiple paths are being explored, such as "should I sprint or not?" This effect can hugely break the outcome for algorithms that depend on it. A star can get away with it, by always setting the value to 0. Though it will take longer to find a path. (Though it will always be the most accurate path to meet your needs.

Scoring is a little weird, but easy if you use square mean. Basically, make sure all values you're scoring, raise about the same way. (Such as the all have roughly the same starting and ending values. And none level up faster then the others.) Now, for each node, get all scores for it. Raise all of them to the power of 2. And find the average. That is the cost for this cell. :)

Now, much sure for make each cell store as little memory as possible. In really difficult situations, it may take many, many nodes to find a result.

In summary, this is my proposal. It sounds great in theory, but I'll have to test it some to see how practical it would actually be in real AI. Thanks for reading, and I hope this gives you some ideas for your game/program/whatever. xD