Which method is better? - GameCreators Forum

Author

Message

gameangel147

11

Years of Service

User Offline

Joined: 2nd Dec 2012

Location:

Posted: 24th Dec 2013 05:46

Link

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.

Back to top

Profile PM

BMacZero

18

Years of Service

User Offline

Joined: 30th Dec 2005

Location: E:/ NA / USA

Posted: 24th Dec 2013 08:09 Edited at: 24th Dec 2013 08:18

Link

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

Back to top

Profile PM Email Website

smerf

19

Years of Service

User Offline

Joined: 24th Feb 2005

Location: nm usa

Posted: 24th Dec 2013 08:21

Link

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.

Back to top

Profile PM Email

The Tall Man

11

Years of Service

User Offline

Joined: 16th Nov 2013

Location: Earth

Posted: 24th Dec 2013 16:25

Link

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.

Back to top

Profile PM

BMacZero

18

Years of Service

User Offline

Joined: 30th Dec 2005

Location: E:/ NA / USA

Posted: 24th Dec 2013 17:58

Link

For fun:

+ Code Snippet

myInt = 997
myFloat = 997.753

startTime = timer()
for i = 0 to 1000000
    e = myInt^2
next i
print "Integer squaring: "; timer() - startTime; " ms"

startTime = timer()
for i = 0 to 1000000
    e = myInt*myInt
next i
print "Integer multiplication: "; timer() - startTime; " ms"

startTime = timer()
for i = 0 to 1000000
    e = myFloat^2
next i
print "Float squaring: "; timer() - startTime; " ms"

startTime = timer()
for i = 0 to 1000000
    e = myFloat*myFloat
next i
print "Float multiplication: "; timer() - startTime; " ms"

wait key

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

Back to top

Profile PM Email Website

gameangel147

11

Years of Service

User Offline

Joined: 2nd Dec 2012

Location:

Posted: 26th Dec 2013 02:28

Link

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.

REM - This loops through once for every tower that exists
for z = 1 to (towerPasteNum - 21)

REM - The Order Number dictates which sprite to target.  Will only check distance if enemy exists.
	if sprite exist(tower(z).orderNum + 10) = 1

REM - This checks the distance between every tower and the first enemy.
		tower(z).distX = abs((tower(z).xPos + 14) - (enemy(tower(z).orderNum).xPos + 14))
		tower(z).distY = abs((tower(z).yPos + 14) - (enemy(tower(z).orderNum).yPos + 14))
		tower(z).dist = sqrt((tower(z).distX * tower(z).distX) + (tower(z).distY * tower(z).distY))
		
                REM - This is the range of the tower.  Will lower enemy health when enemies is within range.  Contact Flags 1 + 2 detect when the sprite has first come withing range and when it has moved out of range.
		if tower(z).dist < 47
			tower(z).contactFlag = 1
			if tower(z).shootTimer = 20
				dec enemy(tower(z).orderNum).health, 1
			endif
			
				dec tower(z).shootTimer, 1
			
				if tower(z).shootTimer = 0
					tower(z).shootTimer = 20
				endif
				else
					if tower(z).contactFlag = 1
						tower(z).contactFlag2 = 1
					endif
			endif

REM - When enemy health reaches 0, enemy sprite will be deleted and tower will target next sprite in the queue.  If enemy health is not 0, it will check to see if the enemy has already been targeted by a tower, meaning it moved out of range, and the tower will move onto the next enemy.
			if enemy(tower(z).orderNum).health <= 0
				delete sprite (tower(z).orderNum + 10)
				tower(z).contactFlag = 0
				for x = 1 to (towerPasteNum - 21)
					inc tower(x).orderNum, 1
				next x
				else
					if tower(z).contactFlag2 = 1
						tower(z).contactFlag2 = 0
						tower(z).contactFlag = 0
						inc tower(z).orderNum, 1
					endif
			endif
		endif
	next z

+ Code Snippet

REM - This loops through once for every tower that exists
for z = 1 to (towerPasteNum - 21)

        REM - The Order Number dictates which sprite to target.  Will only check distance if enemy exists.
	if sprite exist(tower(z).orderNum + 10) = 1

                REM - This checks the distance between every tower and the first enemy.
		tower(z).distX = abs((tower(z).xPos + 14) - (enemy(tower(z).orderNum).xPos + 14))
		tower(z).distY = abs((tower(z).yPos + 14) - (enemy(tower(z).orderNum).yPos + 14))
		tower(z).dist = sqrt((tower(z).distX * tower(z).distX) + (tower(z).distY * tower(z).distY))
		
                REM - This is the range of the tower.  Will lower enemy health when enemies is within range.  Contact Flags 1 + 2 detect when the sprite has first come withing range and when it has moved out of range.
		if tower(z).dist < 47
			tower(z).contactFlag = 1
			if tower(z).shootTimer = 20
				dec enemy(tower(z).orderNum).health, 1
			endif
			
				dec tower(z).shootTimer, 1
			
				if tower(z).shootTimer = 0
					tower(z).shootTimer = 20
				endif
				else
					if tower(z).contactFlag = 1
						tower(z).contactFlag2 = 1
					endif
			endif

			REM - When enemy health reaches 0, enemy sprite will be deleted and tower will target next sprite in the queue.  If enemy health is not 0, it will check to see if the enemy has already been targeted by a tower, meaning it moved out of range, and the tower will move onto the next enemy.
			if enemy(tower(z).orderNum).health <= 0
				delete sprite (tower(z).orderNum + 10)
				tower(z).contactFlag = 0
				for x = 1 to (towerPasteNum - 21)
					inc tower(x).orderNum, 1
				next x
				else
					if tower(z).contactFlag2 = 1
						tower(z).contactFlag2 = 0
						tower(z).contactFlag = 0
						inc tower(z).orderNum, 1
					endif
			endif
		endif
	next z

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.

Back to top

Profile PM

The Tall Man

11

Years of Service

User Offline

Joined: 16th Nov 2013

Location: Earth

Posted: 26th Dec 2013 03:42

Link

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.

Back to top

Profile PM

gameangel147

11

Years of Service

User Offline

Joined: 2nd Dec 2012

Location:

Posted: 26th Dec 2013 11:04

Link

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.

Back to top

Profile PM

BMacZero

18

Years of Service

User Offline

Joined: 30th Dec 2005

Location: E:/ NA / USA

Posted: 26th Dec 2013 19:05 Edited at: 26th Dec 2013 19:10

Link

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:

+ Code Snippet

for each tower that exists
    if tower can shoot
        for each enemy that exists
            if the enemy is in range
                do all the shooting logic here
                
                //Stop looking at enemies and skip to the next tower, since this tower found a target
                exit
            endif
        next enemy
    endif
next tower

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.

Back to top

Profile PM Email Website

The Tall Man

11

Years of Service

User Offline

Joined: 16th Nov 2013

Location: Earth

Posted: 26th Dec 2013 22:00

Link

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.

REM Initialize Arrays & Variables
DIM EnemyPassCount(MaxEnemies)
DIM AimList       (MaxEnemies)
AimListEnemyCount = 0
AimListIndexRead  = 0
AimListIndexWrite = 0

REM Count the number of times an enemy has passed by the tower.
REM If it's more than twice, add it to the Aim List.
IF Enemy(enemyIndex) [passes by the tower]
   EnemyPassCount(enemyIndex) = EnemyPassCount(enemyIndex) + 1
   IF EnemyPassCount(enemyIndex) >= 2
      AimList(AimListIndexWrite) = enemyIndex
      AimListEnemyCount = AimListEnemyCount + 1
      AimListIndexWrite = AimListIndexWrite + 1
      IF AimListIndexWrite >= MaxEnemies
         AimListIndexWrite = 0
      ENDIF
   ENDIF
ENDIF

REM Check if we need to aim at an enemy. If so, get the index to that enemy.
EnemyIndexToAimAt = -1
IF AimListEnemyCount > 0
   EnemyIndexToAimAt = AimList(AimListIndexRead)
ENDIF

REM Once an enemy has been destroyed, delete from the AimList
IF [EnemyDestroyed(EnemyIndexToAimAt)]
   EnemyIndexToAimAt = -1
   AimListEnemyCount = AimListEnemyCount - 1
   AimListIndexRead  = AimListIndexRead  + 1
   IF AimListIndexRead >= MaxEnemies
      AimListIndexRead = 0
   ENDIF
ENDIF

+ Code Snippet

REM Initialize Arrays & Variables
DIM EnemyPassCount(MaxEnemies)
DIM AimList       (MaxEnemies)
AimListEnemyCount = 0
AimListIndexRead  = 0
AimListIndexWrite = 0


REM Count the number of times an enemy has passed by the tower.
REM If it's more than twice, add it to the Aim List.
IF Enemy(enemyIndex) [passes by the tower]
   EnemyPassCount(enemyIndex) = EnemyPassCount(enemyIndex) + 1
   IF EnemyPassCount(enemyIndex) >= 2
      AimList(AimListIndexWrite) = enemyIndex
      AimListEnemyCount = AimListEnemyCount + 1
      AimListIndexWrite = AimListIndexWrite + 1
      IF AimListIndexWrite >= MaxEnemies
         AimListIndexWrite = 0
      ENDIF
   ENDIF
ENDIF


REM Check if we need to aim at an enemy. If so, get the index to that enemy.
EnemyIndexToAimAt = -1
IF AimListEnemyCount > 0
   EnemyIndexToAimAt = AimList(AimListIndexRead)
ENDIF


REM Once an enemy has been destroyed, delete from the AimList
IF [EnemyDestroyed(EnemyIndexToAimAt)]
   EnemyIndexToAimAt = -1
   AimListEnemyCount = AimListEnemyCount - 1
   AimListIndexRead  = AimListIndexRead  + 1
   IF AimListIndexRead >= MaxEnemies
      AimListIndexRead = 0
   ENDIF
ENDIF

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.

Back to top

Profile PM

gameangel147

11

Years of Service

User Offline

Joined: 2nd Dec 2012

Location:

Posted: 3rd Jan 2014 10:03 Edited at: 3rd Jan 2014 10:09

Link

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.

+ Code Snippet

towerAttack:
        REM - Will cycle through each tower.
	for z = 1 to (towerSpriNum - 21)
                REM - Will cycle through each enemy.
		for a = 1 to 10
                        REM - Will check to see if enemy exists and is in range.
			if sprite exist(a + 10)
				if sprite collision((z + 30), (a + 10))
                                        REM - Will attack enemy if in range and stop checking other enemies.  Also it will delete enemy if health reaches zero.
					if enemy(a).health > 0
						if tower(z).shootTimer = 20
							dec enemy(a).health, 1
						endif
					
						dec tower(z).shootTimer, 1
					
						if tower(z).shootTimer = 0
							tower(z).shootTimer = 20
						endif
					
						exit
						else
							if enemy(a).health = 0
								delete sprite (a + 10)
							endif
					endif
				endif
			endif
		next a
	next z
return

Anyways thanks to all you guys who helped me here. If anyone has any other suggestions on the code, feel free to mention it!

Back to top

Profile PM

Phaelax

DBPro Master

21

Years of Service

User Offline

Joined: 16th Apr 2003

Location: Metropia

Posted: 10th Jan 2014 21:30

Link

A few people suggested you go with the comparative distance check, so why did you decide on using transparent sprites and collision instead?

http://zimnox.com

Back to top

Profile PM Email Website

gameangel147

11

Years of Service

User Offline

Joined: 2nd Dec 2012

Location:

Posted: 12th Jan 2014 04:04

Link

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.

Back to top

Profile PM

Phaelax

DBPro Master

21

Years of Service

User Offline

Joined: 16th Apr 2003

Location: Metropia

Posted: 12th Jan 2014 23:28 Edited at: 12th Jan 2014 23:32

Link

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.

+ Code Snippet


type Enemy
    x as float
    y as float
    distanceFromTower as float
endtype


eCount = 20
dim enemies(eCount) as Enemy

towerRange = 10



do

    closestD# = 1000000
    closestEnemy = -1
    rem loop through all enemies
    for i = 1 to eCount
        enemies(i).distanceFromTower = (tx - enemies(i).x)^2 + (ty - enemies(i).y)^2
        rem enemy is within range of the tower
        if enemies(i).distanceFromTower <= towerRange*towerRange
            // shoot at enemy or something
        endif
        
        rem Determine which enemy is closest to the tower
        if enemies(i).distanceFromTower < closestD#
            closestD# = enemies(i).distanceFromTower
            closestEnemy = i
        endif
    next i
    
    rem Do something with closest enemy
    if closestEnemy > -1
        // Focus on this enemy more or something
    endif
    

    sync
loop

http://zimnox.com

Back to top

Profile PM Email Website

gameangel147

11

Years of Service

User Offline

Joined: 2nd Dec 2012

Location:

Posted: 25th Jan 2014 07:34

Link

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.

+ Code Snippet

function protocol1()

    clickFlag as boolean

    clickFlag = 0


    repeat
        cls

        gosub checkForMouseClick

    
        if clickFlag = 1
            print "The mouse is being clicked."
        endif
        
        sync
    until escapekey()


endfunction


checkForMouseCollision:
    if mouseclick() = 1
        clickFlag = 1
    endif
return

Back to top

Profile PM

Phaelax

DBPro Master

21

Years of Service

User Offline

Joined: 16th Apr 2003

Location: Metropia

Posted: 25th Jan 2014 19:07

Link

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.

http://zimnox.com

Back to top

Profile PM Email Website

gameangel147

11

Years of Service

User Offline

Joined: 2nd Dec 2012

Location:

Posted: 26th Jan 2014 10:29

Link

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!

Back to top

Profile PM

Alex Deef

10

Years of Service

User Offline

Joined: 8th Apr 2014

Location: eastern europe

Posted: 15th Apr 2014 00:22

Link

Thanks for all the help!

Back to top

Profile PM Website

Sorry your browser is not supported!

Newcomers DBPro Corner / Which method is better?