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, [b]|[/b] and /| but not |/ or |. Here is an example 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!
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?
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.
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.
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 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.
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). 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.
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.
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.
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.
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…
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.
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.
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’”.
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
“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.
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.
How much time did you spend on that?