Blog for Mathieu Marquis-Bolduc at GarageGames.com

The long path to AI

Mathieu Marquis-Bolduc — 2007-02-07T21:16:44+00:00

Heya all!

Long time since my last update, and big changes too.

First, a lot has been going in my personnal life. Ive been struggling to finish my master degree. I am almost there, when that is finished, it should leave me much more time for hobby development. Publishing scientific articles is such a pain... Second, I am changing job! Not only changing job, but changing country and continent too, as I will be moving from Canada to the Netherlands for a very exciting job over there. Yay! Hope I'll have a good time.

Since my last blog update, I have been busy discussing publishing options, and preparing my AI package for external testing. One of these steps was writing the User Manual, so that the kind people helping me test would not feel totally lost. Writing about your work make you realise a lot of things about it. One of the thing I realized writing the manual is that the GOAD tool was not as intuitive to use as I would have thought. It is very intuitive to me, but I see now that its complexity of use might overcome its usefulness for somebody else. So Im currently putting this tool on Idle while I figure out how to make it simpler to use. Maybe replacing it by a less general but simpler Sport AI tool.

Another thing I have been pondering is a comment on the forums. A kind Torque User commented that while the planner tool seems powerful, the best AI is useless without a pathfinding system (for most games). I have to agree, currently there is few pathfinding options for Torque users. My planner demo use a place-holder pathfinding sytem that is not suitable for any practical use. So in the last holidays Ive been working on a nifty pathfinding tool. The tool is based on navigation meshes. 3 steps to use it:

-> Automatically create a navigation mesh from the terrain geometry
-> Adding custom navigation links (doors, ladders, jumping over ledges, etc)
-> Finding paths in real-time in the game

Im almost finished with the first (and most difficult) step. I'll try to upload some images latter. Its been kind of a pain to learn the very various methods of collision detection TGE use, but I learned a lot in the end. Another thing what slowed me down is the Vector class in TGE, which tries to emulate its STL equivalent but really have a lot of flaws, I lost a LOT of time dealing with it, and Im considering banning the thing from my code. For example, when allocating memory, this Vector class does not seem to call the appropriate constructor, and its iterators are, well, deficient. Anyway! Its become a pet peeve of mine. Navigation meshes are really powerful for pathfinding and other AI use, so I think the work will be worth it in the end. Excluding all of the static geometry from the mesh is not all easy, lots of numericals problems there. It already works, but not well enough yet.

I really dont know how complex step 2 will be. I want so start simple and add more as needed.
Step 3 should be a piece of cake, I have done things like that for a long time now.

I think this tool could be usefull to a lot of TGE user, if I can pull it off.

Well, thats it! No idea when everything will finally be ready. Its almost a year since Ive started working on this, Ive been quite busy with the rest of my life, but thats the joy of hobby development. Thanks for everyone's comments and support, and sorry for the people who have been waiting for so long.
To summarize:

Bad news:

-GOAD tool on hold
-Master degree still now finished
-Busy with moving to Europe

Good news:

-Project still ongoing, if slowly!
-Moving to Europe for a new job
-Master degree *almost* finished
-Pathfinding tool in the works

Planner AI video demo

Mathieu Marquis-Bolduc — 2006-09-23T00:36:22+00:00

Hi everybody!

After a few months of hard work, here is the second AI system that I wish to include in my
AI toolkit: A planner system!

Planners are one of the most powerful AI tools available to game developpers. A very similar
planner is at the core of award-winning F.E.A.R.'s AI*. In fact, I developped this tool after
discussions with Monolith's Brian L, and thanks to Jeff Orkins papers (also from Monolith).

So how does a planner work? Simple. It finds the best sequence of action (a plan) that should take an
AI agent from his current state to a certain goal state. What makes a planner so different
is that a lot more of the thinking is done by the AI, so thats a lot less by the AI designer.

I made a shooter demo featuring the planner engine.
You can view a video of it here on YouTube.
Please tolerate my programmer's map editing skills!

If used correctly, an AI using a planner will be very good at adapting itself to unexpected
situations. As I said, they are also dead easy to use. Taking apart actual debugging of the planner,
setting up the AI for the shooter demo barely took an hour.

Like my previously presented GOAD system, the planner is configured using an XML file.
There are just two sections to this file. The first one list all available actions. For each action, you simply need to mention
what part of the goal state can it helps with and what does that action requires. An improvement to the FEAR
planner architecture is that I also allow you to specify under which conditions it is best to use that action.

An action example from the demo, syntax subject to change:

<ACTION Name = "AttackTarget">
<ARG Name = "x" />
<CHANGE>
<CONDITION Name = "IsAttacked" >
<ARG Name = "x" />
</CONDITION>
</CHANGE>
<REQUIRE>
<CONDITION Name = "AtTarget" >
<ARG Name = "x" />
</CONDITION>
<CONDITION Name = "HaveWeapon" LongValue = "1" />
<CONDITION Name = "HaveAmmo" LongValue = "1" />
</REQUIRE>
<RULE>
<CLAUSE Name = "Always" />
</RULE>
</ACTION>

This tells the planner that the action ""AttackTarget(x)" will try to solve the goal "IsAttacked = x".
It also tells that this actions require the agent to be near the target x, and have a weapon and ammunition.
Finally, it tells us that Attacking the target is actually *Always* an ideal option to solve the "IsAttacked" goal.

That is the descriptive part of the behavior. I feel that it is key, when designing AI, to separate the behavior
description from the action's implementation. As with the previous GOAD system, I wrote all necessary C++ code
to link the planner with torquescript. Lets see how the "AttackTarget(x)" action behavior is implemented in Torque Script.

function AIPlayer::AttackTargetApply(%this, %target)
{
%this.lSetStateVar("IsAttacked", %target);
}

function AIPlayer::AttackTargetExecute(%this, %target)
{
%this.setAimObject(%target, "0 0 1");
%this.fire(1);
}

Yes, its as dumb as that. Each action has two function attached to it. The "Apply" function is used at planning time,
and set the changes in the current state. The "Execute" function is used when executing the plan.

The last bit of AI configuration is to define each class of AI. The only thing you need to go is to list the actions
that are available to each kind of agents/NPCs/Bots in your game. Here is the whole thing from the demo:

<CLASS Name = "Dummy">
<ACTION Name = "Wait" />
</CLASS>

<CLASS Name = "Kork the Mighty">
<ACTION Name = "PullLever" />
<ACTION Name = "GotoObject" />
<ACTION Name = "PickupAmmo" />
<ACTION Name = "PickupWeapon"/>
<ACTION Name = "AttackTarget"/>
<ACTION Name = "GotoTarget"/>
<ACTION Name = "GotoNode"/>
</CLASS>

Planner systems are not suitable to all games. For example, it would be harder to use for a sport game, where you dont typically plan a lot of things in advance, but rather react as things unfold. However,they seems to be ideal for tactical shooters. They could also be great for strategy games, both turn based and RTS, as well as role-playing games with complex NPCS (like the Elder Scrolls or Gothic series). It can also be a very good idea to use both the GOAD system and the planner system together! For example, you could use the GOAD to keep track of currents goals and decide which one is most important, then use the planner to find a way to solve the critical goal.

Well, thats all I have to say now about the planner. From now, I am wrapping things up to a state where I will be able to begin beta testing. Things like writing the manual, and safe-profing everything against memory leaks and exceptions. I already have several people interested in beta-testing the GOAD system (Thanks guys!). If you are interested in beta-testing the planner, please contact me directly. If you have ideas about what kind of AI tools you would like to see in future versions of the toolkit, you can post them here.

Some ending word: My main goal with this project is to provide amateur and professionnal game developpers with the most advanced AND efficient AI systems. While I strive to make them the easiest to use, you will still need moderate game programming skills to use them, and some talent with AI to exploit
them to their fullest.

Thanks again for your interest in this project, it makes all the hard work worth it. I can only hope my AI tools will live up to your expectations.

Mathieu Marquis Bolduc

Foot-notes:

*A few words on the FEAR thing. There is a LOT more about FEAR's AI than just a planner.
Targeting system, pathfinding, squad coordination, etc. But the planner is what determines
the NPC's actions. Big thanks to Jeff Orkins and Brian from Monolith Productions for sharing their ideas and
experiments.

**By the way, both video demos are running in debug mode while recording with Fraps. If used correctly, performance is
excellent. However, to have good performance, its is primordial that all information needed by the planner be readily
available. In middle of planning is not a good time to do ray casting or terrain analysis! You can use the other 99% of
cycles when the AI is not planning to do that other stuff.

Football AI demo movie

Mathieu Marquis-Bolduc — 2006-06-24T00:48:57+00:00

Hey everybody,

Due to popular demand (thats at least 3 people!), I've uploaded a video showing my football AI demo in action. You can see it here on google video. I apologize for the severe compression, can't do better.

I've mainly worked on the offensive play. I seems simple when you see it in action, but there is a lot to it!
The demo currently features:

7 goals and sub-goals;

PlayBall, CatchBall, GrabFreeBall, Offense, OffenseWithBall, OffenseWithoutBall, Defense, ProtectPlayer

8 possible actions, (that are often combined);

RunToGoal, AvoidEnemyPlayers, RunToBall, SeparateFromPlayers, RunToPlayer, CallProtectPlayer, PassToPlayer, InterposeBetween, StayInPassDistance

3 events;

Kickoff, BallCatched, BallThrown

and a grand total of 11 logic clauses:

BallClose/IsCloseToBall, BallHolderInMyTeam, IsBallHolder / HaveBall, AreClose, Protected, InDanger/IsInDanger, InThrowDistance, Always.

At first it is a lot of work, even with the fully operational AI engine. But once you reach a critical mass of goals, events, actions and clause to work with, you can add new behaviors with real ease, just by playing in the behavior rules script file.

I will most probably include this full demo when I'll release the AI engine to the public. The demo is by no mean a functionnal football game, but I think it will work nicely at exposing how to work with the decision making engine. The latter should come as a dynamic link library, with mandatory header files and all necessary and usefull bits of code and scripts to make it run great with TGE.

AI engine shaping up

Mathieu Marquis-Bolduc — 2006-06-19T23:59:48+00:00

Well, I had a 3-pages blog entry written, but that was before I found out you should NOT use accents, it erases the whole thing. So Im just gonna sum it up...

My AI decision-making engine is going on pretty well. I now have a demo of 6 korks playing touch football. Their behavior is described in a XML feed. The Torque engine sends gameplay events and information to the AI engine, who apply this information to the behavior rules, and reacts by updating each agent's goal stack and executing actions in the Torque Engine. Right now in the demo, those actions are mainly activating steering behaviors to make the players go around.

The AI engine is finally using variables, which was a huge milestone. I can now have behavior rules that reads like "Protect X against Y if X have the ball and Y is running toward X". X and Y can be anything, as long as you can express it in a 32 bit value. The engine never actually interpret those symbols, it just pass them back and forth to the game engine.

After I improve that demo a bit, there is two features I want to implement in the AI engine. First, verbatim. I want the AI agents to be able to explain, if asked, why they decided to perform an action. That shouldnt be too hard. Next, I want to implement behavior inheritance. For example, you could describe the behavior class "dog", and the behavior class "football player". Then, you will be able to create an agent that mixes both behavior class. You will then get a dog that plays football. Or an agent that plays football like a dog ;)

Catch the ball

Mathieu Marquis-Bolduc — 2006-05-12T03:46:44+00:00

Well, I finally found a few hours tonight to work on my AI engine and demo.

I now have a new agent ("Catcher") in my demo. He will stand around, watching me and waiting for me to throw a ball. When I throw the ball, he will run to it and try to catch it before I do.

This may sound simple, but in fact I added several new functionalities to the AI engine. The main of these functionalities is event handling. In this case, I used the events "BallThrown" and "BallCatched". The agent decide on how to react to those events depending on its current stack of goals, as well as conditions set in the AI script. For example, in my demo the event "BallThrown" make the goal "waitforthrow" succeed, while the event "BallCatched" make the "CatchBall" goal succeed, but only if the agent is the one who catched it. They could also make the agent perform an action, or add a new goal.

I also worked on making my XML-based AI script simpler and mostly shorter. The behavior described on top is all described in a very tiny XML script.

I need to think a bit about how to best handle the goals when a goal fails. Then I can move on to tackle the next big feature, clause arguments. Write now, I only use logical clauses similar to "Athenian()". I need to move on to something like "Athenian( Socrate )". Arguments are already supported in the engine interface, that is the AI engine can already pass arguments to the actual game (and vice-versa). But it is not yet done in the AI script. The major problem with arguments in a logical script language is the unification of variables. Im not sure if it will be an issue right now, but I have to think ahead.

Well, enough for tonight!

Row Row Row the boat... (he's gonna need one)

Mathieu Marquis-Bolduc — 2006-03-05T03:33:51+00:00

Its been a long time since I last had time to work on Torque.
Im now working full time at a very interesting place, but unfortunatly I havent quite finished my master degree yet, which means that I have very little free time for my "own" projects.

Ive begun working on what I think will be a very good AI engine. The engine itself is coded completely outside Torque and available as a DLL. Ive been working on the necessary linking with the Torque engine and today it finaly worked! Of its own free will (given by the AI engine), Kork the Ork decided to run directly to the (0,0,0) point, which means that he headed directly trough the bottom of the lake, emerged on the other side and continued running as if not wet at all.

So what is currently done and working: (in no particular order)

-Loading of AI rules in XML scripts.
-Interfacing with Torque
-Agent creation
-Simple Decision making
-Goal stacking
-Clause and Actions callbacks
-Error Management

The initial problems encountered while interfacing with Torque were a good thing in the end. They forced me to make my engine more flexible and robust, and forced me to implement the error management right away. Now errors in the AI engine will print themselves in the console.

Next step is to make Kork run around just like before, then script a slightly more interesting Ork featuring more goals.

Sunday Mar 20 23:20

Mathieu Marquis-Bolduc — 2005-03-20T23:20:10+00:00

After having spent some time exploring the SDK to get a good feel of it, I think its time I begin to implement some of the basic stuff I will need. I finally can compile everything with Eclipse thanks the to TBE.

The first think Im implementing is the object picking tool, since it should be a basis for many of the rpg functionnality. Also it should allow me to learn more about the mouse and event system, which will be usefull to implement the camera scheme I plan to use.

Tought of the day:

"After bread, education is the first need of people"