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

Node Map Learning

Artificial Intelligence is an amazing topic. The whole concept of a computer program learning about it's environment and adapting to it is amazing. I've always loved AI, and have made many attempts to reproduce it. Though I have run into numerous problems along the way. Mostly due towards my lack of knowledge on the subject, and because of the ridiculous amount of work involved to make such a program. Though this is to be expected. AI is not a simple subject. There's so much involved in it, that it's almost necessary to use large teams to design anything of a decent scale. Though it can be done. So why don't we have AI around us commonly if it possible? Well, in a small sense we do. Neural Networks for example, are used at banks to help read off hand writing into computer text, and can do so with over 99% accuracy. But this isn't the type of machine learning I am referring to. What about emotions? Self set goals? These things are possible, and have been created in several instances. But the design behind them almost seem primitive compared to even small animals. This is because even though we have many different algorithms to aid in machine learning, they all have one thing in common. They are slow. It will often take many, many, many passes before the computer finally gets anywhere logical. Yes, in a sense the human mind is the same way, taking the first several years of our lives to learn about how to interact with the world around us. But we can't wait that long. For a computer, an environment on a scale such as ours would take almost centuries to understand, and lots of storage space. Not to mention a ridiculous CPU to calculate decisions in real time. Resources we don't have to spare. That's why AI is such a largely studied field. It's constantly coming up with new ways to speed things up, and make it more efficient. That's why I'm here. I proposing a new type of learning method which I hope will make learning on a mass scale much easier. Though I do not fully understand every part of the algorithm yet, I hope to keep fleshing it out more and more over time. This information right here is a basic summary of the algorithm, rather then any detailed math behind it.


The Node Map Learning method is machine learning concept which is hopefully better at understanding much larger and more complex environments then regular algorithms such as Neural Networks and Genetic Algorithms. It works by basically creating it's very own node map, (which functions similar to a program's code, shown right) then filling this node map with many, many functions. Anything that can be given to it. This includes stuff like distance between two points, sorting a list, adding numbers, and of course, actual functions for interacting with the environments. The AI takes all this data, and tries to organize it into a complex tree of data processing to work with such. The tree is constantly changing and evolving. Some of the functions given to the AI might be things such as Neural Networks or Genetic Algorithms, in which case it would also use these functions, and as the AI operated, would also learn to make better use of these functions. One last thing to note, is that each limb of the tree, (the data that comes out of functions, and gets thrown into other ones) must have a "type" assigned to it. Such as "number". This means that a function which accepts 1 input in the form of a number can only accept data that is assigned as a type of number. Data types can extend other data types. Such as "integer" would extend "number". Thus, all integers can be used as numbers, but not all numbers can be used as integers. The tree grows constantly as well, becoming more and more complex as needed. This process occurs in a similar method to genetic algorithms. The AI will semi-randomly (see paragraph below) start testing out different tree designs by adding, removing, or replacing branches on the tree. If the new design functions better, use that tree instead. If not, revert to previous tree. This process continues infinity, until there is absolutely no better way of designing the tree, without completely remaking it.

It chooses a base design by randomly creating X number of completely random tree designs initially. (X is determined by the complexity of the environment, though is usually around 100 or so. Though can be much higher for intricate environments.) Then it tests all X concepts, and looks for patterns in each one, and compares these patterns to how well it did. For example, the AI may test 250 designs, and looking at the designs, trees the used the pattern "Function 1 > Function 2 > Function 3 and 4" tended to have better results, while trees that use the pattern "Function 1 > Function 4" seemed to function very poorly. Taking all the patterns into account, it designs a new tree a sees how it functions. Constantly testing it, changing it, and making it better. Each and every new tree that is tested is broken down into a list of patterns and given a numerical value based on how well it functioned. This builds up after a while, and eventually will give the AI a very clear idea of what kind of designs work better then others.

This is my concept. I hope to have a working proof of concept out later. Thanks for taking the time to read this, and follow to keep updated. I will be posting more on the subject soon.