create a destructible terrain

I’m trying to write a WORMS like 2D Shooter where each player is positioned on a terrain and where a shot can destroy parts of that terrain.

At the moment I ain’t using any images, but I already have in mind how to manage them. The problem is when I try to calculate the impact of a shot onto the terrain.

I am currently saving the terrain in a POLYGON.

When a new Shot is fired, when it hits the terrain, I am first constructing a new Polygon with the circle coordinates of the blast:


            int npoints = 36;
            
            // create the cercle polygon
            Polygon deto = new Polygon();
            for (int i = 0; i < npoints; i++){
                  double angle =(i*(360/npoints));
                  double sth = Math.cos((angle/180) * Math.PI);
                  double sth2 = Math.sin((angle/180) * Math.PI);
                  deto.addPoint((int)(sth*radius + x), (int)(sth2*radius + y));
            }

Now comes the problem. I don’t know any mathematical method to calculate the impact of this polygon on the terrain polygon. But Java does…well, AREA does.

So until now I am storing all the detonations in an ArrayList and at each render() I do this:


            Area surfaceArea = new Area(surface);
            
            g2d.setColor(Color.red);

            for (int i=0;i<detonations.size(); i++){
                  Area tmpArea = new Area((Polygon)detonations.get(i));
                  surfaceArea.subtract(tmpArea);
            }
            
            if (surface.npoints > 2)
                  g2d.fill(surfaceArea);

This takes CPU time at each render call which is absolutely unnecessary if I could find a way to make the subtract and then save the Area back to a polygon.

The reason why I just use an Area all the way is because I need later on the x,y coords to calculate player positions and detonation points etc.

Does anyone know a better way to do this or even a solution to my problem ?

Thanks in advance.

What an insane way of attempting a Worms clone!

If you want to write a Worms clone, do it as Worms did it, and use a collision map for the terrain.

The Java2D API makes it exceedingly easy to do, with the stuff in the java.awt.image package.

I know it probably isn’t the most common way but it was the first way that came into my mind and I don’t have much experience with that.

Could you elaborate more on what a collision map is and how it is so “easy” to do with awt.image ?

Ok, just to show you that I haven’t been lazy…I found some things on the Internet and tried them.

  1. method: create an array the size of your level width and store the height value in the array. Generate an Image and leave it unchanged until an explosion occurs.

this method wasn’t what I wanted because I could only have 1 floor in the game and not two as I want too.

  1. method: create a 2-dimensional array, level width and level height in pixels and store the value of each pixel (drawn or not drawn). With that method I can create several floors in the game and also create caves.

But I don’t know about the processor power I need to draw that when the image changes. I believe it to be very high.

Is there a better method ? The problem is, I can’t use tiles of a certain size because I want the terrain to be fully destroyable and not only in pieces of x,y pixels. I could create blocks of maximal 2x2 size and divide the size of the array by 2 but I don’t want to venture further in the wrong direction.

A tiny hint would help me a lot.

Thanks !

[quote]A tiny hint would help me a lot.
[/quote]
You could always look at Gorillas.bas. It might reenforce for you which ideas will work. :slight_smile:

P.S. In case you have no idea what I’m talking about (shameful, just shameful), you can see an updated version here.

Ok, I try to dig a little into that QBasic Code. I was never that good in lowlevel languages and I hope I’ll understand it somewhat. I think he builds the city skyline with lines that have a certain height. So when an explosion would struck a building, he breaks the line in 2 parts and draws the lower and the upper part.

Don’t know if this is the way to go, can’t imagine Worms or Gunbound to use such a system.

So is the line-based approach somewhat correct ?

Since I don’t have better demonstration material… you gotta deal with… ahem hitler :stuck_out_tongue:

http://kaioa.com/k/HnHFe.png

The first 3 the images are the layers: skull, blood and ugly face. [The 4th is obviously after a neat shotgun blast :)] These 3 layers are (in this case) in a single image, which is once copied over into a compatible BITMASK BufferedImage.

For damage effects the color is just set to fully transparent (0,0,0,0)… then some fillOvals are drawn on the ugly face and then some smaller ones on the blood layer (the drawing is done with that copy of the image). All three layers are then drawn onto each other - resulting in that gory mess.

In a Worm alike game you would do it in a pretty similar way. The map image is split into 2^16 pixel “tiles” (eg 256x256) with transparency set to BITMASK. That’s easy and it’s fast.

If you like to keep the speed you’ll need to do the collision stuff seperated. For this part you need a huge array of bytes for storing all those “the pixel is there/not-there” bits.

So, you’ll need to do all damage drawing things twice; once for the graphics and once for the (invisible) collision map. The former is accelerated and the latter is a software only thing done by the cpu. It makes sense to split it up like that, because you avoid pushing the data around all the time (which slows down everything a lot).

ah, thanks a lot. Gonna try that during this day.

But I have a small concern, in my case I dont have 256256 pixels but rather 2000800 pixels. What about the performance in THIS case.

I use a 2000800 BufferedImage where the content is drawn onto and then only draw a part 800600 on the actual Graphics object from my Panel.

Event @ 32bpp, 2000x800 is only ~1.5mb.

in my case I dont have 256256 pixels but rather 2000800 pixels

You need to copy it once over anyways for ensuring to get a compatible bitmasked image and nothing else. At that time you can also split it into a bunch of 256x256 tiles, because that’s the maximum size (2^16) ddraw can handle for bitmasked images.

For drawing you determine which tiles are on screen and only draw those. The drawing performance should be pretty optimal then… leaving lot’s of CPU cycles for the rest of the game.

I love you guys !!! ;D

Here’s what I’ve done till now:

http://www.martialartsmovies.net/2dballer/2DBaller.rar

java -cp . render.Baller

Ok, so here’s the full history:

  • First I had a normal gravity environment with balls bouncing of the floor and of the walls with full force.

  • Then I wanted to display a background Image (2000x600) that would also define the world size. The area displayed would be limited to 800600.
    Here comes my FIRST MISTAKE: I used a DoubleBuffer System with a BufferedImage of size 2000
    600 and then only displayed the small part on the actual Panel. This gave me horrendous performance. The mistake was the entire background beeing drawn on the bufferedimage at each repaint() even if the bufferedimage was actually never entirely drawn onto the panel. I then changed the size of the bufferedImage to the size of the screen (800, 600) and only draw the part of the background that was displayed onto this bufferedimage. This made my CPU go from 70% to 10% on a Pentium 4 - 2,8 GHz

  • Then I added the actual Map. I wanted it to be a normal graphic with magic Pink (255,0,255) and the magic pink would be replaced by transparency. This went quite well, the only mistake was that at first, I used:
    BufferedImage buffi = ImageIO.read(sth);

and believed this would be a good Type of BufferedImage. I quickly detected the mistake and created the BufferedImage first with type BITMASK (thanks to oNyx) and draw the picture loaded into a temporary bufferedimage onto the buff created. Then i used some per pixel manipulations to replace it with 0,0,0,0. I also had some problems with the JPG format which always had an alpha of -1 … now I use .gif but I don’t see why JPG wouldn’t work now. Just need to pay attention to the order alpha, r,g,b or r,g,b,alpha. (Question: does JPG have 32 bits so does it contain the alpha or does it encode with 24 bits ?)

  • At the same time, I created a boolean[][] for the collision map and loaded true or false into it depending on magic pink found or not. (Question: is boolean 1 bit or why do people often use int[][] instead of boolean[][] for collision map?)

  • Now I wanted my terrain to explode. I used a MouseListener and wrote a method addDetonation(x,y,radius) and draw an Oval on the Map bufferedImage as well as changed the values in the collision map. This went really good and I progressed really well.

  • Now came the hard part…It took me and my friend 4 hours +/- to complete and we are very proud of it. We know that it contains still bugs but we don’t care. It is really more than we expected and for the worms clone I want to create, is more than enough.

We actually wrote a collision detection system that maked the balls bounce on the map surface, regardless of it’s form, in the correct physical way (with angles and stuff).

It would be really hard to explain what we did but if someone wants to read the code (it is well documented), we don’t mind. What we did is, when we detect a collision, we backtrace the curve until we find the exact collision point, then approximate the angle of the wall, we calculate the angle between the wall and the speed vector, we translate the speed vector to the origin 0,0 then we use a rotation matrice to rotate the vector with an angle of what we found. Then we retranslate to the collision point, place the ball on the collision point, set the new speed vector and here we go.

  • If someone has read to this point: I use for the render loop the following method to get the sleep() value:

            while (IS_RUNNING) {
                  
                  // get the current Time in nanos
                  oldTime = System.nanoTime();

                  // update the world objects position
                  updateWorld();
                  
                  // update the Background (if scrolling)
                  updateBackground();
                  
                  // call the render() function of each object and then repaint
                  render();

                  // get the current Time in nanos
                  newTime = System.nanoTime();
                  long duration = newTime - oldTime;

                  // calculate the time a frame should last minus the time it actually lasted
                  // this will give us the time we need to wait in order to make it last exactly
                  // the time we want it to.
                  long waitTime = 1000000000/FRAME_PER_SECOND - duration;
                  
                  try {

                        if (waitTime <= 0){
                              // the frame took longer then the maximum time we wanted it to last
                              // don't wait at all (CPU => 100%)
                              
                              //System.out.println("not ok");
                              Thread.sleep(1);
                        } else {
                              // the frame took less then the maximum time, wait for the rest
                              
                              //System.out.println("ok");
                              Thread.sleep(waitTime/1000000);
                        }
                  } catch (InterruptedException e) {
                        e.printStackTrace();
                  }
            }

This runs really good on my PC and I wanted to know what you think about this and how it runs on your PC.

THANKS FOR ALL YOUR HELP !!!

Just a quick note:

  • the .rar contains a version where 5 balls are created at position 10,100 with a random speed from (0,0) to (10,20).

  • I doesn’t contain the explosions. Well it does contain them, but just isn’t enabled. My friend and I stopped yesterday at 2.00 AM and just couldn’t write a single line where you could change those values with arguments. Expect that version to be ready if not today, then probably tomorrow.

  • It works also really well with detonations, the balls create a detonation, create a new ParticleSystem and then bounce from the ground. I could also make them explode.

  • The particlesystem is written by my friend with a little help from my side and will be used to create the explosion effect for braking rocks etc. It is fully configurable with particle lifetime, color, speed, amount etc…

Update:

You can actually destroy the terrain by clicking with the mouse. I forgot that I still left that code part uncommented.

Random notes:

[1]You can use gifs own transparency instead of ff00ff replacing. There are also some ff00ff-ish seams, which would have been more obvious during the art creation process if gif’s transparency would have been used.

Copying over and preserving of the transparency looks like this:


BufferedImage i = ImageIO.read(new BufferedInputStream(getClass().getResourceAsStream(path)));
BufferedImage c = gc.createCompatibleImage(i.getWidth(null),i.getHeight(null),Transparency.BITMASK);
Graphics2D tg = (Graphics2D)c.getGraphics();
tg.setComposite(AlphaComposite.Src);
tg.drawImage(i,0,0,null);
tg.dispose();

[2]JPG is 24bit - there is no alpha. A seperate grayscale (8bit) JPG could be used for the alpha channel, but that’s quite silly if you just want a bitmask (which is - by definition - 1bit).

You can, however, use a 24bit jpg for the landscape and a seperate 1bit gif, png or bmp as bitmask. You would need to load those two images, pull out the raster, stick em into a new image and finally copy it over into a bitmasked image. Eventually those two last steps could be combined somehow, but I’m not sure how to do that.

[3]Thread.sleep gets only down to about 5msecs and there is also no guarantee that you’ll really get the control back at that time. If you have a high perf timer (eg 1.5’s) you can use my frame capping scheme:


private long timeNow, timeThen, timeLate = 0;
[...]
g.dispose();
sync(1000000000L/75L); //75fps
strategy.show();
[...]
private void sync(long frameFraction)
{
      Thread.yield(); //at least once
      long gapTo = frameFraction + timeThen;
      timeNow = System.nanoTime();

      if(frameCap)
      {
            while(gapTo > timeNow+timeLate)
            {
                  Thread.yield();
                  timeNow = System.nanoTime();
            }
      }

      if(gapTo<timeNow)
            timeLate = timeNow-gapTo;
      else
            timeLate = 0;

      timeThen = timeNow;
}

[4]A rar is a pretty silly thing in the Java world. Create a doubleclickable jar next time :wink:

Oh and for the booleans. I suggest using bytes instead. It’s a bit faster and the amount of used ram is most likely the same (it makes sense to use byte sized chunks for speed reasons, therefore I guess that a boolean takes also one byte).