Author Topic: Collision Detection Explained  (Read 30037 times)

0 Members and 2 Guests are viewing this topic.

Offline meishe91

  • Super Ninja
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2946
  • Rating: +115/-11
    • View Profile
    • DeviantArt
Collision Detection Explained
« on: March 10, 2010, 10:26:52 pm »
So here I am again explaining another bit of code. This time instead of just basic movement though I will be describing a basic way of collision detection.
Note though that this way is not the most efficient way of doing this and this way only works as long as you have a border all around the outside. If there is a gap and you go off screen it will result in ERR:DOMAIN. (Ztrumpet provided some code that adds in the limitations and if I have time (and his permission) I will post an explanation to that too.)

Ok, so to start lets see the code:

Code: [Select]
PROGRAM:MOVE
"//////////////// //I broke this string down into rows of 16 (the first line is 17 though) so it is easier to follow. It would normally be typed on one line.
/___///___///__/
/_///___///__/_/
/______/////___/
/__///__///__/_/
/_////__//__////
/______________/
////////////////?Str1
Output(1,1,Ans
2?A
2?B
Repeat 0
Output(A,B,"*
Repeat Ans
getKey?K
End
Output(A,B,"_
A+(Ans=34 and sub(str1,16A+B,1)="_")-(Ans=25 and sub(Str1,16A-32+B,1)="_?A
B+(K=26 and sub(Str1,16A-15+B,1)="_")-(K=24 and sub(Str1,16A-17+B,1)="_?B
End

"characters in sting"?Str1: The basic function of this is that we are storing those 128 characters into Str1. What this string is though is our map for what we will be maneuvering around when the program is executed. If you hadn't guessed / are walls while spaces are where you can move. These can be changed for any single slot character (ex. =, +, ?, etc.).
Output(1,1,Ans: Quick explanation of the Output( command. Basically it will display *insert what ever being displayed* in row what ever and how ever many columns out (Output(row number (1-8), column number (1-16), thing to displayed). I explain it much further here. Something I haven't explained though is that if the Output( would (in theory) go offscreen it will wrap around and continue onto the next line. Ok, so the Ans here is the string and it is being placed into row one and in column one too. Since the string is 128 characters long (8*16) it will fill in the whole screen. It will basically display like this:

Code: [Select]
////////////////
/___///___///__/
/_///___///__/_/
/______/////___/
/__///__///__/_/
/_////__//__////
/______________/
////////////////

2?A: Pretty simple, stores a value of 2 to the variable A.
2?B: Again, simple. Stores a value of 2 to the variable B.
Repeat 0: This starts a Repeat loop. As covered here it is the only post test loop. Meaning, I believe, that it checks the statement before running again and will exit once true. To be perfectly honest I'm not entirely sure why Repeat 0 creates an endless loop like While 1 creates a endless While loop. To me it is saying "repeat until false" ("repeat until true" for While loops) but this doesn't make sense to me. If some one can explain that please tell me and I will change this. Anyways, this just creates an endless loop.
Output(A,B,"*: This displays a * in row two in column two. We are displaying it here because our map from Str1 has a border around the outside parimeter. This * is also our object that will be moving.
Repeat Ans: This loop will repeat until key is pressed (the key code is stored to Ans completing the loop).
getKey?K: The getKey command is what will tell the calc to collect the key code of what ever key is pressed. This value is then stored to the variable K.
End: This ends the loop that needs a key to be pressed.
Output(A,B,"_: This will display a space over the * from the previous Output(. It effectively erases it so you don't have a trail.
Now for the doozies...haha.
A+(Ans=34 and sub(str1,16A+B,1)="_")-(Ans=25 and sub(Str1,16A-32+B,1)="_?A: So I already went over boolean logic/piecewise espressions in here so I'll just do a recap. If the statement is true it returns a 1, if false a 0. The only new part here is and and sub( commands. I will explain these independently.
-and: When this is used in a boolean logic/piecewise function expression it means that both conditions must be true to return a 1. If either or both are not true it will return 0. Pretty easy. An example of this would be:

Code: [Select]
PROGRAM:TEST
randInt(0,100?A
Disp A>25 and A<75

-sub(: This itself as a few different uses. I'll explain the one most people use it for, then the one that is used here.
--The usual way sub( is used is to display text. It will pull a certain amount of a string and display just that part. The way this works is there are three arguments: the string or list of characters, the point it is starting at, and how many characters it will go out to. For example:

Code: [Select]
PROGRAM:TEST
"ABCDEFGHIJKL?Str1
sub(Str1,3,8 //The string, starts at the third character, goes eight out.

This will display:
prgmTEST
CDEFGHIJ

Though this command can also be used with things other than just strings. For an example of this we can simply optimize our last code:

Code: [Select]
PROGRAM:TEST
sub("ABCDEFGHIJKL",3,8

It will display the exact same thing.
--The way it is being used here is similar but not quite. We are looking through the string but not to display. We are testing to see if the space to the left, right, above, or below the character that is moving is either a / (a wall) or a space. If it is a space then it will return 1 (assuming the correct button was pressed). (As a side note. You can replace all the ...="_" with ...?"/".) The position of the character you're looking for is done with math which you should be able to decode. I will explain it if you need me too. Just ask.
--So there is a third use that is new to one of the OS updates. If you use sub( with only one argument it will divide it by a hundred. It might save you a byte or two if you need to do that.
Ok, so in essence this line is just testing for the key pressed and if the space to where your moving is a space or not. Phew. Finally haha.
B+(K=26 and sub(Str1,16A-15+B,1)="_")-(K=24 and sub(Str1,16A-17+B,1)="_?B: This works basically the same way as the above line. Just for left and right instead of up and down (which is what the other does).
End: This completes the endless loop.

Yay, finally done :D I hope this makes sense and explains some things. I also hope this helps some of you too :)
If you see any mistakes please let me know and I shall fix them.

Again, this is not the most efficient way of doing this. This is just simply what I had come up with (with some help of the guys over here :)) Enjoy :D

Oh ya, one more thing. I thought I would throw this in here too. If you want to make a little game out of this and have score associated with it you can simply make a few changes to the code:

Code: [Select]
PROGRAM:MOVE2
"////////////////
/___///___///__/
/_///___///__/_/
/______/////___/
/__///__///__/_/
/_////__//__////
/______________/
////////////////?Str1
Output(1,1,Ans
DelVarC2?A
2?B
Repeat AB=30
Output(A,B,"*
AB?D
Repeat Ans
getKey?K
End
Output(A,B,"_
A+(Ans=34 and sub(str1,16A+B,1)="_")-(Ans=25 and sub(Str1,16A-32+B,1)="_?A
B+(K=26 and sub(Str1,16A-15+B,1)="_")-(K=24 and sub(Str1,16A-17+B,1)="_?B
If AB<D or AB>D
C+1?C
End
ClrHome
Disp "YOUR SCORE:",C

Hopefully this is pretty self-explanitory. The only part of this that is worth explaining, I think, is the Repeat AB=30 part. This basically means when you move to the spot where that statement is true it will exit the loop.
« Last Edit: March 11, 2010, 12:40:16 am by meishe91 »
Spoiler For Spoiler:



For the 51st time, that is not my card! (Magic Joke)

Offline DJ Omnimaga

  • Clacualters are teh gr33t
  • CoT Emeritus
  • LV15 Omnimagician (Next: --)
  • *
  • Posts: 55943
  • Rating: +3154/-232
  • CodeWalrus founder & retired Omnimaga founder
    • View Profile
    • Dream of Omnimaga Music
Re: Collision Detection Explained
« Reply #1 on: March 11, 2010, 12:10:47 am »
wow very nice, should be very useful for many people starting with RPGs and the like :)

you're pretty good at tutorials btw :)

Offline meishe91

  • Super Ninja
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2946
  • Rating: +115/-11
    • View Profile
    • DeviantArt
Re: Collision Detection Explained
« Reply #2 on: March 11, 2010, 12:36:57 am »
Thanks :D That is why I kinda made it to help people get ideas going for RPG code.

Thanks, just hoping these are helping people O0
Spoiler For Spoiler:



For the 51st time, that is not my card! (Magic Joke)

Offline ztrumpet

  • The Rarely Active One
  • CoT Emeritus
  • LV13 Extreme Addict (Next: 9001)
  • *
  • Posts: 5712
  • Rating: +364/-4
  • If you see this, send me a PM. Just for fun.
    • View Profile
Re: Collision Detection Explained
« Reply #3 on: March 11, 2010, 06:01:13 pm »
Yeah, you are very good at explaining things. ;D

You have my permission to use anything that I've posted. :)

Offline meishe91

  • Super Ninja
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2946
  • Rating: +115/-11
    • View Profile
    • DeviantArt
Re: Collision Detection Explained
« Reply #4 on: March 11, 2010, 06:43:25 pm »
Thanks ztrumpet! :D
Also, thanks. I will probably do that tomorrow then since I'm not going to someones birthday thing...
Spoiler For Spoiler:



For the 51st time, that is not my card! (Magic Joke)

Offline cooliojazz

  • Support Staff
  • LV7 Elite (Next: 700)
  • *******
  • Posts: 619
  • Rating: +66/-9
  • I omnoms on your soul
    • View Profile
    • Unreal Phantasies
Re: Collision Detection Explained
« Reply #5 on: March 11, 2010, 07:09:19 pm »
@Meishe91: It's While This Is True, and Repeat Until This Is True, that's why one's zero and the other's one.  Other than that, great tutorial. :) I really learned something.
Spoiler For Random signess:
You can not beat my skills.
Trust me.
So don't even try.
And remember never to trust someone who says, "Trust me."

TI File Editor Progress: Remade in java like a boss. 50% we'll call it? IDK =P
Java Libraries: JIRC - 90% JTIF - 5%
TI Projects: Unreal Notator - -5000%
Nomcraft, a Bukkit mod
Some of the music I write can be found here | The Rest Should Be Here (Bandcamp)

Offline Radical Pi

  • LV9 Veteran (Next: 1337)
  • *********
  • Posts: 1143
  • Rating: +5/-2
    • View Profile
    • RealityRevolution
Re: Collision Detection Explained
« Reply #6 on: March 11, 2010, 07:36:39 pm »
What if you want to traverse more than just spaces? If you tested each individually with sub(), things would get big fast, so for this case I would recommend a string of characters you can move over and check the inString("characters","where-you're-moving-to")
(or a string of characters you can't move over, if there's less of those. Just use not(inString(... instead)

For example,
Code: [Select]
:"
XX   XXXXXXXXXXX
X              X
X  .......     X
  .       .    X
  .  ..   .     
X  .   ...     
X   .           
XXXXXXXXXXX     →Str1
:Output(1,1,Ans
:4→R
:8→C
:Output(4,8,"π
:Repeat K=45
:Repeat max(Ans={24,25,26,34,45
:getKey→K
:End
:If K=45
:Return
:Output(R,C,sub(Str1,16R-16+C,1
:min(8,max(1,R+(K=34)-(K=25
:If inString(" .",sub(Str1,16Ans-16+C,1
:Ans→R
:min(16,max(1,C+(K=26)-(K=24
:If inString(" .",sub(Str1,16R-16+Ans,1
:Ans→C
:Output(R,C,"π
:End
One of these days I'll get a sig I'm really proud of.

Offline meishe91

  • Super Ninja
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2946
  • Rating: +115/-11
    • View Profile
    • DeviantArt
Re: Collision Detection Explained
« Reply #7 on: March 11, 2010, 09:09:26 pm »
What if you want to traverse more than just spaces? If you tested each individually with sub(), things would get big fast, so for this case I would recommend a string of characters you can move over and check the inString("characters","where-you're-moving-to")
(or a string of characters you can't move over, if there's less of those. Just use not(inString(... instead)

For example,
Code: [Select]
:"
XX   XXXXXXXXXXX
X              X
X  .......     X
  .       .    X
  .  ..   .     
X  .   ...     
X   .           
XXXXXXXXXXX     →Str1
:Output(1,1,Ans
:4→R
:8→C
:Output(4,8,"π
:Repeat K=45
:Repeat max(Ans={24,25,26,34,45
:getKey→K
:End
:If K=45
:Return
:Output(R,C,sub(Str1,16R-16+C,1
:min(8,max(1,R+(K=34)-(K=25
:If inString(" .",sub(Str1,16Ans-16+C,1
:Ans→R
:min(16,max(1,C+(K=26)-(K=24
:If inString(" .",sub(Str1,16R-16+Ans,1
:Ans→C
:Output(R,C,"π
:End

Well like I  said, this is just a really basic version of it. This is also no where near as efficient as it could be and I know. This was meant to just give the basic idea :) Thanks though, maybe I'll go over that sometime soon.

@Meishe91: It's While This Is True, and Repeat Until This Is True, that's why one's zero and the other's one.  Other than that, great tutorial. :) I really learned something.

Thanks! That makes a lot of sense. I shall add that in when I get the chance to do it. O0

By the way, how many people would find a String to Matrix, Matrix to String, String to list, etc. for converting tile based maps?
« Last Edit: March 11, 2010, 09:11:32 pm by meishe91 »
Spoiler For Spoiler:



For the 51st time, that is not my card! (Magic Joke)

Offline ztrumpet

  • The Rarely Active One
  • CoT Emeritus
  • LV13 Extreme Addict (Next: 9001)
  • *
  • Posts: 5712
  • Rating: +364/-4
  • If you see this, send me a PM. Just for fun.
    • View Profile
Re: Collision Detection Explained
« Reply #8 on: March 11, 2010, 10:21:13 pm »
By the way, how many people would find a String to Matrix, Matrix to String, String to list, etc. for converting tile based maps?
That sounds pretty neat. :)
I can't wait to see what you come up with! ;)

Offline meishe91

  • Super Ninja
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2946
  • Rating: +115/-11
    • View Profile
    • DeviantArt
Re: Collision Detection Explained
« Reply #9 on: March 11, 2010, 10:38:44 pm »
Well I already have one that goes from String to Matrix and back :) (All you have to do is have Matrix [A] and Str1 open and you're good to go...as long as you know the dimentions :P)(This is also only for maps who have two different tiles though, which is the downside.)
« Last Edit: March 11, 2010, 10:39:26 pm by meishe91 »
Spoiler For Spoiler:



For the 51st time, that is not my card! (Magic Joke)

Offline Radical Pi

  • LV9 Veteran (Next: 1337)
  • *********
  • Posts: 1143
  • Rating: +5/-2
    • View Profile
    • RealityRevolution
Re: Collision Detection Explained
« Reply #10 on: March 11, 2010, 10:56:47 pm »
Aww, I was hoping you had some kind of great tilemap compression-via-better-data-type routine. I'm sure everyone could use something like that ;)
One of these days I'll get a sig I'm really proud of.

Offline meishe91

  • Super Ninja
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2946
  • Rating: +115/-11
    • View Profile
    • DeviantArt
Re: Collision Detection Explained
« Reply #11 on: March 11, 2010, 11:06:10 pm »
What do ya mean exactly? Maybe I could try making one :P
Spoiler For Spoiler:



For the 51st time, that is not my card! (Magic Joke)

Offline DJ Omnimaga

  • Clacualters are teh gr33t
  • CoT Emeritus
  • LV15 Omnimagician (Next: --)
  • *
  • Posts: 55943
  • Rating: +3154/-232
  • CodeWalrus founder & retired Omnimaga founder
    • View Profile
    • Dream of Omnimaga Music
Re: Collision Detection Explained
« Reply #12 on: March 11, 2010, 11:18:49 pm »
Well at least it is quite good so far. Compression would be cool, though, altough it might be a bit slow for people who want their games to load map fast and take longer to edit maps, since you would need to decompress them, edit them, recompress them, debug, and repeat. This is the reason why Illusiat 13 won,t use any compression for string maps. Plus the task of compressing, when you got 800 areas in your game (which is the case of Illusiat 13), and boolean logic scattered among them, can be a major pain. I guess it depends what kind of game you are making, though.

Also, for those who use instring( for collision detection, while it is much smaller, it can be considerably slower than checking the map character type

Offline Radical Pi

  • LV9 Veteran (Next: 1337)
  • *********
  • Posts: 1143
  • Rating: +5/-2
    • View Profile
    • RealityRevolution
Re: Collision Detection Explained
« Reply #13 on: March 11, 2010, 11:23:30 pm »
meishe91: I guess something like this... Imagine you're storing your 8x16 map in a matrix. That's 1163 bytes, but it can hold a huge amount of different possible tiles in any space (How many digits of accuracy can you get on a number? Yeah, a lot), but you probably won't be using that many different kinds of tiles. So consider a string, length 8x16=128 = 139 bytes. That string can have up to (however many different characters you can access) different tiles.
None of that really matters for 8x16 maps, because all the possible ways to store it are still simple and small. But what about, say, a 50x50 map? What's the most efficient way of storing that? And what's the fastest way of accessing it during the program, if it's different than how it's stored?
See what I'm saying?
One of these days I'll get a sig I'm really proud of.

Offline meishe91

  • Super Ninja
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2946
  • Rating: +115/-11
    • View Profile
    • DeviantArt
Re: Collision Detection Explained
« Reply #14 on: March 11, 2010, 11:29:45 pm »
Unfortunetly...no...:( Sorry, I'm just not following what you said very well.
Spoiler For Spoiler:



For the 51st time, that is not my card! (Magic Joke)