6
\$\begingroup\$

We need to make a zombie videogame for a semester project and I was wondering about what are considered nice algorithms/techniques for implementing zombie AI that don't take too long to implement.

The project is a videogame product, involving other stuff as physics and multiplayer, so we have limited time, so what I'm specifically looking for is:

  • A quick & dirty way to implement zombie AI (I'm thinking on neural networks or perhaps even fuzzy logic)
  • Common ways of implementing and optimizing zombie AI
  • The ideal way of implementing zombie AI (I imagine it would involve pathfinding, or even swarm intelligence?)
  • General advice on zombie AI

Considering that the quick & dirty implementation would perhaps be a place-holder for another and better algorithm/technique.

Thanks in advance.

\$\endgroup\$
6
  • 5
    \$\begingroup\$ In my experience, pathfinding and swarm AI are far, far easier to properly implement than neural networks or fuzzy logic. Both pathfinding and swarm have simple, established algorithms: neural nets are messy and hard to tune. \$\endgroup\$ Commented Jan 22, 2011 at 14:15
  • 4
    \$\begingroup\$ You've got a little bit of a contradiction there - quick and dirty + neural nets? ;-) \$\endgroup\$ Commented Jan 22, 2011 at 20:20
  • \$\begingroup\$ @The Communist Duck Yeah, I think I have a case of the its-the-only-thing-I-learned-so-i-want-it-to-use-everywhere-itis. I made a very simple and reusable neural net some time ago (bitbucket.org/dukeofgaming/chibi-nn), so I was thinking that using it (or parting from there enhancing it) would be quick and dirty... mind modelling the actual game for training cases. \$\endgroup\$ Commented Jan 22, 2011 at 21:00
  • 2
    \$\begingroup\$ I don't think it needs the Homework tag, as even though this is homework, the question and answer would be the same regardless of the source. Do other people have to tag their questions in regards to their current occupation on the project? \$\endgroup\$ Commented Jan 22, 2011 at 21:49
  • \$\begingroup\$ @Hobo: on SO if it's homework (and doesn't get closed) it is tagged homework. This clearly should not be closed, but I think it deserves the tag anyway. \$\endgroup\$ Commented Jan 23, 2011 at 1:46

5 Answers 5

Reset to default
19
\$\begingroup\$

First of all, DON'T use neural nets. They're simply not applicable to this (unless you have some real life zombies where you can get some training data :) )

Just to clarify neural nets and fuzzy logic are not quick and dirty ways of implementing AI. They're fairly in depth (neural nets, more so than fuzzy logic).

Secondly, unless your zombies are clever, they might not need pathfinding at all. Sure it's useful to avoid obstacles, but there are simpler ways of achieving that.

If your semester is around 10 weeks long (approx) you're going to be getting stuck on more important things than the AI (that's not a criticism on your coding skills, it's just usually how it happens unless your design stage is almost perfect). Therefore simplicity is key here.

The simplest thing to do is to combine a number of steering behaviours. Simple behaviours merged together can create intelligent looking behaviour (this is called emergent behaviour if you're interested, and is what swarm intelligence and flocking is based on).

The behaviours I'd suggest you use are:

  • Seek
  • Wander
  • ObstacleAvoidance
  • WallAvoidance
  • Cohesion
  • Alignment
  • Separation

These behaviours are collectively known as steering behaviours and this link will show you exactly how they work (albeit without source code): Steering Behaviours

Read Programming Game AI by Example, as those behaviours are very well documented (or you could just find the source code somewhere).

Cohesion, Alignment and Separation are behaviours that work together to create the "flocking" effect. Cohesion makes sure that each zombie moves towards the average position of the flock. Alignment makes sure the zombie aligns with the average orientation of the flock. And finally Separation just maintains a distance from the zombie's neighbours.

You can optimize this by having each zombie have a "neighbourhood" region, so the zombie will only check it's neighbours for the appropriate values.

If you have a fairly small game world, you can use a grid based partitioning system to optimize further as it's relatively simple to code and won't take up much memory since the world is small. If it's larger, consider using a quad-(oct-)tree. If it's an indoor level, consider using BSP.

But to sum up, keep it as simple as you can. Simple behaviours are easier to debug and when combined they look very impressive. And don't use neural nets, whatever you do.

P.S. If you're allowed to use external libraries, try and use OpenSteer :)

Hope that helps.

Ray

\$\endgroup\$
3
  • \$\begingroup\$ +1 For the comprehensive explanations and advices. I have already taken a course on AI, however the farthest we made it was neural nets. I think I might have accidentally answered myself about swarm intelligence being useful, but after reading your answer now I know its not about one simple algorithm, but many and for each case, I think the book (which I do remember having seen) will be quite the resource. Thanks. BTW, what is BSP?. \$\endgroup\$ Commented Jan 22, 2011 at 17:17
  • \$\begingroup\$ @dukeofgaming BSP stands for Binary Space Partitioning. It's a method that constructs a binary tree out of your level by splitting the level up into sections. It uses the walls in the level to construct subsections (hence why it's suited for indoor levels). This, like the octtree or the quadtree makes it easier to detect collisions, draw certain objects, etc. It's just an optimization. \$\endgroup\$ Commented Jan 22, 2011 at 18:12
  • \$\begingroup\$ Furthermore, all of those algorithms are collectively known as steering behaviours. Actually I'll edit my answer to add that and another link which may be of use to you :) \$\endgroup\$ Commented Jan 22, 2011 at 18:27
9
\$\begingroup\$

You may be over-engineering it, a basic implementation is just a state machine with a state "Shamble" which will cause the zombie to move around a bit (checking it won't hit walls and such perhaps, or stay out of the light etc, it can be expanded upon) and a "Follow" which will cause the zombie to move toward a player (maybe using path finding like A*) and attack him/her if the zombie gets to close.

This will be fairly "realistic" (as far as zombies go) because players usually don't look at enemies for a long time (they usually run from them/attack them).

\$\endgroup\$
2
  • \$\begingroup\$ +1 - Interesting thing about the shamble, sounds like a pretty nice technique to consider (because of the realism factor). Thing is, AI is a requirement for this project. \$\endgroup\$ Commented Jan 22, 2011 at 14:48
  • 1
    \$\begingroup\$ @dukeofgaming AI != neural nets/fuzzy logic/genetic algorithms. Any solution you use to give your zombies an element of "intelligence" is AI, be that steering behaviours, FSMs, pathfinding, fuzzy logic, etc. Just because universities like to teach about neural networks and genetic algorithms, does NOT mean that you can automatically equate them with AI. AI is a much, much broader topic. \$\endgroup\$ Commented Jan 22, 2011 at 16:01
4
\$\begingroup\$

I'm taking all my zombie-related facts from the Zombie Survival Handbook. Which, on a tangent, is a very entertaining read.

A stereotypical zombie would be very stupid - so it wouldn't need AI for things like:

  • Opening doors, though it could probably break them (if you choose to go for a destructible route)
  • Any kind of tactics
  • Climbing, or the Z-axis at all.
  • Swarming.

Instead, you would want zombies to do things like:

  • Walk around aimlessly until they get a target
  • Chase the target until it disappears
  • Follow the trail of the lost target for a short time
  • Repeat

I'm pretty sure a simple state machine would be useful - either WANDER, FOLLOW, OR LOST.

As for the target searching, each zombie could have a field-of-vision check. If target can be seen, change state and set the direction to go.
Something interesting may be to have different target checks. Not just if a zombie sees you, but perhaps if you wandered an area you could leave a 'scent trail', putting a zombie into the LOST state? Or if you fired a large weapon, the zombie would be attracted to your position in the LOST state? This second one could have an area-of-effect radius, giving a swarm-type pattern since all the zombies will end up in one area, and then move as one.

As for implementing, it wouldn't be much more than having a check to see if the player has been seen, then some very dirty pathfinding - quick and dirty rather than something like A* - a zombie isn't going to go the optimal route - and a state machine. Just make sure that your random walk does have some form of obstacle avoiding - I really hate it when enemies just run into buildings for ages. ;-)

\$\endgroup\$
3
\$\begingroup\$

I think whats complicating your project is the fact you are trying to make Artificially Intelligent Zombies.

As another poster stated, I think you over engineering your project. Think about a couple "states" you want your zombies to have.

1) Searching/moving aimlessly

2) Pursuit/Chase

These come to mind, you might consider more for uniqueness.

The nice thing is zombies don't really act intelligently, use this to your advantage!

\$\endgroup\$
4
  • 3
    \$\begingroup\$ So... eating brains does not make them smarter? \$\endgroup\$ Commented Jan 22, 2011 at 20:03
  • \$\begingroup\$ @Lo'oris I actually made that joke to my teammates. Then I told them what we actually needed was artificial stupidity. \$\endgroup\$ Commented Jan 22, 2011 at 20:53
  • \$\begingroup\$ Well, as I said, AI (in some form that enhances gameplay) is a requirement... doesn't really mean they are intelligent enemies, only that they can adapt to the environment in some form that represents a challenge to the player. \$\endgroup\$ Commented Jan 22, 2011 at 20:55
  • 1
    \$\begingroup\$ Considering adding more than just these two states. These are the most basic not including evade (Zombies don't really evade). Think of additional states that you want your Zombies to have. Maybe a Frenzy state, maybe they reanimate after a they player has walked another direction? This is the endless fun with game design =) \$\endgroup\$ Commented Jan 22, 2011 at 21:18
1
\$\begingroup\$

You're going about it all wrong! Zombies are stupid!

if CanSeeCharacter()
    IterateLegalMoves()
    Pick the move that ends up as close to the character as possible (by crow only)
else if Dice < 5%
    PickRandomBearing()
else if Position + Speed * CurrentBearing is legal
    Move()
else
    PickRandomBearing()

No pathfinding, let them get stuck. That's how zombies should behave. If there's enough of them the crowd will fill in any dead ends and force the additional zombies to go around so they can actually get to the character.

\$\endgroup\$
4
  • \$\begingroup\$ I guess you mean crawl? Unless these zombies are somehow bird-propelled, of course. \$\endgroup\$ Commented Jan 23, 2011 at 1:48
  • 2
    \$\begingroup\$ Zombies are stupid, but hungry still. I can't imagine a game like L4D being fun with totally stupid idiotic zombies that can't find you... I mean, all you would need to survive would be a broom to push them away. \$\endgroup\$ Commented Jan 23, 2011 at 4:22
  • \$\begingroup\$ @Lo'oris: I mean that it should evaluate the distance from squares by the straight-line distance, not the minimum path. \$\endgroup\$ Commented Jan 23, 2011 at 5:19
  • 1
    \$\begingroup\$ @Dukeofgaming: How do you get that? The broom isn't going to push them and if you're that close they'll be trying to attack you. Give them a long sense range if you want but zombies are not intelligent, don't give them intelligence in hunting. \$\endgroup\$ Commented Jan 23, 2011 at 5:22

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.