With a new version of Ubuntu out (7.10) I decided to repeat the painful experience I put myself through every couple of years to see if I want to use it as a windows replacement on the desktop.
I've been pleasantly surprised this time. The install process was a bit of a monumental fuck up, but it turned out that my PC has been overheating for a while due to a dirty fan. Windows didn't seem to care. Linux kept shutting down, and I eventually found the system log that told me why it was shutting down, and the exact temperature that caused it. Nice.
At least when linux fails it is usually able to tell you exactly whats going on.
Installing the Nvidia drivers turned out to be a pain in the ass too. The simple procedure they give you to do it from the desktop just didn't work. I then tried Nvidia's simple shell script, which didn't work. And a day or so later I found something called Envy, which did work.
Overall I had to be familiar with linux commands, logging in as root, and editing configuration scripts to get it to do what I needed. It's still a computer experts OS as far as I can tell. Although you can pay for phone support, I don't think they're anywhere near capturing the typical Best Buy PC owner.
So far I can do nearly everything I need to in XP, but the user interface is both flashier, faster, and has the benefit of being linux.
It's still likely I won't be able to fully ditch XP though. I can't chat with my webcam yet. The webcam works but the chat software doesn't support it.
I don't like the fonts, but I'm hoping I can configure that, I haven't spent time twiddling with it yet.
Ubuntu is definitely getting there.
Wednesday, October 24, 2007
C and C++ function pointers
I came across a great page for C and C++ function pointers. It includes the syntax for how you do most things you would ever do with them. An ideal reference because I can never remember the syntax...
http://www.newty.de/fpt/fpt.html
http://www.newty.de/fpt/fpt.html
Tuesday, October 9, 2007
Avoiding Ten Common Game AI Mistakes
1) Moonwalking into walls or objects
Often this is a symptom of the interface between the AI and the game world being too complex, and therefore hard to debug. Sometimes it can simply mean that you have no path finding in the game at all, but we will ignore that for now.
Look for differences in the way that the animation moves and the way it queries the collision system. For example, the AI may do a ray cast to see if there is an object in front of it, but the character control system may move a larger object such as a cylinder, which then collides with the world unexpectedly.
Other problems may be that the general movement code does not handle the collision when it is detected resulting in continuous attempts to move when the physics and collision system will not allow it. Sometimes the movement code fails, switches to an idle state, which then immediately attempts to move again, see item 4 below.
2) Turning "the long way around" to face a target
For some reason this bug often survives until late in a project; sometimes it even ships! It seems like a simple thing to calculate... should I turn left or right to face a target.
Typically people start out getting the X and Z distance to the target and figuring out that as an angle using atan2. Then they take the X and Z components of the facing vector to get that angle via the same route. Finally you just take the difference between those angles.
What usually happens is that if you're not careful when manipulating these angles there are mistakes made when converting between radians of degrees, or when figuring out whether to turn left or right, or when wrapping angles around at 360 degrees.
Let's look at a solution that avoids having to convert and do arithmetic with angles, which is where most of the bugs I see come from.
Firstly take a dot product of the vector to your target and the characters facing direction (just the X and Z components). This gives you the cosine of the angle between the two vectors. Take an acos of that to get the angle in radians. What's nice about that compared to the atan2 route is that it immediately gives you the angle you want, the angle between the facing direction and the target position. You don't have to do anything more to make sure it's the shortest way around.
Then we want to know whether to turn left or right. Again looking only at the X and Z vectors, we can simply figure out whether the target is to our left or right. First we need to get the 2d cross product of our facing direction. If the facing vector is (x,y,z), a vector at right angles to this in 2d is just (-z, x).
If you then take the dot product of this and the vector to the target, the sign of that is whether you should turn left or right! Simple.
3) All the enemies on screen doing the same idle animation in perfect synchronization
This is a very common when a bunch of enemies get spawned at the same time, with the same behaviour and their animations end up perfectly synchronised. Also it happens when the AI's are all hit by some weapon at the same time.
It looks lame, and there's a couple of ways to help this along with making a major impact on your engine. You can play animations at irregular speeds. Play the idle animations at variances of just a few percent, and they won't look wrong, and they will be out of sync with each other. Use sets of random animations as often as you can, especially looping ones. At a higher level you can also make sets of states behave differently. If you have a state machine which has random elements for choosing the next state, then use that to vary the AI's.
4) Enemy behaving unpredictably
However you set up your AI system it will always end up complicated. At it's worst AI code is a mass of "if X then do Y" type statements, and unless you manage it correctly you won't be able to understand what is going on.
Firstly you need to abstract the state actions and state decisions as much as you can. Seperate concepts such as "doing an action" from "perceiving the world" and "deciding to do something". As much as you can allow the AI to be set up in the game data, not in the game code.
Doing so also makes concurrency easier, since if you encapsulate all of your queries about the world, you can execute them in parallel with other game systems, then in a later stage of execution you get the deferred results of those queries and act on them.
But the ultimate solution to unpredictability is debugging tools. You want to be able to store the last few states the AI was in, what transitions got him into that state, and what states it is considering transitioning to. If you can show this stuff on screen, at will, while the game is running, then you're golden. Spend lots of time on this kind of stuff, because I guarantee there will be a time near the end project when someone will come and stand behind you and ask you why something on the screen is doing X instead of Y. If you have no idea, then you're not doing job as an AI programmer.
5) Enemy is vibrating, flipping rapidly between two animations
This happens often in state machines. If you get a state A which transitions to state B, and then on the next update, state B transitions back to A again. Assuming, as often people do, the AI states also trigger animations, then you have the horrible flickering between the two first frames of each.
Ulimately the AI designers can avoid state cycles by not making them, but there are bound to be some that slip through. At which point it, it would be nice to have some mechanism to avoid them. You could flag an error or warning when a state immediately returns to the previous state, or you could have a time within which you cannot return to the previous state.
One nice way to handle this is to make the data about how long you should stay in a state explicit. For example, if an enemy is rolling along the floor then it makes sense that you cannot interrupt that action once it starts, so we have the concept of an interrupt time, before which you cannot break to a different state. Tying states to animations achieves this too, but I don't recommend a one-to-one match of animations to state for reasons that I will cover later.
Having interrupt times that are at least 1/2 a second is a simple way to avoid state thrashing, but you still have to solve the problem at the design level.
6) Irratic running on the spot and sudden direction changes.
Have you ever seen AI's running to a point in the world, then when they get there they overshoot? Or maybe they just keep stopping and running again. Or maybe they spin on the spot.
The problem here is nearly always to do with managing movement and distances to points. There are many ways to get this wrong. For example, if you use a bone or root node on a model as the absolute position of the character, then his distance from a point may vary over time as he animates. Meaning that you keep moving too far from the target point, triggering a new movement state.
Another issue is how close do you have to be to the point to stop trying to move there? If it is 1cm then how accurate is your character movement system? can you move someone with an accuracy of 1cm? If not then you need to enlarge your arrival distance until it is large enough that you can guarantee accurate arrival.
If you couple movement to animation you need to spend a lot of time thinking about where the character is, and a good way is to use a root node that is carefully animated to be well behaved. Then I recommend that you store the displacement of animations, so that you know exactly how far they will move the root node when played.
For ultra slick AI's that walk or run to a point then do a smooth stop animation and end up exactly on the target, you just need to play your walk animation until you get to the point when the transition to stop animation would get you exactly to the target. The you need to play that animation at the right point. You also need to consider where the foot steps are. You can then determine whether to transition to a left or right footed stop.
Finally, it's nice if you can manipulate your animations so that you can vary the distance covered by your walk cycle, just enough so that the transition to stop can be executed at a perfect boundary.
If animation is just something you play in the background and doesn't affect your movement, then things are easier. It comes down to fixing the issues above as best you can, but you don't have to fix them, you will just get sliding and popping now and then. But you won't get the kind of animation driven movement problems that cause you to overshoot.
One final issue is turning. Make sure your characters have a turn speed, that varies with running speed. You can turn on the spot when you're stationary, for example. When running your turning circle is limited.
7) Enemy doing nothing at all
This is pretty much a design level issue, but it's common enough to mention. Sometimes AI's are just dead. They have no idea what to do next and this looks pretty stupid.
Usually this occurs when AI have no valid transition from an idle state. So have your designers think about things the AI should do if everything they typically think he should be able to do cannot be done.
One possiblity is that the path finder is failing. Perhaps the AI spawned in an unreachable area by mistake, or was pushed there, or fell there. If your AI's can get into a situation where they cannot move, then perhaps have them animate now and then so they look puzzled, or are looking around wondering what to do.
Look though transitions from idle and make sure that there is something interested there that can be transitioned to if everything else fails.
This also comes down to good AI system debugging tools. If you can immediately bring up a display showing which transitions the dead entity is considering, you will be able to figure out what to do.
8) Movement deadlocks (doors, bridges)
Choke points happen in AI. Narrow corridors, doors, bridges, tunnels. Sometimes we are even clever enough to come up with a system for handling them. AI's that want to enter the choke point take a queue number, and they go through one by one for example.
Whether you do something like that, or do nothing at all, there needs to be some way to avoid deadlock. One way to do that is by giving your AI's different priorities for movement, so that they can move AI's out of the way. Often a player is able to move AI's about, sometimes simply because he moves first.
If you have a physics based engine for character movement this is easy, just set the mass to be greater on characters that you want to have the highest priority. Otherwise you'll probably have some kind of collision resolution system, and you need to feed in the priority from the AI into that.
9) Using A* for everything
I run a web site which teaches A*, and yet when I come to write a pathfinding or other search program I don't always use A*, and when I do I never do A* on a fine mesh or grid. Why? Because it uses a lot of memory and processing power that is totally unneccesary.
Firstly if you're searching only small data sets, like an AI state graph, or a dozen or so path nodes in a room, you can use Dijkstra's algorithm, which is particularly effective when all the AI's in the room will path find to the same node, since the algorithm will fill out data for the whole network rather than just the start and end nodes. Sometimes even a breadthfirst search is enough.
In general you want the path finding data to be as high level as possible whilst still allowing movement to all possible gameplay areas.
One approach is hierarchical path finding, which really needs to work at engine level. If you divide your game world up into regions, buildings, floors and rooms, for example, an AI can path find at all those levels before finally pathfinding on a grid or mesh level inside the current room it is in.
10) Being too clever
Good AI is often based on quite simple systems. It almost always is built up using good tools and good design, rather than clever algorithms.
Things to watch out for are learning algorithms, unless they are directly related to gameplay, which tend to make it hard to get the behaviour you want. I don't want to sound like I'm stifling innovation, but don't use a back propagating neural network when a simple table would do the job.
At all times make the systems workings clear via debugging tools, and as best you can allow rapid iteration of AI changes, ideally allow real time changes while the game is running.
Often this is a symptom of the interface between the AI and the game world being too complex, and therefore hard to debug. Sometimes it can simply mean that you have no path finding in the game at all, but we will ignore that for now.
Look for differences in the way that the animation moves and the way it queries the collision system. For example, the AI may do a ray cast to see if there is an object in front of it, but the character control system may move a larger object such as a cylinder, which then collides with the world unexpectedly.
Other problems may be that the general movement code does not handle the collision when it is detected resulting in continuous attempts to move when the physics and collision system will not allow it. Sometimes the movement code fails, switches to an idle state, which then immediately attempts to move again, see item 4 below.
2) Turning "the long way around" to face a target
For some reason this bug often survives until late in a project; sometimes it even ships! It seems like a simple thing to calculate... should I turn left or right to face a target.
Typically people start out getting the X and Z distance to the target and figuring out that as an angle using atan2. Then they take the X and Z components of the facing vector to get that angle via the same route. Finally you just take the difference between those angles.
What usually happens is that if you're not careful when manipulating these angles there are mistakes made when converting between radians of degrees, or when figuring out whether to turn left or right, or when wrapping angles around at 360 degrees.
Let's look at a solution that avoids having to convert and do arithmetic with angles, which is where most of the bugs I see come from.
Firstly take a dot product of the vector to your target and the characters facing direction (just the X and Z components). This gives you the cosine of the angle between the two vectors. Take an acos of that to get the angle in radians. What's nice about that compared to the atan2 route is that it immediately gives you the angle you want, the angle between the facing direction and the target position. You don't have to do anything more to make sure it's the shortest way around.
Then we want to know whether to turn left or right. Again looking only at the X and Z vectors, we can simply figure out whether the target is to our left or right. First we need to get the 2d cross product of our facing direction. If the facing vector is (x,y,z), a vector at right angles to this in 2d is just (-z, x).
If you then take the dot product of this and the vector to the target, the sign of that is whether you should turn left or right! Simple.
3) All the enemies on screen doing the same idle animation in perfect synchronization
This is a very common when a bunch of enemies get spawned at the same time, with the same behaviour and their animations end up perfectly synchronised. Also it happens when the AI's are all hit by some weapon at the same time.
It looks lame, and there's a couple of ways to help this along with making a major impact on your engine. You can play animations at irregular speeds. Play the idle animations at variances of just a few percent, and they won't look wrong, and they will be out of sync with each other. Use sets of random animations as often as you can, especially looping ones. At a higher level you can also make sets of states behave differently. If you have a state machine which has random elements for choosing the next state, then use that to vary the AI's.
4) Enemy behaving unpredictably
However you set up your AI system it will always end up complicated. At it's worst AI code is a mass of "if X then do Y" type statements, and unless you manage it correctly you won't be able to understand what is going on.
Firstly you need to abstract the state actions and state decisions as much as you can. Seperate concepts such as "doing an action" from "perceiving the world" and "deciding to do something". As much as you can allow the AI to be set up in the game data, not in the game code.
Doing so also makes concurrency easier, since if you encapsulate all of your queries about the world, you can execute them in parallel with other game systems, then in a later stage of execution you get the deferred results of those queries and act on them.
But the ultimate solution to unpredictability is debugging tools. You want to be able to store the last few states the AI was in, what transitions got him into that state, and what states it is considering transitioning to. If you can show this stuff on screen, at will, while the game is running, then you're golden. Spend lots of time on this kind of stuff, because I guarantee there will be a time near the end project when someone will come and stand behind you and ask you why something on the screen is doing X instead of Y. If you have no idea, then you're not doing job as an AI programmer.
5) Enemy is vibrating, flipping rapidly between two animations
This happens often in state machines. If you get a state A which transitions to state B, and then on the next update, state B transitions back to A again. Assuming, as often people do, the AI states also trigger animations, then you have the horrible flickering between the two first frames of each.
Ulimately the AI designers can avoid state cycles by not making them, but there are bound to be some that slip through. At which point it, it would be nice to have some mechanism to avoid them. You could flag an error or warning when a state immediately returns to the previous state, or you could have a time within which you cannot return to the previous state.
One nice way to handle this is to make the data about how long you should stay in a state explicit. For example, if an enemy is rolling along the floor then it makes sense that you cannot interrupt that action once it starts, so we have the concept of an interrupt time, before which you cannot break to a different state. Tying states to animations achieves this too, but I don't recommend a one-to-one match of animations to state for reasons that I will cover later.
Having interrupt times that are at least 1/2 a second is a simple way to avoid state thrashing, but you still have to solve the problem at the design level.
6) Irratic running on the spot and sudden direction changes.
Have you ever seen AI's running to a point in the world, then when they get there they overshoot? Or maybe they just keep stopping and running again. Or maybe they spin on the spot.
The problem here is nearly always to do with managing movement and distances to points. There are many ways to get this wrong. For example, if you use a bone or root node on a model as the absolute position of the character, then his distance from a point may vary over time as he animates. Meaning that you keep moving too far from the target point, triggering a new movement state.
Another issue is how close do you have to be to the point to stop trying to move there? If it is 1cm then how accurate is your character movement system? can you move someone with an accuracy of 1cm? If not then you need to enlarge your arrival distance until it is large enough that you can guarantee accurate arrival.
If you couple movement to animation you need to spend a lot of time thinking about where the character is, and a good way is to use a root node that is carefully animated to be well behaved. Then I recommend that you store the displacement of animations, so that you know exactly how far they will move the root node when played.
For ultra slick AI's that walk or run to a point then do a smooth stop animation and end up exactly on the target, you just need to play your walk animation until you get to the point when the transition to stop animation would get you exactly to the target. The you need to play that animation at the right point. You also need to consider where the foot steps are. You can then determine whether to transition to a left or right footed stop.
Finally, it's nice if you can manipulate your animations so that you can vary the distance covered by your walk cycle, just enough so that the transition to stop can be executed at a perfect boundary.
If animation is just something you play in the background and doesn't affect your movement, then things are easier. It comes down to fixing the issues above as best you can, but you don't have to fix them, you will just get sliding and popping now and then. But you won't get the kind of animation driven movement problems that cause you to overshoot.
One final issue is turning. Make sure your characters have a turn speed, that varies with running speed. You can turn on the spot when you're stationary, for example. When running your turning circle is limited.
7) Enemy doing nothing at all
This is pretty much a design level issue, but it's common enough to mention. Sometimes AI's are just dead. They have no idea what to do next and this looks pretty stupid.
Usually this occurs when AI have no valid transition from an idle state. So have your designers think about things the AI should do if everything they typically think he should be able to do cannot be done.
One possiblity is that the path finder is failing. Perhaps the AI spawned in an unreachable area by mistake, or was pushed there, or fell there. If your AI's can get into a situation where they cannot move, then perhaps have them animate now and then so they look puzzled, or are looking around wondering what to do.
Look though transitions from idle and make sure that there is something interested there that can be transitioned to if everything else fails.
This also comes down to good AI system debugging tools. If you can immediately bring up a display showing which transitions the dead entity is considering, you will be able to figure out what to do.
8) Movement deadlocks (doors, bridges)
Choke points happen in AI. Narrow corridors, doors, bridges, tunnels. Sometimes we are even clever enough to come up with a system for handling them. AI's that want to enter the choke point take a queue number, and they go through one by one for example.
Whether you do something like that, or do nothing at all, there needs to be some way to avoid deadlock. One way to do that is by giving your AI's different priorities for movement, so that they can move AI's out of the way. Often a player is able to move AI's about, sometimes simply because he moves first.
If you have a physics based engine for character movement this is easy, just set the mass to be greater on characters that you want to have the highest priority. Otherwise you'll probably have some kind of collision resolution system, and you need to feed in the priority from the AI into that.
9) Using A* for everything
I run a web site which teaches A*, and yet when I come to write a pathfinding or other search program I don't always use A*, and when I do I never do A* on a fine mesh or grid. Why? Because it uses a lot of memory and processing power that is totally unneccesary.
Firstly if you're searching only small data sets, like an AI state graph, or a dozen or so path nodes in a room, you can use Dijkstra's algorithm, which is particularly effective when all the AI's in the room will path find to the same node, since the algorithm will fill out data for the whole network rather than just the start and end nodes. Sometimes even a breadthfirst search is enough.
In general you want the path finding data to be as high level as possible whilst still allowing movement to all possible gameplay areas.
One approach is hierarchical path finding, which really needs to work at engine level. If you divide your game world up into regions, buildings, floors and rooms, for example, an AI can path find at all those levels before finally pathfinding on a grid or mesh level inside the current room it is in.
10) Being too clever
Good AI is often based on quite simple systems. It almost always is built up using good tools and good design, rather than clever algorithms.
Things to watch out for are learning algorithms, unless they are directly related to gameplay, which tend to make it hard to get the behaviour you want. I don't want to sound like I'm stifling innovation, but don't use a back propagating neural network when a simple table would do the job.
At all times make the systems workings clear via debugging tools, and as best you can allow rapid iteration of AI changes, ideally allow real time changes while the game is running.
Subscribe to:
Posts (Atom)
