What's the best way to determine the nearest enemy in a tower defense game?

[Adamwpe]

I just complete my first game with flash (and flash punk) and it went well, learnt a lot. But i have a question.

I’m going to make a tower defence game but I want to make it as optimal as possible, both for making the game faster and secondly learning more optimal solutions.

My problem is that lets say i have one tower, but 100 different enemies

A) i could do the easy way of searching all 100 enemies to find the nearest one. Which i have done in java before many times

or

B) using the tile map, when a enemy walks along a tile it is put in a array which is linked to that tile which then the tower will check the nearest tile’s until it reaches a tile with a enemy on it, if the tile array is bigger than 1 then you know there is more than one enemy on it then it would just check the array length rather than all 100 enemies.

Is that a good idea or is there a better way of doing it ?

[NotARaptor]

It probably wouldn’t be terrible to check each enemy, if you only had one tower.

The problem with this approach is that you won’t only have one tower, so if EACH tower checks EACH enemy, that’s when you have a potential problem - it will explode fast (if you have M towers and N enemies, that’s M*N checks).

So if performance is an issue, you don’t want to handle the logic separately for each tower, you want one search that will detect nearest neighbours between towers and enemies in one loop.

There are lots of ways of dealing with this - if you want to read up on it, search for quadtrees, hashmaps and other structures - there’s lots of info out there. A sweepline algorithm might work quite well here (I say “might” as I’ve not used it for this specifically before).

Of course, there’s a very simple way to get started - create a circular collision mask object corresponding to the max range of each tower. Then use FP’s collision detection (collide the range mask against the enemy to see if it’s in range). See if that works!

[billy2000]

Id use one of the neat FP function called nearestToEntity() more details here:

Accessing Entities

One of the most common problems new ActionScript programmers come across when developing games is having variables accessible where they need to be and communicating information between game objects. In this tutorial, we'll take a look at some of FlashPunk’s available tools for dealing with this problem. Finding unique entities -- Sometimes you need a particular entity to be available for all other entities to interact with. For example, you might want all instances of an Enemy class to cons…

[Ultima2876]

Have a look for quadtree and bucket (spatial hashing) collision optimisation.

This is probably only worth doing if you’re allowing for 30+ towers and multiple hundreds of enemies, but you can also split the targeting workload between frames. For example if your tower shoots once every second (once per 60 frames) you can divide between those 60 frames - so if you have 30 towers and 500 enemies, you’re only actually doing 30 * 500 = 15000 / 60 = ~250 distance checks per frame. If you do this, remember to check for stuff like new enemies being spawned or coming into range and handling that appropriately!

[Adamwpe]

Thanks all for a reply, sorry for the late reply, something happened. But i made my version of the quad tree. I don’t know if its the best idea but i give it a go and if it don’t work i still learn’t a lot, so im happy about that.