Jump to content
  • Advertisement
Sign in to follow this  
SteveHatcher

First game AI pathfinding

This topic is 1154 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello,

 

I am a relatively new programmer building a spaceship game and I'm at the point where I would like to add in some (basic) interesting A.I.

 

Right now there are two AI 'options'. One of them is just moving directly towards the player. The other is shooting at the player. I want to make the movement more interesting (right now it is just in a straight line towards the player.)

 

I would also like to take this opportunity to learn pathfinding. My idea is to 'draw' some invisible barriers that the enemy ships cannot pass (walls if this would be a ground based game). The enemies would have to strafe around these barriers to get a clear 'shot' on the player. Of course the barriers are not actually visible in the game world, so I think it would make for a cool effect. Attached is an illustration of the idea.

[attachment=28323:pic1.png]

[attachment=28324:pic2.png]

In pic 2, the red barrier (could be another map layer that is 'collidable') blocks the line of sight from the ship, so it has to scoot around the side to get a clear shot.

 

My questions:

1. What terms should I be looking up / reading that are relevant to this cause?  I have read about A star pathfinding… is that applicable in this situation? Remember I don’t want the ship to literally hug the wall, but a ‘smooth’ strafe around the side of it. (Starcraft 2 style… I wish)

 

2. How does pathfinding and AI interact? Who is the ‘boss’ so to speak. Is it pathfinding that tells AI “go here now, go here now” or is it AI that asks pathfinding “Where do I go, is this clear, can I shoot now?” What is the order in the update loop?

 

3. Is this kind of situation a constant (per update loop) “polling” type situation (like controller input), or an event type situation (like perhaps two objects colliding), or a combination of both.

 

4. I have read that things in game programming should be decoupled as much as possible, is that also relevant in this case?

 

Thanks for all and any assistance.

Share this post


Link to post
Share on other sites
Advertisement

Two basic routes to go about what you want.  One is with pathfinding, either with a grid or a navmesh, A* will probably be what you want, but then look into path smoothing, someone else just recently posted about it, and I posted some links in that thread.

 

The other thing you might want to think about, is steering behavior.  In fact, you may not need any pathfinding if you use steering to make the behavior more interesting than a straight line dive.  For example, you could have a ship that tries to get behind the player, and stay within a certain distance.  If you don't have obstacles, then you could just use steering without any pathfinding or A*.  (Other examples include ships that try to avoid being in the player's fire arc, stay at maximum range, only move in to attack if other friendlies are nearby, etc)  

 

I'm a little leery of invisible barriers for ship navigation as an attempt to make the ships move more naturally, it may just end up looking weirdly artificial.  But it should be easy enough to test with or without pathfinding, you can have steering behaviors to avoid certain areas.

Share this post


Link to post
Share on other sites

i'm only a few builds ahead of you in AI ... to date they have involved environments with obstacles, so AI for the sake of gameplay is sufficient with only a few behaviours because their movement is complex enough.

 

i've also considered, in an venue without obstacles, attackers would simply approach + destroy, which makes for uninteresting encounters, and creating arbitrary "player-unseen" criteria for movement.

 

the solution i last used was to create an "attack pool," of say three opponents... if there are more enemies, they spread out so that the player isn't dealing with a concentration following them around. this worked very well in the simplest form as AI have to avoid steep slopes on a height field, and were usually spread out enough to keep gameplay engaging in the finite playing area.

 

for 3d space without many limitations, devising tactical locations in play may be realistic.. eg. 100 units to one side or another or behind. but i'd guess making the AI more complex would be funnerer... in "real life" an opponent that moves directly to the target better have some kickass attack and defense.. you could try making their piloting worse, or add in some evasive thinking to piloting, eg. weaving back and forth instead of adjusting to center (give the dot product a wider tolerance).. i'm more of a strafer/pass by and fire to one side, so designing AI to do this would be more realistic to me.


another solution would be to make the criteria for "strange movement" temporal or circumstantial... eg. "starts evasive movement after 256 frames because their pilots chicken out or likes to turn left a lot" simply for the reason that checking position against environment is more intensive than checking angle or time or velocity or anything that doesn't have to be calculated.

Share this post


Link to post
Share on other sites

There is a little maths involved in A* and I recommend that if you are new to programming you might want to make sure you understand some other things first such as linear interpolation and vector maths.

 

These are very useful and play a part (a big part) in pathfinding algorithms. 

 

Out of curiosity what programming languages and libraries are you using?

 

If you get stuck you're in the right place to ask!

Share this post


Link to post
Share on other sites

@ferrous Thanks, I would like to code a variety of solutions for learning purposes, and then implement the one I find is the best into my game. I have heard that steering behaviour can sometimes be used instead of pathfinding. I am probably overshooting with ambition here but eventaully when a few enemy ships are around I would like them to also be able to not run into eachother.. but first things first.

 

@xoxos I like the idea of temporal behaviour switching, that would be easy to code and could look quite cool. I guess it could mimic the 'randomness' of humans. E.g. fly towards player for 1-3 seconds, then shift to the left then back off.

 

@braindigitalis Thanks for the input. I am quite confident with maths (use MATLAB a lot for work), so not worried about that aspect of it. I am using C++ with VS2013. I am using the directX tool kit to do my spirte rendering for me, and entityX ECS framework for game objects that have complex behaviours and / or components (such as ships with different guns / effects).

 

Thanks all. I will start with some basic implementations and go from there.

Share this post


Link to post
Share on other sites


. I have heard that steering behaviour can sometimes be used instead of pathfinding. I am probably overshooting with ambition here but eventaully when a few enemy ships are around I would like them to also be able to not run into eachother.. but first things first.

Steering behavior can handle that case as well =)  Pathfinding is more for when a path is needed around multiple objects, or oddly shaped objects.  (Like anything concave)  Many games do a  little of both, with the common case being the pathfinder generating a set of waypoints, and then using steering behavior to travel along them, so I definitely think you're heading down the right track.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!