First Prototype

Currently working on getting the first prototype of this project implemented. The first prototype will consist of a small neural network which will modify the weights of the edges on a graph. I will also implement a graph search algorithm such as the A* algorithm for finding optimal routes.

The first prototype will not interface with the quake game engine. It will be a stand alone component. I have chosen to implement it this way to make testing of the neural network and probability graph easier.

Interim report

Nearly finished my interim report. Currently rewriting the introduction, inserting citations and references and writing the future work section.

Interim report

Focusing mainly on writing my interim report and finishing it up before the due date, at which point I can focus on finishing off assignments. The Background, Literature review along with formating is almost fully complete and I shall be focusing on the design and writing about the methodology I will use over the next week before finishing it up completely for submission.

Didn't have a meeting with my supervisor this week due to public sector strikes, which is fine because I've mainly been focusing on writing this report and other assignments only partially related to this project.

Recent activity.

Ioquake3 is set up with visual studio and is ready for development work. I haven't really done much in the last week beyond reading a bit about more about the C programming language from a book called "The C Programming Language" written by Dennis Ritchie himself. Other than that, I've written a bit more of the background chapter of my interim report.

All of the lecturers are on strike tomorrow (later on today strictly speaking), so that gives me two days off where I can focus more on getting more of my interim report done.

Machine Learning.

Definition - "Any change in a system that allows it to perform better the second time on repetition of the same task or on another task drawn from the same population. " - Machine Learning, Game Play, and Go by David Stoutamire.

Investigation of Planning, Multi-Agent Planning and Task Hierarchial Networks designs

Looking at the above and their application to this project.

http://en.wikipedia.org/wiki/Multi-agent_planning

http://en.wikipedia.org/wiki/Plan

http://en.wikipedia.org/wiki/Hierarchical_task_network

http://abotea.rsise.anu.edu.au/data/offline-htn-planning.pdf

http://www.cs.pitt.edu/~milos/courses/cs2740/HW-SOLS/hw-5-sol.pdf

The rough design of how the rocket jumping solution for routing to otherwise unreachable areas is as follows.

If the bot is given a goal to travel to a destination within its immediate vicinity, it will try and find a route to that destination through the clusters using the cluster portal. If a route can't be found and the destination is in range of a rocket jump, the bot will search for the solution in a graph of abilities and store then act out the optimal path that will achieve the goal.

Neural Networks and Genetic Algorithms

Some helpful white papers about Neural Networks and Genetic Algorithms for Quake III.

http://ticc.uvt.nl/~pspronck/pubs/ImprovingOpponentIntelligenceThroughMachineLearning.pdf

http://www.ieee-cig.org/cig-2009/Proceedings/proceedings/papers/cig2009_041e.pdf

Good starting points for learning about the above:

http://en.wikipedia.org/wiki/Genetic_algorithm

http://en.wikipedia.org/wiki/Evolutionary_algorithm

LCC, the Quake 3 arena compiler.

My understanding is that the quake client runs on a virtual machine and the source code needs it's own compiler.

The source code directory structure is as follows.

• Code: Contains all of the source code for the client, server and game.
• lcc: Contains the compiler for the code for compiling quake 3 for the virtual machine it runs on.
• q3asm: The assembler for the virtual machine.
• ui: This seems to be definition files for menus and user interface configuration files.

http://www.osix.net/modules/article/?id=490

More short term goals.

Look at which data should be store in the knowledge base for new cluster portals linking unconnected area clusters for routing.

Short term goals.

Short term goal right now is to get the visual studio solution for the Quake III arena set up to compile and debug.

Existing Quake AI

While playing Quake, I noticed a couple more flaws in the existing behavior of the bots.

• When ever the bots want to talk, they don't seem to take in to account the surrounding environment. For example, there have been numerous times when one of the bots stopped to chat in the middle of combat or when he was in the line of sight of another bot.
• The bots need to take upgrades and power ups as priority in their routing strategy while chasing another bot. As it is, when a bot is chasing a different bot, its routing strategy may bypass an upgrade that was essential to its survival. If there is an power up with in range of some dynamic threshold, the bot should use that as a node to traverse in its route.
• Bots seem to spawn instantly right after death provided that they're not chatting. This is not always the case in real life. A human player might take time to reflect upon his death in a game if he was killed in an impressive way, or if a player is frustrated then he might quit the game all together.
• The chat system is an obvious give away that avatars are controlled by machine.
  

Trajectory

Looking at formulas in physics to calculate trajectory of balistics.

Forumla: Angle to hit Co Ordinates (X,Y) where X = distance, and Y = Altitude.

A bot could use this formula to calculate the angle it would need to fire it's weapon at, in order to rocket jump to a reach a ledge or different area that is not connected with a path. When it finds a new path way using a rocket jump it could store the map Co Ordinates in a knowledgeable for future use.

I was also looking at maybe writing the bot in C++. I need to look at how exactly that would plug in to the existing game engine which is written in C. However, it may just be a lot simpler to code the bot in C.

I also need to start coming up with design prototypes soon enough. I need to narrow the focus of this project down to concentrate on one of the main ideas I had chosen in the project proposal and start from there.

Pathfinding randomisation

Looking in to the Monte Carlo algorithm and applications of it to this project.

• Path finding.
• Behavioral trees.

Must look at the complexity of such an algorithm.

Also, random number generator "Mersenne twister".

Quake Live and Quake Arena source code

Played a bit of Quake III: Arena yesterday to get a feel for how the existing AI works and how believable it is. There were a couple of things I noticed about the bots.

• They seem to move pretty fluidly thorough out the map, but it appears to be random and after a while the movement behavior becomes rather obvious. I may need to look at an adaptive strategy.
• When spectating, when the bots are aiming at another player it seems as if they're picking random points in the players general direction to shoot at and pointing at those points instantly. The motion doesn't look fluid, and it looks as if they're jumping from point to point. A possible solution to that wold be to SLERP from the points at which they are currently aiming at to the point at which they want to aim at so it looks less obvious.

I also played some Quake Live to observe the behavior of human players who play. The main thing I noticed was that players don't seem to chat that much on the game servers. Also, there were a couple of times where myself and one other particular player would return to the same point and try and battle it out for the same camping spot, which sparked that player engaging in conversation. I may need to look at how exactly to go about provoking conversation like this.

I had a look at the documentation for the existing AI and it seems pretty good. I should get around to building a base AI entity to start work on soon enough.

Start();

This blog is to mark development in my final year project. I plan to implement an artificial agent that will try to simulate a human player on the game server.