Steering behavior using nodes

Question

I've started rewriting some of my code (npcs, navigation and such) and I need some help with my new navigation system.

Basically the way it works is: the game generates a random dungeon. For example:

With the black representing walls. After the map generates, it goes through the map and finds all the outward corners and places a node on them. The end result is something like this:

When it finishes that, it goes through the nodes and connects the nodes that have a clear line of sight to each other. Like this:

So it works like this: enemies use the nodes to navigate their way around the map. When they want to do things like wander, they choose a random node (one they can see) and go to it. Every node has a list of the nodes it's connected to, so from there they choose another node and head towards that one. The enemies keep a list of the previous three node locations, so they don't wander in circles (if there's only one node connected to the current node, they head back.)

The whole thing is based on line of sight, basically. However, there are some limitations, namely: movement. Creatures in my game have tile based movement and can only move in cardinal directions. I also need enemies to try to avoid each other and change direction based on stimuli (such as a change in "bravery" level, causing them to rush the player, retreat or stand their ground.)

Given all that, how can I calculate the ai's next move?

Edit: To be more clear: I want to know how I can have the ai calculate the direction it will move in next. So I need to know what kind of formula the ai needs to determine which tile is the best to get it to it's destination. Something that takes into account the target, other enemies (if there are any) and the bravery level of the ai (which will change player interactions and make them group with other enemies when their bravery is low and they're alone.)

Edit 2: Okay, let me change the question and add some information. My game is turn based, so I need to make steering behaviors work in a system where it can only move once per update (one tile length) and can only move up, down, left and right. I'm not sure how to do this, can you help me?

Answer 1

Often times your ai is the result of several components working together, not just one master ai piece of code. The solution you are after can be achieved in this manner. As already mentioned you can give your creatures states so that they know what their current task is, roaming, rushing, standing ground, retreating, etc. Next you can add pathfinding. This will tell the creature how to get to where it needs to go, regardless if it is chasing a player or roaming. Finally, once the creatures know what they are doing and they know how to get there you can implement object avoidance, so that the creatures will dynamically adjust their paths as they travel to avoid one another.

EDIT: This solution is relevant whether your game is real time or turn based. If a creature is: Roaming state - it will target and seek the nearest empty node x tiles away. If the player comes withing y tiles from the creature and the creatures bravery is high enough then the creature will enter Attack state. If the bravery is not high enough then the creature will switch to Congregate state.

Attack state - creature targets and engages player. If bravery drops too low creature state will change to Retreat.

Congregate state - creature targets and seeks nearest enemy. If creature is within 2 tiles from target state will change to Pack state.

Pack state - closely follows lead creature and gains a bravery boost. If lead creature attacks, this creature will switch to Attack state, regardless of its bravery level. If the "pack" does not engage the player within 10 turns then the creature will "forget" threat and switch to Roaming and its bravery boost will fade.

Retreat state - each turn creature targets the nearest node to the creature that is the farthest from the player. Once the creature is 10 tiles away from player then it state will switch to Roaming. If the creature is "cornered" in Retreat state, it will switch to Attack state regardless of its bravery level.

Once the creature has a target, you can calculate a path, tile by tile that the creature needs to take to reach that target. Each turn the creature takes the next step to reach the target.

To avoid collisions with other creatures during movement you can check "a move ahead" and see if there will be a collision. If you find a collision, you can choose to let it be first come first serve. So, first creature on the list gets to move to that tile on the next turn. The other creature can choose an alternate route around that tile, or choose to wait and not move for that turn, hoping that next turn that tile will be vacant.

Answer 2

You should be able to accomplish this with "creature" states.

1. Roaming
2. Attacking
3. Retreating
4. Defending

On each "turn" you evaluate what the state of each creature should be and handle their movement accordingly. For example, if the current state is "Roaming" and the engine evaluates that an enemy is now in front, the state is changed to "Attacking" and a new path is generated. If the state is the same as before, keep the same path.

You can add as many states as you need and evaluate the "what to do" on the code of each state.

Answer 3

Okay, through some trial and error, I've come up with a system that works. The ai chooses a target node, then uses this method:

public Point Next()
    {
        Point r = new Point(0,0);
        float weight = float.MaxValue;
        Point o = new Point(loc.X + 1, loc.Y);
        float heuristic = Heuristic(targetNode.Position, o);
        float distance = DistanceTo(targetNode.Position, o);

        float op = heuristic + distance;
        if (heuristic + distance < weight && CheckTile(o))
        {
            weight = op;
            r = new Point(1, 0);
        }

        o = new Point(loc.X - 1, loc.Y);
        heuristic = Heuristic(targetNode.Position, o);
        distance = DistanceTo(targetNode.Position, o);
        op = heuristic + distance;
        if (heuristic + distance < weight && CheckTile(o))
        {
            weight = op;
            r = new Point(-1, 0);
        }

        o = new Point(loc.X, loc.Y + 1);
        heuristic = Heuristic(targetNode.Position, o);
        distance = DistanceTo(targetNode.Position, o);
        op = heuristic + distance;
        if (heuristic + distance < weight && CheckTile(o))
        {
            weight = op;
            r = new Point(0, 1);
        }

        o = new Point(loc.X, loc.Y - 1);
        heuristic = Heuristic(targetNode.Position, o);
        distance = DistanceTo(targetNode.Position, o);
        op = heuristic + distance;
        if (heuristic + distance < weight && CheckTile(o))
        {
            weight = op;
            r = new Point(0, -1);
        }

        return r;
    }

To determine which direction will bring it closer to the target. It then adds "r" to it's location, moving it one tile in the right direction. Heuristic is the Manhattan distance and DistanceTo is the Euclidean distance. CheckTile just checks if the tile is a floor tile or not. When it reaches the target it chooses another target and the process continues.

Right now I have a problem where the ai wanders in circles while going from node to node so feel free to give me advice on that, but I've solved the problem.