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.

DarkBASIC Discussion / Collision Effeciency

Author
Message
epicgamer
6
Years of Service
User Offline
Joined: 11th Nov 2012
Location: Unknown
Posted: 19th Feb 2013 04:15 Edited at: 20th Feb 2013 06:23
For simple collisions object collision() seems to bog down when trying to handle many objects. Checking all objects against all objects is factorial.



Looping through all objects checking against one object appears to be much more efficient for simple block style collisions.

TheComet
11
Years of Service
User Offline
Joined: 18th Oct 2007
Location: I`m under ur bridge eating ur goatz.
Posted: 19th Feb 2013 16:13
That won't work, because you're only checking every object against the same one. You'd have to perform n! checks to get all of them, where n is the number of objects.



Why are you using a float for collision#?

TheComet

http://blankflankstudios.tumblr.com/
"You're all wrong. You're all idiots." - Fluffy Rabbit
"Bottom line, people are retarded." - Fluffy Rabbit
Phaelax
DBPro Master
16
Years of Service
User Offline
Joined: 16th Apr 2003
Location: Metropia
Posted: 19th Feb 2013 17:42
Quote: "endif:endif:endif:endif:endif:endif"


I really hope not all your code looks like that!

"You're all wrong. You're all idiots." ~Fluffy Rabbit
epicgamer
6
Years of Service
User Offline
Joined: 11th Nov 2012
Location: Unknown
Posted: 19th Feb 2013 23:34 Edited at: 19th Feb 2013 23:34
Quote: "Why are you using a float for collision#?"


Phaelax
DBPro Master
16
Years of Service
User Offline
Joined: 16th Apr 2003
Location: Metropia
Posted: 20th Feb 2013 01:13 Edited at: 20th Feb 2013 01:23
Code is way easier to read if you format it by spacing and indenting it properly. Are you trying to compact your code into a 20-liner or something?

Here's your code reformatted and I did away with all the unnecessary GOTO statements. Also, you probably shouldn't be using floats in your FOR statement. I don't even know what to say about all the nested IF statements. Not saying it's necessarily a bad thing, but there's probably a better way to organize it. I don't know your collision method you're using so I can't say.






If you want to check an array of objects against themselves, this would be a good starting block:


Oops, I see Comet already had this sorted out. I didn't really look at the code snippet til just now.

"You're all wrong. You're all idiots." ~Fluffy Rabbit
Libervurto
13
Years of Service
User Offline
Joined: 30th Jun 2006
Location: On Toast
Posted: 20th Feb 2013 01:46 Edited at: 20th Feb 2013 01:55
My version:

You really tried to make this as unreadable as possible!
Here it is converted to human readable code (excuse the huge tabspaces I don't know why this happens on copy pasting):

Why on earth did you have "one#=1" and "xiognull#=0" and "half#=2" in there? Looks to me like you're lacking some foundational understanding of this language. I'd suggest going back to the basics: http://forum.thegamecreators.com/?m=forum_view&t=99497&b=10

epicgamer
6
Years of Service
User Offline
Joined: 11th Nov 2012
Location: Unknown
Posted: 20th Feb 2013 03:08
Quote: "
endif
endif
endif
endif
endif
endif
endif
endif
endif
"


Libervurto
13
Years of Service
User Offline
Joined: 30th Jun 2006
Location: On Toast
Posted: 20th Feb 2013 03:11
What?

Fluffy Rabbit
User Banned
Posted: 20th Feb 2013 03:11
From DS2:

Quote: " `Determine which direction the player is going
if u=1 and r=1 and l!1 and d!1
a=45
else:if r=1 and u=d and l!1
a=90
else:if r=1 and d=1 and l!1 and u!1
a=135
else:if d=1 and l=r and u!1
a=180
else:if d=1 and l=1 and u!1 and r!1
a=225
else:if l=1 and u=d and r!1
a=270
else:if l=1 and u=1 and r!1 and d!1
a=315
else:if u=1 and l=r and d!1
a=0
endif:endif:endif:endif:endif:endif:endif:endif"
epicgamer
6
Years of Service
User Offline
Joined: 11th Nov 2012
Location: Unknown
Posted: 20th Feb 2013 03:34 Edited at: 20th Feb 2013 03:34
http://dictionary.reference.com/browse/efficiency?s=t

Quote: "Checking all objects against all objects is factorial."


Quote: "You'd have to perform n! checks to get all of them,"


Quote: "simple block style collisions."


.
Fluffy Rabbit
User Banned
Posted: 20th Feb 2013 04:28
TheComet
11
Years of Service
User Offline
Joined: 18th Oct 2007
Location: I`m under ur bridge eating ur goatz.
Posted: 20th Feb 2013 09:54
Quote: "Looping through all objects checking against one object"


won't work.

TheComet

http://blankflankstudios.tumblr.com/
"You're all wrong. You're all idiots." - Fluffy Rabbit
"Bottom line, people are retarded." - Fluffy Rabbit
Phaelax
DBPro Master
16
Years of Service
User Offline
Joined: 16th Apr 2003
Location: Metropia
Posted: 20th Feb 2013 17:03
Quote: ""Checking all objects against all objects is factorial.""

Technically, you're performing fewer checks than n!

If you break down the FOR loop Comet showed you and assume 5 objects:

outer - inner
1 - 2,3,4,5
2 - 3,4,5
3 - 4,5
4 - 5

That's 10 checks, not 120(5!).

"You're all wrong. You're all idiots." ~Fluffy Rabbit
epicgamer
6
Years of Service
User Offline
Joined: 11th Nov 2012
Location: Unknown
Posted: 20th Feb 2013 20:44
Collision Effeciency

Quote: " Looping through all objects checking against one object appears to be much more efficient for simple block style collisions."


Quote: "won't work."


It actually works well.

epicgamer
6
Years of Service
User Offline
Joined: 11th Nov 2012
Location: Unknown
Posted: 20th Feb 2013 21:08
Quote: "for i = 1 to maxObjects rem if object is invisible, skip checking it against the others if items(i).invisible <> 0 rem loop through all objects for j = i+1 to maxObjects rem make sure this item isn't invisible, otherwise skip it if items(j).invisible <> 0 rem Now do your collision calculations between the two objects endif next j endifnext i"


for i = 1 to maxObjects:if items(i).invisible <> one#
for j = i+1 to maxObjects:if items(j).invisible <> one#
HitCollision#=one#
endif:next j:endif:next I

.

TheComet
11
Years of Service
User Offline
Joined: 18th Oct 2007
Location: I`m under ur bridge eating ur goatz.
Posted: 20th Feb 2013 21:23
It's a troll. I'm calling it. There's no doubt in my mind now.

TheComet

http://blankflankstudios.tumblr.com/
"You're all wrong. You're all idiots." - Fluffy Rabbit
"Bottom line, people are retarded." - Fluffy Rabbit
Fluffy Rabbit
User Banned
Posted: 20th Feb 2013 21:30
Does DarkBASIC support object-oriented syntax? array(i).attribute
Kevin Picone
16
Years of Service
User Offline
Joined: 27th Aug 2002
Location: Australia
Posted: 21st Feb 2013 07:58
Quote: "Does DarkBASIC support object-oriented syntax? array(i).attribute "


Nah.. they're not natively supported in DB Classic. However, some original IDE's (like GuyS) included pre processors, which would parse the user code and spit out a version with the types converted to parallel arrays, rather than individual structures.

so this stuff,

Type Character
Name$,X#,Y#
EndTYpe

Dim Badguys(10) as Character

would become

Dim Badguys_Name$(10)
Dim Badguys_X#(10)
Dim Badguys_Y#(10)

etc

Fluffy Rabbit
User Banned
Posted: 21st Feb 2013 17:34
@Kevin-

Wow! That's a lot of functionality to be added by an IDE. I learned something today.
epicgamer
6
Years of Service
User Offline
Joined: 11th Nov 2012
Location: Unknown
Posted: 21st Feb 2013 18:47
TheComet
11
Years of Service
User Offline
Joined: 18th Oct 2007
Location: I`m under ur bridge eating ur goatz.
Posted: 21st Feb 2013 19:42
That does not support what Kevin is talking about.

Quote: "Does DarkBASIC support object-oriented syntax? array(i).attribute"


Ah, you're completely right. I'm way too used to DBP, and it seems like Phaelax is too.

TheComet

http://blankflankstudios.tumblr.com/
"You're all wrong. You're all idiots." - Fluffy Rabbit
"Bottom line, people are retarded." - Fluffy Rabbit
Phaelax
DBPro Master
16
Years of Service
User Offline
Joined: 16th Apr 2003
Location: Metropia
Posted: 21st Feb 2013 20:55
Quote: "However, some original IDE's (like GuyS) included pre processors,"

I remember that. It was a big deal at the time.

"You're all wrong. You're all idiots." ~Fluffy Rabbit
epicgamer
6
Years of Service
User Offline
Joined: 11th Nov 2012
Location: Unknown
Posted: 21st Feb 2013 20:57

.

epicgamer
6
Years of Service
User Offline
Joined: 11th Nov 2012
Location: Unknown
Posted: 21st Feb 2013 21:04
Quote: " pre processors, which would parse the user code and spit out a version with the types converted "




Latch
13
Years of Service
User Offline
Joined: 23rd Jul 2006
Location:
Posted: 22nd Feb 2013 20:24 Edited at: 22nd Feb 2013 20:26
As pointed out by epicgamer, DarkEDIT also allows for type definitions so you can use such conventions as

for i = 1 to maxObjects:if items(i).invisible <> one#
for j = i+1 to maxObjects:if items(j).invisible <> one#
HitCollision#=one#
endif:next j:endif:next I

Enjoy your day.
Latch
13
Years of Service
User Offline
Joined: 23rd Jul 2006
Location:
Posted: 23rd Feb 2013 19:34
Quote: "Looping through all objects checking against one object appears to be much more efficient for simple block style collisions.
"


I would agree. Somewhere on these forums I wrote up a demo or complete description of this.

If you use "block style" collision testing, it's much, much faster in DBC to use collsion detection from MAKE OBJECT COLLISION BOX than it is to SET OBJECT COLLISION TO BOXES, especially if you use the non-rotating box flag.

Enjoy your day.
epicgamer
6
Years of Service
User Offline
Joined: 11th Nov 2012
Location: Unknown
Posted: 23rd Feb 2013 20:38 Edited at: 23rd Feb 2013 20:54
Example



Latch
13
Years of Service
User Offline
Joined: 23rd Jul 2006
Location:
Posted: 24th Feb 2013 19:25
Since your custom collision routine is checking the size and the position in three dimensions, you could probably increase performance by running your own sphere collision routine instead of cube checking where you only check the distance between radii instead of check x y and z.

You can further improve the check by using squared distances instead of using SQRT() to find the actual distance:



Enjoy your day.
epicgamer
6
Years of Service
User Offline
Joined: 11th Nov 2012
Location: Unknown
Posted: 24th Feb 2013 21:49 Edited at: 24th Feb 2013 22:03
Quote: "sphere collision routine"


The option to switch between the two types, add a block collision or sphere collision is a good idea.

Login to post a reply

Server time is: 2019-08-22 05:56:57
Your offset time is: 2019-08-22 05:56:57