# Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

### Newcomers DBPro Corner / Which method is better?

Message
Posted: 24th Dec 2013 05:46
I'm working on a tile-based tower-defense game and I'm wondering which of the following two methods I should use to detect when an enemy is in proximity. I'm trying to find the way that will take less processing power and be easier to work with overall. Any help would be appreciated.

Method 1: Using A^2 + B^2 = C^2 to calculate the distance. Each tower only keeps track of the distance of the first enemy in line until destroyed.

Method 2: Keep a second transparent sprite the size of the tower's range, then check for sprite collision with enemy sprites.
Posted: 24th Dec 2013 08:09 Edited at: 24th Dec 2013 08:18
Use the distance check, method 1. I don't remember if sprite collision in DarkBASIC even checks against the individual pixels - if it doesn't, you'll end up with box collision instead of circle collision. And if it does, it will be very slow because it will be checking a large number of pixels to see if any of them overlap.

EDIT: Here are some detailed and perhaps very nit-picky optimization tips:

The distance formula is typically implemented like this:
distance = SQRT(x^2 + y^2)
However, the square root function typically takes more work to calculate than the square. So when all you need to do is compare distances, instead of calculate the exact distance, you should do this instead:
distance^2 >= x^2 + y^2

Additionally, if I have been led correctly DarkBASIC uses a powering algorithm whenever you use the caret (^) operator. While the powering algorithm ought to be pretty efficient for a power of two, it would be more efficient still to do this:
distance*distance >= x*x + y*y

Posted: 24th Dec 2013 08:21
I agree with bmac. A little bit of math vs a lot of sprite checks
I generally benchmark as i program by watching my frame rate as i code or add new elements. You can make a loop of different elements like do 10 sprite checks at once then 10 math check loops see what slows down the program the most.

A child's dream never dies.
Posted: 24th Dec 2013 16:25
A*A is faster than A^2.

Q: ...you mean computer imagery was still based on the paradigm that the world was flat? Even into the 21st century??? Talk about doing something the hard way!

A: Yep! Back then people would render simple shapes with complex meshes of thousands of flat little triangles. Next to the bottleneck processors they used, it's the main reason why their computers were so slow. In the last days of the religious atmosphere of centralization and trade, corporate dogmas had people believing that flat was faster.
Posted: 24th Dec 2013 17:58
For fun:

Yep, multiplication is about 14 times faster than squaring on my computer (though of course both take very small amounts of time.

Posted: 26th Dec 2013 02:28
I see what your saying, though all the sprites are squares, being a grid, and I wouldn't be checking pixels or using circle collision.

Another problem I have is trying to keep the order of the waves, since the towers only focus on enemies in order. So if for example, there is a tower that an enemy must pass by twice, then the tower will focus on that first sprite ahead of the others.

A reason I want to use sprite collision is because I can cover the range much more easily and I wouldn't have to use so many flags to detect when the enemy is in range. If anyone has an easier way of getting each tower to only focus on the first enemy in the queue, no matter when it happens, that would be much appreciated.
Posted: 26th Dec 2013 03:42
I didn't quite get everything you said...

To get it to focus on the first one in a queue, you can use a circular list. You have a 1 dimensional array of max elements long. Use two indices, one used for reading, the other for writing. When an index reaches the end of the list, you wrap it around to the beginning again. Have a counter also, to keep track of how many elements are currently in the list.

If you have a lot of things that need be done for a specific result (such as several tests/criteria for detecting when an event has occurred or should be triggered), you can modularize, create a single function (or subroutine) that's dedicated to that single result. That way it doesn't get all confusing and mixed up with the rest of your code.

Q: ...you mean computer imagery was still based on the paradigm that the world was flat? Even into the 21st century??? Talk about doing something the hard way!

A: Yep! Back then people would render simple shapes with complex meshes of thousands of flat little triangles. Next to the bottleneck processors they used, it's the main reason why their computers were so slow. In the last days of the religious atmosphere of centralization and trade, corporate dogmas had people believing that flat was faster.
Posted: 26th Dec 2013 11:04
I don't quite understand the process, could you write some example code please?

What I was trying to explain was that each tower needs to attack the front-most enemy in the wave. If there are multiple enemies within range at once, it should target them by order, and switch targets to the next one after an enemy is destroyed or moves out of range.

Hope that clears it up, and thanks to everyone for the help so far.
Posted: 26th Dec 2013 19:05 Edited at: 26th Dec 2013 19:10
Your orderNum approach is interesting, but as you noticed, it won't work for enemies that pass by the tower a second time. The usual way to do this would be to just loop through each enemy for each tower with a nested loop. This way, each tower can determine on the fly what the first enemy that's in its range is without relying on a stored value.

Here is some pseudo-code for that:

This is fine as long as all your enemies are moving the same speed and thus stay in the same order . If that's not the case, there are probably a number of things you could try. I would probably try to sort the enemy list each frame so that enemies that are closer to the end appear at the beginning of the list. Then the above pseudo-code would still work fine.

EDIT: As a side-note, the "if enemy in range" statement is where you would put either the sprite collision check or the distance check to see whether the enemy is in range. You can see that in this code it doesn't make a difference which one you use in terms of code complexity. However, the distance check will be much faster.

Posted: 26th Dec 2013 22:00
Okay, my understanding is that you wish to aim toward enemies that have passed by your toward twice. And that you wish first pass-twice, first aim, right?

You could store as a characteristic of an enemy, how many times the enemy has passed by the tower.

Then to create a queue where it's first-in, first-out, the circular list I mentioned earlier. Qualifications to enter the aiming list are than the number of passes-by an enemy has made > 1. I'm not familiar with specifically DarkBasic, so I'll post some BASIC-like pseudo code and code mixture.

Q: ...you mean computer imagery was still based on the paradigm that the world was flat? Even into the 21st century??? Talk about doing something the hard way!

A: Yep! Back then people would render simple shapes with complex meshes of thousands of flat little triangles. Next to the bottleneck processors they used, it's the main reason why their computers were so slow. In the last days of the religious atmosphere of centralization and trade, corporate dogmas had people believing that flat was faster.
Posted: 3rd Jan 2014 10:03 Edited at: 3rd Jan 2014 10:09
Okay so this is the code that I ended up making for the order. Pretty much it goes to the first tower, then checks to see if the first enemy exists, and if it does, it checks to see if it's colliding with the transparent range sprite. Then it will attack and stop checking the other enemies and move onto the next tower. I haven't found any problems yet and I'm surprised it was this simple, I imagined it would be a bit more complicated.

Anyways thanks to all you guys who helped me here. If anyone has any other suggestions on the code, feel free to mention it!
Posted: 10th Jan 2014 21:30
A few people suggested you go with the comparative distance check, so why did you decide on using transparent sprites and collision instead?

Posted: 12th Jan 2014 04:04
I'm still very much a beginner and have had trouble understanding the method for checking to see whether one enemy is ahead of another when more than one is in range. I found the sprite collision to be easier, and it has been working for me. I have been testing it with larger amounts of sprites and it still runs at a good frame rate.

I also have more control and accuracy with sprites to choose ranges instead of using numbers. Overall it was just easier for me, though if you have a way for me to use a comparative check while keeping tabs or the order of the enemies, I would be willing to try to learn how to use it.
Posted: 12th Jan 2014 23:28 Edited at: 12th Jan 2014 23:32
This example will determine which enemies are within range and pick out the closest enemy. It also keeps track of each enemies distance from the tower, allowing you to sort them if you wish.

Posted: 25th Jan 2014 07:34
That's actually a lot shorter than I thought, though some parts confuse me.

-When calculating the distance, is there a reason you didn't get the square root and instead just squared "towerRange" instead?

-When comparing the distant to tower for the first enemy and setting "closestEnemy" to 1, isn't it just going to loop through and set it to the next enemy? It looks like it will focus on each enemy rather than staying locked on without an "exit" from the loop.

-I noticed there is no code in the last IF statement, and the code for focusing on an enemy is what I needed more than the rest. Though I think that IF statement is unnecessary if there is an EXIT in the loop. If the first enemy is in range, then attack and don't check the others. Once it is out of range, check the next one in line.

Still it's a lot shorter than the code I had. And on another note, a question about functions and subroutines. If I declare a local variable inside a function, then use it in a subroutine INSIDE the function, will that variable work, or must it be global, even if the subroutine is used inside the function, like below.

Also I really appreciate the help and advice.

Posted: 25th Jan 2014 19:07
Quote: "When calculating the distance, is there a reason you didn't get the square root and instead just squared "towerRange" instead?"

Because you don't need the exact distance in this case, you're only comparing them. For a comparison to see if something is within range, it's quicker to square the C (c = sqrt(a^2 + b^2)) and remove the need for the square root calculation.

Quote: "When comparing the distant to tower for the first enemy and setting "closestEnemy" to 1"

It's setting it to i not 1. And it only updates when an enemy is found to be closer than the last one it updated with.

Quote: "I noticed there is no code in the last IF statement, and the code for focusing on an enemy is what I needed more than the rest. Though I think that IF statement is unnecessary if there is an EXIT in the loop. If the first enemy is in range, then attack and don't check the others. Once it is out of range, check the next one in line. "

You would run into problems if you exit the loop as soon as you found an enemy within range. For starters, what happens if more than one enemy is in range? Your array is not sorted by distance from the tower, so enemy(3) might be within range at 40px away but enemy(7) could be only 20px away. If we exit, it'll fire at an enemy that's farther away that what should otherwise be considered a more immediate threat with enemy(7). You want to shoot at the closest one first, and to do that you need to check ALL the enemies.

I would avoid calling subroutines from functions. But to answer your question, off-hand I would think it needs to be global.

Posted: 26th Jan 2014 10:29
Okay, I get it now. I was looking at it differently because I used an exit command in the box collision method I used. Thanks for all the help!
Posted: 15th Apr 2014 00:22
Thanks for all the help!