Ask General Programming Questions Not Worth Their Own Thread

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > The Cavern of COBOL > Ask General Programming Questions Not Worth Their Own Thread

«‹›671 »

EternalMoogle: Jul 8, 2008

So, I see things like the visualizers in audio software (iTunes, WinAmp, etc), games like Audiosurf, and so on, and I'm wanting to learn more about how exactly those work. I'm sure there are websites with information on how to start playing with audio files, but it seems my google-fu is extremely weak on this subject, because I don't even know what to begin looking for. Can anyone point me toward some good starting resources?

I'm an undergrad CS major, so I'm kinda-sorta-experienced in the programming world. Just not with audio stuff.

# ? Jan 1, 2009 18:29

Adbot: ADBOT LOVES YOU

# ? May 15, 2024 02:04

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

EternalMoogle posted:

So, I see things like the visualizers in audio software (iTunes, WinAmp, etc), games like Audiosurf, and so on, and I'm wanting to learn more about how exactly those work. I'm sure there are websites with information on how to start playing with audio files, but it seems my google-fu is extremely weak on this subject, because I don't even know what to begin looking for. Can anyone point me toward some good starting resources?

I'm an undergrad CS major, so I'm kinda-sorta-experienced in the programming world. Just not with audio stuff.

You'll probably want to start by googling for some terms like "spectrum analyzer" and "fourier transform", or take a class on signal processing.

# ? Jan 1, 2009 22:23

Randomosity: Sep 21, 2003; My stalker WAS watching me...

I'm messing around with the XNA, trying to make a space invaders clone or some other top down shooter.

I'm making it pretty OO, so I've got a Sprite class and a GameObject abstract class (inherits from Sprite) with an Update() function. The idea is all game objects have their update behavior defined for themselves. I like this approach, but I realized it'd be near impossible to trigger events in other gameObjects with this approach, unless I pass in the entire Game object to each Update function.

Sorry if this is s context specific. I know that generally passing a huge object like that into a class is terrible (in traditional OO), but I'm wondering if this makes sense as an exception.

# ? Jan 3, 2009 05:14

hexadecimal: Nov 23, 2008; by Fragmaster

Randomosity posted:

I'm messing around with the XNA, trying to make a space invaders clone or some other top down shooter.

I'm making it pretty OO, so I've got a Sprite class and a GameObject abstract class (inherits from Sprite) with an Update() function. The idea is all game objects have their update behavior defined for themselves. I like this approach, but I realized it'd be near impossible to trigger events in other gameObjects with this approach, unless I pass in the entire Game object to each Update function.

Sorry if this is s context specific. I know that generally passing a huge object like that into a class is terrible (in traditional OO), but I'm wondering if this makes sense as an exception.

Why can't you pass a reference to said huge object? If you pass a reference or pointer (I am not quite sure what XNA is, but its bound to have pass by reference), then you are not copying that huge object each time, but just 32 or 64 bit address to it.

# ? Jan 3, 2009 06:17

Randomosity: Sep 21, 2003; My stalker WAS watching me...

hexadecimal posted:

Why can't you pass a reference to said huge object? If you pass a reference or pointer (I am not quite sure what XNA is, but its bound to have pass by reference), then you are not copying that huge object each time, but just 32 or 64 bit address to it.

It's not a technical limitation, just wondering if it's terrible design. The actual code is C#. XNA is Microsoft's library. It's more a game code design question than tech question. C# passes non-primitives by reference.

# ? Jan 3, 2009 06:29

hexadecimal: Nov 23, 2008; by Fragmaster

Can you explain your design in more detail? So each entity in your game inherits from GameObject class, which has update() function, and you would like to let some of your entities know about specific events that happen, correct? I don't understand why you need to pass GameObject to the other entities?

You shouldn't trigger events by calling update() function. You should probably have some sort of event/listener design, where one class generates events, and has a list of objects that are interested in that event, and when said event occurs you call a callback function in each listener object.

Alternatively you can maintain a list of events in current time quantum, and access it in update() function. This way, however, you may run into concurrency issues in case you have multiple threads running update() functions for different objects.

# ? Jan 3, 2009 06:46

Randomosity: Sep 21, 2003; My stalker WAS watching me...

hexadecimal posted:

Can you explain your design in more detail? So each entity in your game inherits from GameObject class, which has update() function, and you would like to let some of your entities know about specific events that happen, correct? I don't understand why you need to pass GameObject to the other entities?

You shouldn't trigger events by calling update() function. You should probably have some sort of event/listener design, where one class generates events, and has a list of objects that are interested in that event, and when said event occurs you call a callback function in each listener object.

Alternatively you can maintain a list of events in current time quantum, and access it in update() function. This way, however, you may run into concurrency issues in case you have multiple threads running update() functions for different objects.

This is basically for determining if events happen. For example, if I've got a laser in the game space, the laser's update() checks to see if it collides with the enemy. To do that, we get each enemy's position from the game context passed in.

This is just a stupid learning game, I'm just pressing forward with my design and seeing how it goes. What you say makes sense for a serious project or one of a larger scale. Thanks for the help.

# ? Jan 3, 2009 07:30

hexadecimal: Nov 23, 2008; by Fragmaster

Randomosity posted:

This is basically for determining if events happen. For example, if I've got a laser in the game space, the laser's update() checks to see if it collides with the enemy. To do that, we get each enemy's position from the game context passed in.

This is just a stupid learning game, I'm just pressing forward with my design and seeing how it goes. What you say makes sense for a serious project or one of a larger scale. Thanks for the help.

For collision detection, you probably want a single class containing a data structure that can efficiently determine if collisions happen. This data structure can contain coordinates for each object in game, and reference to that object. When collision happens, you can notify appropriate objects about it.

Look up quad-trees for doing efficient 2d collision detection.

# ? Jan 3, 2009 07:38

Avenging Dentist: Oct 1, 2005; oh my god is that a circular saw that does not go in my mouth aaaaagh

hexadecimal posted:

Look up quad-trees for doing efficient 2d collision detection.

Quadtrees aren't a collision detection method, they're a culling method. Besides that, with a Space Invaders clone, you'd do just as well with a fixed-size grid for culling.

# ? Jan 3, 2009 08:05

NightGyr: Mar 7, 2005; I � Unicode

If I'm building a PBEM type game in python, but adapting it to the internet, where clients submit turns through a webpage, what's the most efficient way to reload the game state into the turn processor? How much of a performance hit would it be if I pickle it and store it on the server until the clients submit their next turn?

This is for an in-depth game, so there may be a few hundred or thousand objects in the game state, and turns may come in hours apart, so it would be silly to keep it running while waiting.

# ? Jan 3, 2009 09:07

rjmccall: Sep 7, 2007; no worries friend; Fun Shoe

NightGyr posted:

This is for an in-depth game, so there may be a few hundred or thousand objects in the game state, and turns may come in hours apart, so it would be silly to keep it running while waiting.

It sounds like, in the worst case, your server will be marshaling a few hundred megabytes every few minutes. This is not the sort of scale that's worth optimizing for; just do the easiest thing until it really starts biting you. If/when you do decide to get fancy, I would suggest using a memory-sensitive cache of game state; Python has weak references, which should help a lot with that.

# ? Jan 3, 2009 11:21

hexadecimal: Nov 23, 2008; by Fragmaster

Avenging Dentist posted:

Quadtrees aren't a collision detection method, they're a culling method. Besides that, with a Space Invaders clone, you'd do just as well with a fixed-size grid for culling.

Yea, good point. I just wanted to point out a good data structure to use that is better done with having all coordinates in one class, versus the design the Randomosity was suggesting. Also I think it would be a great exercise in algorithms as well as OOP design to implement quad trees even for space invaders.

# ? Jan 4, 2009 19:53

ToastedZergling: Jun 25, 2007; Chubby Walrus:
The Essence of Roundness

Hello programming goons,

After originating in the Web Development megathread, I was redirected here for some relatively advanced algorithm development help. Generally, I'm looking for people with more expertise in mathematics than programming. I am attempting to solve the Crackless Wall problem, #10 from overclock.net

quote:

Consider the problem of building a wall out of 2x1 and 3x1 bricks (horizontal�vertical dimensions) such that, for extra strength, the gaps between horizontally-adjacent bricks never line up in consecutive layers, i.e. never form a "running crack".

There are eight ways of forming a crack-free 9x3 wall, written W(9,3) = 8

W(18, 5) = 7958.

Calculate W(32,10).

At this point, my program returns the correct values for W(18,5). However, if I attempt to calculate larger values such as W(32,10) the program grinds to a halt; it's simply too inefficient.

Here is my high level pseudocode:
1 Object total
Class Row
Row->cracks = integer (used as a bit array of crack positions, see source code comments for more details)
Row->width = integer width
Row->findTables(allRows, tableHeight, count) = returns an int for the number of possible tables that can be created from an array of possible Row objects allRows, and a size tableHeight, starting from int count. It's fully recursive.
Row->matchesBelow(row) does binary operation on cracks property to determine if they are a match or not.

main()
1. Generate All Possible Row Objects
2. Foreach Row Object, find all its possible matches (Optional. See Below)
3. Foreach Row Object, call findTables method to find every unique path / table
4. Return totalCount

Step 2 is optional, as you can just compare every row to every row in step three, using the matchesBelow method. It slows things down, but reduces some overhead.

If you think you can help, please visit the example page. It's written presently written in javascript (Why? Because a problem as simple as this should be fully capable of working within a web browser, plus, it's easier to share & manipulate an interpreted language). If you need a debugger, use firefox and use firebug or for ie use microsoft visual web developer 2008 express.

# ? Jan 5, 2009 00:04

Avenging Dentist: Oct 1, 2005; oh my god is that a circular saw that does not go in my mouth aaaaagh

ToastedZergling posted:

it's simply too inefficient.

...

It's written presently written in javascript

Hahahahaha.

# ? Jan 5, 2009 00:07

Jo: Jan 24, 2005; Soiled Meat

Avenging Dentist posted:

Hahahahaha.

It's very difficult to disagree with you, but he's right -- if an algorithm is good, it shouldn't matter what the implementation language is.

EDIT:

Jo fucked around with this message at 00:21 on Jan 5, 2009

# ? Jan 5, 2009 00:14

Avenging Dentist: Oct 1, 2005; oh my god is that a circular saw that does not go in my mouth aaaaagh

Jo posted:

It's very difficult to disagree with you, but he's right -- if an algorithm is good, it shouldn't matter what the implementation language is.

No, not really. Most Javascript implementations are incredibly slow. Unless you're using Firefox 3.1, Chrome, or whatever beta version of Safari, you're going to be wasting a ridiculous amount of time. For basic operations like looping, the Firefox Tracemonkey engine is almost 40x as fast as the old Javascript engine.

# ? Jan 5, 2009 00:18

Jo: Jan 24, 2005; Soiled Meat

Avenging Dentist posted:

No, not really. Most Javascript implementations are incredibly slow. Unless you're using Firefox 3.1, Chrome, or whatever beta version of Safari, you're going to be wasting a ridiculous amount of time. For basic operations like looping, the Firefox Tracemonkey engine is almost 40x as fast as the old Javascript engine.

An algorithm that's O(n) can outperform one of O(n^2) even if the implementation is in a language 100x slower, so long as the problem size is large enough.

# ? Jan 5, 2009 00:23

ToastedZergling: Jun 25, 2007; Chubby Walrus:
The Essence of Roundness

Please, stay on topic. This is about reducing an O(2^N) algorithm into something more reasonable. This is the general programming questions thread, not the bash javascript thread. I am running these in the latest versions of firefox and chrome, they're still slow. Making this a multi-threaded java application is not the solution I'm looking for, scalability is.

Edit... uh yeah what he said above :-)

# ? Jan 5, 2009 00:28

Avenging Dentist: Oct 1, 2005; oh my god is that a circular saw that does not go in my mouth aaaaagh

Jo posted:

An algorithm that's O(n) can outperform one of O(n^2) even if the implementation is in a language 100x slower, so long as the problem size is large enough.

Yeah, but according to what he's saying, the problem size isn't especially large. The height of the wall shouldn't even be a factor in terms of the computational complexity, so you only need to optimize row-generation.

# ? Jan 5, 2009 01:17

Avenging Dentist: Oct 1, 2005; oh my god is that a circular saw that does not go in my mouth aaaaagh

Here. This runs in about 10 seconds in FF 3.0 and almost instantly in FF 3.1:

code:

function Row(width, cracks) {
    this.cracks = cracks;
    this.width = width;
    this.potChildRows = [];
    this.memo = {};
}


Row.prototype.findTables = function(allRows, tableHeight) {
    if (tableHeight === 1) {
        return 1;
    }
    else if(this.memo[tableHeight] == null) {
        var count=0;
        for (var i = 0; i < this.potChildRows.length; i++) {
            count += this.potChildRows[i].findTables(allRows, tableHeight - 1);
        }
        this.memo[tableHeight] = count;
    }
    return this.memo[tableHeight];
}

# ? Jan 5, 2009 02:11

ToastedZergling: Jun 25, 2007; Chubby Walrus:
The Essence of Roundness

Wow thank you Avenging Dentist. You made it look too easy... that worked phenomenally. =)

# ? Jan 5, 2009 02:26

rjmccall: Sep 7, 2007; no worries friend; Fun Shoe

Well, let's start with lowering the constant factors of your current algorithm.

You're passing a lot of unused parameters. Don't.
I'm almost positive that none of the current JavaScript implementations ever do CSE on property lookups (including array access). You should really be doing this yourself on expressions like, e.g., rows[i].potChildRows, which can be hoisted out of a hot loop.
Arrays have a push method for appending values to the end of the array, and it really should be faster than what you're doing.

Okay, now, the algorithm. Suppose we're solving WxH. Let R(W) be the number of unique rows of width W, and N(W) be the expected number of potential neighbors for a row of width W. Then your algorithm has these running time recurrences:

pre:

  T_W(W,H) = T_findAllRows(W) + T_findMatches(W) + T_findUniqueTables(H,W)
  T_findAllRows(W) = 1 + T_findAllRows(W-2) + T_findAllRows(W-3)
  T_findMatches(W) = R(W) * R(W)
  T_findUniqueTables(H,W) = R(W) * T_findTables(H,W)
  T_findTables(H,W) = N(W) * T_findTables(H-1,W)

T_findAllRows is O(2^W). Use dynamic programming; you should be able to get it down to θ(R(W)*W) (you can count them in θ(W)).

T_findMatches is θ(R(W)^2); that's asymptotically optimal, I think, but you can cut the constant factor roughly in half by taking advantage of the fact that matchesBelow is symmetric and never reflexive.

T_findTables is θ(N(W)^H). Again, there's a dynamic programming algorithm which can drop this to O(H*R(W)*N(W)).

Finding the dynamic programming algorithms is really the challenge of the problem, so have fun. EDIT: or AD can post one of them, whatever.

rjmccall fucked around with this message at 06:58 on Jan 5, 2009

# ? Jan 5, 2009 02:56

ToastedZergling: Jun 25, 2007; Chubby Walrus:
The Essence of Roundness

rjmccall posted:

awesome stuff

Wow, thank you, I never have seen code written out like that or thought to think about my code like that. What does theta mean exactly? Recommend any books / articles on optimization / dynamic programming?

# ? Jan 5, 2009 06:41

Avenging Dentist: Oct 1, 2005; oh my god is that a circular saw that does not go in my mouth aaaaagh

ToastedZergling posted:

Wow, thank you, I never have seen code written out like that or thought to think about my code like that. What does theta mean exactly? Recommend any books / articles on optimization / dynamic programming?

Big-theta is another notation for asymptotic complexity of an algorithm. O(f(n)) says that a function grows (asymptotically) as fast or slower than f(n), while Θ(f(n)) says that a function grows (asymptotically) as fast as f(n). There's also Ω(f(n)), which says that a function grows (asymptotically) as fast or faster than f(n).

# ? Jan 5, 2009 07:06

rjmccall: Sep 7, 2007; no worries friend; Fun Shoe

ToastedZergling posted:

Wow, thank you, I never have seen code written out like that or thought to think about my code like that. What does theta mean exactly? Recommend any books / articles on optimization / dynamic programming?

This is all just informal reasoning about asymptotic running times. Wikipedia is not the worst imaginable reference for all this, but you'd probably be happiest taking a real course in algorithms from somewhere.

θ(f) is just the set of things that perform asymptotically the same as f. O(f) is really just an upper bound; e.g. I described T_findTabes as O(2^W) because I'm not really sure what it is, but all the others were &theta(something).

# ? Jan 5, 2009 07:42

Avenging Dentist: Oct 1, 2005; oh my god is that a circular saw that does not go in my mouth aaaaagh

Just to be completely nit-picky, you should probably use Θ instead of θ. Not that it matters a ton in this situation, since little-theta wouldn't really make sense (at least not in the sense that Θ is Ο and &Omega).

# ? Jan 5, 2009 08:29

rjmccall: Sep 7, 2007; no worries friend; Fun Shoe

Avenging Dentist posted:

Just to be completely nit-picky, you should probably use Θ instead of θ. Not that it matters a ton in this situation, since little-theta wouldn't really make sense (at least not in the sense that Θ is Ο and &Omega).

Hmm, good point. I've been using θ for ages, but you're right, it's a Θ.

# ? Jan 5, 2009 08:36

hexadecimal: Nov 23, 2008; by Fragmaster

ToastedZergling posted:

Wow, thank you, I never have seen code written out like that or thought to think about my code like that. What does theta mean exactly? Recommend any books / articles on optimization / dynamic programming?

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg.

http://www.amazon.com/Introduction-Algorithms-Thomas-Cormen/dp/0072970545/ref=pd_bbs_sr_1?ie=UTF8&s=books&qid=1231161807&sr=8-1 - this book is rather expensive, but I definitely found it helpful outside the class I had to buy this for.

# ? Jan 5, 2009 14:24

Fly: Nov 3, 2002; moral compass

hexadecimal posted:

http://www.amazon.com/Introduction-Algorithms-Thomas-Cormen/dp/0072970545/ref=pd_bbs_sr_1?ie=UTF8&s=books&qid=1231161807&sr=8-1 - this book is rather expensive, but I definitely found it helpful outside the class I had to buy this for.

There have got to be older editions for sale at a quarter of that price.

# ? Jan 5, 2009 16:45

POKEMAN SAM: Jul 8, 2004

Fly posted:

There have got to be older editions for sale at a quarter of that price.

It'd be worth it at that price anyways. You'll have more luck finding a cheaper/used copy after most universities are well into their second quarter/semester/whatever, as opposed to right now when most students are buying books for the upcoming quarter.

# ? Jan 5, 2009 20:22

Jo: Jan 24, 2005; Soiled Meat

Fly posted:

There have got to be older editions for sale at a quarter of that price.

I picked up a used copy for $20 at the start of the semester.

It was in Chinese. :downs:

# ? Jan 5, 2009 22:26

csammis: Aug 26, 2003; Mental Institution

Jo posted:

I picked up a used copy for $20 at the start of the semester.

It was in Chinese.

That should make it at least 50% more comprehensible :v:

# ? Jan 5, 2009 22:44

UNCUT PHILISTINE: Jul 27, 2006

I work at a Bakery/restaurant, and I need to completely reformat all the recipes, add bakers percentages (each ingredient percentage based on one ingredient, usually the flour), add a "times 2" column for making a double batch, and have them all in the same format (they should have done this years ago).

Right now my boss uses excel, enters the data, fucks around with the cells and makes ugly tables that are difficult to manage, let alone read.

Assuming I have to enter each recipe again (into whatever software), how can I create this new format easily and quickly? I thought about writing a script in some language that takes all the ingredients, finds the percentages, and spits it out into a LaTeX table and then I can easily make PDFs out of them.

Is there an easier way to do this quickly?

# ? Jan 6, 2009 16:24

tef: May 30, 2004; -> some l-system crap ->

Use a web app, and output simple html, and use css to make it less ugly?

# ? Jan 6, 2009 17:34

Mata: Dec 23, 2003

Alright, bear with me on this one.. I'm trying to generate an infinitely large height-map. I want it to resemble a landscape/map of some sort, so I don't want there to be any obviously recognizable patterns, but it can't be "too" random: Hills and mountains have slopes, not random jagged spikes, same with continents and oceans... So I figured, overlapping sine functions with random periods might look good: A huge sine curve would form continents, smaller ones would be mountain ranges, smaller still might make hills, etc: Plus, it "loops" so it doesn't matter wether you're looking at a region at (100000,70000) or at (0,0).

Here's a slightly simplified version of the code:

code:

def calculate_elevation(var)
    period = 0.2
    height = 5
    return (math.sin(var*period)*height) + random.random() * (height/2)

def get_region(self,offset,size):

    for x and y in size:
        terrain.append ( average ( calculate_elevation(x+offset[0]), calculate_elevation(y+offset[1]) ) )


    return terrain

Which looks like this:

So, an infinite field of perfectly symmetrical hills. A single sine function with some noise thrown obviously isn't very complex, and I thought I could work from here by randomly changing the "period" variable so the hills would start forming different shapes, but making "period" random just turns into a mess of noise, since at each pixel the elevation can vary quite steeply. No matter how complicated i tried to make the pattern it just either turned into a noisy mess or (with overlapping sine functions) some elaborate plaid-looking pattern.

I'm ready to abandon the sine approach but I don't know what to try next! Can anyone think of a practical way to do this or should i settle for a finitely large map instead?

# ? Jan 6, 2009 22:04

hexadecimal: Nov 23, 2008; by Fragmaster

This is what I have done before for random height maps that looked smooth.

Read your heightmap from some image file. Then use Photoshop to generate your height map. In Photoshop, just create a whole bunch of noise then use filters to smooth it out, and feel free to use brushes to add hills or valleys, or whatever else you'd like.
Generate random noise in your program, then use a simple smoothing algorithm to smooth it out. You can also add random circles or ellipses here and there to create appearance of mountains, mountain ranges, etc. You can use a simple blending function when you add these random shapes. The simplest one is just add. Also instead of making a circle or ellipse or other shape with uniform values in it, you can try gradient (this will make a nicer slope).

The simplest smooth algorithm is to create a new array that is same size as the one you populated with random noise. Then for so many steps, you take a point from the old array and add up the values of items around it, and divide by their number. So average them. Write new average value in new array, then swap them, and repeat the iterations untill you get more or less smooth image.

# ? Jan 6, 2009 22:21

Avenging Dentist: Oct 1, 2005; oh my god is that a circular saw that does not go in my mouth aaaaagh

Look up "fractal terrain generation".

# ? Jan 6, 2009 22:23

csammis: Aug 26, 2003; Mental Institution

Have you looked at the paper here? Page 10 of the guy's thesis has a very nice height map generated by stochastic subdivision - more complicated than throwing noise into sine functions, but much more realistic results. I don't know whether the map is infinite or not, but there's probably nothing stopping you from extending it indefinitely.

Avenging Dentist posted:

Look up "fractal terrain generation".

Yeah, mine was the first hit for "landscape generation algorithm" :c00l:

# ? Jan 6, 2009 22:24

hexadecimal: Nov 23, 2008; by Fragmaster

csammis posted:

Have you looked at the paper here? Page 10 of the guy's thesis has a very nice height map generated by stochastic subdivision - more complicated than throwing noise into sine functions, but much more realistic results. I don't know whether the map is infinite or not, but there's probably nothing stopping you from extending it indefinitely.

Yeah, mine was the first hit for "landscape generation algorithm"

Wow that seems a lot cooler than my slow rear end smooth poo poo with random shape. You wrote this: http://gameprogrammer.com/fractal.html?

vvvv Oh sorry. Still pretty cool article. Thanks.

hexadecimal fucked around with this message at 23:04 on Jan 6, 2009

# ? Jan 6, 2009 22:58

Adbot: ADBOT LOVES YOU

# ? May 15, 2024 02:04

csammis: Aug 26, 2003; Mental Institution

hexadecimal posted:

Wow that seems a lot cooler than my slow rear end smooth poo poo with random shape. You wrote this: http://gameprogrammer.com/fractal.html?

Why on earth would you think I wrote that?

e: Oh, the word "mine" - I meant the link that I posted.

# ? Jan 6, 2009 22:59

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > The Cavern of COBOL > Ask General Programming Questions Not Worth Their Own Thread

«‹›671 »