CGT Honors Project Blog

Finished

2009-05-19T15:23:00.001-07:00

Handed in my project today. Just need to work on the poster for friday

Honours Project

2009-05-17T15:20:00.000-07:00

I am now more or less finished. All the sections are in, some of them need a few changes but nothing major. I will have to go and format the entire document which hopefully shouldnt take too long. Ive had it proof read again, still have a few comments in it where i have missed things or need to explain them more. Also still have to go through it and number all the figures etc

progress

2009-05-10T14:55:00.000-07:00

The results write up is now finished as is most of the conclusions and future work.. Had the presentations last week, seemed to go fine. The application is now finished, will try and improve the visuals if I have time.

Ive been going through alot of the dissertation and again rewriting large sections of it, mostly to try and reduce the work count a bit. Ive had a few people read it through, including my supervisor who all agree that it would be very hard to remove parts without leaving a hole in the report. Therefore, it is going to have to stay the size it is.

progess

2009-05-01T14:50:00.000-07:00

All the testing is now done and ive started organising the results that were dumped to text files into an excel sheet to make charts etc.

Ive spotted a few that might have to be done again.

I've now started wrting up my results section. I have finished the methodology section completely and will go back to it at a later date.

I have also briefly planned out what will be in the conclusions/ future work sections

testing

2009-04-28T14:38:00.000-07:00

I have now fixed the problem i was having previously. Testing is now able to continue. Again, still just reading over my dissertation while running the tests as it is taking up most of my time

Progress

2009-04-22T14:02:00.000-07:00

Managed to get more test done, however, hit a problem with the fact that it was running in release instead of debug, which meant that for some reason, a few minor changes that were made didnt actually apply to the program. This lead to several tests having to be scrapped.

To solve this, I'm going to have to completely redo several tests just to make sure that the results are fine.

As for the dissertation, I have been proof readin what i already have and rewording several sections at a time to make them read better

Testing

2009-04-15T14:18:00.001-07:00

I have now managed to get up to test 20 which has involved running the program almost 600 times! I aim to have all the testing finished by the end of this week so that I can go back to working on my dissertation.

Update

2009-03-30T12:50:00.000-07:00

I've spent the last few days completly re-writting sections of my dissertation. The fuzzy logic section of the literature review, as well as the FIS and FuSM sections have been reworded. The FIS and FuSM methodology has also had some re-wording and extra information put into them. Made a start on the Environment section of the methodology but decided to leave it untill the project has finished as I'm planning to redo parts of the environment code if I get the chance.

I've started writing up the results plan. There is so much that can be tested with this project that I'm having to spend a good deal of time working out what I will include in the results section along with an explanation about what the result is telling me. I can see this taking a good few days, I will mostly likely have to schedule another meeting with my technical supervisor to go over it just before I finalise it and begin the testing.

I've also for the first time been able to run the application with everything in it and the manager running which has reveled to me several hidden bugs as well as things that I had simply forgotten about. I'm going through these and trying to fix them as they come up. However, with the manager running, the ecosystem does seem to maintain itself within a state of balance which is what I had been hopeing for.

Progress

2009-03-24T15:42:00.000-07:00

I think that is now me officially finished implmenting the techniques into the application. The fuzzy inference system now feeds the final defuzzified value as input into the fuzzy state machine which then performs transitions based upon the input.

All that really remains to be done with the techniques now is continue to tune them so that they work better together. Some of the techniques simply feed into empty functions, these will have to added to so that they now have an effect of the ecosystem. The fuzzy state machine at the moment does not actually do anything to the plant that it is monitoring, however this should not take long to adjust.

Continued to reword my FIS implentation section. I have one last thing to check on it before it is ready to be added into the first draft of my dissertation.

Progress Update

2009-03-23T14:15:00.001-07:00

Earlier today I managed to get a defuzzification method working on the Fuzzy Inference System within the application and am now able to return a single crisp numerical value. This value will then be fed into the FuSM. This now means that all the techniques that were going to be implemented within the application have been created and added. Now that these techniques are in place I can focus on making them work together.

More work has continued on the creating of freely growing vegetation within the environment. While in theory the methodology in place for this should work fine, after about 40 new plants have been created the graphics side of the application locks up. The program itself does not die as the console window continues to print of data as the ecosystem ages. A cause and a solution to this problem have yet to be found.

Yesterday I completely re-done the FIS methodology section as I found some much better research on it. I now have to go back and finish off the methodology for the FIS, writing about the Defuzzification method, and then further update the FuSM.

The implmentation of the environment itself also has to be written up.

more updates

2009-03-21T11:00:00.000-07:00

While I wait to have another discussion about my FiS within the application, I moved on to "tune up" parts of the ecosystem itself. While doing so, an architecture problem was uncovered. This problem related to how much vegetation and water could be present within the ecosystem at any one time. While on its own it does not appear to be very problematic, however since it had been continually build ontop of and the fact that several other components of the ecosystem were dependant on this a solution had to be found. The solution I was looking for would allow a limitless number of plants and lakes to be formed, simply creating new instances of the respective classes on the fly as the program ran. Two attemps at solving this earlier on were through the use of the STL - namely lists and maps. Therefore much of the day has been spent tyring to implment these as solutions. However, in the end, a much more straight forward solution was devised.

If the plant life was allowed to become unlimited, then the ecosystem itself may become to overpopulated resulting in the death of everything. Therefore an array of 100 pointers to the vegetation class was created which would remain nulled untill a new plant appears. Since the herbivores will always be eating, there will never be the full 100 plants on screen which means when one dies off completely, it can be remade in a new location, giving the impression of freely growing vegetation.

Some basic tests have been carried out with this approach, a new tree has been grown at the end of each system day. This method itself seems to be working fine, however a slighty annoying bug has developed which results occasionally in 2 plants being created instead off one as well as the positions of the lakes changing when a new tree appears.

With the dissertation, the Methodology section is almost finished, all that needs to be added to it is the end of the FIS section. Once that is done, I will need to go back and include the FIS into the RQ aswell as the literature review section as these were written before the FIS was included into the project.

EDIT:

Fixed the problem of the lakes changing position aswell as the vegetation. As it turns out, one of the positional arrays was not large enough so for some reason the data was then moving into a different array altering the positions of the lakes

FiS update

2009-03-20T09:00:00.001-07:00

Managed to implement a Fuzzy Inference System within the application. However it still needs a proper defuzzification method applied to it. At present, it simply takes the output state with the highest DOM and uses it.

The FiS does not run constantly, it simply takes in a snapshot of the current system at the end of each "day" and then calculates the state of a specific vegetation piece. It was mentioned previously that the FiS will take in three seperate input states, however, for simplicity and untill I can implement the Combs Method effectively the FiS will only deal with two input states. These states are based on how much water is left within the system, and how much the piece of vegetation in question has been eaten. The output states of the FiS are as follows:

High yield - vegetation produces alot more resource than normal

Normal Yield - vegetation produces the standard amount

Low Yield - vegetation produces around 1/4 of the standard yield

DeadYield - the vegetation does not grow back as often

This is currently only applied to a single vegetation piece. Once the defizzufication method is applied fully, it will then be implemented on the majority of the vegetation

Progress meeting

2009-03-17T14:00:00.000-07:00

Had my second progress meeting where I explained why I have not achieved much the last week or so. However, now that the dare application and math test are out of the way, I am now able to focus more on the honours application.

Also had a meeting with Dr. King today. I have been looking into the Combs Method for the Fuzzy Inference System. The combs method cuts down the amount of rules required by a FIS to come to a result. While this result is not as accurate as the normal method, the CPU time saved is rather helpful. It saves resource use-age by reducing the amount of rules required from an exponential equation to a linear equation which would be very helpful as has been shown in the literature review section of the dissertation, ecosystems are increadibly complex and as such would require alot of rules.

The rest of tonight and tomorrow will have to be written off as I am attending the code works, jobs in digital fair which takes place in Newcastle tomorrow.

However, since I now have a normal fuzzy inference system running correctly (still minus the defuzzification part) I have decieded just to go ahead and implement a normal FIS into the application and then change it later when I manage to successfully implement the combs method

Week Update

2009-03-13T21:03:00.000-07:00

Not much progress has been made this week as alot of time has been spent on the dare application as the deadline is only a few days away now. Also on the horizon is the annual Game In Scotland event which is happening on Saturday, because of this alot of time has been spent (and will continue to be spent) on polishing up demos and the CV for the event.

I had another meeting with my technical supervisor, i discussed more of my ideas and thoughts about the FIS and explained that I have been working on the AI coursework so that I can then hopefully port it over to the demonstration application once it is ready. I have now almost completly finished the methodology section and I'm now just waiting on constructiong the FIS before writing about it in the Dissertation.

I have also contined to take some of the base results from the application which will be used later for the next section of the dissertation, the results section

Progress

2009-03-10T11:43:00.000-07:00

The math exam is over which gives me alot more time to focus on the project. The methodology section of the dissertation is coming along very well and is now almost finished. I hope to have more done on it for my meeting with my supervisor later this week.

Since I am planning on trying out a Fuzzy Inference System (FIS) within the application, I have decided to spend more time on my A.I. coursework for Dr. King as this also entails creating a FIS. I have been doing research on FIS's reading up on several academic and other papers which has helped boost my understanding of them. I have constructed the basic FIS class (minus a defuzzification method) and have been testing it out. While it seemed to work at first, it does not return sensible values for all of the inputs, therefore I will have to spend some more time trying to find out why.

Had my first progress meeting today. I will post up my progress report later on today

Update for this week

2009-03-07T15:50:00.000-08:00

Unfortunately not much progress has been made with the project as a whole this week. Maths revision has continued to take up the majority of my time. Some progress has bee made with the dissertation as I continue to work away at the methodology section. Some minor additions have been made to the application, such as printing out some of the ecosystem information onto the screen. Once the math exam is over and the dare application has been submitted i should hopefully be able to concentrate more on my project as a whole

News

2009-03-03T19:41:00.000-08:00

I have been continuing with my dissertation and have managed to make a start on the methodology section, writing up my implentation of the A-Life algorithms used within the application.

Work on the demonstration project itself has been rather slow to non existant due to other university and outside deadlines. This will most likly continue for the rest of the week therefore I do not expect much progress to be made on the application itself. There is a math class test which counts for 10% of the mathematics module on the 9th of this month, therefore alot of my time will be focused on revising for this. The deadline for the Dare to be Digital application is also looming closer which has resulted in longer dare related meetings.

I have however continued to think about how I will implement the fuzzy state machine into the demonstration application. I will also be able to continue the write up of the methodology section

Update

2009-02-27T18:00:00.000-08:00

Since I had finished the literature review section, I had pulled together all that I had done on the dissertation so far and loosely arranged it into how it will appear in the final document. I then emailed it to my technical supervisor so that he could take a read over it so that I could have some feedback on it. I was slightly worried about the size of my literature review as it is around 6500 words alone, when the introduction, RQ, and motivation sections were added in, it came out at around 8300.

The feedback I got from the meeting was actually rather good. As it turns out my supervisor had expected this the size of my dissertation to be rather large simply because I have alot to write about. The size is going to stay the same for the time being so that I can weigh it up against the rest of the dissertation (if it turns out it is huge compared to the rest of it, then it will be cut down).

As it turns out there were very few problems with what I had written so far, most of the things that were suggested to me was simply to reword a few senteces and then find the diagrams for the literature review section.

As for the practical side, I had a talk with my supervisor about the best way to implement the Fuzzy State Machine for the vegetation. As it stands, the FuSM can only accept one crisp input. I had been trying to use the rate at which the vegetation was increasing/decreasing as this input but with little success. We both agreed that it would probably be better if i could somehow base this input on several factors. In the end we decieded that three factors should influence the input to the FuSM: these would be the rate at which it is being eaten, the remaining herbivore population and the remaining water levels.

In order to base the input off three seperate values, a Fuzzy Inference System will be used. This would allow be to take into consideration the three input values and return a single crisp value which could then be used as input for the FuSM.

One other thing that did come out of this meeting was that allow the FuSM seems like a good idea, it may be overkill. By overkill I mean, it may be trying to be too realistic with out actually making much of a difference as it may turn out that its implemtation does not actually have a visible effect on the system. Therefore, it was decieded that it will only be applied to a handfull of vegetation as a test, if it goes well and does indeed make a difference, then it will be applied to all the vegetation.

progress

2009-02-25T12:00:00.000-08:00

I have managed to finish the literature review section now. It still needs to be read over as there are a few sections within it that I will need to revisit and reword. I also still have to scan in a few diagrams and tables to help illustrate some of the points that have been made within this section.

Not much progress has been made on the application, seem to have hit a bit of a motivational slump with it. Some minor tweaks have been made, some of the code has been clean up and commented. The next major task in the Honours project is to implement the fuzzy state machine for the vegetation. The Fuzzy State Machine had been created near the start of the term (as I had been working on one over the winter break) . However, a lot of though needs to go into how this will actually be implemented within the application as I do not believe it will be a simple task.

Practical work and Dissertation

2009-02-22T17:08:00.000-08:00

Work on my dissertation has continued. The Literature review section is coming along very well and should hopefully be finished soon. I have written down some thoughts on how to go about writing the Methodology section of the dissertation aswell.

The MADTFDA is almost fully in-place. Several of the functions can now influence the application and its inhabitants. As an example of this, the function that checks for low herbivore populations and high resource amounts is able to alter the herbivores perception range (among other things) to allow them to spot food more easily etc.

Dissertation and application

2009-02-18T15:57:00.000-08:00

I've been continuing to work on the first draft of my dissertation. I've managed to get a very large chunk of the Literature review out of the way and have finished a new introduction which is a combination of the proposal introducting, plus more up to date and more relevant information.

Hopefully I will have the first draft of the introduction and literature review finished by a week tomorrow (which will be the 26th Feb)

AS for the application, I now have acceptable boundaries within the MADTFDA. I am able to check if the data fed into the graphs is under specific thresholds (such as high population but low resources or vice versa) and also to get the threshold with the highest priority returned.

Next on the list is to actually make the manager start to alter variables to help restore the system. To do this, the variables with the largest impact will have to be found. Once this has been set up for the herbivore population, it can then be applied to the carnivores and after that the omnivores.

Further enhancements to the flocking algorithm and environment code will also have to be made, such as over grazing on areas of vegetation causing it to take longer to grow back

Practical Work and Dissertation

2009-02-16T16:46:00.000-08:00

Started writing up my dissertation. written about 1250 words of the literature review which just now covers background reading on A-Life, fuzzy logic and eco-systems. Made a start at the previous work part as well.

On the application side, getting close to finishing enough to have a very basic model up and running. The herbivores successfully flock around the environment, avoiding obstacles. WHen they are hungry, they move over to vegetation to eat. When the vegetation drops too low, the system manager starts to grow more. Need to add in water resources and allow the manager access to the herbivores need to breed, average life expectancy and hunger rate to help control the flow.

Practical work

2009-02-11T15:25:00.000-08:00

Been working on combining the basic flocking model with the MADTFDA and fusm. Found a few problems with the boid and flock class feeding wrong information into the MADTFDa classes, but I think I have fixed that problem now. Will continue to combine the techniques to create the first iteration of teh basic system

Practical Work

2009-02-03T07:15:00.000-08:00

Stopped working on my basic flocking.

Started coding the Multi-Axial Dynamic Threshold Fuzzy Decision Algorithm.

Once a basic one of these is up and running, I will need to plan out some graphs

FuSM

2009-01-25T09:08:00.000-08:00

A basic FuSM has now been created. The initial thoughts for the FuSM was that it would represent the overall state of the entire ecosystem, however that Idea had been scrapped as ecosystems are too complex to be represented in this manner. A new idea was to have the FuSM control the desires of the entities that would inhabit the system. This would then allow the entities or agents to switch between behaviours depending on their current state(s).

Another Idea is instead to have the FuSM control the resources within the system. This would allow for factors such as over grazing and soil errosion to have an effect on how much resource is within the system.

The FuSM at present takes in a single crisp input value which is used to trigger state changes.

EDIT:

The FuSM will now be used to control only the vegetation within the system. Instead of monitoring the vegetation as a whole, it will monitor individual "trees" or "plants" making all the vegetation within the system different. Some plants will produce more than others depending on their current state

Flocking

2009-01-24T12:28:00.000-08:00

Flocking

Flocking (sometimes known as swarming or Herding) is a technique created by Craig Reynolds in his 1987 paper for SIGGRAPH called “Flocks, Herds and Schools: A Distributed Behavioural Model”.

Five Steering Behaviours

Separation -> Steer to avoid crowding local flock mates.

Alignment -> Steer toward average heading of local flock mates.

Cohesion -> Steer to move toward average position of local flock mates.

Avoidance -> Steer to avoid running into local obstacles or enemies.

Survival->Steer to eat as needed, or to avoid being eaten if a predator is seen.

What’s interesting about these five simple behavioural rules is how life like the resulting behaviour of the boids can be.

Separation

Gives an agent the ability to try to maintain a certain separation distance from other agents in the immediate vicinity. This prevents crowding together while ensuring a “natural-looking” closeness that emulates groups in the real world.

Alignment

Provides an agent that has the ability to align itself with other agents in its immediate vicinity, (i.e. Head in the same direction and/or speed as other agents). As with separation, this accounts for alignment through each member of a flock looking at nearby flock mates and then adjusting its heading and speed to match the average of the flock.

Cohesion

Gives an agent the ability to “group” with nearby agents, emulating similar behaviour seen in nature.

Avoidance

Provides an agent with the ability to steer away from obstacles and avoid collisions. This behaviour is accomplished by giving each agent the ability to “look forward” some distance and determine whether a collision with something is likely and adjust to avoid.

Every boid is a bit different

To make each boid a bit different we would have to individualise all the boids with various parameters – range of sight, maximum speed of flight etc. We would have to allow a randomised component apon boid creation. A newly created boid would now have some “personality” making each one a little different from its fellows – some wont see well, others will see very well, some want to maintain more distance from their fellows than the norm. Some will be hungrier than the others.

Why Do This?

A couple of reasons for doing this. Both of which add to the life like behaviour of the creatures in our little world.

First, providing each boid with slightly different capabilities is simply more realistic than an endless army of clones.

Secondly, the differences will combine to provide some forms of novel emergent behaviour as out boids interact, again providing what in the end is a more realistic representation of a group of creatures moving “en masse”. The tug and pull of tow boids in the same flock, one of which wants to maintain a cohesion much tighter than it’s fellow, will make for some interesting group dynamics, as will a boid that can see an oncoming predator just a bit farther than any of his flock mates.

All of this adds overhead, but not much though.

Feeding the Flock

If follows that if were going to have classes of boids that feed on one another, we will need something to control that hunger. To represent this, each class of boids that have the ability to eat will have a hunger rating that decrements a little each update cycle. When it reaches zero, our boid will become hungry and will actively seek out prey to satisfy that hunger. Each time a boid eats, a random test will determine if it is still hungry by comparing its current hunger rating to its starting hunger rating. E.g. if a boid starts with 10 hunger points and eats 4 of those points away, theres a 40% chance it will be satisfied and stop eating.

No Memory

Note that the steering behaviours say nothing about state information or about a given agent maintaining knowledge of the flock, it’s environment, it’s heading etc. Flocking is therefore a stateless algorithm in that no information is maintained between updates, each boid re-evaluates it’s environment every update. This reduces memory requirements which might otherwise be needed for similar behaviour using other approaches/ techniques, but also allows the flock to react in real time to changing environmental conditions. The result of this is that the flocks exhibit elements of emergent behaviour. No individual boid knows about where it is going, the flock moves as a single mass, avoiding obstacles and enemies and keeps pace with each flock mate in a fluid, dynamic fashion.

How This is Useful for Computer Games

Flocking provides a powerful tool for unit motion and making more realistic environments that the player can explore. It has been used with great success in a variety of commercial titles e.g. Unreal(Epic) and HalfLife(Sierra) use flocking for many of their monsters. Enemy Nations (Windward Studios) used modified flocking to control unit formations and movement across 3D environments. Groups of animals can wander terrain in real time strategy games or RPG’s more realistically than simple scripting. Groups of archers or swordsmen can be made to realistically move across bridges or around boulders or other obstacles. Monsters in an FPS can wander the dungeon halls in a more believable fashion, avoiding players where possible but perhaps launching an attack when the flock grows large enough.

The possibilities are practically endless.

Constraints

Several constraints on the boids restrict how they move and react. Possibly the most influential is the boids perception range, which restricts how far a flock mate can “look” about its environment to detect other flock mates, potential obstacles ro enemies. The larger this range, the more organised and coherent the flocks and the better they are at avoiding enemies and obstacles. Making it smaller results in more erratic flocks, groups of boids splitting off more often when confronted by onstacles or enemies and so on.

Another constraint on how the agents can move is their velocity and max velocity change. In the real world, animals in flocks are restricted in their ability to keep up with their flock mates by how fast they can move, how fast they can turn and the like. We can simplify this problem by ignoring acceleration and focus entirely on velocity. Changes in velocity can be restricted to some proportion of the overall maximum velocity – this would prevent ridiculous bursts of speed when boids try to catch up with each other. This also provides a governing restraint on how quickly they can slow down or alter course to avoid an obstacle.

More Fuzzy Logic and FuSMs Notes

2009-01-23T05:16:00.000-08:00

Contrary to popular belief, FuSMs are not really fuzzy logic systems. Fuzzy logic is a process by which rules expressed in partial truths can be combined and inferred from to make actual decisions. It was created because many real-world problems couldn't always be expressed (with any degree of accuracy) as finite events, and real-world solutions couldn't always be expressed as finite actions. Fuzzy logic is merely an extension of regular logic that allows us to deal with these kinds of rule sets. The simplest form of actual fuzzy logic in games (which is very common), is straighforward if. . .else statements (or their equivalents, through a data table or some kind of combination matrix) that describes changes in behaviour. For example, the statement “if my health is low, and my enemy's health is high, I should run away” is a straightforward fuzzy rule. It compares wo perceptions (my health and my enemy's health) in a fuzzy manner (low versus high) and assigns it an action (run away). This statement has probably been written as an if statement for hundreds of games over the years. This represents the barest minimum of an actual fuzzy system. A real fuzzy logic system would comprise many general fuzzy guidelines for any given combination of my health, my enemy's health, and all the other variables of concern into matrices of rules that will give me a response action through algorithmic combination of my health, my enemy's health, and all the other variables of concern into matrices of rules that will give me a response action through algorithmic combination. This tens to be a powerful way of getting results from a fuzzy system, but suffers when there are many fuzzy variables (each of which may have numerous possible value states or ranges) by creating a quickly unmanageable necessary rule set size, a problem called combinatorial explosion. This can be worked around using a statistics technique called Comb's method, which can reduce the required rule set, but also reduces accuracy.

FuSMs are rapidly becoming common in game AI usage. The predictability of FSMs is becoming undesirable, and the overall content of many games is becoming rich enough to warrant the additional design and implementation complexity of FuSMs.

FuSM definitely require more forethought than their finite brothers do. The game problem must really be broken into the most independent elements that the problem allows. An FSM could be implemented within the confines of an FuSM system, by calculating the digital activation levels and designing the system so that there is no overlap in state execution. FuSMs are not suited to the general range of problems as FSMs are. FuSMs are a kind of FSM that simply allows for the activation of multiple states as the current state, as well as being able to have a level of activation of activation to the degree that the game situation merits each state.

In fact, many people will contend that FuSMs are not even really state machines at all (because the system isn't in a solitary state) but, rather, are more like fuzzy knowledge bases where multiple assertions can be partially true at the same time. But, by coding independent states to take advantage of these multiple assertions, we can use FuSMs to accomplish our AI goals that require this kind of mechanism.

From AI GAME ENGINE PROGRAMMING 1st ED

Some Notes on Weighted Sums

2009-01-22T12:26:00.000-08:00

Extending Simple Weighted-Sum Systems

Decision making is one of the key functions of every AI engine. There are many decision-making strategies available, but a straightforward and powerful one is the weighted sum system, in which you simply weight the available options and select the one with the highest score. This is a very flexible technique that can be applied to situations that can't be easily modelled with more traditional approaches.

It is easy to write a naïve implementation of a weighted-sum system using only a direct combination of factors. Such an approach, however, is not easily adaptable to a number of situations that appear frequently during typical game development. The result is that much time is spent tweaking and tuning weights, often by trial and error, until the observed behaviour resembles the expected one.

Much research has been devoted to decision-making in the field of artificial intelligence. Utility theory is a formalization of the intuitive process of choosing the most desirable alternative when making a decision. Utility is a number used to measure desirability for all the possible outcomes of the decision. The rational choice then is to select the option with the highest utility.

Finding a value for the utility of a decision is highly subjective: different people might assign different values to the same situation. However, calculating an exact utility value is not possible in the presence of uncertainty, which is the norm in nearly every game. If you cant predict exactly what the result of a decision is going to be, you wont be able to evaluate how much you will like it. The traditional approach in this situation is to estimate the utility according to the probability of each possible outcome. This value is called expected utility.

Each situation demands a specific algorithm to calculate the expected utility of a decision. Typically, for games we have to resort to heuristics. A general method is to observe the factors that might affect the outcome, try to predict their influence on the result (whether positive or negative), and combine them using a mathematical formula. For instance, chess programs sometimes assign a payoff value to each piece. Each piece is a factor that helps calculate a value for the state of the board. By summing these payoff values, utility scores can be computed for every board configuration.

Unlike chess, most games have several different factors. Moreover, not all factors have the same influence in the outcome: some factors are more important than others are. A simple formula for combining factors that works fairly well is the weighted sum. Factors are multiplied by weights that represent their relative importance and then added together to calculate the expected utility:

EU(A) = (SUMOF) WiFi(A)

In practice, the exact factors that affect a decision depend heavily on the specific problem domain. A factor can be anything that can be measured in the game and has some kind of influence on the result of a decision. It is the programmer's responsibility to ensure the combination of factors represents an accurate measure of the desirability of making that decision.

One of the best features of this technique is that it is very robust in the face of emergent situations. Because the factors that define the game world are considered when making decisions, the AI will be coherent and act appropriately in nearly any circumstance. Contrast this with a heavily scripted AI, which has to explicitly take into account every single possible situation. The result is either incorrect behaviour when faced with an unexpected situation, or long and complex scripts, which take a lot of time to write and debug.

TO be finished

Notes on the Combs Method

2009-01-22T07:55:00.000-08:00

The Combs Method.

The Combs method depends on a rather simple result stemming from classical logic. The rule

'a' AND 'b' ENTAILS c

can be re-written as

(a ENTAILS c) OR (b ENTAILS c)

where ENTAILS is a Boolean operator that has it's own truth table:

a	b	A ENTAILS b
TRUE	TRUE	TRUE
TRUE	FALSE	FALSE
FALSE	TRUE	TRUE
FALSE	FALSE	FALSE

The operator 'ENTAILS' can be expressed as “IF a THEN b”. A better explanation of this would be that if 'a' is true, then 'b' must also be true. If 'a' is false then it makes no difference if 'b' is true or false.

With this rule in mind, on first glance it would appear that the third rule from the table above is incorrect.

False ENTAILS true = true.

However, this rule is actually quite logical. To help clarify the logic behind this rule, consider the following example by (Millington, I. 2006).

IF I'm-in-the-bath THEN I'm-wet

so if were in the bath(which is not empty of water), then we will obviously be wet. However, the bath may not be the only reason for being wet: getting caught in heavy rain, being splashed by a hose and so on. Therefore the above rule can still be correct when I'm-wet is true and I'm-in-the-bath is false.

What the above equates to is that we can write:

IF a AND b THEN c

(IF a THEN c) or (IF b THEN c)

MAKE SURE I MENTION THAT THE CONCLUSIONS FROM RULES ARE OR_ED TOGETHER, this allows us to split this new method of formatting rules into two individual rules

IF a THEN c

IF b THEN c

For clarity, the above shall be referred to as the Combs format.

Larger rules can also be expressed in this formating:

IF a1 AND . . . AND a(n) THEN c

can be re-done as

IF a1 THEN c

IF a(n) THEN c

This has taken us from requiring rules in all the possible state combinations to a much simpler set of rules requiring only a single state in the IF and THEN clauses. This method removes the need for multiple combinations which in turn leaves us with the number of rules equalling the number of states. This cuts the growth of rules from exponential to linear. E.g. having 10 inputs each with 5 states would result in only 50 rules compared to the unmanageable 10million rules.

When using the Combs method, all the rules have to be built from scratch. It is not possible to change a general set of rules into Combs format as truth tables using Combs format rules cannot be created or represented. While their will be examples that can convert rather easily, these are nothing more than a convenient coincidence.

As an example of this, consider the following pair of rules:

IF corner-entry AND going-fast THEN brake

IF corner-exit AND going-fast THEN accelerate

These two rules would be broken down into the following four rules:

IF corner-entry THEN brake

IF going-fast THEN brake

IF corner-exit THEN accelerate

IF going-fast THEN accelerate

Decomposing the original two rules into Combs format results in an inconsistent rule set. Rule 2 and 4 from the decomposed set contradict each other, we cannot possibly accelerate and break at the same time. Therefore which rule do we follow? The answer to this question would depend on our location within the corner.

When limiting a fuzzy system to only using the Combs format, the systems overall sophistication will unavoidably restricted. However, the tractability of rule creation allows these rules to be altered more easily (Millington, I. 2006)

It is not practical to apply the Combs method to traditional logic, the result would be incredibly restrictive. But when used with FL, where multiple fuzzy states can be active at any one time, this means that the different states can interact with each other (meaning we can both accelerate and brake at the same time, but the overall change in speed would be determined by the DOM of each state). The Combs method produces rules that are still able to produce interaction effects between all the states, even although these interactions are not explicit within the rules.

FuSM - Practical Work

2009-01-21T04:47:00.000-08:00

Work started on building a Fuzzy Finite State Machine(FuSM) on Friday the 16th January. A very basic FuSM is now up and running although a lot of work will have to be done to it to make it suitable. However, as the project is most likely going to go through several iterations, a basic FuSM will suffice for now.

At the moment, the FuSM in place monitors the total resources (plant life and water) within the system. The program takes in an integer (which at the moment is generated by srand()) as input.

This input will later be set to the actual total amount of resources. The input is fuzzified and it's Degree of Membership(DOM) in the appropriate states is found. This degree is then de-fuzzified and at the moment, a simple text line is printed to the console, which will later be replaced by the appropriate action.

If the input falls into two states, the highest DOM is kept and the state that the DOM applies to is stored. When the action for this state is executed, it will do so in ratio to the DOM

Fuzzy Logic Notes

2009-01-18T14:16:00.000-08:00

Fuzzy logic is a superset of conventional (boolen) logic that has been extended to handle the concept of partial truth – truth values between “completely true” and “completely false”. It was introduced by Dr. Lotfi in the 1960's as a means to model the uncertainty of natural language.

Zadeh says that rather than regarding fuzzy theory as a single theory, we should regard the process of “fuzzification” as a methodology to generalize any specific theory from a crisp (discrete) to a continuous (fuzzy) form.

Fuzzy Subsets

Just as there is a strong relationship between Boolean logic and the concept of a fuzzy subset, there is a similar strong relationship between fuzzy logic and fuzzy subset theory.

In classical set theory, a subset U of a set S can be defined as a mapping from the elements of S to the elements of the set {0,1},

U : S → {0,1]

This mapping may be represented as a set of ordered pairs, with exactly one ordered pair present for each element of S. The first element of the ordered pair is an element of the set S, and the second element is an element of the set {0,1}. The value zero is used to represent non-membership, and the value one is used to represent membership. The truth or falsity of the statement

x is in U

is determined by finding the ordered pair whose first element is x. The statement is true if the second element of the ordered pair is 1, and the statement is false if it is 0.

Similarly, a fuzzy subset F of a set S can be defined as a set of ordered pairs, each with the first element from S, and the second element from the interval [0,1], with exactly one ordered pair present for each element of S. This defines a mapping between elements of the set S and values in the interval [0,1]. The value zero is used to represent complete non-membership, the value one is used to represent intermediate degrees of membership. The set S is referred to as the universe of discourse for the fuzzy subset F. Frequently, the mapping is described as a function, the membership function of F. The degree to which the statement

x is in F

is true is determined by finding the ordered pair whose first element is x. The degree of truth of the statement is the second element of the ordered pair.

In practice, the terms “membership function” and fuzzy subset get used interchangebly.

An Example:

Let's talk about people and “tallness”. In this case the set S (the universe of discourse) is the set of people. Let's define a fuzzy subset TALL, which will answer the question “to what degree is person x tall?” Zadeh describes tall as a linguistic variable, which represents our cognitive category of “tallness”. To each person in the universe of discourse, we have to assign a degree of membership in the fuzzy subset TALL. The easiest was to do this is with a membership function based on the persons height.

    tall(x) = { 0,                                 if height(x) <>            (height(x)-5ft.)/2ft.,       if 5 ft. <= height (x) <= 7 ft.,            1,                                    if height(x) > 7 ft. }

A graph of this looks like:  1.0 +                   +-------------------     |                  /     |                 / 0.5 +                /     |               /     |              / 0.0 +-------------+-----+-------------------                   |     |                  5.0   7.0                  height, ft. -> Given this definition, here are some example values:  Person    Height    degree of tallness -------------------------------------- Billy     3' 2"     0.00 [I think] Yoke      5' 5"     0.21 Drew      5' 9"     0.38 Erik      5' 10"    0.42 Mark      6' 1"     0.54 Kareem    7' 2"     1.00 [depends on who you ask]  Expressions like "A is X" can be interpreted as degrees of truth, e.g., "Drew is TALL" = 0.38.

http://www.cs.cmu.edu/Groups/AI/html/faqs/ai/fuzzy/part1/faq-doc-2.html

Humans have the incredible ability to communicate skills simply and accurately by using vague linguistic rules. For example, medium thickness, small amount, very close. Conventional logic is inadequate for processing such rules.

When considering linguistic terms such as “far” and “close” or “gently” and “firmly”, a human being is able to place vague boundaries on those terms and allow a value to be associated with a term to a matter of degree.

Fuzzy Logic, invented by a man named Lotfi Zadeh in the mid-sixties, enables a computer to reason about linguistic terms and rules in a way similar to humans. Concepts like “far” or “slightly” are not represented by discrete intervals, but by fuzzy sets, enabling values to be assigned to sets to a matter of a degree – a process called fuzzification. Using fuzzified values computers are able to interpret linguistic rules and produce an output that may remain fuzzy or – more commonly, especially in video games – can be defuzzified to provide a crisp value. This is known as fuzzy rule based inference, and is one of the most popular uses of fuzzy logic. [See picture, pg 417 – programming game ai by example]

crisp sets

Crisp sets have clearly defined boundaries: An object (sometimes called an element) either completely belongs to a set or it doesnt. This is fine for many problems since many objects can be precisely classified. The domain of all elements a set belongs to is called the universe of discource. [see picture – p417]

Using mathematical notation these sets can be written as:

Odd = {1,3,5,7,9,11,13,15}
Even = {2,4,6,8,10,12,14}

As is evident, the degree of membership of a number to a crisp set is either true or false, 1 or 0. The number 5 is 100 percent odd and 0 percent even. In classical set theory all the integers are black and white in this way – they are members of one set to a degree of 1 and to the other to a degree of 0. It's also worth highlighting that an element can be contained in more than one crisp set. For example, the integer 3 is a member of the set of odd numbers, the set of prime numbers, and the set of all numbers less than 5. But in all these sets its degree of membership is 1.

Set Operators

There are a number of operations that can be performed on sets. The most common are union, intersection and complement.

The union of two sets is the set that contains all the elements from both sets. The union operator is usually written using the symbol [insert symbol]. Given the two sets A = {1,2,3,4} and B={3,5,7}, the union of A and B can be written as:

A[SYMBOL]B = {1,2,3,4,5,6,7}

The union of 2 sets is equivalent to ORing the the sets together – a given element is in one OR the other.

The intersection of two sets, written using the symbol [SYMBOL], is the set containing all the elements present in both sets. Using the sets A and B from above, their intersection is written as:

A[SYMBOL]B = {3}

The intersection of two sets is equivalent to ANDing the sets together. Using our two sets above there is only one element that is in set A AND in set B, making the intersection of sets A and B {3}.

The complement of a set is the set containing all the elements in the universe of discourse not present in the set. In other words, it is the inverse of the set. Lets say the universe of discourse of A and B is A[SYMBOL]B as given in equation(above) then A's complement is B, and B's complement is A. The complement operator is usually written using the ' symbol, although some times it is denoted by a bar across the top of the sets name.

Fuzzy Sets

Crisp sets are useful but problematic in many situations. For instance, lets examine the universe of discourse of all IQ's, and lets define sets for Dumb, Average and Clever like so:

Dumb = {70 . . .89}

Average = {90 . . .109}

Clever = {110. . . 129}

A graphical way of showing these crisp sets is shown below. Note how the degree of membership of an element in any of the sets can be either 1 or 0.

More still to come

Harvard Refs

2008-12-01T07:52:00.000-08:00

I decided that since it's not going to be possible to write up notes on everything that I have read so far, I will just put up some of the sources that will go into my references and bibliography.

DeLoura, M. 2000. Game Programming Gems. US: Charles River Media

DeLoura, M. 2001. Game Programming Gems 2. US: Charles River Media

DeLoura, M. 2006. Game Programming Gems 6. US: Charles River Media

DeLoura, M. 2008. Game Programming Gems 7. US: Charles River Media

Rabin, S. 2002. AI Game Programming Wisdom. US: Charles River Media

Rabin, S. 2004. AI Game Programming Wisdom 2. US: Charles River Media

GameDev. [Online]. Available from: http://www.gamedev.net [Accessed October 2008]

Gamasutra. [Online]. Available from: http://www.gamasutra.com [Accessed October 2008]

Smed, J. And Hakonen, H. 2006. Algorithms and Networking for Computer Games. England: Wiley

Vaart, Elske. And Verbrugge, R. Agent-Based Models for Animal Cognition: A Proposal and Prototype. [Online] Available from: http://www.aamas-conference.org/Proceedings/aamas08/proceedings/pdf/paper/AAMAS08_0555.pdf [Accessed September 2008]

Tu, X. And Terzopoulos, D. Artificial Fishes: Physics, Locomotion, Perception, Behaviour. Department of Computer Science, University of Toronto. [Online] Available from: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.8083 [Accessed September 2008]

Goldenstein, S. , Large, E. And Metaxas, D. Dynamic Autonomous Agents: Game Applications. Center for Human Modelling and Simulation, Computer and Information Science Department, University of Pennsylvania. [Online] Available from: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.27.8837 [Accessed October 2008]

Go, J. , Vu, T. And Kuffner, J.J.K. Autonomous Behaviours for Interactive Vehicle Animations. School of Computer Science, Carnegie Mellon University. [Online] Available from: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.61.1577 [Accessed October 2008]

Reynolds, C,W,R. Steering Behaviours For Autonomous Characters. [Online] Available from: http://www.red.com/cwr/. [Accessed October 2008]

Reynolds, C,W,R. Interaction with Groups of Autonomous Characters. [Online] Available from http://www.red3d.com/cwr/papers/2000/pip.pdf. [Accessed September 2008]

Intrinsic Algorithm. 2008. [Online]. Available from: http://www.intrinsicalgorithm.com/. [Accessed November 2008]

A Primer on Artificial Intelligence Technologies. 2000. [Online] Available from: http://users.erols.com/jsaunders/papers/aitechniques.htm. [Accessed November 2008]

Amit’s A* Pages. 2008. [Online]. Available from: http://theory.stanford.edu/~amitp/GameProgramming/. [Accessed November 2008]

Game AI. 2007. [Online]. Available from: http://www.gameai.com/. [Accessed November 2008]

Generation5. 2004. [Online]. Available from: http://www.generation5.org/articles.asp?Action=List&Topic=Artificial+Life. [Accessed November 2008]

Bourge, D. and Seemann, G. 2004. AI for game developers. 1^st ed. USA: O’Reilly.

Fairclough, C et al. 2001. Research directions for AI in computer games. Department of Computer Science, Trinity College, University of Dublin. [online] Avaliable from: https://www.cs.tcd.ie/publications/tech-reports/reports.01/TCD-CS-2001-29.pdf [Accessed on September 2008]

Diller, D et al. Behaviour Modeling in Commercial Games. [Online] Available from:http://seriousgames.bbn.com/behaviorauthoring/BRIMS_Behavior_Authoring_in_Games_2004.pdf [Accessed on September 2008]

Anderson, F. 2003. Playing Smart – Artificial Intelligence in Computer Games. [Online] Available from: http://old.zfxcon.info/zfxCON03/Proceedings/zfxCON03_EAndersonText.pdf [Accessed on September 2008]

Laird, J.E.L. and Lent, M.V.L. Human-Level AI’s Killer Application Interactive Computer Games. [Online] Available from: http://www.aaai.org/ojs/index.php/aimagazine/article/viewFile/1558/1457

[Accessed on October 2008]

Brooks, R.A.B. Intelligence Without Representation. [Online] Available from http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.12.1680 [Accessed on October 2008]

Guy, W. 2008. AI and Artificial Life in Video Games. 1^st ed. USA: Charles River Media.

Mark, D. 2008. Multi-Axial Dynamic Threshold Fuzzy Decision Algorithm. In: Rabin, S. AI Game Programming Wisdom 4. pp.347- 358.

Buckland, M. 2005. Programming Game AI by Example. USA: Wordware Publishing Inc.

Theres alot more to come aswell!

Notes on an Eco-System

2008-11-25T05:28:00.000-08:00

These notes were taken from wikipedia and the bbc bitesize websites

An Eco-System is composed of living elements sharing the environment with non-living elements.

Small scale (micro) eco system eg a pond

Medium scale (messo) eco-system eg a forest

Large scale (biome) eco-system eg a tropical rainforest

Sunlight is the main source of energy – allows the plants to live which allows herbivores to live which allows carnivores to live (the food chain).

The term eco system was coined in 1930 by Roy Clapham, to denote the physical and biological components of an environment considered in relation to each other as a unit.

Biomes are defined based on factors such as plant structures (such as trees, shrubs, and grasses), leaf types (such as broadleaf and needleleaf), plant spacing (forest, woodland, savanna), and climate.

Influencing Factors:

Elevation
Humidity
Drainage
Salinity of water
characteristics of water bodies
Climate
Human influences such as grazing, hydric regimes,

Introducing new elements, biotic (living) or abiotic (non living) into an eco-system tend to have a disruptive effect. Sometimes this can lead to ecological collapse or "trophic cascading" and the death of many species belonging to the ecosystem in question.

Under this deterministic vision, the abstract notion of ecological health attempts to measure the robustness and recovery capacity for an ecosystem; i.e. how far the ecosystem is away from its steady state.

Often, however, ecosystems have the ability to rebound from a disruptive agent. The difference between collapse or a gentle rebound is determined by two factors -- the toxicity of the introduced element and the resiliency of the original ecosystem.

Ecosystems are primarily governed by stochastic (chance) events.

An ecosystem results from the sum of myriad individual responses of organisms to stimuli from non-living and living elements in the environment. As the number of species in an ecosystem is higher, the number of stimuli is also higher.

Mathematically it can be demonstrated that greater numbers of different interacting factors tend to dampen fluctuations in each of the individual factors. Given the great diversity among organisms on earth, most of the time, ecosystems only changed very gradually, as some species would disappear while others would move in. Locally, sub-populations continuously go extinct, to be replaced later through dispersal of other sub-populations.

Stochastists do recognize that certain intrinsic regulating mechanisms occur in nature. Feedback and response mechanisms at the species level regulate population levels, most notably through territorial behaviour. Andrewatha and Birch^[12]suggest that territorial behaviour tends to keep populations at levels where food supply is not a limiting factor. Hence, stochastists see territorial behaviour as a regulatory mechanism at the species level but not at the ecosystem level.

An ecosystem is an environment containing a community of interdependent plants and animals. Food chains link animals to the plants/animals they eat and the animals that eat them.

Ecosystems are made up of both non-living (abiotic) and living (biotic) factors.

Abiotic factors are the elements of an ecosystem that are non-living. Nevertheless, they still have an affect on the ecosystem. Water, temperature, relief (height above sea level), soil type, fire, and nutrients are all examples of abiotic factors.
Biotic factors are the living elements of an ecosystem, i.e. plants and animals. All biotic factors require energy to survive. These living organisms form a community within an ecosystem.

The community within an ecosystem is linked together by food chains. Biotic factors become linked in a food chain when they eat one another. The start or bottom of a food chain is made up of producers, such as plants and algae.

These producers are at the bottom as they do not eat other biotic factors for their energy. Instead of taking energy from food, producers get energy by converting it from carbon dioxide and water using sunlight (Photosynthesis).

Consumers eat other organisms to get their energy.

There are four types of consumer:

1. Herbivores are organisms that eat plant matter (producers) to gain energy.

2. Carnivores are organisms that eat meat to gain energy.

3. Omnivores are organisms that eat both plant (producer) and animal (consumer) matter to gain energy.

4. Decomposers are organisms that feed on the remains of dead plant and animal matter. They help to speed up the process of decay. They also assist in recycling nutrients back to producers in nutrient cycles.

In the same way as energy passes through the food system, so do toxins. A toxin is a poisonous substance. When it enters an organism it will be stored in the tissues of that organism.

· Producers absorb toxins and store them.

· The toxin will pass to an herbivore when it consumes the contaminated producer.

· The toxin will pass to a carnivore when it consumes the contaminated herbivore.

· The toxin will pass to a higher carnivore when it consumes the contaminated carnivore.

The more contaminated organisms a carnivore consumes, the more toxins it will amass. This process is called the bioaccumulation of toxins and can have undesirable affects on organisms near the top of a food chain.

Notes from the article "Beyond A: IDA and Fringe Search" by Robert Kirk DeLisle

2008-11-23T09:39:00.000-08:00

Beyond A*: IDA* and Fringe Search

“Graph search techniques are ubiquitous in game programming”. The genre of the game does not matter, the basis of a game is inevitably formed by methods of graph search. The most popular genre of the moment FPS are normally very dependant on pathfinding methods that allow the NPC’s to move about in the game universe to perform various actions. This is also used in 2d/2.5d games which involve crossing a terrain or navigating a maze.

Typical problems encountered within the pathfinding universe normally relate to trees. (The start of the tree is considered to be the root). The root is then expanded on producing a number of new nodes (child nodes). The normal process followed in 2d pathfinding is most apparent when each child node represents a movement direction. As the path to the goal is extended, each of the child node are further expanded.

When problems are formulated in this sense, a graph traversal problem with starting and goal states inside the graph, we open the door to a number of algorithms.

Of all the available pathfinding algorithms, A* has emerged the most popular within game AI.

A* started with the breadth first search. In this search, all child nodes from the root node are expanded and explored before then algorithm progresses to the next level in the tree. If the goal node is not on the current tree level, the next level is accessed and all the children are expanded and evaluated. “Open” and “Closed” lists were then added to this algorithm as a modification by Dijkstra. This modification provided two fundamental capabilities:

The cost of a path to the current node is kept by the current node. The “Open” list can then be sorted by this cost which allows for a “best first” search strategy. This comes in particularly handy when the cost between two nodes is not always the same i.e. traversing swampland compared to dry land. This allows the best path to be biased away from costly paths.
All of the explored and evaluated nodes are stored in a sort of catalogue which stops the algorithm re-expanding nodes which it has already dealt with. This drastically improved the Breadth First search but more improvements were made through the introduction heuristics which allowed the incorporation of an “Informed Search” strategy.

The cost of any individual node up to this stage is viewed as the cost from the target/goal node to the current node and is normally referred to as g(). We can significantly improve an uninformed search of this sort if we include an estimate of the remaining cost between the current node and the goal node. This is the heuristic calculation – h() – gives us another method to make a good estimate at the total cost of the path and again is very bias in directing the search toward the goal. To get the total overall cost from any individual node we use the calculation f() = g() + h(). H() should always be admissible or an underestimate of the cost to the goal from that node. If h() holds an over-estimated value, promising paths could be missed out from the search or just delayed, causing the calculation to become more expensive. A* and Dijkstra both follow the same general algorithm. However the associated cost now takes into consideration the estimated cost to the goal as well (the heuristic cost).

It isn’t really a surprise to see that the fundamental weakness of A* is in it’s management of the two lists of the explored and un explored nodes. The open list has to always remained sorted in order of cost, i.e. the top node has the lowest cost to the goal. A* can create quite a high cost in terms of efficiency on the CPU as it constantly has to poll the two lists to see if a node has been evaluated yet. Although there have been many optimizations made to A* to try and speed it up a bit it doesn’t really matter as if the search space is huge, the application can experience serious loss of performance and possibly even stop functioning as the overall costs of maintaining the two lists increases with the size of the search space. Finding a path in a complex 3D environment can easily hinder A* with situations that may not be produced from a simple 2D pathfind.

A good example of showing the complexities of demanding situations would be to look at a Rubik’s Cube. Finding the quickest solution to a Rubik’s cube using A* can easily cause it to exceed it’s available memory after just a couple of minutes. This is because, in a 3x3x3 cube for example, any individual node can have as many as 18 child nodes to search. It doesn’t really matter if we place restrictions on the movement manipulations of the cube (for example, not turning the same side twice) would only limit a node’s children to 13 or so. Therefore after 8 turns, over 1 billion possible combinations appear. Therefore it is wise to find other methods to find a solution in a more timely and efficient manner.

The Iterative Deepening A*(IDA*)

IDA* is an extension to A*. This algorithm has a problem in that it is possible to evaluate the same node several times. This is because it kills the two lists and does not use them. However this problem can be catered for by carefully structuring how the nodes and evaluated and expanded. i.e. specific orders and stopping of backtracking.

It can sometimes also be self accommodating as nodes that are expanded earlier have a lower value of g() compared to nodes expanded later on. It should also have the same value for h() no matter when it was evaluated. A maximum threshold for the cost is defined and if a node exceeds this value, it will not be explored. If however after expanding all nodes that fall under this value and the goal has not been reached, the threshold is increased. The search must be reinitiated for the original node since no history is kept without the lists. Each node must then be expanded that fall under the new threshold. This might seem counter productive, but it costs less to re-expand a node than to store all expanded nodes in the lists and keeping them maintained. “In addition, the frontier nodes, those at the edge of the search that were not explored before, will always be greater in number than the number of expanded nodes below the threshold.” Therefore the cost of re-evaluating a node is smaller compared to the cost of expanding the new frontier. The ultimate goal is for the lowest possible overhead in memory, CPU time and the time for the actual search itself.

The Fringe Search Algorithm

In-between the two algorithms mentioned above is the Fringe algorithm. Similar to IDA* it expands nodes under the guidance of a cost threshold. But in this case, the frontier nodes are not lost. They are instead kept in two new lists called now and later.

The current node atop the now list is investigated. If the f() value exceeds the threshold it is moved to the later list. If the f() is lower, the child nodes are expanded and the current node is discarded. The child nodes are then placed on top of the now list.

The nodes are expanded much like the depth-first fashion of IDA* but this algorithm keeps the lists in a semi sorted state. Again like IDA* if the goal isn’t found under the current threshold value, it is increased. The later list is then made to be the now list and the search continues using the new now list. There is no sorting cost associated with the maintenance of the two lists. The extra memory needed to do this is less than A* on it’s own uses as there is no need to store all the previously explored nodes. There is no speed loss either compared to the loss when IDA* has to repeat searches from iteration to iteration.

Conclusion

There is an abundance of available pathfinding algorithms today. The biggest consideration behind picking one of these algorithms are the memory constraints and the time constraints (normally one has to be sacrificed for the other). A* is the most popular choice because of the degree to which it can be specialised and optimised for each applications. IDA* and fringe are very useful modifications of the traditional A* set of algorithms and could prove to be better compared to the usual approaches to pathfinding.

Notes from the Artical -"Designing a Realistic and Unified Agent Sensing Model" by Steve Rabni and Michael Delp

2008-11-23T08:52:00.000-08:00

This entry focuses on developing a better Agent Sensing Model, more specifically, the agents vision.

Designing a Realistic and Unified Agent-Sensing Model - notes

With increased visual realism in modern day games, gamers expect to see game agents with the ability to sense the game world with greater fidelity and subtlety. Traditionally, this has been done in a very simplistic manner through a combination of view distance, view cones and line-of-sight testing. A similar approach is taken when applying agent hearing. A simple method of just testing against some pre-determined cut-off distance to check if a sound can be heard or not. Although these methods are simple and cheap ways to create agent sensing, they are rather transparent and can produce rather shallow game play. As an example, if the player is somewhere in front of the agent, the agent will perform a discrete distance check to see if the player can be seen. This creates a blind zone beyond the maximum distance the agent can see. Many players are now aware of this flaw and exploit it to their advantage by momentarily appearing within the agents sight range, then running away, effectively luring the agent away from it’s position.

This method is going to enhance this basic sense/perception model by applying a handful of clever additions that will make the agents perception model appear much more life-like and realistic.

Basic Vision Model

The core model used for agent vision model in many modern day games comprises of three main techniques and calculations. These techniques – which are usually calculated in this order due to efficiency – are as follows; view distance, view cones and line of sight.

{Insert Picture}

The view distance calculation is a rather simple distance check. It is more efficient to use the squared distance in the test rather than the actual distance to avoid performing a square root calculation. For example, if an agent is standing position (0,0,0) can see 50 meters away and the player is at (25, 30,0), we can take the dot product of the vector between the agent and player and compare this against the view distance squared. (The dot product of the vector between the two is 25^2 + 30^2 + 0^2 = 1525. 1525 compared to the squared view distance of 2500 means that player can be seen by the agent as 2500>1525). The distance can be squared as we are only after the relative distance.

After this, the view cone check can be done. To do this the dot product between the agents normalised forward vector and the normalised vector that goes from the agent to the player. If the result from this calculation is greater than 0 then the player is within a 180degree view cone from the agent, if the result is more than0.5, the player is within the agents 120 degree view cone (cos 60 = 0.5). If only the 180degree cone is needed, we can optimize this by not normalising the vectors (which potentially eliminates two square root calculations).

The line-of-sight test is usually the final check to perform, and is the most demanding of the three. A ray is fired from the agent to the player’s location. If the ray intersects an object before it reached the player, the agent cannot see the player. If bounding boxes are used for the geometry and other in game objects then this test can be optimised slightly.

It is these three core methods, outlined above, that lay the foundation for the agent’s vision model. These techniques will be expanded upon and improved to provide a better, more realistic model.

Augmenting the Vision Model Toolbox with Ellipses

The methods mentioned previously do not model realistic human or animal vision very well. View Cones in particular have several flaws.

Potentially the agent will not be able to see any other agents or entities that are right next to it.
The visual acuity is at it’s highest at the centre of the vision cone and degrades as the distance increases. Far vision is overestimated and the near vision is underestimated.
To avoid giving an agent a very good far vision, designers and developers tend to make the view distance unrealistically short.

One way that some developers have tried to get around this, is by using multiple vision cones in attempt to try and model something similar to human vision. The problem with this approach is that it can create large holes or blind spots in the agent’s vision.

{insert Picture}

On the left, the thin cone represents the centre of focus which reaches far into the distance. The wider cone gives a much broader view but has a short range. The circle around the agent detects any entities adjacent or behind the agent (this is used to mimic the fact that humans often have the ability to sense when someone is behind them). Note the blind spots produced at the intersection points of the two cones.

A simple way to solve this would be to represent the vision model using an ellipse. As can be seen by the picture, the ellipse offers up a solution with the “degradation of visual acuity with distance without leaving holes in the vision”. The ellipse is started behind the agent (again to model a humans ability to sense people behind them).

Ellipse Implementation

To be able to produce an accurate vision model using an ellipse, it is very important that we understand its components.

{insert picture}

Major axis length is 2a, minor axis length is 2b. F1 and F2 (focal points) are at +/- c from the ellipse centre and c^2 = a^2 – b^2.

Middle figure displays important fact about the ellipse. The distance from the 2 focal points to any point on the outside of the ellipse is 2a. To determine if something is within the ellipse, the focal point positions must be found.

For human vision, one end of the ellipse is placed at the agent’s eye and the view angle specified. A triangle is then formed from the view angle at the agent’s eye and the ends of the axis in the centre of the ellipse. Given that Theta is half the view angle and a is half view distance we find the equation of c given theta and a.

{insert equation}

To find out if an entity can been seen by the agent, we simply have to take the entities distance from each of the focal points, add them together and check that they are less than the maximum viewing distance of 2a. Therefore all that is needed is two distance checks for each entity in question per agent. Note that squared distances cant be used in the equation as we have to add them together. This works for 3d and 2d. If height becomes important in the game, we will use 3d.

Using this ellipse to model the vision is easy to calculate in not really much more expensive than the view cone method.

Notes from the Paper "Interaction With Groups Of Autonomous Characters" by Craig Reynolds

2008-11-19T09:43:00.000-08:00

For my project I am going to have to find the best method that will allow the construction of a large group of autonomous agents which will be able to respond to the users interaction while maintaining a decent frame rate. The agents will need some sort of mental model that will allow them to actively select which behavioural goal they should be after, and control the agents steering.

Intro

Our world is a very active and populated place. Therefore why aren’t games. Games in contrast are usually very static or desolated. (With the exception of a few). Normally only a few agents move autonomously and a few areas on the game environment move in predefined cycles. My project will have agents that will be able to react to and coordinated their movements in respect to not only each other, but to the environment and the player as well.

Three key concepts will be looked at.

Behavioural Models: The programs that serve as the brains of the character.
Spatial data structures: used to calculate locality queries to help with performance.
The techniques used to drive the movement from the behavioural models.

Related Work

Generally, most games employ some sort of autonomous characters. Any or all in game agents that are not directly influenced by the player must have some sort of autonomy associated to them. The historical trend has been for autonomous agents to just follow pre-built scripts and very little to no ability to react to a dynamic environment, going towards agents that have to level of reactive ability and then toward agents that have the ability to learn. Many games are now looking to be able to create autonomous characters that can react and respond to the user.

Behavioural Models

Autonomous agents rely and need some sort of behavioural model/ controlling program to drive them. In the game environment, objects can fall under several categories; static, player controlled, periodic/running a pre-defined animation or they can have a degree of autonomy. Autonomous agents are driven by a controlling program which makes use of a behavioural model. The agents behaviours and actions are mapped to the environment by the controlling program. The agent has two environments. The external environment – the game universe that it resides in – and the internal environment – it’s memory or other mental/ cognitive processes. The level of autonomy that an agent has can vary widely.

A very simple representation for the physical representation of the agent can be used. A simple point mass that has a velocity and a local frame of reference. The local system can be updated every frame, making sure the mass and velocity are always aligned correctly. A finite steering force could be applied to move the agent and the velocity can be capped to represent appropriate levels of friction or drag.

“The position, velocity, orientation and visual appearance of the character is driven by the behavioural model, primarily through control of the steering force”

An autonomous agent should have multiple yet distinct behavioural states. There should be an active control in each state and take appropriate actions based on it’s perception of it’s own local and immediate environment. However, this will be tempered by its currently active behavioural states. Eg, a jet low on fuel take different responses when patrolling than when in a dogfight. Changes in an agents states are triggered by internal and external environmental conditions. Eg spotting an enemy changes you from wander to engage.

Panic within startled agents could be made to be contagious, so a normally calm agent would run away if several of it’s neighbours begin to run off. The urge to go wander away could also be contagious, so each agent would be sensitive to the percentage and amount of other agents that have wandered off. When a panicked agent runs, it will run a small distance before returning to it’s original spot (unless it’s being chased). An annoyance value could be present for each time an agent gets the panicked, the higher the value, the further the agent runs. It would then decay when it is calm.

Reacting to the User

The autonomous agents should be able to react to the user in two different ways – discrete and continuous. The agents may want to keep their distance from the player, simply moving out the way when the player is far away and slowly moving toward the agent, compared to the player being close and moving fast, then the agent will run off.

Brief notes from the paper "Intelligence Without Representation" by Rodney Brooks

2008-11-19T09:42:00.000-08:00

Intelligence Without Representation

The starting goal of AI was to enable a machine so that it could replicate human level intelligence.

Once people started to realise the magnitude and difficulty of this task, hopes started to diminish. Over the following 2 and a half decades there was very little progress made in producing isolated aspects of intelligence.

Requirements for “creatures” or agents.

The agent must be able to cope and respond in a timely fashion in a dynamic environment.
Any changes in the properties of the game world that the agent inhabits should not lead to the collapse of the agents behaviours, the Agent should be able to slowly change it’s behaviour to match the environment.
The agent should be able to maintain multiple goals and be able to switch between these goals depending on it’s current circumstances.
The agent must have a purpose in the world.a

Notes from the paper "Behavioural Modeling in Commercial Games" by David E. Diller et al

2008-11-18T13:23:00.000-08:00

Introduction

The computer games indusrty is now more and more concerened with developing sophisticated in-game characters.

Computer games developers aren’t the only people looking to create immersive simulated worlds, training application developers (such as the military) also have a great interest in this area.

Developers are wanting very realistic and robust behaviours that they can apply to their game agents. “As advanced high resolution graphics become commonplace, game developers are increasingly relying on “game AI” (i.e., behaviours of synthetic entities) to distinguish their game from competitors”.

The developers are very interested in creating entities that are more adaptive to new and unusual situations, not as predictable and therefore harder to play against.

Game developers are mostly interested in the “illusion of intelligence” and not actually making truly intelligent agents. i.e. the behaviours only have to appear to make their agent intelligent. Paul Tozour, AI programmer for Deus Ex 2 says regarding games:

“The whole point is to entertain the audience, so no matter what you do, you need to make sure the AI makes the game more fun. If a game’s AI doesn’t make the game a better experience, any notions of “intelligence” are irrelevant.”

Behaviour Generation – Components of behaviour in games

Although the game universe that the agents operate in is obviously much simpler than real life, the agents have to be able to successfully display capabilities such as: sensing immediate surrounds (or the entire universe), reasoning with spatial layouts, planning then executing appropriate actions as well as being able to communicate with other in-game agents or players. To do all this the agents will need to be able to perform a very wide ranging set of functions.

Sensation and Perception

Sensory mechanisms that give game agents “sight” and/or “hearing” can range from simple to extremely complex. There is a huge difference when we compare the game universe that the player sees to that of the game agents. The game agents world is rather impoverished. The universe is normally stripped down and abstracted so navigation purposes. Collisions are detected by radiating some sort of check out from the agents current position. The sensory mechanisms normally only take into consideration objects that can actually affect the agent.

In the game Halo, an NPC’s ability to see the player is constrained. The NPC can only see the player if, the player can see the NPC. The reason for this was that the players often felt cheated if they were killed by enemies that they can’t see.

Decision Making

The most common representations for modelling decision making in game agents is through the use of FSM’s. The behaviours that agents have are modelled as a set of states that are finite. The transitions between each state are directed by a graph. The character can only be in a single state at a time. The transitions are driven by actions that happen in the game. FSM’s are cheap to utilise, simple to use and easy to understand. There are several extensions available to improve simple FSM’s, these are; FuFSM’s, Hierarchical FSMs and Probabilistic FSMs.

Smart terrains/ environments are also seeing a good deal of use in games. The objects within the smart terrain contain all the information needed for an agent to decide what to do with the object.

Several games have recently developed goal directed reasoning techniques for character behaviour. The characters using this technique have a set of goals given to them, and they must choose themselves which goal to go after. (how they do it in this case is usually hard coded into the game).

Smart Environments/Terrains

Models for agent behaviour are usually constructed from the point of view of the agent living in an environment with inactive objects. Some games do this the other way around and have very simple agents living in a complex world with smart environments to produce interesting behaviours.

An agents current primary goal is visible to the player. The player can then use this information to predict what the agent is likely to do next.

Conclusions

Games companies are increasing developing and making use of intelligent, virtual agents to help distinguish their game from the rest. Therefore we are going to continue to see vast improvements in game AI. There is already a movement away from the traditional simple FSM and scripting techniques to the more interesting and robust techniques that employ less predictable behaviour.

Notes from the Paper -"Playing Smart - Artificial Intelligence in Computer Games" by Eike F Anderson

2008-11-18T12:36:00.000-08:00

Almost all modern computer games utilize realistic, high quality 3D animated graphics and 3D sound effects. These two aspects work very well to give the illusion of realism. However, this impression of reality can be smashed if the behaviour of the Non Player Characters (NPCs) is not natural or just doesn’t “feel right”.

The AI in most computer games isn’t really the same as academic AI. It’s more of a mix of techniques that are related to A.I. and are mainly concerned with giving a believable appearance of intelligence. AI doesn’t have to be incredibly complex as very little is required to fool the human brain, a complex A.I would actually be hidden and therefore hard for the player to spot. “The concept of “less is more” can therefore be applied to AI in computer games.” The biggest requirement for creating a captivating illusion of intelligence in games would be managing and controlling perception, I.e. organising and evaluating data from an agents environment which would mostly be sensory data but would also include the communication between multiple agents within a game world.

“The decision cycle of those NPCs constantly executes

three steps [van Lent et al 1999]:

1. perceive (accept information about the environment – sensor information)

2. think (evaluate perceived information & plan according actions)

3. act (execute the planned actions)”

At first glimpse this appears to be a very simple approach which may be inappropriate for creating captivating and entertaining game play. However, most computer games do not really need NPCs that are extremely capable, possibly even more so than the player themselves, as games are meant to be fun to play. If the game is too challenging, causing the player to constantly loose, it will loose it’s attraction and will therefore not be played.

AI was used in early games to produce believable adversaries to challenge the player. Depending on the genre of the game, RPG, arcade, RTS, different techniques and methods were used to create the A.I system, but the end result was always the same – create a believably life like adversary to give the player a challenging but fun and rewarding game play experience.

As games expanded and grew with the constantly evolving computers that ran them, incidentals, background agents, that did not contribute to the main story line started to make an appearance to help enrich the game universe. Game agents that could move about in the background, living out their ‘lives’.

High quality graphics no longer make a computer game stand out any longer. This has led to game developers increasing the complexity and believability of agents within the game universe. To make an agent seem life-like and intelligent, it needs to exhibit natural looking behaviour.

Since game agents have to work in real time, developers have to exclude many AI techniques so illusion is not spoilt by agents reacting slowly. One of the main issues affecting the real time requirements of AI is the fact that the AI has to be processed along with the games graphics, physics, sound, input, networking etc etc. Generally game AI was not viewed as hugely important and did not receive much attention, therefore not much processor times was reserved for it. With the advent of graphics accelerators in the mid 90’s, AI started to receive more attention as greater amounts of graphics processing was being moved onto dedicated graphics hardware.

The game agents in most modern computer games face the problems of

1. Path finding or path planning

2. Decision making

3. Steering or motion control

It is a combination of relatively simple methods applied to these problems that create the illusion of artificial intelligence in computer games.

Both games and the AI techniques used in games have come a long way over the past two and a half decades. Usually the most favourable choices for AI techniques are the older, more established ones. These techniques have actually varied very little over time.

“However over the past decade more and more novel ideas and methods for games AI have filtered into the game development process [Sweetser 2003] “

agents – Intelligent agents are NPCs that have the ability to make decisions and are made up from a combination of AI techniques.

Proposal Presentation Speach

2008-11-17T06:57:00.000-08:00

Intro

Hi, my name is David Higgins and I’m going to be investigating if it is possible for a combination of A.I. and A-Life techniques to not only be used to create an enduring eco-system, but also to calculate the boundaries that allow this system to remain in a state of equilibrium.

Issues

In a game situation, we could want an eco-system that we know is stable. On the other hand, we may want a system that, for whatever game related reason, is not stable.

I’m going to apply selected techniques to see if a believable Eco-system, populated by animals, can be created and then find out what the limits are that will keep the system in stability, otherwise it will die.

To give a Basic Example: Keeping it simple, we could say that if you have between ‘X’ and ‘Y’ amounts of ‘Variable’ it will die out in a week. Therefore if that’s what the game requires, we can just put these numbers in.

The techniques used are going to have to be able to allow the game agents to successfully navigate through the environment and fulfil their needs. Therefore I will need to find out if the techniques of: Fuzzy State Machines, Flocking, Path Finding and Chasing and Evading can create a realistic eco-system, and what the most effective way to apply the techniques would be.

Boundaries for the system will also have to be found, and these could range from something simple, such as the amount of available food, to the more complex, such as how far the agents can see, how strong they are etc.

Since there will be a great deal of variables in the system, some of these variables having a bigger impact than others, I’m going to see if the boundaries can be applied to a “God” AI that will be able to alter a select few of these variables so as to help keep the system in check (if that’s what the game requires).

Why it’s Important

As advanced high resolution graphics become common place, game developers are increasingly relying on gameAI to distinguish their game from the rest. With advances in processing power and dedicated hardware, there are more resources available that can be used for AI.

The illusion of realism that game developers work so hard to create can be easily smashed by poor or rigid A.I.

If, for example, the player, in an RPG game, can somehow introduce a disease that would ravage the environment, we could just tell the developers the limits to allow the system to die out over a period of time, making it much more realistic.

How to solve

To answer the research question, an extensive literature review (which currently on-going) into AI and A-Life will be needed. Since there are a lot of elements involved in a real life eco-system, a brief investigation into this will also be done so that all the elements of a real life system can be stripped down to only the most important one’s that will allow the construction a basic virtual eco-system.

The system would start off small and its boundaries found. More and more elements would then be added to the system and slowly but surely building it up producing larger and larger systems.

Why it’s Interesting

Most games don’t employ a truly persistent environment, that is, that the changes and influences made by the player are only temporary. The approach would allow me to create both a truly persistent or non persistent environment.

This approach could also allow the application to be used as a package, this package could then be built into a game as an eco-system.

Significance

The significance of answering the RQ would be that it would show that it is possible to greatly enhance the impressiveness of a game by creating a believable, life-like eco-system that you have great control over.

WorkSheet 4

2008-11-17T06:40:00.000-08:00

The final worksheet.

No comments on this sheet, it was sent off for comments but was never returned.

Introduction

What is the topic and aim of the project?

This project will investigate Artificial Intelligence (A.I) with several aspects of Artificial Life (A-Life) and thetechniques that can be combined to create an effective life-like A.I. system.

Issues

What issues do you want to address.

Several issues will have to be addressed to be able to effectively fulfill the project aim and answer the research question.

Due to time constraints, it was decided to create an eco-system populated by animals. Animals were chosen over humans as it would be much easier to model their basic instincts and behaviours.

The techniques utilised will need to allow the agents to successfully navigate through the game universe in order to fulfill their needs such as feeding; drinking; hunting and evading; exploring; mating etc.

The A.I. technique will need to be able to represent the agents’ basic cogitative abilities and therefore must be able to determine the most appropriate course of action given an agent’s current situation, eg an agent needs to feed, therefore it should hunt down / locate a food source instead of "socialising and exploring" with with other agent’s of the same species.

These methods mentioned above need to be combined as efficiently and effectively as possible to see if the self-sustaining aspect of the eco-system can “emerge”.

If the system can become self-sustaining, boundaries that allow the system to stay in equilibrium will then have to be found and applied to the game universe.

These boundaries could then be applied to a "God" A.I. This A.I. technique would have knowledge of the entire universe and would be able to monitor the state of the eco-system. This would then allow any user or developer to receive an advance warning if the system starts to fall, or has fallen, out of balance. If desired, this “God” A.I would be able to adjust the balance of the eco-system to help maintain equilibrium. This would be done indirectly so that it would not appear to be cheating by spawning agents out of nowhere. Instead, it would be able to adjust a few specific variables that have the greatest effect on the game universe, such as the rate that vegetation grows at, how often agents need to feed or how often they breed. This would allow the user to experiment and “play” within these boundaries so as to not destroy the balance.

Research Question

What is your current research question?

Addressing the Question

How do you envisage yourself carrying out the project – a short exposition of the project.

To be able to address the question effectively, a great amount of research will have to be conducted into the many existing A.I. and A-Life techniques that would be capable of accurately mimicking animal behaviour and managing an eco-system. This research has already begun and as such, the following techniques have been selected on the basis of best relevance to the question stated above: Fuzzy Logic; Flocking; Path Finding; Chasing and Evading; Potential Function Based Movement. An in- depth and extensive literature review of each of these techniques will now have to be conducted to find the most suitable. This review will consist of looking at the general theory behind each of the techniques, the pros and cons in relation to the research question and the specific ways that they can be, and have been, applied to game situations.

After the literature review has been concluded, the most relevant way to advance the investigation into the techniques listed above would be the creation of an application demonstrating the selected techniques in action. Since the application is going to model animal behaviour, it was decided that the most appropriate simulation to create would be that of a constant eco-system. This constant eco-system should be able to function and remain in a state of balance with or without user interaction. The agents within the eco-system will be almost fully autonomous and will go about their ‘daily lives’ just like real life animals. It is essential that the eco-system be able to reach a state of equilibrium so that:

Firstly, it can be observed if the selected techniques can perform such a task.
Secondly, so that the boundaries can be established that will allow the eco-system to remain in this state of harmony. ( Since there will be a great number of variables being used in each of the techniques, the variables that will have the strongest effect on the overall outcome of each technique will be identified and these will be altered to establish boundaries.)
And finally, if the selected techniques are capable of keeping the eco-system within a state of equilibrium after some form of ‘natural’ disaster and / or user interaction has upset this balance.

To be able to create this demonstration program, an appropriate engine must be sought out and reviewed.

The game universe that the eco-system will be demonstrated in will be made up of a terrain with randomly located lakes positioned throughout it. Around and nearby to these lakes will be vegetation. This vegetation will be used to give the herbivores a source of food, and a hunting ground for the carnivores to prowl when hungry.

Methods must then be chosen to be able to employ the selected techniques. The best way to select the methods would be through meticulous analysis of the literature review.

Progress

What have you managed to do so far and how has this influenced your vision?

General background research into A.I. has been conducted. This research is still continuing and there is still much more to be done. This general research has shown common problems encountered in the field of A.I. along with a few suggestions on how to get around them. Methods and techniques that previous commercial games have implemented along with the problems, successes and failures that these games have encountered have also been identified.

Research into low level A-life techniques such as Flocking, Chasing and Evading, Fuzzy Logic, Potential Functions and Path Finding has also begun. There are copious amounts of information available on each of these techniques, however, the part that is proving most difficult is finding information that is relative to this project. There are no freely available code examples to examine, therefore all these techniques are going to have to be coded from scratch.

WorkSheet 3

2008-11-17T06:28:00.000-08:00

This is my worksheet 3, comments are given in Itallics

Introduction and Motivation

This project will investigate the use of combined Artificial Intelligence (A.I.) and Artificial Life (A-Life) techniques to create a believable, immersive and self sustaining eco-system.

For the first time since 3D graphics were introduced into computer games, game developers are now able to utilise levels of processing power that were previously inaccessible. One of the biggest issues restricting the progress and development of computer game A.I. had always been the absence of CPU resources. In spite of the progress made in processing power and other available resources – in both PC and console platforms – over the last two decades, game A.I. has not developed to its full potential. “99 percent of commercial games on the market in 2008 use a combination of the basic AI techniques from games of the 1980’s” (Guy.W,2008)

A-Life is still undergoing a great deal of development and as such is considered a fairly young discipline. “The key selling point that A-Life has over strict AI is that the result is more than just a few AI routines put together”(Guy.W,2008). If that was all A-Life had to offer there would have been no reason to leave the A.I. domain.

The video games industry has grown so much that it now generates more revenue than the movie industry. Until recently the technology used in games was compelled by a yearning for real-time, photo-realistic graphics. To a large degree, graphics technology has now arrived at a stage such that “visually stunning games are the norm rather than the exception…” (Faircloud et all, 2001). This technology is capable of completely immersing and captivating the player within the game universe. However, poor A.I. can effortlessly destroy this illusion leaving the player unimpressed. Game developers are now looking for fresh technological innovations, away from exceptional graphics to drive game development and search for a new selling point. With the constant advancements made in graphics hardware, a greater amount of graphic processing can now be moved over on to this specialised hardware, releasing much needed CPU resources, A.I is coming to the fore of new development.

Game developers have now started to take advantage of the greater levels of processing power available and have created very advanced and complex A.I. systems for use in games while not sacrificing any graphical fidelity. Games such as “S.T.A.L.K.E.R: Shadows of Chernobyl” and “Fallout 3” make use of very advanced Non Player Controlled characters (NPCs) that behave much more realistically than the NPCs of any previous game. These games, along with several others, exhibit the levels of immersion and realism available through the creation and use of combined advanced A.I. techniques.

If i remember correctly the A-Life system in STALKER was intended to control all agents, animal and human NPCs. However they kept finding problems with the gameplay as it was very difficult to produce a state where one faction of PCs would not be able to overwhelm the other. I think that you are underestimating the complexity of creating a system which is stable left alone, let alone one which can move toward stability following disaters and player intervention.

Research Question

Addressing the Question

To be able to address the question effectively, a large amount of research will have to be conducted into the many existing A.I. and A-Life techniques that would be capable of accurately mimicking animal behaviour and managing an eco-system. This research has already begun and as such, the following techniques have been selected on the basis of best relevance to the question stated above: Fuzzy Logic; Flocking; Path Finding; Chasing and Evading; Swarming and Potential Function Based Movement. An in depth and extensive literature review of each of these techniques will now have to be conducted to find the most suitable. This review will consist of a look at the general theory behind each of the techniques, the pros and cons in relation to the research question and the specific ways that they can be, and have been, applied to game situations.

After the literature review has been concluded, the most relevant way to advance the investigation into the techniques listed above would be the creation of an application demonstrating the selected techniques in action. Since the application is going to model animal behaviour, it was decided that the most appropriate simulation to create would be a constant eco-system. This constant eco-system should be able to function and remain in a state of balance with or without user interaction. The agents within the eco-system will be almost fully autonomous and will go about their ‘daily lives’ just like real life animals. It is essential that the eco-system be able to reach a state of equilibrium so that:

Firstly, it can be observed if the selected techniques can perform such a task.
Secondly, so that the boundaries can be established that allow the eco-system to remain in this state of harmony. ( Since there will be a huge amount of variables being used in each of the techniques, the variables that will have the strongest effect on the overall outcome of each technique will be homed in on and these will be altered to establish boundaries.)
And finally, if the selected techniques are capable of keeping the eco-system within a state of equilibrium after some form of ‘natural’ disaster and/or user interaction upsets this balance.

To be able to create this demonstration program, an appropriate engine must be sought out and reviewed. Methods must then be chosen to be able to employ the selected techniques. The best way to select the methods would be through meticulous analysis of the literature review.

Is the eco-system being activly managed or is it simply that you have arranged the initial conditions such that the simulation will be stable?

What kind of scale is your eco system going to be on (number and density of agents) and what kind of complexity (how many different species of agent) and over what timescale should it remain stable?

I’m not sure if you really need to be tweaking that many variables to achieve ecosystem stability. I would think that if there will be as many herbivores as the ecosystem can support with as many carnivores that can be supported as can be had from the growth and wastage of your herbivore population. There will be some equilibrium reached after the simulation has run for long enough. It’s just a matter of whether it’s a very interesting equilibrium or one with very few animals alive.

I take it the goal is for the ecosystem’s population distribution among species to reach a new stable state as opposed to a minor imbalance from natural event/player actions leading to a massive change? What if the player decided to eradicate a certain species of agents, would additional populations be brought in from outside the ecosystem or would the species be allowed to become extinct? It might be difficult to create a self-sustaining eco-system that can withstand a destructive player without resorting to cheating methods like spawning additional animals from nowhere.

You don’t necessarily need to create a 3d visualisation of the ecosystem. It might be better for you to save your efforts in this area and produce only a simple 2d visualisation which would be more than sufficient to allow one to see how the animals were interacting by seeing their distribution and perhaps be able to hover over a animal icon and get a status for that animal?

Have you considered implementing this as a mod for an existing game? You could make use of that game’s existing low-level AI behaviours like pathfinding which would allow you to focus on the high-level ecosystem modelling stuff.

Resource Requirements

The resource requirements for the project will be kept relatively simple. Access to a windows based PC with a working copy of Visual Studio .NET 2005 installed. This computer will also need to have the selected 3D engine available and both OpenGL and DirectX installed to be able to create the application. These requirements are not out of the ordinary – with the exception of the 3D engine. However, a couple of engines are freely available to students, and are also installed on certain PC’s within the University therefore choice of engine will have to be based on this.

Overall David I think your proposal is an interesting proposition. I think you need to look more into how an ecosystem actually works in order to get a better understanding of the processes you are modelling and how these can be achieved with the mix of AI techniques you are proposing.I think the difficulty will be more in creating a stable ecosystem which is interesting, (can I request you model the platypus – I have often wondered as to the point of this creature in an ecosystem) stability should be reached just by supply and demand of food.

WorkSheet 2

2008-10-23T06:14:00.000-07:00

Honours Project Worksheet — #2

(Annotations in Courier with Italics)

You should have decided upon a broad topic for your honour’s project and identified some issues associated with the topic that you want to research.

1. Formulate a research question for your project. Details on the research question can be found in presentation 1 in the module folder.

“Is it possible for a combination of A.I. and A-Life techniques to not only be used to create an enduring eco-system, but also to calculate the boundaries that allow this system to remain stable and identify if the techniques can help the system to recover from “natural” disaster and/or user interaction and thereafter return the system to a state of equilibrium.”

The topic sounds really cool but the question is a bit of a mouthful. Does the stuff about natural disaster and returning to a state of equilibrium need to be mentioned as they are already partially implied. The recovery could then be discussed further once the question has been stated.

2. When developing a research question you must produce a question that can be answered by performing literature research, practical experimentation and critical analysis. The question should also focus the activities of your project.

a) What is the focus of your project?

The focus of this project is to combine specific A.I. and A-Life techniques to allow the creation of a self-maintaining 3D eco-system. The boundaries that allow the system to remain persistent will be determined. The eco-system will then be subject to random “natural” disasters and/or user interaction. The main focus would therefore be to see if the techniques could be used to create the eco-system and if these techniques can recover from the disasters and restore the system back to a state of equilibrium.

What sort of eco-system will be created? Underwater? land? Ailen? That might be outside the scope of this worksheet, but I think it would definitely need a lot of consideration.

b) What information do you need to find out about?

There are numerous differing A.I. and A-Life techniques existing that could be used in this project. These techniques would have to be studied to find those that are most relevant and appropriate and that would best suit the task.

The framework that the project will use will be researched, i.e. will it be built from scratch using OpenGL or DirectX? Or would it be easier to use a pre-existing 3D-engine.

Although largely depending on how you want to approach the graphical side of things, I would recommend a pre-built engine (ogre?). Animation, lighting, model loading atc are usually already implemented leaving you to focus more on the topic at hand. What sort of visual assets would you be using.

c) What Experimental work do you need to perform?

The experimental work will take place once the most appropriate techniques have been selected. Small demo applications showcasing each individual technique may have to be constructed to get a better understanding of the implementation issues surrounding the technique before the final application that combines them all is constructed.

Might be a good idea to look into already existing eco-system simulations outside of the games world.

3. How will the information that you obtain in 2 allow you to answer the research question?

The research mentioned above will provide better knowledge of the selected techniques and allow a better judgment to be made of whether or not it will be possible for the selected techniques to perform the task. It should also supply the knowledge to construct a working three dimensional model which can show case if the techniques can firstly create a stable eco-system, secondly, determine the boundary conditions and finally, allow the system to endure disasters and/or user interaction.

Worksheet 1

2008-10-23T06:07:00.000-07:00

Comments are in Italics.

1. State the topic of interest that you may wish to take forward into a project

The topic of interest is the use of combined Artificial life (A-Life) and Artificial intelligence (A.I.) techniques to create a self sustaining, believable eco-system within a game environment.

Very good, you seem to have a clear idea of what you want to achieve from this project.

2. Indicate the issues surrounding this topic that you may wish to investigate.

The issues would be if the eco-system was to be populated by different groups of autonomous agents, how would these agents know and be able to behave and respond in an appropriate manner as to create the most believable and immersive application possible.

The agents would not only have to be able to respond to other agents and objects within the eco-system, but also able to respond to user interaction – the user would be able to alter aspects such as the amount of food and water available, and also be able to select and kill agents at will. The user would be able to observe the effects of their actions and see how the eco-system would respond to the changes that they have made.

A.I and A-Life techniques would have to be investigated in order to offer the best solution to the issues mentioned above.

3. Outline your initial ideas about how you would carry out the practical aspects of the project. i.e. what do you envisage yourself actually doing for the project.

Finding and creating a list of both A.I. and A-Life techniques that would be the most useful and appropriate for the project. Research into each of these techniques would then be conducted in an attempt to find not only the most appropriate techniques, but also the techniques that would be possible within the given time limit.

For the practical side of the project, I would create either a 2D or 3D (ideally 3D for a more immersive experience) environment. The agents would then be placed within the world and free to roam around. Water supplies and foliage would be randomly located throughout the environment. The herbivores would track down the foliage to feed from and the carnivores would hunt down the herbivores for food. In order to make the eco-system self-sustainable, both groups would have the ability to reproduce.

The demo seems to be pretty impressive, if completed will show the techniques that you have learnt at work. Also look good for the show case at the end of the year.

Some Notes

2008-10-15T12:00:00.000-07:00

Defining Artificial Life (A-Life)

Strong A-Life -> Truly alive, synthesized life.

Weak A-life -> Not truly alive, but modelling lifelike behaviour.

Genetic algorithms and genetic programming. These are similar and related yet subtly different approaches to breeding solutions and behavioural models.

Genetic algorithms (GA) – Take a best fit solution to a specific problem.

Genetic programming (GP) – modifies the solution to fit the problem by changing the actual algorithm.

Both use algorithms borrowed from our observation of life – mutation, inheritance, and genetic crossover – combined with some selection criteria. These selection criteria may differ accordingly to what the designer is trying to achieve, but they are commonly linked to the success of GA/GP implementation with respect to a given problem domain.

In our case, the algorithms are derived form classic AI building blocks and A-life theory to create more natural in-game behaviour models.

Calculated A-Life and Synthesized A-Life

Take for an example, a tile in sim city, which is designated as residential. If the population is already housed, then the square will remain empty until a calculation indicates there are more bodies than houses – at which point the square will be built apon. This is calculated A-life. The synthesized A-life might allow a passing sim to see a virtual for sale sign, which beginning a series of decisions that lead it to build on that square or not. Another visiting sim might see the 1^st sims house for sale, note that there are good jobs in the area, a nice shopping mall, and decide to buy it. The result is the same. On the one hand we have dictated the outcome and on the other hand we have allowed it to take place.

I would be looking to make use of both Calculated and Synthesized A-life in my project.

If the player chooses to influence the game somehow, we allow it to react to that interaction from the ground up, whatever the consequences.

CGT Honors Project Blog

Finished

Honours Project

progress

progess

testing

Progress

Testing

Update

Progress

Progress Update

more updates

FiS update

Progress meeting

Week Update

Progress

Update for this week

News

Update

progress

Practical work and Dissertation

Dissertation and application

Practical Work and Dissertation

Practical work

Practical Work

FuSM

Flocking

More Fuzzy Logic and FuSMs Notes

Some Notes on Weighted Sums

Notes on the Combs Method

FuSM - Practical Work

Fuzzy Logic Notes

Harvard Refs

Notes on an Eco-System

Notes from the article "Beyond A*: IDA* and Fringe Search" by Robert Kirk DeLisle

Notes from the Artical -"Designing a Realistic and Unified Agent Sensing Model" by Steve Rabni and Michael Delp

Notes from the Paper "Interaction With Groups Of Autonomous Characters" by Craig Reynolds

Brief notes from the paper "Intelligence Without Representation" by Rodney Brooks

Notes from the paper "Behavioural Modeling in Commercial Games" by David E. Diller et al

Notes from the Paper -"Playing Smart - Artificial Intelligence in Computer Games" by Eike F Anderson

Proposal Presentation Speach

WorkSheet 4

WorkSheet 3

WorkSheet 2

Worksheet 1

Some Notes

Notes from the article "Beyond A: IDA and Fringe Search" by Robert Kirk DeLisle