Artificial Intelligence comes to Z-Day

As I mentioned on the last blog, we've wrapped up our alpha v0.25, have fixed up the major bugs found and it's full steam onto the Artificial Intelligence, although there will be an element of PvP in the game it's the Zombies that will pose the major threat so it's a key part of the design to get them moving, thinking and attacking with enough challenge to keep players interested.

So where does that process begin?

For us that's been with a lot of reading through books, blogs, forums and articles to gain ideas and see if there are some existing product we could use, we did finding some truly stunning A.I. middleware unfortunately though all of it had one problem... the price tag!

There are some great A.I. and pathfinding resources on the site here Dan Kellers Flexible A* and Gavin Bunneys Immersive AI engine to name just a couple but they're all based on waypoint grids and we wanted a NavMesh based approach for pathfinding which leaves us one option... code our own solution (I know, I know, it's horrible actually having to code something ourselves!!)

Onwards then to;

Phase 1 - Pathfinding

The first phase has to be pathfinding, if the zombies can't move around the city well then the rest of the AI may as well be forgotten any of the behavioural elements we want to add all require some type of movement so seems as good a place as any.

I could spend a long time talking about the pro's and con's of waypoint grids vs NavMeshs but for those interested I think Paul Tozours blog sums up things much better than I could write. So we're going for a Nav Mesh based approach - that is a set of connected convex polygons (we're choosing triangles for simplicity to begin with) but any convex poly would work and N-sided polys would be great we'll save that for a later date though.

The NavMesh will be built up from a few classes starting at the bottom these will be:

Points - These are simply vertices that are used to construct the Nodes.

Nodes - A set of three points that form a triangle and represents an area that an AIplayer can walk around freely within without hitting anything else.

Grids - These are purely for helping the editing of the Mesh, rather than trying to work on the entire world at once we tie Nodes to a grid and will then turn on and off editing of nodes within that grid. We've chosen to make grids tied to objects in the world i.e. Interiors or Static objects and take that objects bounding box as the boundary for placing nodes in that grid area - its both a nice logic way but it'll mean if we move or rotate the world object we can then move/rotate all objects in the grid to match it rather than having to redraw the entire mesh.

Zones - A zone is a collection of Nodes just like a grid, except these are used for actual gameplay and are more strategically placed and serve a number of purposes:

1. Hierarchical A*Star - with a large map it would be faster to first calculate a route through the zones and then at a more detailed level when you're in that specific zone (think of it as LOD system for Pathfinding)

2. Precalculated paths - as a Zone will have predefined entrances and exits when you're just needing to find a path through that zone these can be precalculated and stored in memory then used many times.

3. Learning - Common to most FPS games is that some buildings or areas of maps see a lot more of the player traffic, human players soon learn those areas and that's something else zones give us, the ability for the A.I. characters to learn which zones are used most then we can use that data to seek in those areas more often or direct more of the AI characters to those areas.

4. Strategic Attacks - We've all seen the movies with some form of monster trying to attack and break into the house from every available entrance... marking a zone out for a building will let us be more strategic with our attacks breaking into the house from several directions.

etc, etc...

The Team

Obviously that's quite a lot to deliver and write so it's going to require more work than I alone could reasonably deliver in a shortish time frame so let me introduce you to the team:

Chris Gosling - All round star of Z-Day, Chris is one of those really annoying people that is great at both artistic (modelling & texturing) work and coding...he's been leading up the design and pathfinding elements of what we're working on, it's rumoured that Chris works a standard 32hr day and as an Australian when he's not teasing us Brits about the weather he's off to the beach.

Daniel Delp - A recent addition to the Z-Day team Dan has jumped straight into things porting over Z-Day to run on a Mac (mostly complete unfortunately we can't get DXTC textures working on a mac just yet), its great to have Dan as part of the team some of you may have seen his blogs on some A.I. work he'd being doing on TGE and we're pleased to say that he's ported over the automatic Mesh Generation to TGEA. When Dan's not coding on Z-Day he's off out Snowboarding on the powered white stuff.

Myself - Apart from the fact that I get to write these blogs and take all the glory, I've been working on getting an Editor for the NavMesh working within TGEA and when I'm not focused on that then I'm off Mountain Biking or topping up my alcohol levels.

So what have a Beach Bum, a Snowboarder and an Alcoholic achieved so far since my last blog a month ago, well enough of the words here's a video to watch of an early prototype of the editor


(excuse the numbers of "errms" and "and again" for some reason I couldn't stop saying them!!)

We'd be really interested to hear from anyone that has any thoughts, comments or suggestions or even if you'd like contribute and work with us so please get in touch.

Hopefully we'll have more to share with everyone soon until then thanks for reading.