Tuesday, May 25, 2004

[Ant Attack] Smelly Ants!

This is more for me than you but anyway.

I'm been trying to figure out how to make the ants 'home in' on the player, while still playing fair, i.e. not being able to see through walls or have knowledge of the player that they shouldn't really have.

In the original game they just headed towards you, so if you were to the south and a little to the west of an ant, it'd just move down south until it was level with you and then turn west. Even if you were on the other side of the outside wall.

Now I'm not strong when it comes to AI so I've been left with 4 choices (probably far more, but these will do).

1. Head directly N/S,E/W toward the player
Basically just that, each ant figures out where the player is in relation to them and heads off in that direction. Along the axis with the greatest distance. i.e. if the player is 12 tiles south and 6 tiles west, we'll head south first and then zig-zag in when we get to 6 tiles south and 6 west.
Pros: Fastest to calculate and in keeping with the original game.
Cons: Unrealistic and unfair. Can get trapped when there's an easy and obvious way round an obstacle.

2. Line of sight (LOS)
We check to see if the ant has line of site to the player and if so head directly towards them.
Pros: Still pretty fast, we only have one line of sight test per ant. Difficult to get trapped, as being trapped normally means there's no LOS.
Cons: Feels like it'll be too direct, very easy to hide from. As soon as LOS is lost you've got to figure out what to do next. Maybe keep going until you reach the spot where you last spotted the player and then go into some form of searching pattern?

3. A* Path finding algorithm
All about that here. It'd work because our map is tile based and the "cost" for moving is either free (in open space) or blocked (in walls). However it doesn't really fit our needs, as you're either always trying to find the best path from the ant to the player, in which case you're cheating and assuming knowledge of the player loaction, so this only solves the getting stuck issue of #1. Or you don't assume knowledge of the player, in which case you may as well use LOS #2 above.
Pros: Will be able to track down the player without getting stuck.
Cons: Will have to impliment A* path finding algorithm and I'm too lazy.

4. Using Ant Pheromones

1024x768 119kb gif

Now I'm not sure what the technical game programming term is for this but this is the option I'm hoping to get working. I'm thinking about using the principle of smells. The player is smelly, as they walk around every second (or fraction of) they drop a scent marker, shown as a green cube in the screen shot above. Over time the scent markers fade until they're gone.

Every few game cycles the ant does a LOS test on each scent dropped figuring out which is the strongest one they can "see", the player themselves being the strongest. If the ant can see at least one marker they then drop their own scent at about 80% of the strength of the strongest one they can see.

So if a player has run through an area fairly recently an ant will be able to "smell" than and start following the scent trail, dropping their own scent (shown in red) to alert other ants. In theory a player may be in the top left hand corner and visible to an ant in the bottom left corner, who'll drop a scent, that in turn is visible to an ant in the bottom right hand corner. Thus the farthest away ant can still start to track the player, even though they cannot see them.

This strikes me as quite Ant like, so it's the one I'll experiment with for a while.

Pros: Good and tracking down a player once they've moved out of site.
Cons: Gunna be computationally heavy.

/goes off to do some coding.


Post a Comment

<< Home