Welcome Guest [Log In] [Register]
Welcome to Mp2d. We hope you enjoy your visit.


You're currently viewing our forum as a guest. This means you are limited to certain areas of the board and there are some features you can't use. If you join our community, you'll be able to access member-only sections, and use many member-only features such as customizing your profile, sending personal messages, and voting in polls. Registration is simple, fast, and completely free.


Join our community!


If you're already a member please log in to your account to access all of our features:

Username:   Password:
Add Reply
A Challenge!; Logic-based
Topic Started: May 31 2009, 06:56 AM (270 Views)
DeProgrammer
Member Avatar
Elite Pirate
[ *  *  *  *  *  * ]
Okay, so for my Metroid Genesis engine, to make it faster, I require a piece of code that will outline a chunk of tile-based terrain. I have developed a system that works pretty well.

The possible tiles are 45-45-90 triangles sitting flat or squares. No 45-45-90 triangles with one point on the bottom. So basically, |\ and /| but not |/ or \|. Here is an example image.

Posted Image

I used that for much of my testing, but it obviously doesn't have every possible combination of the given shapes.



This is a challenge that some of you (the ones who will actually try it!) will most likely find entertaining. How would you go about it? (If you choose a coding style, you can use the constants I'm using: TILE_AIR, TILE_SOLID, TILE_LEFT45 /|, TILE_RIGHT45 |\...or just 0, 1, 2, and 3 respectively.)

I will post my solution in pseudo-code later, if there's any interest. Might link to the VB version I'm making, too, if I feel like it. (I'm coding it in VB because it makes debugging easy, but then I'll transcode it to C for the sake of Genesis.) And yeah, I designed my solution without any help!
Posted Image
Signature by Rewrite.
My talent comes from deep within...like vomit!
Offline
 
aundy
Zoomer
[ * ]
I don't completely understand what you mean by outline. Do you mean that an array of points specifying the border should be returned?

Also, how is the chunk of tiles specified, as in are you given directly which tiles are in the chunk or are you given a rectangular region that contains the chunk or are you given one tile within the chunk.

One more thing, in the sample picture, are all the tiles considered one chunk or are those two on the bottom left that are connected only by a corner considered separate?
Offline
 
DeProgrammer
Member Avatar
Elite Pirate
[ *  *  *  *  *  * ]
If you can think of something other than points that is usable in the same way, you can probably use that.

You are simply given a rectangular region, which may (and most likely will) contain more than one chunk of terrain. (The chunks themselves don't really matter except for the sake of knowing what you're outlining.) The region may be as big as 256x192 tiles.

If they're visibly touching, they're considered connected (so if a /| is at the bottom-right corner of another tile, it's not connected). The purpose of this is to eliminate as many line segments as possible, so if you have a |\ with another |\ touching its bottom-right corner, you'll end up with only one diagonal line.

I'll point out another issue: What if a chunk has two outlines, like an O shape? The inside still matters if any of the tiles are destructible.

Further hintage: There are 36 possible combinations of 1 angle + 2 shapes. 6 of them are not visibly touching. Posted Image
Posted Image
Signature by Rewrite.
My talent comes from deep within...like vomit!
Offline
 
aundy
Zoomer
[ * ]
Well, here's the first thing that came into my mind.
I made a function that returns the tiles along the boundary of a chunk going clockwise. So for the sample shape you provided it would return the tiles in the following order.

Posted Image

Then, since you know that the tiles are going clockwise and are on the outside of the chunk, getting the points is pretty simple.

To handle O shapes (the attached codes don't do this cuz I was lazy) you would test the tiles within the boundary looking for any open spaces, and If these open spaces were found, then you would run the same function to get the tiles on the boundary and get the points.

The codes written in c++ can be found here http://aundy.110mb.com/main.txt (I couldn't upload a .cpp file for some reason)

The program loops over a tile map containing the numbers 0,1,2, and 3, and then makes a list of boundaries that are then printed out. The code is kind of messy and not very well commented, but I'll explain in detail how that FindBoundary function works a little later today once I get some free time.
Offline
 
DeProgrammer
Member Avatar
Elite Pirate
[ *  *  *  *  *  * ]
Pretty intense. That's basically a shortened C++ version of mine (I also went clockwise!), without drawing the tiles (mine currently draws them instead of storing them). :P How much time did you spend on that?

You can't upload a .cpp file to 110mb unless you have a certain account upgrade. You can't upload MP3s either.
Posted Image
Signature by Rewrite.
My talent comes from deep within...like vomit!
Offline
 
aundy
Zoomer
[ * ]
It took about 2 hours to make, but I didn't actually draw the tile map so I didn't have to worry about graphics. Can you see the image that I posted, for some reason now its just saying user posted image for me. Just in case, here is the link http://aundy.110mb.com/img.png. In any case it seems like you had a similar approach.

Also, I was looking through your website for Metroid: Genesis, and you said that you are awaiting physics assistance. What kind of physics engine will Meroid: Genesis use? Will it be similar to the other 2D Metroid games like Super Metroid or Zero Mission.

Oh, and on 110mb, i noticed that some other random file extensions aren't allowed like .exe but its pretty pointless since it doesn't actually check the file so if I just change the extension I can upload any file I want.
Offline
 
DeProgrammer
Member Avatar
Elite Pirate
[ *  *  *  *  *  * ]
Geeze, I haven't updated that site in forever. Haha. Genesis will use a 2D metroid styled physics engine, yes.

Man, I've made about 6 physics engines and designed another, and Guy Perfect came along today and said it's really simple and straightforward...then proceeded to show me another, much simpler design. Of course, me being DeProgrammer, I probably can't pull it off so smoothly. :P
Posted Image
Signature by Rewrite.
My talent comes from deep within...like vomit!
Offline
 
aundy
Zoomer
[ * ]
I was just wondering cuz I'm currently writing a 2D metroid styled physics engine, and I wanted to know if you had any ideas for how to implement such an engine.

What I'm doing right now is detecting collisions using the separating axis theorem, and then based on the velocity and location of the player the program decides whether to correct the collision by moving the player up and down or right and left (or a combination of both if the player is colliding with multiple shapes). So far it seems to be working with rectangles and right triangles with variable slope, but it feels like the way I'm doing it is more complicated than it needs to be.
Offline
 
DeProgrammer
Member Avatar
Elite Pirate
[ *  *  *  *  *  * ]
I had been doing it a very complicated way, which of course caused a million bugs that each needed fixing... But hey, the method I was using could work nicely for vector-based maps. Guy Perfect outlined some stuff here that you might look at.

I found out that collision detection is about a fifth of the necessary work in a physics engine, heh...
Posted Image
Signature by Rewrite.
My talent comes from deep within...like vomit!
Offline
 
aundy
Zoomer
[ * ]
I was doing something similar to what Guy Perfect is doing. I was doing collision response pretty much exactly as shown in fig. 8, but this caused the player to slide down slopes since every frame I increase the y velocity to mimic gravity. So, I ended up treating every slope as if it was flat when doing the velocity calculation. Also he (I'm assuming Guy Perfect is a guy) didn't talk about handling multiple collisions. You can't just handle them one at a time because then its possible that the player will still be colliding with an object after all collisions have been handled.

Oh, and if you're interested, I posted my engine here http://z3.invisionfree.com/MP2D/index.php?showtopic=2537. The most recent version is the one hosted on 110mb not on rapidshare.

Also, the zip you linked to is password protected.

*edit*
Now that I think about it, the thing I said about multiple collisions wouldn't be a problem if when you were moving the player after a collision you did so according to the players velocity. As in if the player was moving at at 45 degree angle up and to the right and then collided with something, then you move the player down and to the left at a 45 degree angle to correct the collision.
Offline
 
DeProgrammer
Member Avatar
Elite Pirate
[ *  *  *  *  *  * ]
Turn off gravity when your object is on the ground. Check to see if it's no longer on terrain with a separate, simpler system.

The best way to do it is to shorten the movement instead of simply un-moving your object. I'd recommend running the collision testing twice and taking the shortest collision of the first complete collision check before starting the second. (You're not going to be running into 3 things at once if your object is rectangular, you know!)

Can't get your engine running. It was missing a texture, so I copied the SamusNormal ones to make the missing one, and then it told me "Player instance has no attribute 'Key'".
Posted Image
Signature by Rewrite.
My talent comes from deep within...like vomit!
Offline
 
aundy
Zoomer
[ * ]
Hmm, thats strange. I just downloaded it and it ran fine for me. I think its might be because I never tested if the way the paths to the textures are being specified will work in windows (I'm using linux). I replaced the zip on 110mb with a new version. Its the same link http://aundy.110mb.com/MetroidEng.zip.

Also, What is in the Textures folder? two files are needed: SamusNormal.bmp and SamusNormal.info. What is the error message that it gives you?

Isn't it possible to be colliding with three objects if there is a situation like this

Posted Image
Offline
 
DeProgrammer
Member Avatar
Elite Pirate
[ *  *  *  *  *  * ]
"Couldn't open Textures\SamusMP2d.bmp." (which isn't included in the ZIP)
And if I make that file and its associates, its complaint is "Player instance has no attribute 'Key.'"

If you code it the way I suggested instead of "un-moving", it's not possible to be colliding with 3 objects in a situation like that.
Posted Image
Signature by Rewrite.
My talent comes from deep within...like vomit!
Offline
 
aundy
Zoomer
[ * ]
Oh, opps. I completely forgot main.py even existed. Use Engine.py.

**Edit**

Oh, I think I get what you mean by shortening the movement. I see now how that would work, but the down side is that it would require doing collision testing twice.
Offline
 
Under The Ashes
Member Avatar
A Screaming Riot
[ *  *  *  *  *  *  * ]
I think my brain just exploded.
Posted Image
Signature by our own lovely Tim.
Candy Man Criminal
 
its not sex just cuz you switched hands
Offline
 
ZetaBoards - Free Forum Hosting
Free Forums. Reliable service with over 8 years of experience.
Learn More · Register Now
Go to Next Page
« Previous Topic · General Discussion · Next Topic »
Add Reply