Platformer Enemy AI

Question

I'm currently developing a platformer shooter. The game is multiplayer and while my net code could use some real work I have put that off for the time, so currently I'm trying to implement the AI.

The game is pretty simple; Players run around on a map filled with a X amount of zombies that try to eat their brains, classic and overused I know. Weapons spawn at random intervals around the map. The problem is that the zombies, when they find their pray the have to follow it for some while.. And here is the problem, running the AI navcode seems to take for ever.

So here is the ideas I have come up with so far

1. Have the AI update at different intervals with a maximum of Y ms with no updates.

2. Have the zombies assigned to groups of zombies. One is appointed the leader of the group who finds the way to the player - the rest just follows the leader. If the leader dies another one of the zombies in the group is appointed president of the zombie swarm. If there is less than five zombies in a group they try to meet up with other zombies.(Aka they are assigned to a different group and therefor a new leader)

3. Multi-threading option one or two?

For navigation I have some kinda navmesh(since the game is not tile-based) that tells the zombies where they can walk etc. If anyone else got some ideas on how to do navigation I would love some input.

For LoS(zombie -> player) I have split the map into grids. If the players grid is connected to the zombies grid(if I go with option two I would only need to check if leader zombies grid is connected to player, aka less checks) - if they are connected and there is more than 250ms since last check do a raytrace..

This is my first time programming AI so input on any field is appreciated.

Answer 1

Perhaps you could try an algorithm that does not update all its data in one step, but can do partial improvements (in smaller time steps). Even if the calculated path is not always the shortest one -- you have to check this: maybe the difference is so small the player will not really notice (and also zombies are supposed to be kind of stupid).

Here is a suggestion of an algorithm; I did not test it.

First, split the map into segments. For each segment remember all neighbor segments, and a distance towards each of them. (For example the distance from center of segment A to center of segment B.)

Each segment will remember its "target" segment, which is one of the neighbor segments where the zombies are supposed to go from here. (The idea is that when the player is in this segment, or perhaps in one of the neighbor segments, zombies will ignore this value and navigate per pixel. But if the player is further away, zombies will navigate using the segment-to-segment map.) You can initialize these values randomly; just choose a random neighbor as a "target".

Now you can calculate a segment-distance between a segment and a player. If the player is in the segment, the distance is zero; otherwise it is a distance from this segment to its target segment, plus distance from target segment to player. (If you detect a loop on the path, the distance is infinite.)

When player moves from segment A to segment B, you must set A's "target" to B. This part is necessary to ensure that every segment ever visited by a player will contain a path (not necessarily the shortest path) towards the player. All other improvements are optional.

An optional improvement for a segment X is done by choosing all its neighbors, for each of them calculating the distance to player plus distance between these two segments, and choosing the one with the smallest result as X's "target". This operation can only improve the segment-to-segment map, it never makes it worse. (The quality of the map degrades automatically by the player moving. It changes from "shortest path to player" to "follow the player's path".)

You can repair the whole map in a linear time. First, improve the neighbor segments near the player's segment. Then, recursively improve the neighbors of those neighbors which changed, starting with the ones with shorter distances to player. If you have enough time to fix the whole map, that's great. But if you don't... then you need some heuristic.

One idea is that you only fix 10 or 100 nearest segments in one step. If in the next step the player stays in the same segment, you continue fixing next 10 or 100 segments. But if the player moves to another segment, you start again from the beginning. If the player stays in one segment long enough, the whole map will be fixed.

Another idea is that you can fix all the map in one slow wave. Start the wave from the player, fix the nearest 10 or 100 segments, and in another step fix additional 10 or 100 segments (avoiding those which were already fixed in this wave), until the whole map is fixed. The problem is that the later fixes will direct the zombies towards the position where the player was at the beginning of the wave.

Or you can combine these two ideas, and in each step fix the nearest 10 or 100 segments, and the next 10 or 100 segments of the slow wave.

Answer 2

I hope I understood the question correctly, you are asking how to help the zombies navigate to the player? Basically in your game all the zombies do, is find a path to the current location of the closest player?

I would recommend running a 'Probabilistic roadmap' beforehand (not during game) and saving the resulting graph data to a file for that map. Than navigating the graph using a BFS or a Dijkstra algorithm for each group of zombies to the node on the tree that is closest to the player. You can find the node quickly by dividing the map into sectors (like a spacey grid) and only checking for nodes in the four sectors closest to the player position.

To speed things up I would recommend breaking the Dijkstra process into chunks and running only a little of it each frame. You can then repeat the process once it is finished if the player moves to the proximity of a different node.

If you would like more info, please comment and I will gladly elaborate.