Java-Gaming.org Hi !
Featured games (81)
games approved by the League of Dukes
Games in Showcase (513)
Games in Android Showcase (119)
games submitted by our members
Games in WIP (577)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Design help for dynamic destructable landscapes please...  (Read 6469 times)
0 Members and 1 Guest are viewing this topic.
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Posted 2006-07-12 07:39:47 »

I never know exactly where to post my questions, but this seems as good a place as anywhere. Maybe Java2D because it's about Polygons... Regardless.

Hey guys. I've got a an issue I just can't wrap my brain around. I'm trying to make a game like Worms: Armageddon that has weapons which fire and destroy the ground dynamically. I decided to use Java's built-in Polygon objects
to do this, although if anyone knows of a much better way I'm all ears.

WHAT'S GOING ON:
The ground is a big dynamic Polygon, or a list of Polygons (either or, it doesn't really matter). Say we have a piece that looks like a mountain: it has points starting from the base and going to the peak, then back down to the other side. This forms a complete Polygon, and is drawn as such. Simple enough. But my problem is not making these Polygons, it's dynamically changing them.

Let's introduce an explosion. This takes away a big chunk of the landscape. To do this, I've figured a few steps (which work). First, the explosion is also a polygon, I am currently using a 100-gon to look like a circle. If there is polygon interception between the 100-gon and the ground, then part of the ground should be removed. To do this, first all points of the explosion that individually intercept the ground are stored – they will form a new border later, replacing a chunk of the ground. Next, any points of the ground that aren't within the explosion are stored, effectively removing points from the ground that were within the explosion.

Now we have all points from the ground excluding any that were within the explosion radius in one list, and another list with any points of the explosion that encroached on the old ground. In a perfect world, put these points together in one Polygon and you've got the original ground with a circle-shaped chunk taken out of it. I thought it was a perfect world.

THE PROBLEM:
When Polygons are drawn they do it according to some technique I forget the name of. The way that works is that if some points overlap others then that area becomes "negative," not being drawn. Because of this, the order the points are added into the Polygon is INCREDIBLY important. It can't just find the overlying shape and draw that. I've tried to come up with and tested every possible way I could think of to have an algorithm that works in every case, but I can't get it to work. Even if I insert the 100-gon points into the right place order-wise, the 100-gon points also need to moving in the exact same direction the points it replaced were going. I can't figure it out.

Hopefully that's followable. If not, I'll try to include some pictures or something. What follows is my code for factoring explosions in. You can't see the code for the Ground or the generation of the points for the explosion here, but they shouldn't make much of a difference.
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
/**
    * This method "explodes" a Polygon, removing/adding points from it to form a "hole" or
    * explosion in that Polygon. This is called by the Ground and the ground's Polygon rendering
    * is passed into this method. The passed Polygon itself is modified, thus void is returned.
    * @param p   The Polygon (generally Ground) to explode.
    */

   public void explode(Polygon p)
   {
      //Cycle through each of the explosion's points and find which ones
      //intersect the passed Polygon p. These intersecting points are added
      //to the list to be used later.
      java.util.ArrayList addedPoints = new java.util.ArrayList();
      for (int i = 0; i < explosion.npoints; i++)
      {
         if (p.contains(explosion.xpoints[i],explosion.ypoints[i]))
            addedPoints.add(new Point(explosion.xpoints[i],explosion.ypoints[i]));
      }
     
      //Once we have our added points, we can remove any points from the ground
      //that fall within the explosion Polygon, effectively doing the opposite.
      //The index knows where the explosion should be inserted.
      java.util.ArrayList newPolygon = new java.util.ArrayList();
      int index = -1;
      for (int i = 0; i < p.npoints; i++)
      {
         if (!explosion.contains(p.xpoints[i],p.ypoints[i]))
            newPolygon.add(new Point(p.xpoints[i],p.ypoints[i]));
         else if (index < 0)
            index = i;
      }
     
      //The newPolygon will be all of the addedPoints included with the points
      //that did not intersect the explosion.
      if (index != -1)
         newPolygon.addAll(index,addedPoints);
      else
         newPolygon.addAll(addedPoints);
      int[] pxs = new int[newPolygon.size()];
      int[] pys = new int[newPolygon.size()];
      for (int i = 0; i < newPolygon.size(); i++)
      {
         pxs[i] = ((Point)newPolygon.get(i)).x;
         pys[i] = ((Point)newPolygon.get(i)).y;
      }
      //Finally, change the original Polygon to the new one.
      p.xpoints = pxs;
      p.ypoints = pys;
      p.npoints = newPolygon.size();
      arena.remove(this);
   }


That you very much anyone who cared to read all that crap and attempted to help me out.  Smiley

See my work:
OTC Software
Offline bahuman

Junior Duke





« Reply #1 - Posted 2006-07-12 08:58:40 »

Because you mention Java2D, I'm going to assume your Worms clone will be in 2D.
The easiest way to circumvent your problems, is to use a large bitmap to keep track of where is ground, and where is air. The Worms custom levels, by the way, really are just bitmaps. For example: transparent means there is air, and any other color means there is ground, of the color specified.

Now when an explosion blasts away a piece in the ground, you just need to figure out a way to draw a circle in your bitmap, and make all of that transparent. Smiley
Offline ryanm

Senior Duke


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #2 - Posted 2006-07-12 10:04:07 »

You might want to take a look at the Area class.
It sounds like you've re-implemented a subset of it's functionality, specifically the subtract() method.

My advice would be just to use the Area class, and possibly have some vertex decimation to stop your scene becoming too complex.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline beowulf03809

Junior Duke




We live for the code, we die for the code


« Reply #3 - Posted 2006-07-12 13:24:52 »

I have seen this problem brought up recently in another thread as well.  It's interresting to me that there is not a relatively easy solution for modern Java to some game mechanics that are over 10 years old.  The basic issue is the same if you are trying to make a clone of Worms or Lemmings ( a landscape which can be altered / destroyed by the characters ).

One suggestion, see how someone else already doing it is handling the issue.  This is no different than picking up one of the MANY books out there for programming the hottest FPS game, except that no one writes books on how to program these kinds of games.  There are a few OS solutions you can grab to see what basic process they are using for handling the landscape model.  In addition to Vorms ( a Java clone of Worms I found w/ a quick Sourceforge search ) there is a clone of Lemmings for the Linux platform called Pingus.  It's released under the GPL and the source code is available.  I have never poked at the code for either of these yet because I'm not currently looking at reproducing a game of that style, but they may help give you some ideas.
Offline bahuman

Junior Duke





« Reply #4 - Posted 2006-07-12 15:06:13 »

another idea often tossed around is voxel landscapes or engines, but since it's hard to do this in triangle-based 3D accelleration API's, they have a hard time surviving.
Basically, most of the voxel engines (even on OpenGL) look like the graphics date from the 80's  Tongue
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #5 - Posted 2006-07-12 16:33:08 »

Great, thanks for the prompt help, guys. I'll check out Area, bitmaps, and Vorms to see what I can figure out.

And yes, the game is in 2D, at least for now (and probably always). I'm stll just trying to get all the basic functionality working.

I'll post here if I need any more help or suggestions.

See my work:
OTC Software
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #6 - Posted 2006-07-12 17:24:25 »

Okay, I'm trying to use the Area class, but there is no way to draw it! How can I display it? I see I can construct it from a Shape, but I can never get a Shape or any other drawable object out of it. Any ideas?

See my work:
OTC Software
Offline ryanm

Senior Duke


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #7 - Posted 2006-07-12 17:28:51 »

Area is a Shape (it implements the java.awt.Shape interface), so you can use Graphics2D's draw( Shape s ) and fill( Shape s ) methods.
Or you could extract the geometry from the PathIterator and do your own thing.
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #8 - Posted 2006-07-12 18:03:23 »

Oh, duh. I didn't look at its Interfaces, I forgot that Shape is an Interface. Thanks, I'll check this out. Smiley

See my work:
OTC Software
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #9 - Posted 2006-07-12 18:18:32 »

Hooray! Area worked perfectly. Thanks very much for the help. It's just sad that my 100 lines of code is now useles...  Cry Oh well.

See my work:
OTC Software
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Anon666

Junior Duke




aka Abuse/AbU5e/TehJumpingJawa


« Reply #10 - Posted 2006-07-12 23:45:27 »

Why are people suggesting the use of Area as a suitable solution to this problem?

It seems to have lots of extra complications, and no apparent benefits.
Are you intending to implement some game feature/mechanic that is only possible by storing your terrain as complex sets of geometry?
If not, the conventional approach is to (as suggested further up this Thread) represent the terrain as a bitmap.

If it were 3D, then yes representing the terrain as geometry is a much more conventional approach. (although, I have seen some very impressive voxel engines - just begging to be converted into a Worms clone Cheesy)
Offline bahuman

Junior Duke





« Reply #11 - Posted 2006-07-13 07:31:10 »

If it were 3D, then yes representing the terrain as geometry is a much more conventional approach. (although, I have seen some very impressive voxel engines - just begging to be converted into a Worms clone Cheesy)

Don't tease us like that!  Shocked
Give us some links, or -even better- some screenshots/eye candy  Cool


Come to think of it, I wouldn't mind a few ideas on how to handle modifiable 3D landscapes. So far, I use a heightmap, but you can't have overhangs using this technique.
Offline CommanderKeith
« Reply #12 - Posted 2006-07-13 09:48:59 »

The Area class is crap.  You can't get underneath it to access its actual x & y points without creating loads of PathIterator garbage.  I made my own implementaion which is buggy but at least it works.

Offline CommanderKeith
« Reply #13 - Posted 2006-07-13 09:57:39 »

Pixel maps are to be avoided I think if you want to be able to do smooth scaling (ie zooming in & out), for this you need vector graphics like the J2D Area class (but with an implementation without the garbage).

Offline ryanm

Senior Duke


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #14 - Posted 2006-07-13 11:26:11 »

The Area class is crap.  You can't get underneath it to access its actual x & y points without creating loads of PathIterator garbage.  I made my own implementaion which is buggy but at least it works.

I agree it's not the most convenient option for some operations (collision detection etc), but it sure beats having to write and test your own reimplementation.
I would suggest using Area only to perform the CAG operations, and then dump the geometry back into some more convenient format.

As to geometry vs bitmap, I reckon it breaks down like:
Geometry:
  • You can scale and zoom at will
  • Easier to integrate physics (bringing a rockslide down on your opponents sounds pretty cool)

Bitmap:
  • Constant memory/computation requirements
  • Braindead-simple, blindingly-fast collision detection
  • Braindead-simple, blindingly-fast terrain deformation
  • Looks better - images of scenery rather than coloured polygons

For my money, bitmaps are the way to go.

Quote
Why are people suggesting the use of Area as a suitable solution to this problem?
I suggested it because that's what the OP was recreating
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #15 - Posted 2006-09-14 18:51:49 »

Yeah, I've gotten a lot of problems with finding the actual slope of a wall when a bullet hits it because I am using the Area class. So, the bitmap option sounds better, but...

How do I implement that? Am I simply storing an Image of some kind and then searching through pixels for transparency, or what? I don't understand exactly how I would do it this way.

See my work:
OTC Software
Offline ryanm

Senior Duke


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #16 - Posted 2006-09-14 23:01:36 »

I hate to break it to you, but it's far easier to find the slope of a edge of an Area than to compute the slope of some bitmap.

For an Area - Use the PathIterator to identify the line segment that the collision took place on -> you've got the end-points -> you know the slope.

For a bitmap - you find that a bullet has hit an occupied pixel, you have to scan the nearby pixels to try and compute the slope. In the ideal case, there'll be an easily identied line of pixels with no ambiguity as to which way is up and which is into the ground. Maybe I'm just pessimistic, but I can envisage a whole host of situations where it becomes a non-trivial to compute the slope ( single pixel on on it's lonesome, random cloud of pixels, single line of pixels, etc ).

Aaaaanyhoo, as to your question
Quote
How do I implement that? Am I simply storing an Image of some kind and then searching through pixels for transparency, or what?

Yep, that sounds about right. Have a BufferedImage/byte array for your level, and a specific background colour/value that signifies that a pixel is not occupied. For working out a geometrical oultine from a pixelated image, try googling the "Marching squares" algorithm.
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #17 - Posted 2006-09-16 08:20:06 »

Hmm, sounds like it could be very difficult, but I'll look into both possibilities. Anyone know if there is a way to use an Shape as a mask for a drawn image (and that way I could have prettier backgrounds)?

See my work:
OTC Software
Offline ryanm

Senior Duke


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #18 - Posted 2006-09-16 09:52:01 »

Not directly, but you could get the same effect by drawing the ground texture over the whole screen, and then use the Area class to make make a sky shape ie: start with a screen-filling rectange, and subtract() all of your ground shapes, and then draw this sky shape over the ground texture, perhaps with a nice gradient fill. Add some clouds, and the job's a good 'un.
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #19 - Posted 2006-09-19 08:38:48 »

Very good call. I can just make a giant rectangle Area and then subtract pieces to represent the mountains. Then I can just draw images underneath instead of drawing the actual Areas.

See my work:
OTC Software
Offline Abuse

JGO Knight


Medals: 13


falling into the abyss of reality


« Reply #20 - Posted 2006-10-20 09:50:20 »

I don't know if Graphics.setClip(Shape clip) works with the Area class - *it should*, but the javadoc warns that it may not. (If it doesn't, it *should* throw UnsupportedOperationException)

Make Elite IV:Dangerous happen! Pledge your backing at KICKSTARTER here! https://dl.dropbox.com/u/54785909/EliteIVsmaller.png
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

Longarmx (49 views)
2014-10-17 03:59:02

Norakomi (38 views)
2014-10-16 15:22:06

Norakomi (31 views)
2014-10-16 15:20:20

lcass (34 views)
2014-10-15 16:18:58

TehJavaDev (65 views)
2014-10-14 00:39:48

TehJavaDev (65 views)
2014-10-14 00:35:47

TehJavaDev (54 views)
2014-10-14 00:32:37

BurntPizza (72 views)
2014-10-11 23:24:42

BurntPizza (43 views)
2014-10-11 23:10:45

BurntPizza (84 views)
2014-10-11 22:30:10
Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!