Sign in to follow this  
brcolow

My Approach - Critique Please

Recommended Posts

I have spent the past few days writing out my approach to AI for my first person shooter. I will summarize my approach below and, after reading it, please tell me any faults or improvments I can make to the approach. Also, at the end I will have a few questions as well. Thanks My Approach: This will be done in C++ (object orientated). First, there will be a "CAIBase" class that handles the following: Pathfinding State Machine Base Members Living Entities Weapon Packs Specific living entities classes will inherit from the CAIBase and will include additional specific things to that entity (such as a catchFly() function for a frog). Pathfinding: I think the best way to get realistic and dynamic results with pathfinding is to use the A* algorithm. There will be a few tweaks though. First, I will not be spliting the terrain into a 2d grid. All terrain should be and is walkable. The only things an entity can not walk on would be objects such as walls, houses, trees, rocks etc. I will store the objects x,y,z values into a lookup table (probably a vector) and when calculating a path from A (x,y,z) to B (x,y,z) it will avoid those points. State Machine: Each living entity that has AI needs to have a currentState. The currentState is one of the available states. A "state" is what the living entity is currently in the process of doing. The state a living entity is currently in is influenced by what is going on around them. For example, if a living entity has a low health, it will be in STATE_NEED_HEALER etc. The states are basically handled by a lage case statment. Each state performs specific things, usually maps are labelled with certain entities relating to the states. For example, for the STATE_NEED_HEALER state, an entity marked ANCHOR_HEALER is on our map near a hospital, bandages, etc. Each living entity does not have access to every state. For example, a frog does not have the STATE_TALK_TO_ALLY, STATE_LOCATE_TEAM_LEADER states, but it may have states that others don't, for example STATE_EAT_FLYS, STATE_RIBBIT_LOUDLY, etc. What states a living entity has is handled in their external LUA script file in the Scripts\AI\Type_of_Entity\Entity_Name where Type_of_Entity is it's type such as "Human", "Animal", "Insect", etc. and Entity_Name is the specific name of the entity such as "Peasent", "Ronin", "Samurai", "Frog", etc. Base Members: These will be the members (variables) that each living entity will have. For example: Health Name Speed etc. Living Entities: This is just the fancy name for our AI creatures. They will be created through their specific class like Cool_Frog = new CAIFrog("base members"); which as mentioned inherits from CAIBase. Living entities will not actually be created in the C++ file, they will be scripted through LUA (and binded with toLua++) Weapon Packs: This is another base member that each living entity will have. For animals, children, peasents etc. they will have the Bare pack which includes nothing. For samurai, they will get the samurai pack which will include, for example, a katana and a healer potion. A ninja will get 10 shuriken and 2 healer potions, etc. My Question(s): 1. Should I be using A* for this? The game will take part almost all outdoors with terrain. If I don't have a 2d grid..can this still work? Or must I use a 2D grid and mabye just mark off the ones you cant walk on if they are on an object? Sounds pretty tough to me. Is there a better way that provides the same results (the game is 3D btw but I should theoritically still be able to use A* since entities will be on the ground and for those that fly (butterflies etc.) will just be flying at a set height. Now, please critique this plan to hell. But if it's good, say so! I just want to make sure before I spend a ton of nights coding this sucker..I am doing it in a very efficient, error-prone and dynamic way. Also, in your suggestions I am using the following languages in my game: Lua C++ XML So keep suggestions to those languages (don't suggest, for example, that I should use Python bindings or something ;)) Thank you for taking the time to read this and I look foward to reading and implementing your ideas/critiques. Don't hesitate to be mean..I can take it :D Thanks, Mike

Share this post


Link to post
Share on other sites
Quote:
1. Should I be using A* for this? The game will take part almost all outdoors with terrain. If I don't have a 2d grid..can this still work?


Doesn't strictly need to be a 2d grid, but has to be quantised.

Your best bet is to split it into an invisible 2d grid which is sufficiently small that no gap is likely to be smaller than 1 grid square. Then create functions which determines the walkability and cost for a given area.

To stop it blowing up if there is no route, you could always put limits on the area which it considers (i.e. do not open any nodes outside a certain distance of the start and end points). This means of course that if a route is very tortous it might not be discovered, but if your map is fairly open it should be ok.

Quote:
Is there a better way that provides the same results (the game is 3D btw but I should theoritically still be able to use A* since entities will be on the ground and for those that fly (butterflies etc.) will just be flying at a set height.

Not really. Some other algorithms are basically the same as A*.

Your walkability function would be different for a flying thing, it could perhaps go over obstacles which would block others. The cost is probably also going to be constant.

I've created an algorithm which uses A* for path finding, then optimises the path based on objects which can move in any direction not just orthogonally.

Mark

Share this post


Link to post
Share on other sites
So far so good, with a few exceptions. :)

1. You could create a class for each weapon (i.e. an interface). If you do this your bot will be able to simply ask the selected weapon class things like 'Am I in range of x,y,z' or 'Is there a letal line of fire'. without the bot itself having to know the details about the weapons attributes.

<code>
public class CPUPlayer
{
WeaponClass gWeaponList[];
.
.
.
}
</code>

2. I would rethink the pathfinding a bit. You could probably precompute certain paths since in most FPS's there are a lot of 'paths' that can only be accessed one way. i.e. Jump on box, jump on railing, enter door. This way your bot only needs to plan paths to these entry points.

The rest of your plan sounds solid enough.

I am curious why you plan on using XML though.

C/C++ has been my language of choice for a long time. I'm stuck to it--but I've been using C# more and more at work. You might want to have a peek at C#; it could save you a lot of time.

Best of luck!
Will

Share this post


Link to post
Share on other sites
Markr, thanks for the information ;)

Thanks very much for the tips Will. I will probably be doing that with the weapons, sounds good to me. Before reading your post I did re-think pathfinding. I will use A* but instead of a grid, I will use plotted waypoints on the map.

I am using XML for parsing map data, dialogue and weapon specifications. It's an easy format to use, and my level editor exports in it, so..:)

I already have started to make a pretty solid base in my game with C++, so I will not be moving to C# but thanks for the suggestion :D

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this