Hey all,

I am attempting to change how towers choose what creep to attack. The goal is to make it attack the creep that is the closest to the exit (right now it doesn't always do that).

Can anyone find me an example of a tower defence game that has all these qualities :

1.) You can place towers anywhere on the map (ie. no fixed path for creeps)
2.) The towers will always attack the creep that is closest to the exit.
3.) all the creeps cannot have the exact same move speed (there has to be at least 1 creep that can go faster than the others.
4.) You can send more than 1 wave at once.

The reason i am asking this is because I am having a hard time coming up with an algorithm to calculate which creep a tower should attack. I'd like to see if any other tower defence games out there were able to accomplish this.

Coming up with an algorithm is easy.... coming up with an efficient algorithm is not. Just remember that in BTGTD you could have 100+ creeps on the screen and 60+ towers on the screen (those juggle maps sometimes have 1000+ creeps on the screen. So I need to make this as efficient as possible :)

I think DTD has it.
(Desktop Tower Defense)
And uhmm, let me check my list, brb :)

Onslaught - http://onslaught.playr.co.uk/
Has fixed paths btw, but the programmer (Gaby) is probably more then willing to help out.

Warzone Tower Defense - cant seem to find the homepage.

Hmm, just checked and you might be right.

My brain hurts!

Go for DTD 1.5 or DTD Pro or Desktop Defender

http://www.handdrawngames.com/DesktopTD/Game3.asp
http://www.handdrawngames.com/DesktopTD/Game.asp
http://apps.facebook.com/desktopdefender/

Each is made by the same person, but they go from oldest to newest in that list

I'm not a programmer (DBA here :P), but isn't it in some way possible to only have 1 creep tagged as closest?
As in, instead of calculating the distance to the exit for every creep, just do that once when spawning (hey, the first to spawn is closest!), and again when a tower is built/sold. Check distances, and "mark" the one creep closest. When it dies, re-calculate.
Or wouldn't that really make a big difference anyway?

-edit-
Nope, never mind. That would only work with unlimited range for all towers, duh.

Just brainfarting here, sometimes a n00b can have brilliant ideas or at least help out a bit :)

So, basically, the creeps figure out the shortest path to the exit when they spawn, and when a tower is built/sold.
Is that some value that is stored? As in measured in pixels or something? If that value would be something like a global variable, the towers could use that for targeting, in combination with their range ofcourse. But they would only need to know it for the creeps in range, right?
So if you first make a sub-selection of the creeps in range, and then for the one closest to the exit, would that make a difference?
Like i said, no programmer :P

For each tower, calculate which part if it's range is closest to the exit while still being a valid place to path though, if there is a creep there target it, then proceed to go further and further away from the path, backwards along it looking for creeps and target any that are found. This should be VERY fast since it doesn't matter how many creeps are alive, just how many towers you have.

Example Picture
http://img806.imageshack.us/img806/9317/targetalgorythm.png
Red = Invalid location
Green = highest Priority
Yellow = Lowest Priority
Invert check for reverse creeps
Check every square for speed or 1/2 square for added precision

Edit: This would be very efficient, since it would only need to recalculate when a tower is built or sold.

Ya Zodiac, that's the idea. The only thing you missed was there should be 4 times as many circles on the screen (since each circle you have there is the size of a tower... and towers occupy a 2x2 area).

So, going with your idea, I'll explain why it's harder than it seems. here we go :

1.) user places tower
2.) For every tower on the screen, loop through each tile within it's radius. Find the tile that is the closest to the exit.
3.) check that tile to see if there are creeps on it, if so, attack one of them.
4.) if no creeps were found in step 3, repeat step 2 all over again, but this time look for the second closest tile to the exit
5.) continue this over and over until you find a tile that has a creep on it.

Multiply this by 2 because there are also backwards creeps...


It doesn't seem like much, but that's a lot of processing. It's the right idea though... I'm going to try a variation of what you mentioned now...

Well here is how I would approach it -

The creeps know who is closet when you work out the path (whoever has the shortest path) - tag the leader. In fact give every creep a path length in its attributes.

When a tower does it's clockwise 'sweep' if it finds 'the leader' keep hitting that creep unless it is no longer found in the sweep - I.E. until it is out of range - then find the next creep with the shortest path attribute in the sweep.

Lots of TD's have tower options that you can select - e.g. strongest / closest / weakest / etc. I assume these all work by checking the credentials of the creep that it found in range.

I think you could also tweak the 'sweep' - I.E. I assume at the moment the sweep always starts at 1 and works around (from you graphic in the other thread) - this could be tweaked so that the second sweep starts where it last found a creep. I.E. It finds a creep at slot 7 - next shot should check slot 7 first.

Yeh exactly.
Right now it seems the algorithm focuses on the grid - which tile is the creep on etc. But the creep itself already knows which tiles to go to for the shortest path, so put the focus of the algorithm on the creep, not on the path.
Kind of hard to explain what i mean, meh.

Calculating for creeps would be very slow since they move/change paths and get created or destroyed much more frequently than towers.

Not what i meant. The calculating is already done by the creep itself, so is it possible to use those values?
I only know SQL and PL/SQL, and not even that much, so bear with me if i'm n00bish.

Zodiac - this calculation must already be happening so the creep knows which direction it should be going

i must that i dont have understand all what you have say, so sorry if you already have say it in another word,

in protector, the "tower" can attack the strongest , right?
so, the "tower" see the stat of all the creep in range, right?
in btgtd, the creep calculate the shortest path, right?
sooo,the creep is supposed to know how much pixel ramaning to the end,right?


what if you put the remaning pixel of the creep in the stat, the tower is supposed to see it, and , like in protector, the see the lowest amont,

thank to have read me

carlnini

Yes, that works, but what if the creep with the most health isnt what you want targetted? If it shot the 1hp creep instead of the 10k one that was leaking, it could have prevent 1 leaking instead of the none it prevented.