Game Development Megathread

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > The Cavern of COBOL > Game Development Megathread

«‹›3 »

Hubis: May 18, 2003; Boy, I wish we had one of those doomsday machines...

stromdotcom posted:

For those of you working with XNA, I got a bunch of requests to do a series of tutorials on building animated models with Blender for XNA and finally did it. This has always been a major stopping point for me -- either I hire someone to do it, or the project dies. I always just wanted to know how to whip up something temporary in Blender and get it to work, and then hand it off to a modeler.

Links:

Part 1: Non-UV Texturing
Part 2: UV Texturing
Part 3: Rigging
Part 4: Animating and Exporting

The topic comes up every 5 seconds on the XNA forums, so these were geared towards coders.

Very nice.

# ¿ Mar 20, 2008 15:49

Adbot: ADBOT LOVES YOU

# ¿ Apr 23, 2024 18:32

Hubis: May 18, 2003; Boy, I wish we had one of those doomsday machines...

IcePotato posted:

god drat I am so bad at basic math. I'm trying to calculate the path of a bullet in my top-down strategy game - basically I want to draw the bullet moving at a specific speed until it hits something.
code:
location = new Vector2(orgin.X, orgin.Y);
slope = new Vector2((destination.X - orgin.X),(destination.Y - orgin.Y));

public Vector2 path(GameTime gameTime)
        {
            location += slope / (spd * (float)gameTime.ElapsedGameTime.TotalSeconds);
            return new Vector2((int)location.X, (int)location.Y);
        }
This is wrong - all my bullets appear in the top-left and don't really do much. I have no idea how to fix this because I didn't retain anything from high school math

I'm confused as to why you're dividing your direction vector by speed*time instead of multiplying it, for one.

# ¿ Mar 24, 2008 22:08

Hubis: May 18, 2003; Boy, I wish we had one of those doomsday machines...

heeen posted:

OpenGL/GPU question:
Can I use different filtering for the same texture in the same Scene? does changing the filtering on a texture require a pipeline flush?
As I understand it filtering is done on the TMU, so when I change the filtering on the TMU, this would require all triangles currently in the pipeline for this TMU to be finished first before the new filtering can be applied to new triangles, right?

As I understand it, yes that would insert a bubble into the pipeline.

# ¿ Mar 25, 2008 19:48

Hubis: May 18, 2003; Boy, I wish we had one of those doomsday machines...

ultra-inquisitor posted:

I'm writing a rather specific fragment shader (GLSL but can change to Cg if necessary). I'm hoping to use it to doing picking. Every polygon to be rendered has a unique colour to identify it, and I pass the current mouse position into the shader using uniforms. Thus, in the shader, I can test whether the mouse position is the same as the fragment position, and if it is, I know the mouse is over whichever polygon is signified by the colour.

So the shader knows which polygon is selected, but how do I get this information back to the actual program?

You could use the ARB_occlusion_query extension to get the number of fragments generated that overlap your cursor area. Basically, what you'd do is render each selectable object (wrapped with an occlusion query set/retrieve pair) and have a shader that renders some value (it doesn't matter what) if the cursor overlaps the fragment, or discards the fragment otherwise.

It won't be the swiftest thing in the world, but it would be a lot faster than reading back and parsing framebuffer data from the card.

# ¿ Apr 2, 2008 14:31

Hubis: May 18, 2003; Boy, I wish we had one of those doomsday machines...

krysmopompas posted:

At the same time, it's not like you're yielding the thread at all, do you really expect it to use less than 100%?

There's nothing in d3d that says the vsync wait has to actually sleep or anything.

yeah, from what it looks like, you're running the while loop as fast as possible

# ¿ Apr 14, 2008 02:25

Hubis: May 18, 2003; Boy, I wish we had one of those doomsday machines...

The "right" way to solve this (in my opinion) is to have two threads, one your "game update" thread and the other your "graphics update" thread, which run, at most, at your desired framerate (say 10 hz and 60 hz respectively), and yield time by using a "Sleep(0)" call wrapped with a high resolution timer at the end. Of course, this is somewhat complicated, especially when you have to deal with data protection. A good alternative is to structure your code something like this:

code:

while (!quit)
{
    frameTime = GetTime();
    if (frameTime > lastLogicUpdate + logicUpdateTime)
    {
        UpdateGameLogic(frameTime - lastLogicUpdate);
        lastLogicUpdate = frameTime;
    }

    if (frameTime > lastGraphicsUpdate + graphicsUpdateTime)
    {
        UpdateGamePhysics(frameTime - lastGraphicsUpdate);
        RenderFrame();
    }

    Sleep(0);
}

Each loop through, you (a) update the 'desire'/interactions of your game objects if a certain time limit has passed, (b) update the physical location/graphical properties of your game objects and render them if a certain time limit has passed, and (c) yield the thread to avoid a busy loop.

# ¿ Apr 14, 2008 12:39

Hubis: May 18, 2003; Boy, I wish we had one of those doomsday machines...

cronio posted:

Sleep(0) only yields time to other threads in the same process, so it will still use 100% of a CPU if you're looping like that.

Ahh, you know I never read the spec that way but you're absolutely right. It says it will yield to other threads, but that doesn't necessarily mean other processes. Huh.

# ¿ Apr 15, 2008 19:07

Hubis: May 18, 2003; Boy, I wish we had one of those doomsday machines...

cronio posted:

So it will still expand to use whatever resources are available, it just won't be as greedy as without the Sleep(0).

Right, and more-over if there are no other threads waiting, the thread will immediately resume and the Sleep will essentially be a no-op

So, basically,

code:

while(true)
{
    Sleep(0);
}

Will still peg your CPU at 100%, but won't bog down other applications if they're running as well.

# ¿ Apr 16, 2008 14:17

Hubis: May 18, 2003; Boy, I wish we had one of those doomsday machines...

DBFT posted:

Does anyone have any links to article or just any advice on generating maps for a 2d tile based game?

It is a top down RPG and the terrain will be a natural island so will need to have rocks beaches forrest grass rivers etc. I'm struggling with the theory of how to decide what goes next to what. There must be an article on it somewhere? I've googled with no luck

What exactly do you mean by "Generating maps"?

# ¿ Apr 22, 2008 17:15

Hubis: May 18, 2003; Boy, I wish we had one of those doomsday machines...

DBFT posted:

Apologies if I was vague

I mean procedurally generating the terrain (the grass, water, rock, etc)

If water is 0, grass is 1, rock is 2, tree is 3 and I have an array of integers 50x50 I need to go through that and assign it a value which makes the map look "natural". The joins between different terrain types etc is to be handled seperately so right now I only need to generate what type the terrain is.

One way to do it is to imagine your map as a series of layers - Sand, Rock, Grass, Water, etc. The value in your map of integers specifies the layer that occupies the center of each tile, while the adjacent numbers specify what layers occupy the neighboring tiles. Thus, if I have a terrain map like this

code:

O = Water
X = Land

O O O O
O X O O
O X X O
X X X O

Then my tiles would actually be representing this

code:

OOO OOO OOO OOO
OOO OOO OOO OOO
OOO OOO OOO OOO

OOO OOO OOO OOO
OOO OXO OOO OOO
OOO OXO OOO OOO

OOO OXO OOO OOO
OOO OXX XXX OOO
OOO OXX XXX OOO

OOO OXX XXO OOO
XXX XXX XXO OOO
XXX XXX XXX OOO

Each tile above (All X's, X's with O's across one side, etc) represents a 'variation' in the tile, based on what is occupying the neighboring cell in that direction. These variations can be smoothely transitioned so they look like shore-lines, etc.

Does that make sense?

e:

TSDK posted:

Wang tiling is your friend:
http://en.wikipedia.org/wiki/Wang_tiles

Wang Tiling is a much better approach

# ¿ Apr 22, 2008 17:51

Hubis: May 18, 2003; Boy, I wish we had one of those doomsday machines...

DBFT posted:

If I'm not mistaken aren't the methods you gave me more to do with how the map will appear (blending one tile into another, etc.) rather than making the layout of water/land/rocks/etc look natural?

I looked up Wang Tiles but I can't see how it relates to my problem all that well, I may have not been clear though

Ah sorry, I mis-interpreted again, then.

This is probably the gold standard for what you're looking for: http://www.dwarffortresswiki.net/index.php/World_generation#How_World_Generation_Works

# ¿ Apr 22, 2008 18:18

Hubis: May 18, 2003; Boy, I wish we had one of those doomsday machines...

DBFT posted:

So I would use this to generate a hightmap then use that to decide what is land and water? I think i'll try that out as it seems it works for other people.

I think the best way for the type of game I'm trying will be to attempt something similar to dwarf fortress generating temperature, rainfall etc first then basing the map on that.

If anyone has any other suggestions please tell me

Though this method is theoretically for generating terrain geometries, Dwarf Fortress actually uses something similar to generate it's "elevation map", which in turn influences rainfall, rivers, temperature, and whatnot.

# ¿ Apr 23, 2008 12:37

Hubis: May 18, 2003; Boy, I wish we had one of those doomsday machines...

DBFT posted:

Then it's decided, generating an elevation map using the diamond square algorithm just as soon as I can figure out how to implement it correctly. I'll no doubt be back asking for more help in the future but you guys have been a great help so far thanks.

As a side note, the nice thing about the "multi-pass" method that dwarf fortress uses is that, in theory, each layer (rainfall, temperature, elevation, goodness/evilness, etc) can be both randomly generated for gross content construction and then hand-edited to help maximize "fun-factor". While I'm a big fan of procedural generation systems, I find that they're pretty much useless unless they allow for at least some kind of human intervention to make it ultimately 'fit' gameplay designs. This isn't as important for a sandbox game like dwarf fortress, but is necessary if you want to use tools like this for building more linear content.

# ¿ Apr 23, 2008 15:27

Hubis: May 18, 2003; Boy, I wish we had one of those doomsday machines...

Vinlaen posted:

What are some of the most complete game engines for a indie developer?

I'd like an engine to support simple networking (eg. synchronizing player movement) and allow me to create objects for the player to interact with.

For example, I'd like to create an alarm clock that players can select and it would prompt them for a time (eg. custom scripted dialog box), and then at a set time everybody on the server would have an event fired making them lose health or whatever.

I don't want to have to worry about the engine at all (eg. object selection, collisions, networking, etc).

Does anything like this exist at all?

Look at Ogre 3D or Torque

# ¿ Apr 23, 2008 21:20

Hubis: May 18, 2003; Boy, I wish we had one of those doomsday machines...

fret logic posted:

Anyone here well versed with GLUT? If so how did you get learned in it? I'm not trying to really make anything serious, just kind of getting my feet wet with graphics programming, and I'm not sure if I should be reading up on GLUT specifically or general OpenGL programming. I'm using C by the way.

GLUT's definitely the way to go as far as learning your way around OpenGL and graphics programming are concerned; for building an actual game, you might want to look at a more specialized framework like SDL.

# ¿ May 5, 2008 15:23

Hubis: May 18, 2003; Boy, I wish we had one of those doomsday machines...

heeen posted:

For my project I need a stencil buffer-only write pass, which is the most efficient way to disable writing to the color buffer, glColormask, glBlendfunc or glDrawbuffer?

glDrawBuffer won't do what you want it to do because in that context, 'buffers' are really more like 'surfaces' (Color/Depth/Stencil sets, depending on your dev params). glBlendFunc would be a bad idea since I don't think you'll actually get any sort of savings (i.e. you'll still be paying the full bandwidth cost to be blending a pixel with zero alpha into the buffer) unless you use alpha testing as well, which would kill the entire fragment and mess up your stencil writes. I've always seen glColorMask used to filter out the color buffer in cases like this.

e: "depth testing" => "alpha testing"

Hubis fucked around with this message at 15:11 on May 6, 2008

# ¿ May 5, 2008 20:22

Hubis: May 18, 2003; Boy, I wish we had one of those doomsday machines...

Sigvatr posted:

If anyone is looking for a game artist, then I can help. I have a portfolio of stuff here: http://sigvatr.com/portfolio/

Email me at me@sigvatr.com if you are interested.

Nice stuff; are those screens mock-ups, or from actual games?

# ¿ May 6, 2008 00:42

Hubis: May 18, 2003; Boy, I wish we had one of those doomsday machines...

SkankerX posted:

I'm looking into implementing a templated fixed point class in C++, but before I go reinventing the wheel, does anybody know of an existing one available for download? Most of the ones I've come across don't really cut it.

I don't, but I'm curious as you what you want to use it for. The consensus I had always heard was that fixed point calculations were pretty much un-necessary after the Pentium, due to the relative speed- and accessibility of floating point co-processors. I suppose it might be useful for data packing?

# ¿ May 29, 2008 15:54

Hubis: May 18, 2003; Boy, I wish we had one of those doomsday machines...

SkankerX posted:

Fixed point is still necessary for most portables, including the iPhone (for OpenGL ES) and for the DS (for everything). Having a nice, type safe fixed point class which overloads the standard mathematical operators would go a long way in keeping other dependent code platform agnostic (typedef real numbers as float or fixed, depending).

ahh, that completely makes sense

# ¿ May 29, 2008 17:55

Hubis: May 18, 2003; Boy, I wish we had one of those doomsday machines...

Jo posted:

First question:
I'm thinking about placing the shadow-casting objects in a quadtree, but I'm not sure at what object count the speed benefits will be apparent. My other alternative is to build a list of shadow casters and discard all objects outside the light ~~sphere~~ rectangle. If I use an early out algorithm for detection, can I expect a significant performance improvement in a map with 60-70 shadow casters?

It really depends all on how balanced your pipeline is and where your bottlenecks are. For my money, I'd say an oct-/quad-/bin-tree is a great solution to this. For my money, what you ACTUALLY want to do is to keep TWO spatial hierarchies -- one has all the dynamic lights in it, one has all the dynamic objects in it. When one moves, it intersects it's "bounds" (size of the objects, distance-to-90% attenuation or something for the lights) with the tree for the other class of object, triggering any updates as needed.

# ¿ Jun 2, 2008 11:39

Hubis: May 18, 2003; Boy, I wish we had one of those doomsday machines...

DBFT posted:

What would you guys recommend for getting into games development (to enter the game dev competitions for example).

I'm not new to programming, I know Java and PHP well and have a working knowledge of Ruby (for use with Rails mostly) however I've done very little game development in the past. Really I'm looking for an engine which will cover lots of the stuff for me while letting me be creative.

I've looked at blitzmax but can't find any decent information on how to get started.

Also I'm on OSX so can't use anything Windows only such as that XNA.

I always consider writing a Tetris clone to be the "Hello World" of a new game system (graphics library/framework, language, etc).

Depending on what you're doing, I'd suggest either SDL+OpenGL or Ogre3D. If you're starting with a simple game, then do the SDL+OpenGL route because Ogre3D would be a bit of Overkill

# ¿ Jun 4, 2008 13:28

Hubis: May 18, 2003; Boy, I wish we had one of those doomsday machines...

DBFT posted:

Fair enough. I Guess I'll go with SDL+OpenGL.

I have some knowledge of C so I guess I'll use C and try to fill in the blanks in my knowledge as I go. Does anyone have any recommendations for tutorials/books for beginning with SDL+OpenGL?

NeHe's for scrubs.. Nate Robins is where it's at http://www.xmission.com/~nate/tutors.html

# ¿ Jun 5, 2008 01:32

Hubis: May 18, 2003; Boy, I wish we had one of those doomsday machines...

vanjalolz posted:

Elaborate!!

I hear that NeHe is bad, but there is a LOT more stuff on there than Nate's website.

Yeah, but honestly your average Tutorial on GameDev.net is probably about as good anyways

# ¿ Jun 6, 2008 15:07

Hubis: May 18, 2003; Boy, I wish we had one of those doomsday machines...

FigBug posted:

I'm working on product that has a haptic knob on it, and I want to add an easter egg, so I'm thinking of break out. It seems simple enough, since I don't have much time to work on it. The only thing I don't know is the rule for the ball bouncing off of the paddle. I know the angle varies by the position the ball strikes the paddle, but does anybody know exactly how?

Or, what are some other simple knob based games I could implement that could make use of force feedback? For breakout, I'm just making the user feel a bump as the paddle hits the wall.

There's always the original dial game, "Pong"

# ¿ Jun 19, 2008 16:59

Hubis: May 18, 2003; Boy, I wish we had one of those doomsday machines...

IEatBabies posted:

There are also alternatives to GLUT. There is also SDL, sfml (never used), and, if you're strictly Windows, WGL.

GLUT is primarily just a platform-independent way of creating your window and handling I/O.
http://en.wikipedia.org/wiki/OpenGL_Utility_Toolkit

Also, I would outright refuse to use OpenGL without something like GLEW or GLee

# ¿ Sep 14, 2008 04:27

Hubis: May 18, 2003; Boy, I wish we had one of those doomsday machines...

If you really want to implement something massively threaded, you should look into writing a game engine using CUDA instead.

Dodger_ posted:

The context switches alone thrash the cache to hell and back again. Especially with such disparate threads fighting for cycles.

Not to mention any synchronization he might be doing

# ¿ Sep 14, 2008 18:30

Hubis: May 18, 2003; Boy, I wish we had one of those doomsday machines...

Kimani posted:

Well, you can do that. The system is very flexible!
This is the plan. We'll have, say, 1024 core machines sometime in the future, and this system will take full advantage of them. All new PCs sold today are dual core or better as it is.

Probably not. The "Super-Multi Deep-pipelined core" intel was trying to push 5 years or so ago is pretty much dead, as programmers are having trouble designing individual programs that effectively utilize more than 2 cores (games aside) and the perf/dollar just isn't there. Thus, the move to GPU computing/Larabee.

# ¿ Sep 15, 2008 11:05

Hubis: May 18, 2003; Boy, I wish we had one of those doomsday machines...

Exposing parallelism is good, but only a means to improving utilization -- the efficiency with which you use the sillicon on the processor.

Kimani posted:

Avenging Dentist's examples were supercomputer related. So I figured I'd note that I'm familiar with MPI. There are some other things I've written that are threaded.
He says you need to synchronize two objects to compare them, so I should put them together in the same thread. I say I put representations of both objects in a data structure on the heap, so any thread can access both objects, so you don't need to synchronize them.
Opening up the debugger and freezing it, with 299 threads active, only 18 entities are running. That's, what 6%? The rest are asleep. Each will probably send a couple messages each time they're alive, but it's not like with a 1024 core processor every core will be sending a message at the same time. I do understand, I guess, it just might not be that bad.

What do you think would be a better solution? Getting as much parallelization as possible would, naturally, be ideal. Game logic can be parallelized very nicely ( which hopefully this program shows! ) and I'm betting that collision detection can be as well. Is having a certain amount of worker threads each of which assigned a bunch of entities to loop over better? ( as suggested earlier ) Or maybe something more interesting can be done to better take advantage of what's available.

you can actually get a good deal of parallelism and improve the amount of synchronization needed by "double-buffering" your game state -- having a read-only version of the current world state which all your "threads" (compute tasks mapped to your N worker threads) read from to do their processing, and a write-only buffer to which the threads write their output. After a processing frame, swap the two buffer's modes, so read becomes write and vice versa.

Of course, then your worker threads need to have little (ideally no) overlap in their write output ranges to eliminate contention. This means not relying on intermediate computations from other worker threads, which will require doing some redundant computation in each of your worker tasks; however, this will likely still be more efficient than the overhead from locking or incomplete hardware utilization.

# ¿ Sep 15, 2008 11:29

Hubis: May 18, 2003; Boy, I wish we had one of those doomsday machines...

guenter posted:

Yeah, I use that in the little code sample I posted. It just feels a little dirty - the renderer has to know about particles and any time I add a new kind of effect I would need to modify the renderer.

Maybe you're suggesting I do something with the handle? Do you have any examples I could take a look at? For something that seems like it should be a pretty common problem I'm having a lot of trouble finding references.

You can separate it by having a "ParticleEffectShader" class, which handles the renderer state related to the shader, and a "ParticleShaderEffectProperties" class, which is associated with each effect system instance. When you create/update an instance, you give it it's own ParticleShaderEffectProperties instance, which contains values for the "life", etc. When it's time to render, you feed the particle system instance to the renderer, which feeds (a) the input geometry, and (b) the render state (which should include the ParticleShaderEffectProperties) and it will then feed that to the ParticleEffectShader, which does all the API-level work.

# ¿ Sep 20, 2008 03:36

Hubis: May 18, 2003; Boy, I wish we had one of those doomsday machines...

TSDK posted:

Good grief, you're all making it more complex than it needs to be. The original question is essentially how do you move a 2D character along, given sloped and non-sloped tiles.
[Height Sampler]

This is how it works in Doom/Quake/etc (that's how you can walk up stairs).

If you want to get fancier, to 2D vector math -- just find out if the player's velocity vector intersects the slope line, and if it does project the velocity vector along the slope at the intersection point and make that the new velocity*. If you'd like, I can explain the math involved further, but it's fairly straightforward.

*_{Alternately, you can apply a negative force accounting for the difference in the projected velocity and the original velocity back onto the player.}

# ¿ Oct 22, 2008 01:43

Hubis: May 18, 2003; Boy, I wish we had one of those doomsday machines...

Morpheus posted:

Please explain. I'm pretty certain I know how to do this, but the last thing I want to do is try to debug something where the base math is incorrect.

I'll start with the basics. This is all 2d -- each vector is a 2-component <x, y> value. You have a player with position P, and velocity V. Each frame, you update the world with a timestep dT, so you get
P_new = P_old + dT * V
If your velocity changes over the timeframe dT (because you hit an object), you must find the place in dT where the intersection occured. Your updated becomes
P_new = P_old + dT_1 * V_old + dT_2 * V_new
Note that this can work for an arbitrary number of dividions of dT. Now, we have reduced the problem of re-vectoring to simply finding dT_2 and V_new.

To get the intersection time with the slope, we express the players position with a parametric function PlayerPos(P, V, t)=P+tV, and then intersect that function with a line representing the slope in point-normal form -- a normal vector N and an offset value d. Usually, the point-normal form of a line is specified such that the equation N.P=d is true for any point P on the line. Since we want to find out where the players position intersects with the line, we substitute PlayerPos for P and solve for t:
N.PlayerPos(P, V, t) = d N.(P+tV) = d (N.P)+t(N.V) = d t = (d - N.P) / (N.V)
The distance from the player's position P is equal to t*||V||. If t<dT, then the intersection happens this timestep; dT_1 = t and dT_2 = dT-t. Note that the value of t can be undefined if N.V=0 -- this indicates that the line and the player will never collide (i.e. the velocity is running parallel to the slope). Futhermore, t will be negative if the velocity is heading away from the line.

So now we have P, V, dT_1, dT_2, and N (the normal of the surface). We now just need to decide how to find V_2. At this point, things can get a little more complicated depending on the physics system and level of simulation you are doing. At the simplest level, you can just re-vector the velocity along the slope by projecting the velocity onto the tangent T of the line. In 2D, you can basically just use the slope of the line as a vector and normalize it. You can compute the new velocity as
V_2 = Proj(V_1, T)*T V_2 = (V_1.T)*T
If you want to find the actual force, then you need to go into a bit more depth with the properties of the material (elasticity/rigidity, mass of the player, etc). Ultimately, you'll end up with an impulse force which you can then add to the player's velocity to get the new value. Note that a trivial physics simulation can run into problems if it has no "steady state contact" detection, as the player will just be constantly jittering/"micro-bouncing" off the ground, so it's best if you somehow threshold the values to avoid this sort of error.

# ¿ Oct 22, 2008 13:17

Hubis: May 18, 2003; Boy, I wish we had one of those doomsday machines...

Mithaldu posted:

Just a real quick question: Where would i go to look for algorithms that take a 2d grid of values that are either 0 or 1 as input and then identifies all possible non-overlapping rectangles in it?

this is going to be a tricky problem

0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 1 0 0

How do you divide this? Are you trying to find the set of rectangles of minimum count that cover the valid area? How do you chose between two equally valid options with the same number of rectangles? It seems like it's something approaching a 'discrete backpack' problem, so a heuristic solution may be the best you can do...

e: A simpler example
0 0 0 1 0 0 1 1 0 1 1 0 1 1 0 0

e2: thinking about it, you could probably come up with a naive algorithm based on something like flood-filling that does very well for grids that have mostly rectolinear spaces, even if it would do very poorly in a worst-case scenario.

Hubis fucked around with this message at 14:07 on Nov 3, 2008

# ¿ Nov 3, 2008 13:57

Hubis: May 18, 2003; Boy, I wish we had one of those doomsday machines...

Mithaldu posted:

Here's how i'd like that to be sub-divided:
0 0 1 0 0 0 0 0 0 0 2 2 0 0 0 0 0 0 0 3 0 0 0 4 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 6 6 6 0 0 0 0 0 6 6 6 0 0
0 0 0 1 0 0 2 2 0 3 3 0 4 4 0 0
This. Efficiency is not as important. I'm mainly trying to strike a balance between doing some work every few minutes that takes less than 0.005 seconds for a dataset of (9*8)*(16x16) blocks, where each block is viewed as one unit; as opposed to cycling through each of the tiles in each block on each frame draw.

I also don't mind if it fails in a worst-case scenario, as long as it solves the majority of all cases decently.

Aside from that, i've already got the one characteristic sorted out that will help efficiency most, which is to do multiple cycles with each one restricting the size of rectangle it accepts. I.e. first it only accepts 4x4 and bigger, next cycle 3x3 and bigger, etc.

What i'm figuring however is: Someone else had to have had the same problem before and i'm not a very good mathematician. So basic programmer values tell me to first try find algorithms from such people first, before wasting time on creating a possibly horrible hand-made implementation.

Heh -- I understood the '1's and '0's as having opposite meaning from you (the 0's being clear, and the 1's being blocked). Regardless, I see what you are going for.

This might seem like overkill, but you may do well to re-organize your 2D grid into a linear array that corresponds to points along a Hilbert Curve. The idea is that you can search a linear chunk of values, and if they're all clear then you can expand your search outward. I suspect this may be overkill however, and would be tricky to get right...

I think you're iterative solution (search for the largest boxes, remove them from the data set and resize down) is probably a reasonable optimization.

# ¿ Nov 3, 2008 17:49

Hubis: May 18, 2003; Boy, I wish we had one of those doomsday machines...

Mithaldu posted:

Now THAT is a good idea. Scan once vertically for all columns, then once horizontally, find the point with the intersection of the two biggest ones that do intersect, then expand the rectangle from there. Once maximized, rinse and repeat. Thanks.

you could also try throwing your scene into a very 1-bit implicit quadtree. I.e. your top level node will cover the entire world and contain a single value that is 1 if all the elements within are "open", and 0 otherwise; it's 4 children will each cover a quadrent of the world, and contain a similar value. Repeat until you're down to a 1-tile/1-cell resolution. This would allow you to quickly validate/reject areas.

e: this is actually kind of a generalization of the Hilbert Curve idea I mentioned above, but is a bit simpler.

# ¿ Nov 3, 2008 23:01

Hubis: May 18, 2003; Boy, I wish we had one of those doomsday machines...

Hubis posted:

you could also try throwing your scene into a very 1-bit implicit quadtree. I.e. your top level node will cover the entire world and contain a single value that is 1 if all the elements within are "open", and 0 otherwise; it's 4 children will each cover a quadrent of the world, and contain a similar value. Repeat until you're down to a 1-tile/1-cell resolution. This would allow you to quickly validate/reject areas.

e: this is actually kind of a generalization of the Hilbert Curve idea I mentioned above, but is a bit simpler.

Thinking about it more, you should have 3 states for each node: All_Clear, All_Full, and Mixed. That way you can use the following algorithm

code:

QuadTree nodeTree = BuildTree(world)
List rects = {0}
Queue<QuadTree::Node> toProcess = {0}
QuadTree::Node currNode = root
while (currNode)
    if (currNode.status == All_Clear)
        rects.append(currNode.bounds)
    else if (currNode.status == Mixed)
        for each (childNode in currNode.children)
            toProcess.push(childNode)
    else if (currNode.status = All_Full)
        // Do nothing; no blocks in here
    currNode = toProcess.pop()

This will produce a list of blocks that are fairly reasonably aligned. Obviously, the main problem with this is that it only produces an 'optimal' set if your rooms/blocks/etc are neatly aligned to the quad tree's grid. You might end up with cases where a rectangle could be made bigger by extending it across a node's bounderies. However, I don't think this is necessarially a problem, because after you generate the initial list of rectangles, you can then run another pass over them, merging any rectangles which exactly share an edge.

# ¿ Nov 4, 2008 01:00

Hubis: May 18, 2003; Boy, I wish we had one of those doomsday machines...

Mithaldu posted:

drat, i knew it was a good idea to ask before i went on. This is really a pretty drat awesome method, thanks.

Glad I could help

Mithaldu posted:

I can't read your code very well, as i'm working in Perl, but i've already got a pretty good idea on how to implement this. It's VERY nice, as it allows me to save time by creating the tree while loading the map data. Additionally, the only post-processing it needs is to combine adjacent sectors, but that's done while going through and creating the display lists, so it'll be really fast.

That's ok; as you're working in Perl, I'm sure I can't read your code very well either :xd:

# ¿ Nov 6, 2008 01:37

Hubis: May 18, 2003; Boy, I wish we had one of those doomsday machines...

It now occurs to me that this might work better with an axis-aligned BSP tree, where at each level you basically split the space either horizontally or vertically, chosing a split location that maximizes contiguous space. In fact, now that I think about it I believe this is essentially how Wolf3D worked (And Doom, though Doom used non-axis aligned split planes in its BSP, which in turn was extended out of 2D to 3D for Quake).

This is just a minor optimization though, and can basically be encapsulated in the "BuildTree" function once you get the quadtree working.

# ¿ Nov 6, 2008 15:12

Hubis: May 18, 2003; Boy, I wish we had one of those doomsday machines...

Mithaldu posted:

It doesn't combine rectangles beyond directly adjacent squares, but i'm fine with that unless i missed some really easy way to do that.

You'd probably just have to run the "combine" pass over the set of squares multiple times (each time with fewer squares, as some were combined in the previous pass) until no adjacencies are found.

# ¿ Nov 7, 2008 17:28

Hubis: May 18, 2003; Boy, I wish we had one of those doomsday machines...

Vinlaen posted:

Thanks for all of the help with my other questions but now I have some about networking...

I'm trying to create a "simple" networked/multiplayer 2D game and so I've been trying to a read a lot about networking principles, player synchronization, etc. However, it seems like most articles (eg. gaffer.org) tell you to send keyboard/mouse inputs to the server, have the server process them, and send the results back to the client.

Why?

Is this only done for cheat protection?

What is the disadvantage to sending actual player position to the server and doing a sanity check? It seems like this way is better because then players will know their position even while moving and won't require interpolation or prediction.

Keep in mind that I'm talking about a simple 2D game with different objects moving around, etc.

I'm going to have a bunch of other networking questions I'm sure, and I thought about starting a new thread but hopefully you guys can help me out here.

Your second solution is what Half-Life/Half-Life 2 do. They have the advantage of having less latency -- when you press a key, you move immediatly instead of waiting 2-10 frames to have your input realized. This is good, but the downside is that (a) you now need to make sure the client has all the relevant world state needed to interact with the world properly (so, more data) and (b) if it doesn't update correctly (say some other player moved in your way for example) then you have to overwrite the local value with one from the server, and then have to deal with "bouncing" or "popping" or "lurching" movement, as the world state is changed. So, in some cases it can be more smooth, while in others (esp. those with high lag/packet loss) it can be worse.

It's also a simpler design, since all your logic is being handled in one place, and the specialized client-side physics and rollback code is something else you wouldn't have to write anymore. Unless round-trip latency between client and server are a problem, I'd stick with the "dumb client" model.

# ¿ Jan 15, 2009 16:48

Adbot: ADBOT LOVES YOU

# ¿ Apr 23, 2024 18:32

Hubis: May 18, 2003; Boy, I wish we had one of those doomsday machines...

Bastard posted:

It seems you misread my post. The learning experience is not about learing to make a game, but about what goes on behind the scenes. For a very, very basic example: "User presses button, causing in-game weapon to fire, bullet hits enemy, enemy dies".

This leads to: How does mapping a button to an action work? How do hitscan weapons work? When do you allocate resources such as sound and animation? etc.

Learning things like that is what we want to accomplish for ourselves, not making another Zybourne Clock. In the end, we're programmers, not game designers.

I'd play devil's advocate to this by pointing out that, if you're learning what needs to be done to make a game and in turn how to do it, then you "don't know what you don't know". From personal experience, I'd say the best approach is to try and make a simple game (a Gauntlet clone is a really good example that covers a lot of bases) and take notes on what systems you needed, the way you implemented it, and what improvements/regrets you might have after the fact.

Trying to design a utility library from step one is almost always the wrong thing to do -- you almost always spend too much time overdesigning your system with no gaurentees that the decisions you are making are even any good. It would be much better to do a simple all-in-one program; then for the second iteration, pull out the code you want to keep into a library while re-writing the systems you think could be done better.

# ¿ Feb 18, 2009 16:31

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > The Cavern of COBOL > Game Development Megathread

«‹›3 »