Disclaimer: I clearly have no idea what I'm doing. :) I've written a rudimentary vector graphics Asteroids clone. The collision detection works well and I've polished it to make the physics reasonable. I'd like to start adding artificial intelligence, but I think this is going to be tricky. I'm not at all looking for hand holding, but some suggestions would help. I'd like ships to be able to navigate a moving asteroid field and make a reasonable attempt at killing the player. Some wrinkles: /* Ships rotate at a fixed and finite rate. Ships are equipped with guns that can, if brought to bear, destroy asteroids. */ I've been coding A* demos lately, so I am getting very familiar with this sort of pathfinding, but this kind of changing environment is scary to deal with. The plan so far: Start with an empty field. Get the ship to steer itself towards a point in space with total disregard for its surroundings. Add stationary rocks to fly around. Only look at their bounding circles. Ignore the actual vectors (mesh? Is that what these are really called?) Add moving rocks. To handle this, do I need to calculate the positions of each rock for each step of the path I've found? (Ala: For move t, the rocks are all located at x + vt) I'm worried that this sort of calculation will kill the framerate. Add the ability to destroy a rock, rather than fly around it. And so on. I'm wary, since I'm told A* is a CPU hog and I'd like to eventually have a large group of AI ships at once. A* also seems like it's better when you're not pathing on a pixel to pixel basis. I'll take any comments you guys have to offer. This is intimidating, but I like a challenge and I'm willing to wrestle.

Well, there are at least 2 approaches to this.

1) Actively to path planning like A*, except we can probably use something simpler.
2) Perform passive navigation with the use of a potential field. Have craft be attracted towards the target and repelled from the obstacles with force based on distance. (I'm a big potential field buff right now. :P)

For the first approach, let's tackle stationary objects, which you mentioned will use bounding spheres. So we can do the following:

1. Assume your current position is A and the target is B, and you have a number of obstacles T1 to Tn. Draw a line from A to B.
2. Check how many objects intersect with this line. This means that the shortest distance from a object's center to the line is smaller than the object's bounding sphere/circle's radius.
3. Starting from the closest obstacle to A, assuming T1, draw a line from the center of the T1 to the line segment AB such that the line from T1 is perpendicular to AB. Then you can find a point T1' such that T1' is on this perpendicular line and is at least a certain distance from the center of T1. Your path now will then become A -> T1' -> B. Then repeat step 2 and 3 with line from T1' to B. Until the path intersects no more obstacles.

This is a fairly straight forward deterministic algebraic method of determining shortest path. In the best case scenario, you won't have to perform step 3. However, this does not account for the fact that if you have multiple entities moving towards a target, whether they will bump into each other. The nice thing about this method, in a static environment is that you only have to do it once. In a dynamic environment, you can simply repeat this every cycle....well, sort of....

In a dynamic environment, you can take a pure vector approach. The ship will always move towards the target, and since you know all the obstacles' bearings and speeds and the ship's bearing and speed, you can calculate when and where the onjects will collide. Thus, you gradually adjust the ships bearing to avoid collisions, starting from the one in the nearest future. Kind of a greedy approach. This is when your blasters kick in, because there will be situation where avoiding one object will force you into another, which is when you decide which one to destroy based on some criterion.

Hopefully, this has been helpful. These two approaches are purely mathematical, and you should be able to find the various formulas and equations for line intersection, distance from point to line, etc. online through a simple google search.

Have a look at Steering for obstacle avoidance and pursue from here...
http://www.red3d.com/cwr/steer/
AI Game Programming by Example by Mat Buckland (superb book but I don't want to say too much as he's a regular here :) applies thes techniques to Asteroids.

Thanks, guys. I'm looking into all of this, now.

And Mat Buckland's book is in the mail. I swear this website is going to bankrupt me yet. :)

Quote: AI Game Programming by Example by Mat Buckland (superb book but I don't want to say too much as he's a regular here :) applies thes techniques to Asteroids.

No I don't. I cover steering behaviors for velocity alligned vehicles but they'll need modifying for a vehicle with different properties, such as a spaceship.

Brian Schwab's book however does use Asteroids as a test bed to demonstrate various techniques. You can find the table of contents here:

http://www.charlesriver.com/Books/BookDetail.aspx?productID=86952

Hopefully that will be more applicable but I couldn't say for sure since I haven't read it.

I'm working on a space game and my AI works as follows:

Each bot has an order queue. Typically it consists of move orders and attack orders. When the bot decides to do something else via its think function, it pushs another order into the queue (either on the top or the back depending on priority). This works well because it means the bots don't fly around like scattter-brained insects - they remember their goals and can achieve intermediate tasks, such as dodging an asteroid. To dodge an asteroid, assuming they've seen it coming and think they might hit it, they just push a move order to avoid the obstacle onto the top of their queue and begin executing it immediately.

Quote: Original post by fup

Quote: AI Game Programming by Example by Mat Buckland (superb book but I don't want to say too much as he's a regular here :) applies thes techniques to Asteroids.

No I don't. I cover steering behaviors for velocity alligned vehicles but they'll need modifying for a vehicle with different properties, such as a spaceship.

Brian Schwab's book however does use Asteroids as a test bed to demonstrate various techniques. You can find the table of contents here:

http://www.charlesriver.com/Books/BookDetail.aspx?productID=86952

Hopefully that will be more applicable but I couldn't say for sure since I haven't read it.

Oops. I got my books mixed up.

Quote: No I don't. I cover steering behaviors for velocity alligned vehicles but they'll need modifying for a vehicle with different properties, such as a spaceship.

Brian Schwab's book however does use Asteroids as a test bed to demonstrate various techniques.

That's alright. I'd prefer it not be spelled out for me. You never learn anything unless you do it yourself. Taking a system and adapting it to my problem will be a good thing and I'll learn more than if I can nearly do a cut and paste job. (Bad. Very bad.)

Besides, Mat. Your book's reviews have excited me. This could be the perfect place to start as long as I don't choke and die on the language. I code in C+, not C++. ;) Me thinks it's time to learn all the C++ stuff I neglected.