Wednesday, May 21, 2008

The Game Engines of War

I was all set to create a battlefield area for "Faithless" when I realized that I had no idea how large my area was supposed to be. I need to make several battlefields for my module, but I did not know what the minimum dimensions are and how many NPC soldiers the NWN2 engine can handle without slowing down too much. To give me some inkling of these figures, I decided that making an initial set of AI scripts for relatively large scale battles was in order.

Instead of writing my scripts in the NWN2 Electron Toolset, I chose to create them in the NWN1 Aurora Toolset first. Scripting and testing in NWN1 is much faster than in NWN2. I figured that porting my NWN1 scripts to NWN2 later would be a simple matter.

After two days, I got an initial set of scripts working. To test the scripts, I pitted an army of 38 dwarves against a total of 41 enemies -- 28 orcs, 11 half-orcs, and 2 hill giants. All of the foot soldiers on both sides were level 3, and most of their commanders were level 5. The exceptions were the dwarf king, who was level 6, and the hill giants, who were level 12. Despite the slight superiority of the orcish alliance in terms of numbers and total character levels, the dwarves generally won.

I couldn't help but smile when I saw the dwarven archers march in formation to get within arrow range of the enemy and loose their volleys together. Having squads fight as a unit is what differentiates the default AI from the one that I wanted to develop.

Incidentally, the scenario described here will not appear in "Faithless." The sole purpose of this scenario was to test my battlefield AI routine.

After spending an additional day ironing out a few kinks, I was ready to port the module to NWN2. I had to create the area and NPCs from scratch. I only spent a couple of hours creating the battlefield since I didn't want to obsess over an area that I wasn't going to use in my module. For my NWN2 demo, I pitted 26 dwarves against 45 orcs. I was too lazy to add half-orc NPCs to the module, and since the Electron Toolset does not have any hill giants, I couldn't add those. As for my scripts, I exported them to an ERF file, which I then imported to the NWN2 module. The scripts compiled without a hitch. When I ran the module, however, my game kept freezing as the armies were about to clash.

Panic time.

Fortunately, I had created a trace debugging technique for NWN1 three years ago. This debugging technique also works in NWN2, although setting up the game to output error logs is more convoluted than in NWN1. With this technique, I found that the problem was with something completely unexpected. The NPCs were issuing too many shouts that other NPCs had to respond to. This was causing the engine to overload and break down from sheer stress. It took me two days to get my scripts to run without freezing the game.

Features of the Battlefield AI

The battlefield AI that I created makes soldiers fall in formation when they are spawned. Even if the soldiers are placed haphazardly in their area, they will immediately organize themselves around their unit leader during the game. Hence, the only soldiers that have to be positioned properly are the unit leaders.

The picture below is from the toolset. It shows how the dwarves are initially arranged in their area. In particular, the dwarven archers on the right and the royal guard at the rear are scattered. The dwarven men-at-arms on the left are spaced widely apart.

Below is an in-game view of the dwarves shortly after the module starts. Notice that all soldiers are now neatly lined up in close formation.

Soldiers on the move will also march in formation, albeit somewhat sporadically. Below are a couple of images of orcs on the march. These images were taken within seconds of each other.



Soldiers will generally fight as a unit. Unless their commanders order them to attack, they will stand their ground. The moment steel cleaves flesh or crushes bone, however, fights will quickly degenerate into chaos. But then, such is the nature of war.

The first time that a military unit suffers 50% losses or more, all its soldiers must make a morale check, which is basically a Will save versus fear at DC 20. Any soldier that loses at least 50% of its hit points must also make a morale check. Soldiers that fail will flee the battlefield.

Below are a couple of pictures of orcs exercising the better part of valor. A tell-tale sign that they are running away is that they are no longer carrying their weapons, having dropped them along the way.

To Do

There is still quite a bit of work to be done with this AI routine. For example, I have not implemented any fancy maneuvers such as flanking. In addition, I haven't coded any routine for unit commanders to try to rally their troops. Also, the in-game frame rate when there are too many soldiers in the area is bad. I'll have to figure out what the maximum number of NPCs should be to maintain a minimum frame rate of, say, 15 per second.

All these features will have to come later. For now, I wanted to post an update in this blog regarding my progress. It has been a while since I've written anything here.

Making a War Movie

Screenshots of NPC soldiers in the battlefield are nice, but nothing captures the drama and excitement of war better than a video. I ran my module several times, shooting scenes from different positions until I had enough footage to make a three-minute movie.

While filming, I found out that my frame rate was terribly slow. The actual rate varied from time to time, but I was getting as low as 7 frames per second. Sometimes, my video speed dipped even lower than that. This is unacceptable. I will have to find a way to raise the video speed. The most obvious way is to decrease the number of NPC combatants, although my scripts can probably stand a little more streamlining.

To create a movie out of my footage, I used Microsoft Windows Movie Maker, which comes packaged with Windows XP. Within a few minutes, I started wishing I had bought a reliable video editing software. Windows Movie Maker kept crashing on me. Each time I made a move, I had to save my file for fear of losing all my hard work. This travail was worse than playing the computer game version of Temple of Elemental Evil. War is hell, but so is making a video with Windows Movie Maker. If I had been coerced into using it, that action would have constituted a crime against humanity. Since no one forced me to use the software, I can only excuse myself by pleading temporary insanity.

After a day of madness, I finally completed the video to my satisfaction. It isn't Apocalypse Now, but at least it shows what my battlefield AI is capable of doing. A somewhat hi-res version of the video may be downloaded from the Neverwinter Vault at this page. A very low-res version may be viewed below.


mooncalf165 said...

This is immensely cool- congratulations on figuring it out; I think I'd probably have got sick of Movie Maker after the first effort.

All the best,

dirtywick said...

I can see the framerate is not all that good. That will continue to be a problem as your area gets more objects in it as well.

Cool scripts, though. I'm going to be doing something similar myself soon, just for formation movement, though. It shouldn't be too intensive.

How are you doing it? My plan is to create like a virtual graph on the lead NPC and have locations spaced out along that created as the NPC moves so the members of the formation can predict where they should move to keep the formation. But the pathing in NWN2 is kind of awful in that regard.

Anyway, very cool stuff, I'm sure you'll get the kinks worked out.

Frank Perez said...

Thanks for the feedback, Nick. If I ever make another video, I'll probably get a reliable video editing software rather than rely on Movie Maker. I might be able to find a good one at the Sourceforge site.

Dirtywick, the frame rate is indeed problematic. I realize now that there's a good reason why OEI didn't put too many soldiers in the Crossroad Keep encounters. I wanted to see how far I can push the limits, and it looks like I pushed too far.

As for how I made soldiers fall in formation, I gave each soldier an index number similar to the indices in an array. That index number is the basis for determining their row and column position in their unit -- effectively like a 2-dimensional array. I then use trigonometry to compute each soldier's location within the formation, using the location of the unit leader as the basis.

Merecraft said...

That's just astonishing. Even the formation scripting is very impressive.

Wyrin said...

top stuff!

Frank Perez said...

Thanks, guys. It looks like this concept is getting quite a bit of interest among players.

Anonymous said...

Oh Wow.

In regards to the framerate problem, I can think of several issues:

-How much of the lag is due to troop number, and how much is due to script execution. E.g. If you have all those soldiers on the field slugging it out in straight fight (without formation and fleeing all that) then how fast can it go? If it goes quite fast, then a key issue becomes script optimization.

-You might then try trimming the script for story related reasons (e.g. Undead, Constructs and Paladins don't flee so they do not need a flee script applied. Similiarly, certain races tend to be too disorganized to march in formation, even if they do fight as squadrons, so those need a far simpler script without formation marching.

-On a related note, things will get hairy with higher level troops that have multiple options at their disposal (Disarm, Knockdown, Whirlwind, Divine Might etc) and extremely hairy if you use spellcasting troops.

-As to Calvary, you can use models of Horse and Rider, and give them speed bonus. The problem being that they can't be dismounted. And I'm not sure where you can find models of horse and rider.

Frank Perez said...

Excellent suggestions, my anonymous friend. I'll do some benchmarking to find out whether the performance problem is due to the battlefield scripts or number of NPCs. I have a feeling it's mostly because of the latter. Regardless, I'm sure that my scripts can benefit from optimization.

For performance reasons, foot soldiers shouldn't be higher than third level. Keeping their levels low ought to trim their available combat options. (Not to mention, having an army full of high-level foot soldiers would strain players' suspension of disbelief.) Likewise, I don't think the game engine can afford to have squads of casters blasting the area with their spells. Those visual effects can make video frames crawl to a snail's pace. I'd rather keep the spellcasters and high-level characters limited to the PCs and some choice NPCs, including companions.

Anyhow, thanks for dropping by. Your comments are much appreciated.

E.C.Patterson said...

This looks very promising. I especially look forward to seeing your move in formation script.

As you probably know, NWN2 includes quite a few formation functions (in ginc_group I believe), for spawning in and moving.

The problem I've had with formation movement is that creatures will not take the most straightforward path to their in-formation destination and will bump into each other, which halts their movement right there. They can be kickstarted again of course, but all semblance of formation movement is lost at that point.

So, as I said, I look forward to seeing your scripts and how you deal with such issues! :) Good luck.

Liso said...

And the battle is on!!

Don't miss Frank's interview on podcast this weekend! :) He did an awesome job :)

Frank Perez said...

Hi, E.C. I didn't know about the formation functions in ginc_group until you told me about them. Typical of me to go off making my own functions when the toolset already comes with a number of ready-made ones that fit the bill.

Unfortunately, my functions also have a problem with soldiers bumping into each other and halting in their tracks. That's why the unit leader has to stop once in a while to reissue the command to fall in formation before marching again. I'm looking forward to patch 1.13, which promises to have a function that can toggle creatures' bump state. That might solve the problem.

Hey, Liso, thanks for mentioning my interview. I'll be sure to post a link at my blog when it comes out.

E.C.Patterson said...

Hi Frank. That's a good point about the new on the fly collision setting (not the same as bump state - my tests had demonstrated that bump state had no effect on the issue). Hopefullly that will solve the problem since creatures, as I understand it, should now be able to path *through* each other. Keep up the good work!

Phoenixus said...

I admit Frank,

Because of the large numbers of creatures I use in my own stuff, mostly because... well that's the way things are on the Savage Frontier... Your AI scripting routines may be something I'd be interested in too.

Frank Perez said...

Hey, Phoenixus, thanks for your interest in these scripts. I might actually release another module tentatively called "Fantasy Armies" before I finish "Faithless." "Fantasy Armies" will have the battlefield AI that I'm developing. I'm hoping that by releasing this module earlier, I'll get a chance to fine-tune the AI based on players' comments. Other module builders will also get an opportunity to read the scripts and adapt them for their own use.