The Daily Click ::. Forums ::. Klik Coding Help ::. Tower defence AI problem
 

Post Reply  Post Oekaki 
 

Posted By Message

Menthalmotion



Registered
  20/01/2007
Points
  42
2nd May, 2007 at 06:32:36 -

I'm creating a TD game with MMF 1.5.
When a enemy comes in range they'll shoot.
But witch enemy should they shoot at?
And if i just decide they'll shoot a random enemy, maybe they'll shoot at somone less important when the castle actually is in great danger.
How should i make the towers AI?

Image Edited by the Author.

 
Timetravel ^^
* Bad english warning

Aptennap



Registered
  23/04/2004
Points
  916
2nd May, 2007 at 09:48:03 -

The enemy that is closest?

 
Oh sweet mary.

axel

Crazy?

Registered
  05/02/2005
Points
  4766

Game of the Week WinnerYou've Been Circy'd!
2nd May, 2007 at 09:53:25 -

You set up a list of enemies, sorted by threat level. Then you make it so that each tower starts checking for enemies from the top of the list. If it finds an enemy in range, it attacks it; if it doesn't, it continues to the next enemy on the list.

Well okay, you don't need to set up an actual list, but you get the idea.

 
n/a

Joe.H

Evil Faker

Registered
  19/08/2002
Points
  3305
2nd May, 2007 at 10:19:14 -

Distance formula:
s = sqrt((X2-X1)² + (Y2-Y1)²)


You know... people should know that, it's REALLY basic pythagoras theorem.

With this you can run a fastloop between enemies (like axel said) to find those that are <= to the maximum distance you want.

 
My signature is never too big!!!

axel

Crazy?

Registered
  05/02/2005
Points
  4766

Game of the Week WinnerYou've Been Circy'd!
2nd May, 2007 at 10:39:49 -

Or maybe do something like this:

Threat = Distance / Enemy HP

And then make the towers prioritize, so that they shoot enemies with higher threat first.

 
n/a

Peblo

Custom ratings must be 50 characters or less

Registered
  05/07/2002
Points
  185

Game of the Week WinnerVIP MemberI'm on a Boat360 OwnerAttention GetterThe Cake is a LieCardboard BoxHero of TimePS3 OwnerIt's-a me, Mario!
I'm a Storm TrooperSonic SpeedStrawberryI like Aliens!Wii OwnerMushroomGhostbuster!
2nd May, 2007 at 13:51:18 -

With a lot of enemies though, that distance formula won't work... unless you want an awful amount of slowdown. I was testing it near 500+ objects though.

 
"Isn't it always amazing how we characterize a person's intelligence by how closely their thinking matches ours?"
~Belgarath

axel

Crazy?

Registered
  05/02/2005
Points
  4766

Game of the Week WinnerYou've Been Circy'd!
2nd May, 2007 at 13:57:12 -

Well, I have yet to see a TD game with 500 enemies on-screen at the same time.

 
n/a

Peblo

Custom ratings must be 50 characters or less

Registered
  05/07/2002
Points
  185

Game of the Week WinnerVIP MemberI'm on a Boat360 OwnerAttention GetterThe Cake is a LieCardboard BoxHero of TimePS3 OwnerIt's-a me, Mario!
I'm a Storm TrooperSonic SpeedStrawberryI like Aliens!Wii OwnerMushroomGhostbuster!
2nd May, 2007 at 14:30:57 -

Eo Neo was meant to be a tower defense game originally, but slowdown issues made me change it slightly.

For the tower AI, you could possibly try this: Have the turret pick the closest enemy in range, and have it 'lock on' to that enemy until the enemy leaves the range of the tower. Then the tower would pick a new target and repeat.

 
"Isn't it always amazing how we characterize a person's intelligence by how closely their thinking matches ours?"
~Belgarath

Sketchy

Cornwall UK

Registered
  06/11/2004
Points
  1970

VIP MemberWeekly Picture Me This Round 43 Winner!Weekly Picture Me This Round 47 WinnerPicture Me This Round 49 Winner!
2nd May, 2007 at 18:04:35 -

I'd say go with the previous suggestions.
Before I go any further, I haven't actually done anything to test this.

Anyways, apparently computers are relatively slow at calculating square-roots, since it's far more complicated than just adding or subtracting or whatever (see http://en.wikipedia.org/wiki/Methods_of_computing_square_roots ). Unless you desperately need to know the distance in actual pixels (which you don't in this instance) you can skip the square-root part altogether, and maybe get less slowdown with lots of active objects. Like I said, never tested it so don't know, but would be interested to find out.

Also, there's an extension called the "value finder" object (I forget the author) which could be very useful in helping you find the closest object with the minimum of hassle and code.

The only other suggestion I'd have, is to build some other factors into the "threat" rating if neccessary. Like maybe an enemy catapult would pose a greater threat than a swordsman at the same range. I don't know how your game works so I can't give a better example, but you get the idea. Obviously that means more calculation and less speed though.




Image Edited by the Author.

 
n/a

axel

Crazy?

Registered
  05/02/2005
Points
  4766

Game of the Week WinnerYou've Been Circy'd!
3rd May, 2007 at 04:04:00 -

The alternative would be to use a circular active object as a detector, but I'm not sure if that'd be faster than calculating the distance directly. You could also avoid square roots by using the slightly less accurate "manhattan method": ΔX + ΔY.

Image Edited by the Author.

 
n/a

Menthalmotion



Registered
  20/01/2007
Points
  42
3rd May, 2007 at 11:07:13 -

Thank you all. Im very greatfull ^^

 
Timetravel ^^
* Bad english warning

Sketchy

Cornwall UK

Registered
  06/11/2004
Points
  1970

VIP MemberWeekly Picture Me This Round 43 Winner!Weekly Picture Me This Round 47 WinnerPicture Me This Round 49 Winner!
3rd May, 2007 at 13:06:37 -

Useful Distance Formulae
------------------------------

X1 = X position of 1st object
Y1 = Y " "
X2 = X position of 2nd object
Y2 = Y " "

Example file here;

http://www.angelfire.com/mech/banshee/Distance.cca (copy & paste to address bar)



Image
The Euclidean distance is the straight-line distance between two points. It is calculated using Pythagorus' theorum, and is sometimes referred to as "Pythagorean distance".

Distance = SQR(((X1 - X2) * (X1 - X2)) + ((Y1 - Y2) * (Y1 - Y2)))



Computers are relatively slow at calculating square-roots. The following approximation avoids doing so, but remains accurate to within 3% of the actual distance.

Distance = ((Max(Abs((X1 - X2)), Abs((Y1 - Y2)))) * 0.941246) + ((Min(Abs((X1 - X2) ), Abs((Y1 - Y2)))) * 0.41)



Image
The Chebyshev (Tchebyshev) distance is similar to the Manhattan distance, but allowing for vertical, horizontal, and diagonal movement. An analogy would be the number of squares a king or queen would have to cover, in order to move between the two points on a chessboard.

Distance = Max(Abs(X1 - X2), Abs(Y1 - Y2))



Image
The Manhattan distance can be thought of as the distance between two squares in a grid, allowing only vertical and horizontal movement. An analogy would be the number of squares a rook would have to cover, in order to move between the two points on a chessboard. This is the least accurate method (furthest from the Euclidean distance).

Distance = Abs(X1 - X2) + Abs(Y1 - Y2)



Image Edited by the Author.

 
n/a

Pixelthief

Dedicated klik scientist

Registered
  02/01/2002
Points
  3419

Game of the Week WinnerWeekly Picture Me This Winner!You've Been Circy'd!VIP MemberI like Aliens!Evil klikerThe SpinsterI donated an open source project
3rd May, 2007 at 21:07:39 -

Although those are invaluable for gridbased games, bear in mind.

 
Gridquest V2.00 is out!!
http://www.create-games.com/download.asp?id=7456

Sketchy

Cornwall UK

Registered
  06/11/2004
Points
  1970

VIP MemberWeekly Picture Me This Round 43 Winner!Weekly Picture Me This Round 47 WinnerPicture Me This Round 49 Winner!
4th May, 2007 at 10:59:40 -

they're not just for grid based games, though the chessboard analogy is a bit confusing (and they are *really* useful for grid movement). you can imagine each screen pixel as a grid square. if you look at the example file, you'll see that the Chebyshev distance is actually a very close approximation in spite of its simplicity (Manhattan less so).

 
n/a

Sketchy

Cornwall UK

Registered
  06/11/2004
Points
  1970

VIP MemberWeekly Picture Me This Round 43 Winner!Weekly Picture Me This Round 47 WinnerPicture Me This Round 49 Winner!
4th May, 2007 at 11:00:26 -

double post

Image Edited by the Author.

 
n/a

Radix

hot for teacher

Registered
  01/10/2003
Points
  3139

Has Donated, Thank You!VIP MemberGOTW WINNER CUP 1!GOTW WINNER CUP 2!GOTW WINNER CUP 3!GOTW WINNER CUP 4!
4th May, 2007 at 21:14:28 -

my rshift has shit under it and i don't feel like using lshift so bear with the lack of capitalisation.

you want the towers to target the frontmost enemy. forget about the 'threat level' stuff. if a lesser threat enemy is in front of a greater one, it'll die first anyway and the turret will move onto the next dude in sequence.

give each enemy an incremental ID when they are created, and have the turret target the one with the lowest ID of those in range.

the reasoning is that unless there's a standard, logical way of allocating targets, your damage will be applied inefficiently. it makes the most sense to target the frontmost first since it'll always be the first one to come within range. this way when the frontmost enemy move out of range the next frontmost is targeted and so on, so the damage is distributed towards the front of the pack, meaning as soon as the front target dies the next target will be in a weakened state, and the turrets further down the line will move on to progressively weakened targets.

 
n/a

Paul_James



Registered
  02/07/2002
Points
  1320
5th May, 2007 at 11:30:19 -

actually sketchy the manhattan is the same as the chebevey in MMF because each pixel counts as one grid square

there are no decimals and to be honest
probably the best and simplest form to find distance than pythagorean theorum


 
Its not enough,I need more
Not enough to satisify
I said I dont want it, I just need it.
To believe, to feel, to know I'm alive.

Knuckle deep beneath the borderlines.
This may hurt a little but its something you'll get used to.
Relax. Slip Away...

Sketchy

Cornwall UK

Registered
  06/11/2004
Points
  1970

VIP MemberWeekly Picture Me This Round 43 Winner!Weekly Picture Me This Round 47 WinnerPicture Me This Round 49 Winner!
5th May, 2007 at 13:18:46 -

Not exactly sure what you mean, or where decimals come in, but Chebyshev & Manhattan are NOT the same.
Recommend you download the example;

http://www.angelfire.com/mech/banshee/Distance.cca (copy & paste to address bar)
it shows the distance between the active object and mouse cursor, as calculated by euclidean, estimated euclidean, chebyshev, and manhattan methods (in that order).

you'll see that the Chebyshev and Manhattan formulae produce very different results, with the former being consistently more accurate, and not significantly more complex.


Getting back to the original question, and having actually looked up precisely what a tower defense game is (http://www.jeannettevejarano.com/tower-defence.swf), I'd have to say that Radix is totally right (at least assuming you don't make it any more complex - different attackers having different vulnerability to different turrets etc), and for something this simple there's probably nothing wrong with using a hidden circle object to determine what's in range, as someone else suggested. Feel free to ignore everyhting I posted...

Image Edited by the Author.

 
n/a
   

Post Reply



 



Advertisement

Worth A Click