A quick update today, I have graduated college and am officially in the work force. Great time to do so I know, luckily I am under no emergency to get a new job, but I am looking. Therefore, if you are visiting here and you like what you see, please visit my About page to download my resume, cv, and portfolio. I am willing to relocate ( eager, in fact ), and prefer jobs that are interesting and will challenge me to learn and improve my existing skills.
You are currently browsing articles tagged research.
Ever want to get more out of your music? Feel like your relation
ship is entirely one sided? Then you probably have not played Audiosurf yet. In a nutshell this program turns you music into a game that you play for points and against other people if you so wish. There are quite a number of cool features in Audiosurf but they are easily discovered while playing or researching the game. Instead I wish to make this post about a problem Audiosurf has, which is that tracks can be inconsistent across operating systems.
If you have ever seriously tried to play Audiosurf with someone or maybe a group of people you might discover that another person’s track is different then yours, in both congestion and block positioning. It so happens that me and my friends have setup a mini competition where we get scored for points and positions in several weekly songs. For full details: http://surfoff.blogspot.com/
Back to the main purpose of this article, yes, tracks do differ between operating systems, most common are windows xp to windows vista. The problem seems to be with the mp3 decoders, or so they say.
Here is how to fix this problem, simply use an open source audio editor like audacity and export the mp3 as a wav file. Then distribute and surf the wav file. You might want to use a good compressor, like winrar, for the file however, as it will be big.
Why does this work?
Audiosurf must first decode an mp3 before it can process it for block positions and colors. This process can differ between operating systems as previously discussed. So what we do here is decode the mp3 once on one machine and distribute the song uncompressed. This way Audiosurf does not need to decode anything, which in turn means it is not operating system sensitive.
Happy surfing
Ok ok, I am writing again! If you read my previous posts on dynamic npc actions then this is an update on my progress. If you have not, this is about how to create good file formats for your applications.
As some might have expected this project is taking more time then expected, partially because I am currently downing bosses in WoW, and partially because its very hard. So lets just cover what has been going on since my last post.
I spent a lot of time thinking of the best structure for my idea in terms of objects and file formats. I do not know if I covered this before because I am to lazy to view my past posts so heres a recap of the basic composition of what I have been calling a ‘Puppet.’ A puppet is a game object with x number of movable joints. These joints are built in a tree structure and move based on messages passed to his parent. These messages are generated from a actor class who learns actions and movements as I previously discussed. When I was designing the puppet class I hit a big fat road block. I wanted the ability for a puppet to be independent of his underlying joint structure. That way I could have a puppet control everything from a human to grass. So you might think, ‘No problem, do some tricky interface work and have derived classes for each type of puppet.’ WRONG!
See I myself have read many articles about component game object design, and I do believe I wrote an article on this in the past. However do not get the wrong idea, what I did is not EXACTLY component objects, but kind of close. Because when I thought about components I also thought how to best describe them in a file format. And after thinking about that I decided that I wanted a global file format to describe not only each type of puppet but the entire world. And that the entire game will be built out of components in a tree structure built at load time from this file format. I am getting a bit ahead of myself here so lets get some examples here.
<world>
<name type=string>Main</name>
<description type=string>
Big world for which to run tests in
</description>
<floor type=plane>
<p1 type=vector>-1000 -1000 -1000</p1>
<p2 type=vector>1000 1000 1000</p2>
<material>dirt01.mat</material>
</floor>
<joint>
<position type=vector>0 0 0</position>
<orientation type=vector>0 0 0</orientation>
<puppet>arm.puppet</puppet>
</joint>
</world>
This is my toy world I am working in. The file format is xml and I use tinyXML to load and parse these files. For those familiar with ogre, I made a resource of type XMLFile to load these. Now here comes the clincher, this XMLFile resource will load every type of game object I desire, regardless of type or purpose. Not only that, but I only added 2 methods to the class.
So let me explain a bit about these methods, they are named ‘build’ and they are called usually immediately after loading the file. Basically what they do is look at an element in the xml, find a builder for it, have the builder build it, and attach the new object to the world tree. In this example, the world has no parent and all elements inside the world tags are children of the world. I use the type descriptors so that I would not have to write many classes that do the exact same thing. Elements that load another file, like the puppet tags, will load that file in their own world and all objects created from that are children of the puppet. After the build the main program is not aware of any object other then the world. Messages are passed to the world when need be, however most thought processing is done in the world object, not by the game engine.
Lets get an example puppet up here:
<puppet>
<name type=string>arm</name>
<description type=string>
Generic arm
</description>
<joint>
<name type=string>shoulder</name>
<gib>upperarm.gib</gib>
<joint>
<name type=string>elbow</name>
<gib>forearm.gib</gib>
<joint>
<name type=string>wrist</name>
<gib>hand.gib</gib>
<joint>
<name type=string>pinky</name>
<gib>pinky.gib</gib>
</joint>
<joint>
<name type=string>ring</name>
<gib>ring.gib</gib>
</joint>
<joint>
<name type=string>middle</name>
<gib>middle.gib</gib>
</joint>
<joint>
<name type=string>index</name>
<gib>index.gib</gib>
</joint>
<joint>
<name type=string>thumb</name>
<gib>thumb.gib</gib>
</joint>
</joint>
</joint>
</joint>
</puppet>
As you can see this file format is very flexible, the same structure that built the world can build a puppet and also a gib:
<gib>
<name type=string>forearm</name>
<notes type=string>
Fore arm gib
</notes>
<mesh>forearm.mesh</mesh>
<input>
<name type=string>shoulder</name>
<position type=vector>0 0 0</position>
</input>
<output>
<name type=string>elbow</name>
<position type=vector>7 0 0</position>
</output>
</gib>
I want to clarify one thing before I go on. Elements called position or orientation, these attributes are not given any attention by the builders. Instead those objects simply exist on the tree for someone else to read them and make the correct adjustments. For example, the puppet’s name element simply sits as an element on the tree until a debugger opens and the entire tree structure is displayed. At that time the debugger will go through each element and find name tags that it will use to give more information on the node. And the description works the same way.
They are both created by the string builder, as denoted by the ‘type=string’ attribute I give them. The value is assigned and the name of the new object is set, but the type is always a string.
So what exactly is required to declare a new type of object? Just a builder and an actual object. Take this example of the string object.
class ScktString : public ISocketable
{
friend class StringBuilder;
public:
void setValue( std::string val ) { _string = val; }
std::string getString() { return _string; }
private:
ScktString( std::string propName ) : ISocketable( propName ) {}std::string _string;
};class StringBuilder : public IBuilder
{
public:
StringBuilder() : IBuilder() {}
Socket* build( std::string element, Socket* parent );
const std::string& getType() const;
static std::string BUILDER_TYPE_NAME;
private:
static const StringBuilder registerThis;
};
As you can see its relatively easy to create a new object. Lets start at the builder, when the xmlfile is building it will search for a builder based on its type name, which is assigned by you. A builder list is created at the start of the program, as each builder has a static ‘registerThis’ variable that adds it to the builder list. Those familar with static factories should be familiar with this. The builder’s build method gets called with the name of the element and its parent’s socket. A socket is an object that accepts links from children. The builder then builds the object passing its name. The sockable base class is for objects that can be socketed or linked with a parent.
So the string object is created and the string builder passes back the parent object. This is done in case the new object has a socket himself. In that case he would pass back his socket and the builder would build his children and attach them to him. In string’s case however, there is no socket and a little while later the builder assigns the string object a value by calling the setValue method in the parent object with the objects name and value as parameters.
After all the work we are left with one tree that contains all objects in the game. Kind of like a scene manager, but for ALL objects, not just renderable ones. And oh, don’t forget that the entire tree was created by one instance of XMLFile. As programmers we should always strive to achieve the cleanest and most powerful format we can muster. This format is not only really easy to implement, but also holds unlimited power. You want to load a texture? Create a texture socketable object, and implement file specific loading inside it. You want to script AI? Either create an AI socketable object that reads children objects that decribe a strategy, or create a python socketable object that will load your ai scripts and parse them. In this way our file format can act a proxy for another format or as the direct format. The most important thing however is that none of our in game objects need to give file formats a single thought.
Tags: computer science, design, factory, Programming, research
A little while ago, Valve had been quoted as saying that critical hits in Team Fortress 2 are skill dependent. That the chance to get a critical hit increases the better you do. A couple of weeks ago I made up an experiment to test these statements out in game.
First off, I should explain that I wrote a plugin for Team Fortress 2 called TFTrue. This plugin maintains critical chance and damage for server owners wishing to change the default settings. To make the plugin I had to study the take damage function in the game to figure out where the percentages were coming from ( which if you are curious, default you have a 5% chance to crit with weapons and 15% chance to crit with melee ). I thought this statement was weird because after all my searching I never came up with any ‘skill’ variable that increased or decreased the crit chance. I setup my test to work out all the unknown variables in the game code and find out whether or not score has an impact on your crit chance. I will summarize my data here, if you want to refer to the hard data, see the end of this article.
I setup a private server with TFTrue installed and crit chance set to 50%. I made a test map with 1 spawn point and set the respawn time to 0. This made my bots all spawn in the same place with little death delay. I expended 80 rounds of rocket ammo at a wall and observed my critical count. For my control test I ended up with exactly 50% critical chance, so far so good. Next I stepped it up, introducing 7 bots on the opposing team to test the idea that being out numbered helps. After firing all 80 rounds, my crit chance still remained 50%.
Next test involved killing the bots enough to achieve the ‘domination’ status with all of them. With my high score and high skill (according to the game), I fired 80 more rounds at the wall. Still 50% crit chance. What does this mean? It means being consistently better than the other players will not increase your crit chance.
The final test I did was tacked on as a side note when I noticed something interesting while killing the bots. It appeared that I was getting all crits when constantly killing the bots as they spawned right in front of me. So on a hunch I started firing constantly into the crowd of bots and low and behold, 100% crits for all 80 rounds. Upon further investigation I found that after killing 2 players in quick succession increased your crit chance about 4 times. Meaning default crit chance would become 20%. This effect lasted a variable amount of time depending on the weapon type. I timed the demoman’s sticky grenades to last for a bout 20 seconds, however the rockets only lasted about 5. To figure out what specifically influences this behavior we must look back at our code.
Before the Nov. 7th patch, Valve had kept private critical chance variables in the game. Namely, tf_crit_chance, tf_rapid_crit_chance, tf_melee_crit_chance. The first and last variable are pretty much self explanatory, however, what is rapid crit chance I wondered. Back then I decided that it was the chance to crit while firing rapidly. However after reviewing my test results I now believe that maybe this rapid chance is what determines critical chance when killing players rapidly. This is all theory and I have not tested it, but I do think that while playing if you kill a player the game rolls a number to compare to the rapid chance and turns crits on for you if you are lucky. After the Nov. 7 patch the TFTrue plugin treats both those numbers the same, they are both controlled by tftrue_crit_chance. And after further reviewing the code it supports this idea. So if we do work with this theory lets walk through a typical game.
Player Spawns
Player Shoots gun at wall (5% chance to crit)
Player runs to enemy territory
Player kills enemy player (5% chance to start “crit chain,” if the player if lucky he will now shoot crits for X seconds)
Player kills another enemy (5% chance to start “crit chain,” regardless if they are in one or not)
Player shoots (5% crit chance, unless in crit chain, then its 20%)
Player Dies.
I think if you are a hard core tf2 player you can easily identify with this result, just remember that this senerio is purely hypothetical. I have not done any tests modifying rapid crit chance. Like I said earlier however, the code supports this situation.
Now we must turn back to our original hypothesis. Does the critical hit chance get bigger the better you do? In one word, no. However I think we can easily see how Valve would mix up this system with a skill reward. In this system you can be a complete noob and get 1 kill to put you in a crit chain. Your skill as a player has no bearing on the crit chance. How you get more crits in tf2 is to kill more people. The more people you kill, the more shots you have at hitting that 5% chance on the nose.
Test Data:
Test 1: 15 / 40 crits | 24 / 40 crits
Test 2: 18 / 40 crits | 20 / 40 crits
Test 3: 22 / 40 crits | 18 / 40 crits
Test4: 39 / 40 crits | 40 / 40 crits
The true cornerstone of a project such as this will be dynamic and human like actions. I have spent the last two weeks thinking of a system that would allow the development and evolution of dynamic actions, searching the internet, writing down ideas, and finally come up with a design I feel confident enough to post about. I am writing this down for my benefit as well as anyone who is curious, so the train of thought it going to be random and probably hard to understand. For that I apologize, I will have more solid implementation details ready when I have a working system written.
I started by defining what I would be given, and what I would need to produce, and I decided to start with nothing but basic preprogrammed controllers attached to the actor’s to control everything about it. Rotation, position, scale, etc. For an npc, he would have controllers on all his bone joints, for an example. These controllers will have a predefined range of accepted values and know how to move around those ranges. What I wanted to end up with was a high level action, something that will ultimately be composed of hundreds of controller movements over time. And I needed a nice system to wrap up all this data into a structure the npc can store and build off of.
To start off, picture a flat plain of controllers. Each controller knows what it can do, but there are no existing actions yet so this npc is stupid as a brick. During training, actions will start simple, something along the lines of, ‘bend index finger’ works. The npc would look at its action graph and see only the flat plain of controllers, so then its asks each controller if it can accomplish the task of moving the finger’s x position by 1. The controller(s) that respond will have already been defined as able to do this so the npc builds a new action that connects directly with the controllers found previously. Now if the game asks to bend a finger, this action will say ‘I can do that’ and use the correct controller to chance the finger’s position. Its worth noting how the action knows it can do this, so I will explain that a bit. Each action has a function that reads the actor’s current state and determines if it has actions or controllers in its collection to handle that state in any way. If it does, it says yes.
So as the npc adds more and more actions it builds it’s web of linked actions, the process looks a lot like building a neural network. Actions have many actions linked to it, and many actions linked to. I cannot go to much farther without showing you the action class definition so here you go:
class Action
{
Action();
Action( Action* next );
bool validStart( Actor* );
bool validEnd( Actor* );
void AddNext( Action* );
void RemoveNext( Action* );
private:
std::set<Action*> actionList; // Each entry in this action array represents a start state.
// What about actions that have many independant start actions?
};
When designing this class I thought it was going to be some monster from hell, but after I thought about it, added some recursion, and trimmed it down I think it ended up rather nice. Its simple and works well. Each action will hold links to one or more actions. Each action link represents a valid start state, so when validStart is called the class should call each of it’s start states validState functions and return the OR of their return. This design is very recursive, a next link could be another action or a controller at the very basic level. Therefore chains of actions will form in neural network fashion with proper training. When the npc wants to change his state (execute an action) he simple needs to figure out what state he wants to be in, call validEnd( endState ) on each of his higher level actions that match his start state and if one matches, execute the action.
Only problem here is the tremendous overhead of using the brain. Take an example actor with just three levels of actions, when the game asks to do an action on the third level that action asks for valid start on all level 2 actions linked to it, and in turn those level 2 actions call valid state for all level 1 actions linked to it, which in turn call validstart for all controllers that are linked with it. We could be looking at thosands of function calls with a simple 4 or 5 level npc. And the growth is
exponential.
For now we will just have to deal with it since I believe this to be the best way to describe dynamic actions however in the future tremendous effort will be required to optimize this code.
I will be working on integrating this design into my demo project so if my explanation is way off I will have sample code sometime soon.
In a continuation of my last article, I would like to record the process I have been taking to creating and designing the component AI I described in my last post. Component AI is my term for this idea right now, I really have no idea if it has been done before so for right now its what I call it. Now, for those of you who might be familiar with component based object systems (Game Programming Gems 5), this concept will not be to hard to understand.
Basically, we want the npcs to operate off of components they learn about through their training. I know I did not mention training in my last post, but it is necessary for the npcs to not look like mindless zombies through half the game. Each npc will have to be fed through a virtual school where they will learn, through various tests and challenges, how to operate in their world. But I am getting distracted here, back to the design.
Component based objects can be summed up as imaginary containers that are filled with components that operate the object. For example, one component might be a renderer, another holds a model, and one more holds animations. These three together form a solid object that will be displayed in game. They are attached to each other solely through the object manager, but nonetheless are able to effectively communicate with each other through interfaces and a messaging system. I wish I had GPG5 around me so I could yank their example, but I think you get the general idea.
Anyway, objects communicate with themselves through messages, and each of the components that make up an object can subscribe themselves to different messages. A render component would subscribe itself to a ‘draw’ message, that way when the game sends a ‘draw’ broadcast, all objects that have the render component will draw themselves.
That is how component object systems work, when we introduce the ability to pick up new components during run time through actions, we have component AI. The npcs will be equiped with the simple components, model, render, animate, physics, ai, etc, and they will be able to pick up new components from the world to plug into their brain for future use. These types of components can subscribe themselves to messages, and even communicate with each other to achieve the best results. Some form of genetic training will have to be used to teach these components how to effectively communicate. When the npc comes across something new that it doe not know how to handle, picking up a chair for example, it will need to know things about weight, body position, what limbs to use, how to grip it, pretty much everything, and the only way he will know is if the components in his head know how to communicate effectively.
Yes I did mention body position and dynamic animation. I already mentioned the fact that objects themselves will hold data on how to handle them, generally. Then after the npc does that action he will gain a new component for handling that object. This system does not conform very well to static animations like most games keep. So animation will be dynamic and learned by the npc over time. This allows npcs to gain their own style of movement and actions.
Yes yes, I know I am going a bit over board again, running 8 or so npcs each tugging about 10,000 or so AI components will probably be a big load. That is why I need to write a demo application one of these days to see how much this will cost. For right now I am planning to go all out, screw the cpu, but most likely for slower computers we can introduce a system to merge and combine components to save processing time. However the more components you combine the more hard coded the npc becomes.
I had a thought today while walking outside about human-like ai. This is of course, in relation to the game idea I posted a few days ago, but the gist of my goal is to have npc’s that can successfully animate and control characters designed from popular animes.
The idea is pretty simple, the npc’s will derive their actions off objects, not off of themselves. In other words, they will look at the object to determine how to handle it, not depend on preprogrammed responses to objects that are a chair. The objects will store data that the npc can use to lets say, pick it up, throw it, eat it, ect. And the npc will use their MBTI to determine what should be done in the given circumstance.
Part two of the idea is that these objects will also hold ‘experience’ data that the ai will pick up and remember for certain lengths of time. This data can be pugged into their design making structure and called on during other circumstances to determine what to do or how to interact.
Heres a live example,
The npc walks up to a wooden chair
He sees that the chair can be picked up, sat on, broken, and burnt
Along with these verbs are tags that help the npc with the decision.
Example, ‘sit down’ is tagged for resting
‘burn’ is tagged for warmth
He thinks about it and determines that he needs a rest so he sits down
His fatigue goes down and the chair teaches him that sitting down makes him rested
After that he thinks again and determines that he is really cold, so he finds an object that will light the chair (oil and matches) and does so
This demonstrates another part of the idea, in which objects must interact with each other using the npc as a medium. The matches will be tagged as ‘makes fire’ the oil would be ‘spreads fire’ and the chair’s ‘burn’ tag will say that it needs something to start and spread the fire, in order to be used. Sort of like, requirements for an action. To discover the tools, the npc must be able to scan local tags.
The chair is lit and the chair teaches the npc that burning things will make him warmer
However this chair exists in a hay barn, and now that there is a giant fire in the room, all the hay ignites
This is can be accomplished by state broadcasting. In which objects changing state ( eg. Stable to ablaze ) will broadcast the change to all other objects and and objects listening to such a change will decide what to do. ( eg. burst into flames )
So now our npc is to hot and the hay teaches him that hay + fire is not good.
He leaves the barn because the environment outside is not on fire
This action causes a conflict in his code.
On one hand he learned that fire is warm and thus good when cold
On the other hand he learned that hay on fire is bad and makes him to hot
This is not exactly what should be learned here, but I never said this design was perfect
And so our npc lives to see another day, only slightly smarter then he was before. But he gained some valuable survival skills.
This design still needs some tweaking, but at least now we have a working model that I can start writing and testing.
One other thing I should mention though, as these npc’s collect environment data from these objects, certain ideas and concepts are going to collide and others will become useless. We should also account for the human’s ability to forget ideas as well. Some form of garbage collecting will have to be done to clear out bad data. Just keep that in mind.
Recent Comments