Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 04 Jul 2003
Offline Last Active Today, 09:39 PM

#5001696 random midpoint displacement self-intersection problem

Posted by JTippetts on 16 November 2012 - 10:56 PM

I have run into exactly the situation you are describing.

To my knowledge, there is no easy way to prevent it. Fractal functions (either subdivision-based such as midpoint displacement, or implicit such as fractal noise) are not "self aware". There is no easy way for point (x,y) to make adjustments to itself to avoid intersecting with the displacement provided by point (x1,y1). The points are mutually unaware of each other, effectively speaking; at least in this context. The problem is compounded by the fact that the heightmap plane is topologically a planar membrane that is being stretched and forced into self-intersecting forms.

There are some things that you can do to try to mitigate the problem. Here is an image of a distorted spire, formed as a cone displaced in X and Z by a couple of fractal methods:

Posted Image

You can see it has a lot of the deviant behavior you describe, and that behavior only gets worse as the scale of the displacement is increased. In this next one, I calculated a scaling factor as (MaxHeight-PointHeight)^2, and used that to scale the amount of X and Z displacement applied to the geometry. The higher up the spire a point is, the smaller the scale and thus the smaller the displacement.

Posted Image

This is a bit of a hack to avoid the weird mountaintops, and you still get plenty of weird folding on lower-elevation peaks and ridges.

Basically, once you try to introduce overhangs and other elements of a 3D nature, then the displaced heightmap plane is no longer a sufficient abstraction to work with, and you need to shift your thinking to a volumetric method. If you think of your ground surface as simply the threshold between solid ground and sky, and don't try to force it into a heightmap representation by displacing a 2D plane, then it doesn't matter how the volume is folded and distorted by the displacement functions; the generated mesh geometry will not be self-intersecting. An example:

Posted Image

In places where the threshold of the ground is pushed through itself, it might bore holes, and it still might result in some unrealistic geometry (floating chunks, etc...) but at least the mesh geometry itself isn't weirdly folded and self-intersecting. And the strange formations can be controlled by the parameters of the system, such that floating islands are reduced, if not eliminated altogether.

#5000780 Creating "Chains" of objects with smooth motion.

Posted by JTippetts on 13 November 2012 - 10:12 PM

Correct, the posted videos probably weren't using physics systems. However, in today's world, 2D physics libraries are an extremely cheap drop-in solution, and you can get such a thing up and running literally in moments. I did a small test using Love2D and Box2D, and got a chain swirling around very much like the one in the second video in about 15 minutes. I can post the code, if you like; it's dead simple. The hard work is done by the physics library, all I had to do was tweak a few parameters.

That being said, you could probably also achieve a similar effect by using "canned" animations, by pre-computing animation tracks for each ball in the chain for a particular movement, especially for the Zelda boss, since there isn't the wavy variation that the second one has. I suspect the second one might be canned, too, since those bullet-hell games tended to be pretty tightly timed and patterned.

#5000468 tic tac toe AI

Posted by JTippetts on 12 November 2012 - 11:16 PM

Pretty tough to say what's going on without seeing the rest of the code (such as how the variable player_X is set and when, etc...) But still, it seems as if you are kind of going about this oddly.

You have a board that can hold 'X', 'O' or ' ' (space for empty). To find a randomly selected space for player O, you could do something similar to this:

int Computer::findRandomSpace()
     int move=-1;
while (board[move]!=' '
     return move;

Of course, this method will hang if the board is full, so ensure that you test the board first for a win/loss/draw condition. Essentially, you loop until you find an empty space, generating a new random board index each time.

Another way would be to iterate through the board and find all the empty spaces, and add the empties to a vector:

std::vector<int> Computer::getValidMoves()
     std::vector<int> moves;
     for(int c=0; c<9; ++c)
          if (board[c]==' ') moves.push_back(c);
     return moves;

After calling getValidMoves(), you will have a vector that is either empty (if the board is full), or holds the indices of all empty spaces in the board. Now, you can choose one at random:

int Computer::chooseMove()
     std::vector<int> moves=getValidMoves();
     if(moves.size()==0) return -1;   // Board is full
     int length=moves.size();
     return moves[rand() % length];

Another benefit of constructing a vector of all valid moves is that when you move on to a smarter AI, you can change the getValidMoves() method to prioritize spaces by how much closer they get you to a win condition. For example, if a space will generate a win condition for the player, it receives the highest priority; if a space will block the other player from a win condition, it gets the next highest priority. And so forth. You can sort the vector based on priority, then in the chooseMove() method, instead of grabbing a random space you grab the space at the back of the list (assuming you sort from lowest priority to highest). That way, you always choose the best move you can make.

#5000247 Despondent

Posted by JTippetts on 12 November 2012 - 08:49 AM

Whoa, there, you need to relax a bit. It sounds like you're overwhelming yourself with too much.

First of all, why are you bothering with source control right now? Source control is great, but when you're just learning it's not necessary. At this moment, you need to learn how to program, and there is simply no need for you to worry about learning to use source control at the same time.

Any time you face complexity, the only thing you can do is to break it down into more simple pieces, and work on them one at a time. Trying to take it all on at once will just lead to frustration.

#5000101 starting over

Posted by JTippetts on 11 November 2012 - 09:50 PM

Make some video games.

#4998601 sfml problem/question regarding VideoMode

Posted by JTippetts on 07 November 2012 - 03:52 PM

What FLeblanc and I mean when we say "native resolution" is that every LCD monitor has a recommended resolution, dependent upon the monitor's size and quality. Using this recommended resolution means that there is a 1:1 correspondence between a "logical pixel" (what resides in the frame buffer) and a physical pixel (the actual bit of screen hardware that displays a pretty color). Choosing a resolution that is not the recommended resolution means that logical pixels can be spread across multiple physical pixels, resulting in blurring and shimmering artifacts as the picture moves.

By default, a game should detect optimal resolution by default (going with a user's current desktop resolution is probably best, since it will usually be the optimal setting) but present a dropdown box of alternative, allowable modes they can choose from if they have performance problems or other personal reasons to switch. But my personal opinion is that you shouldn't force a player to a non-optimal fullscreen resolution by default, and any game that does is likely to earn my ire.

#4998463 How to avoid singleton

Posted by JTippetts on 07 November 2012 - 10:51 AM

Why does there need to be a concrete Fireball class anyway? A fireball is just a projectile with an exploding component that does fire damage. Object composition is your friend. By creating concrete classes like that, you limit your options and make a lot more work for yourself in trying to shoehorn everything in. What if you want an Iceball spell? You could create an Iceball class, duplicate some code from Fireball and change some things around, or inherit from a base class... but all of that is a code smell that ultimately leads you into a bad place of spaghetti code that can kill your project. Why not construct a composition system, instead? Break it down into individual behaviors, and add those behaviors to an object as it needs them.
Here is the gist of how I construct a fireball spell in Goblinson Crusoe:

1) Create an Object. An Object is an empty canvas; at this point, it could be anything.
2) Add a projectile component. Now, the object is a thing that moves from one place to another, and when it gets where it's going or hits something along the way, it sends itself a message that it has collided. It listens for logic update messages to know when to move. Lots of spells would share this component: fireball, ice spear, thrown rock, shot arrow, etc...
3) Add an animation component. Now, the projectile has a visual presence in the world, a looping animation of a fireball streaking through the air. Lots of spells would share this component, too.
4) Add an explosion damage payload. This component listens for the notification that is has collided with something, and when it receives such a message it will query the world for all other objects within a specified radius, and deliver a packet of Fire damage to each one. Some spells might use this area-effect payload, others might use a single-target-damage payload. Others might use a heal-target payload, or a heal-area payload. Still others might use a polymorph-other payload. Whatever; this component describes what happens when the thing hits something.
5) Add a Flash component, which also listens for a collided notification and spawns an explosion animation.
6) Finally, add a terminator component that also listens for collided, and sends the object a message to die.

At any step along the way of constructing this object, you can tweak things. Change the damage type to Ice and the animations to iceball and ice explosion. Add a component that spawns additional projectiles for damage debris or ember shards that strike additional enemies. Add a component that spawns 100 little floating daisies to settle out of the fire-seared air onto the scorched earth. Change the projectile component type to tracking rather than straight-line, in order to hunt down and destroy. Change the Flash animation to a nuke going off, for extra visceral effect. You name it. You are not limited to just one generic type of fireball. And there are no singletons to be seen anywhere in that scenario.

#4998165 sfml problem/question regarding VideoMode

Posted by JTippetts on 06 November 2012 - 01:25 PM

You can use VideoMode::getFullscreenModes to get a vector of all valid (fullscreen) modes. If you require a resolution that is not supported then you can do as you suggest, and just draw to a sub-section of the window. Just check the enumerated mode for the next largest valid mode, or use native resolution, and center your active area. Be aware that this may annoy your players, some more than others. For such a small window, given the native resolution of modern LCD monitors (and you should try to stick to native resolution, for image quality) 800x600 will amount to more black-space than used-space. I would certainly complain about a game that did that. I highly recommend you do what you can to use a higher active resolution.

For windowed mode, 800x600 shouldn't be a problem.

#4996978 How to find the closest interception point?

Posted by JTippetts on 03 November 2012 - 03:26 PM

Maybe this thread might be of some use:


It talks about leading shots on enemies, and one poster presents a solution to the shot-leading problem by solving a quadratic equation.

#4996714 Who would consider a game interface an art?

Posted by JTippetts on 02 November 2012 - 06:07 PM

Once upon a time, art wasn't really a word or a thing. People made stuff, that's it. Cave paintings, carved sticks, whatever. They didn't make it to be all hoity-toity in their stupid art magazines. Grok didn't look over at Blorg and say, "Blorg make carved stick, not rock people; carved stick not art. Blorg dumb." Blorg was probably dumb, but Grok's no-carved-sticks-are-art rule was still stupid. If some ass-hat can crap in a can and call it art, then game interfaces can be called art as well. Your average game interface certainly takes more creativity and skill to create than pooping in a tin can.

#4996599 Why is this terrain using 4d simplex noise not tiling?

Posted by JTippetts on 02 November 2012 - 11:03 AM

Yes, loopx0 and loopx1 are constant. If you were to map the range specified by loop to the entire map all at once, that map would tile with itself. mapx0 and mapx1 are specified as sub-ranges of loop, and correspond to each sub-chunk of the map. So if the loop range is 0 to 1 and there are 10 sub-chunks across the map, mapx0 for the first chunk would be 0, mapx1 would be 0.1. For the second chunk, mapx0 would be 0.1, mapx1 would be 0.2. But for all chunks, loop would be the same.

Now, there is a problem with mapping the range [0, tilewidth*numberoftiles] to loop. Say your tile width is 64 and you have 100 tiles. This means the looping range would be 0 to 6400. Mapping this range of noise does not produce anything meaningful, basically just white noise, unless you turn the frequency of the noise function WAY down. This is because, in Perlin noise (gradient as well as simplex, even the value-noise variant) there is roughly 1 "feature" per integral coordinate at the default frequency of 1. This means that in the range 0,6400 there would be produced approximately 6400 "hills" or "valleys". The output would be very much like the third screenshot in your original post. You need to turn down the range specified in loop to correspond what you wish to map.

#4995601 Why is this terrain using 4d simplex noise not tiling?

Posted by JTippetts on 30 October 2012 - 04:41 PM

It's a little tough reading your code, since it seems the forums ate your newlines, so correct me if I'm wrong about what you are trying to do.

1) You have an array of tiles, tiles indexed on i and j.
2) Each tile is a chunk of noise, the individual pixels of which are indexed on localx and localy.
3) You want to calculate each pixel of the tiles such that the whole map tiles seamlessly with itself

For reference, here is how the 2D tiling noise in ANL is constructed:
	    size_t w=a.width();
	    size_t h=a.height();
	    static double pi2=3.141592*2.0;
	    size_t x,y;
	    for(x=0; x<w; ++x)
		    for(y=0; y<h; ++y)
			    double p=(double)x / (double)w;
			    double q=(double)y / (double)h;
			    double r;
			    double nx,ny,nz,nw,nu,nv,val=0.0;
			    double dx, dy, dz;
			    nx=ranges.loopx0 + cos(p*pi2) * dx/pi2;
			    ny=ranges.loopx0 + sin(p*pi2) * dx/pi2;
			    nz=ranges.loopy0 + cos(q*pi2) * dy/pi2;
			    nw=ranges.loopy0 + sin(q*pi2) * dy/pi2;

Now, comparing your code, these lines where you calculate your noise input coords look suspicious to me:

nx = absx + Math.cos(s * 2 * Math.PI)*dx/(2*Math.PI);		  
ny = absy + Math.cos(t * 2 * Math.PI)*dy/(2*Math.PI);		  
nz = absx + Math.sin(s * 2 * Math.PI)*dx/(2*Math.PI);		  
nw = absy + Math.sin(t * 2 * Math.PI)*dy/(2*Math.PI);

absx and absy are calculated as the global pixel coordinates of the sample, so they are going to change in value as the pixel coords change. In my original implementation, I use loopx0 and loopy0 here, which do not change. The only way the coordinates change is through the value of s and t, which should be calculated from the pixel coords.

In my implementation, I specify the ranges over which the noise loops explicitly, rather than tying the range to the tile coordinates. Similarly, I specify the ranges over which the tiles are mapped explicitly. The ranges loopx0 to loopx1 and loopy0 to loopy1 specify the range of noise mapped to the entire map. The ranges mapx0 to mapx1 and mapy0 to mapy1 specify the range of noise (a sub-range of the larger looping range) to map to a given tile. This would be calculated by dividing the larger loop range up into as many equal-sized pieces as there are tiles.

As far as getting different terrain, I implement a seeding technique where a seed is passed as another input to the noise function, and is hashed together with the input coordinates. Change the seed, get a different output.

#4994925 pong paddle

Posted by JTippetts on 28 October 2012 - 09:25 PM

You can import it into Gimp, color-select the white background, and fill it with black.

My suggestion is that you avoid using JPG for sprites, though. Typically, a sprite is going to have transparent areas, and JPG doesn't support alpha channel. Also, JPG compression is lossy, so you can lose detail. I'd suggest going with PNG, TGA or some other format that supports loss-less compression and a alpha channel.

#4994853 How do I avoid hundreds of identical scene graph traversals?

Posted by JTippetts on 28 October 2012 - 04:45 PM

Instead of each node pulling from its parent (which in turn pulls from its parent), push instead. Calculate the root node's transforms first, then push them out to all children, who will calculate their transforms and push to their children in turn.

#4994634 Why does this look so flat?

Posted by JTippetts on 27 October 2012 - 10:45 PM

If you're not yet skilled at pixel art, one trick you can do is to draw it several times larger than you want it to be, then scale it down to the size you need. If you are not good with form, you can try modeling with simple 3D shapes in something like Blender, then tracing over it with pen tools in Gimp to provide strokes and outlines. A quick (and pretty crappy) example of both techniques:

Posted Image

The anchor was quickly modeled by dragging some points in Blender and doing a Skin modifier plus a subdivision surface, then rendered and quickly traced with some outline, then scaled down. Working from a 3D render like this can also help you to work on your own hand-shading if that is the way you really want to go. The 3D render gives you a template to work from, and you can draw and shade on a layer over the top of it to practice your skills.