A Practical Guide to Building a Complete Game AI
I've been through and seen a lot of terrible, terrible things thanks to running this site, ranging from unbelievably stupid racist jokes and Golden Girls fan club sites to the worst marketing products in the entire universe, but I've always managed to retain my faith in God. I don't subscribe to any particular faith or religion because the thought of suddenly being told what to think by some rich guy in a bathrobe squirting water on people doesn't really appeal to me. However, I have to keep my belief in some kind of God, or else I'll just go nuts thinking about the hundreds of jerks in college I could've beaten to death without suffering any consequences. Things like that will haunt you for the rest of your life, folks.
So it really shocked me when juicy and plump reader Jimmy sent in a truly horrifying and brain-melting link that immediately made me question my faith in not only God, but the entire existence of good and evil as we know it. No, I'm not referring to the revelation that Jesus will protect us from marine life, but the following article:
Doesn't sound too scary at first, does it? I didn't think so either, at least until I looked down and realized who wrote the article: Geoff Howland. Geoff Howland from Lupine Games. Jeff Howland from Lupine Games who created one of the most shitty and buggy games to ever reach a public location other than a men's public restroom, Hatfields and McCoys (click here for the SA review). Posting an article from Mr. Howland regarding a game's AI is the equivalent of allowing Hitler to record his qualifications for "Humanitarian of the Year." It's the same as asking Wal-Mart to voice their opinions on their hottest clothing aimed at the Hollywood movie star clientele. This is no better than attending a joint Cyrix / 3DFX round table discussion entitled, "How to Capture the Stock Market and Dominate the Competition." This simply should not be. According to the laws of the physics, the universe should implode before anybody at either Lupine Games or ValuSoft (the "e" in "value" was dropped for budgetary reasons) writes a book about artificial intelligence. Hell, I'd be surprised if any of them could READ a book on AI, much less write one. Let's take a quick look at the "Practical Guide to Building a Complete Game AI" by convicted war criminal Geoff Howland and dig a little deeper into this unholy masterpiece, shall we? (HINT: We shall)
Artificial Intelligence (AI) is based on making intelligent looking decisions, for the units in our games to look intelligent they have to perform actions that seem reasonable for the situations they are in. In a Real-Time Strategy (RTS) type game these actions would consist of moving, patrolling, avoiding obstacles, targeting enemies and pursuing them. Lets take a look at what it would take to implement each of these actions.
I assume all three of these sentences are written in pure hypotheticals, because there's no way any creature featured in Hatfields and McCoys experienced any of that. The most complicated example of AI that the enemies showed consisted of them running back and forth in a straight line until they were either shot or the player kicked the CPU off his motherboard and proceeded to break the CD into a million pieces.
Moving, in its most basic form, consists of simply advancing from one set of coordinates to another set over a period of time. This can be performed easily by finding a distance vector and multiplying it by the speed the unit is moving and the time since we last calculated the position.
Yes, that's a fantastic assessment of the situation, Geoff. I'm sure all the time you spent coding the advanced movement engine for Hatfields and McCoys taught you a lot. For example, it probably taught you that despite what anybody else claims, you still possess the ability to spend two hours inhaling the glue fumes from your child's airplane model and then code a routine that allows digital white trash to advance in a straight line from Point A to Point B.
Because we are working from a mouse based input system, we don't expect the user to have to make all the movements around obstacles like they would in a joystick or first-person shooter. The way to keep the user from having to click their way around obstacles is to create an action queue so that we can have more than one action in a row completed. This way if a path has to avoid an obstacle we can add the additional paths in front of the final destination to walk the unit around the obstacle without player intervention.
What a positively fantastic idea. Perhaps you could actually implement that in your 99-cent bargain bin games from now on, instead of simply writing about it like any amateur Art Bell nutball. I can't count the number of times my player in Hatfields and McCoys decided to stop moving because there was an object in front of him... or anywhere within a 50-mile radius. Hell, I would've been happy with the plain old "Point A to Point B" routine you mentioned before, but I'm sure your dev cycle of 19 minutes just didn't allow enough time.
Patrolling consists of moving to a series of specified positions in order. At the time when a unit has moved to a destination and has nowhere else to go, we can compare his current position to his list of patrol points and set a new destination to the one after where he is closest to. There isn't a lot to this, but having units moving on the screen, as opposed to standing still and waiting, makes the world look a lot more alive and gives them a lot less chance of being snuck up on and catching intruders.
If you're in a Lupine Games title, there is nowhere else for you to go, period. Your only option is succumbing to the vile will of Geoff Howland or putting a shotgun to your head and decorating your digital brains all over the pixellated walls. As for addressing "the world look a lot more alive", perhaps the trick isn't just making your idiotic characters run back and forth from a tree to an outhouse every six seconds. Maybe you'd have better luck, oh, I don't know, giving them more than nine total frames of animation, or including artwork that wasn't produced by children in a hospital burn ward, or generally refusing to produce a game that has the raw realism factor of "The Naked Lunch." No wait, screw it, having a guy in overalls walk in a line for an infinite amount of time is easier and requires less skill, let's go with that.
Avoidance algorithms require the understanding of how your maps are going to work and how you want your units to interact with them while moving around. In our case we are going to assume an outdoor environment with relatively small and simple obstacles such as small buildings and objects. We will also assume that you cannot go inside an obstacle and that obstacles are convex polygons with 4 vertices.... When you want to get into some more advanced path finding algorithms, you should look into A*, which is a popular algorithm for finding the shortest path through very maze-like areas. Beyond A* there are various steering algorithms for gradually moving around obstacles and other more hard-coded situations such as creating funneling intersections that can be used to get to different areas of the map.
I don't understand how Geoff can possibly be lecturing on avoidance algorithms. For Christ's sake, the enemies on Hatfields and McCoys would run on ground level and suddenly appear on top of a house where they would become stuck and remain motionless for the remainder of the game! There were a few times where the bad guys would run towards me, head face first into an outhouse or tree, and just sit there, running in place all eternity! Maybe Geoff's "avoidance algorithms" are limited to his procedure of staying away from his boss who is unaware that all of Geoff's coding experience stems from the 16 days he took a Visual Basic course in college before he was kicked out for "lewd and offensive acts" with his workstation.
Targeting for other units will greatly depend on what you want your player to be doing in your game. You may want your player's units to automatically fire on enemies they see, so that player can devote themselves to the big picture. You may want your units to only attack if specifically told to keep your player's attention on the units and their surroundings.
"The big picture"? The big picture in Hatfields and McCoys was to last five minutes without tearing your pubic hair out by the handful. You could click on enemies, but it was simply blind luck if your character would actually fire upon them (or do anything for that matter). It was about as strategical as a salad bar.
Once your enemies have found a target, you won't want them to just wander around aimlessly if they lose sight of their prey. At this point you need to make a choice about how you wish to handle your searching though. Up until now we have only talked about spotting units based on actually being able to see them. In some cases this may get a little tricky when pursuing an enemy, so you may opt to cheat and just set the destination of the unit being tracked as the tracker's destination.
Yes, and if you're too lazy / incompetent / drunk to even "cheat", then just have the enemies move seven inches in your direction and stop. That will apparently work too.
The secret to implementing all game AI is the understanding the cases you are trying to deal with and the results of what you want it to look like. If you can picture what you want the actions to look like and formulate an algorithm to make them turn out that way you are 90% of the way done. However the last 10%, getting it to work, can easily take 10 times as long as figuring out how to do it&
As far as I can tell, this is Geoff explaining that doing 90% of the work is a lot, and a pretty good number when you think about it, so don't get really bent out of shape when his game is shipped missing a critical 10%. I don't blame the guy; who the hell would actually buy Hatfields and McCoys anyway? Surely not people with a large enough collection of brain cells to drive themselves home without careening into the side of Goodwill store, so what does he have to worry about? It's not like ValuSoft will lose its reputation as one of the most high quality game distributors out there, since they're pretty much the White Castle of gaming. It just boggles my mind how Geoff could write an article about AI and a website would PUBLISH it. They couldn't have done it for the hits or traffic, because mentioning the phrase "Lupine Games" evokes the same response in most people as casually mentioning you just caught their grandmother inserting various Christmas ornaments into her anal cavity. If there is in fact a God, He would not allow such an article to exist. And, even if He did, He would find enough pity in his heart to strike me dead before my web browser has a chance to open it.
For more information on the millions of reasons Hatfields and McCoys is just about the worst product ever created, check out our review of the game.
Since all the other "reputable" sites out there have been writing about Microsoft's newest DirectX 8.0 release, I asked Jeff K. if he would be up to reviewing it. Oh boy, was he ever up to it! Presenting Jeff K.'s latest informative article, "WHY YUO SHOULD NEVAR INSTALL DIRECT X 8.0 OR AND MICROSOFT IS SUCKS!!! ANYWAYS!!!"
this shows that Direct X maeks yuor computar slowar too load becuase it isant coded vary good at all! THEY TAKE CODEING LESSONS FROM LITHTECH I THINK!! because teh codars at Lithtech just keep addeing in new code and more and more new code and more code because theyre afraid to deletes any old code because JASON HALL WILL CRUSH THEM IF HE SENSES INCOMPOTENSE!!! RAARRRRRRRRRR!!! Jason Hall si SUPAR MUSCALES and evary time he blinks it creates a HURRICANE OF DESTRUCTIAN! so dont displease Jason Hall by deleteing code from Lithtech v.12.50 or hell smashes yuor head liek SOUP/
If you read it on a webpage, it must be true! So go read it!