Making Heat Seeking bullets

Hey,

I am playing around with a game program but I ran into a problem I am having a hard time solving. I have everything in the game broken down into classes that handle themselves at the moment

Game Class (handles all functions pertaining to the game)
- Ship Class (handles all funcations and data for the player's ship)
-- Bullet Class (handles all the bullets shot by the player)
-- Shape Class (keeps data associated with the shape and location)
- Enemy Class (handles all functions associated with enemy behavior)
-- Bullet Class (handles the bullets that this enemy has fired)
-- Shape Class (stores data associated with the shape and location)
- Upgrades Class (drops after a kill and carries an upgrade quality)

The game checks collosions through booleans of the class enemy and ship using a point to bounding box collision detection aka

Code:

---

if(ship.Collide(pointX, pointY, pointZ))
  ship.Kill();

---

Once that was working well together and I could fly around and shoot the enemies I started to add my upgrades class. When I started to program a second behavior for the class bullet I ran into some problems. I am trying to program a heat seeking bullet which basicly has to find an enemy on the screen and head for its position. I am having problems creating a solution since the Bullet of the ship handles itself and basicly has to reach out of itself and the ship class then into the enemy class to the shape class to find a location of an enemy. Since there are many enemies on the screen at once I am having trouble doing a few things.

1) knowing when the bullets current target is dead.
2) knowing where the current target moved this round
3) Basicly keeping track to the current target out of a possibility of 20-30 enemies on the screen and with up to twenty heat seeking bullets on the screen.

I am not having any problems with the code itself so I didn't post it. Any suggestions would be greatly appreciated maybe its a bad idea to let each class handle its own physics?

Well I had an idea. The Game checks collisions between the ship and the enemies every turn and their bullets as well. To do this I was passing the coordinate of every enemy one at a time and returning true or false based off it's center point. I decided i could use this moment when the coordinates are passed from the main game to pass the coordinates to the heat seeking bullets as well. Once a bullet has a target it won't be set again until the beginning of the next turn. So each bullet will always be passed the coordinates of a living target and then once it moves it forgets about its target until next turn. This does not seem like the greatest solution but it seems to work (a little to well I'm going to have to dumb down the following logic so it occasionally misses). Of course everyone is still welcome to offer solutions I like to be open minded if a better one comes along ;o).

Thanks for your time.

Quote:

---

1) knowing when the bullets current target is dead.

---

Use the observer / listener pattern. The bullet will tell its listeners when it is dead and then those listeners can respond appropriately. You can also do this for damaging objects. The bullet would tell the object 'hey I did X amount of damage to you'.

Quote:

---

2) knowing where the current target moved this round

---

This can be handled via an object manager and a target ID of some type. When you fire the bullet call the manager to get the object. This should be a ref counted object or a shared_ptr. It must have some type of ref count system on it b/c another object could destroy the target object which means your bullet would then de-ref a null pointer and bad things would happen. Alternatively you could grab the object from the manager at run-time but the additional overhead could cause problems. Once you have access to the object you can query the object for it's position. Alternatively you could simply query the object manager for the object's position and pass in the ID of the target be it a string or a numeric value. Search time is critical for this operation b/c you will be performing this many times a frame for many objects. A std::map has an O(log n) lookup time and a list has linear search time. The best option would be if the ID of the object was the hash value of the object and that would index into a hash table. Hash table's have O(1) lookup time or constant time. The main issue with hash tables is the algorithm used to compute the hash. If it does not have good distribution and you have a lot of objects you can end up wasting a lot of memory and/or wasting time finding a place to put the object in the hash table. You can Google for the Dan Bernstein hash algorithm (DJB 2). I have had good success with it and it produces a good distribution in small arrays. You can use std::vector IF you never remove (read: erase()) anything from the vector. If the ID is the index of the item in the vector and you remove an item in the vector you could have problems. Vector's invalidate all iterators past the point of removal and thus all the indices would change and your system would fall apart.

Quote:

---

3) Basicly keeping track to the current target out of a possibility of 20-30 enemies on the screen and with up to twenty heat seeking bullets on the screen.

---

• The first test would be to check the distance between the objects. If the square of the distance is greater than any of the two objects can move in the next frame then those two objects cannot collide in the next frame else put the object in a 'potential' list.
• Second, perform a dot product between the bullet's velocity vector and the velocity vector of the object you are testing against and only do this for the objects in the 'potential' list. If the dot product indicates the vectors are facing away from each other then they can never collide in the next frame and the object should be removed from the 'potential list'.
• Lastly, eliminate repetitive tests. If you have tested if object A collided with object B then there is no need to test if object B collided with object A.

A spatial partitioning system or tree like a binary space partition tree or a quad-tree allows you to narrow down the possible collision candidates very quickly. The main problem is that usually moving objects are not part of the tree b/c it is non-trivial to constantly re-arrange objects so they are in the right nodes of the tree.