Game Development Megathread

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

«‹›622 »

Morpheus: Apr 18, 2008; My favourite little monsters

TSDK posted:

Good grief, you're all making it more complex than it needs to be.

*height-based collision detection*

So you're saying that the player should always be thrown up on top of the object it's colliding with, unless it would be moving up too high, yes? I like this idea, I might try it out.

# ? Oct 22, 2008 00:35

Adbot: ADBOT LOVES YOU

# ? May 12, 2024 12:08

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

Morpheus: Apr 18, 2008; My favourite little monsters

Hubis posted:

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.

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.

# ? Oct 22, 2008 03:18

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

nihilocrat: Jun 8, 2004; all the hep cats jam to "cat /dev/hda1 > /dev/audio"

Morpheus posted:

So you're saying that the player should always be thrown up on top of the object it's colliding with, unless it would be moving up too high, yes? I like this idea, I might try it out.

You'll probably also want to do the same with the top of the bounding box, in case the player jumps up and collides with a sloped ceiling.

Also:

Has anyone thought of taking the various wisdom in this thread and putting it in a wiki of some sort?

If we are in a sharing mood, someone could just copy and paste a few of the 'recipes' to the GameDev Wiki.

nihilocrat fucked around with this message at 17:45 on Oct 23, 2008

# ? Oct 23, 2008 17:43

SlightlyMadman: Jan 14, 2005

Has anyone ever coded an isometric tile map where the tiles have an odd height? The algorithm I'm using works great with an even height, but I can't figure out how to properly handle an odd height.

code:

	def GetPositionForTile(self, pos_x, pos_y, origin_x, origin_y, offset_x = 0, offset_y = 0):
		# get the raw pixel location
		half_width = self.tile_width / 2
		half_height = self.tile_height / 2
		
		shift_x_height = pos_y * half_width
		shift_x_width = pos_x * half_width
		shift_y_height = pos_y * half_height
		shift_y_width = pos_x * half_height
		
		draw_x = origin_x - shift_x_height + shift_x_width
		draw_y = origin_y + shift_y_height + shift_y_width
		
		# subtract the offsets to track the screen
		draw_x -= (offset_x - offset_y)
		draw_y -= (offset_y + offset_x) / 2
		
		return draw_x, draw_y

# ? Oct 23, 2008 18:11

nihilocrat: Jun 8, 2004; all the hep cats jam to "cat /dev/hda1 > /dev/audio"

Ok! I figured out how to get py2exe to work properly.

This is my Spacewar! clone called Raumkrieg (German for .... Spacewar). For now, you actually need to play with another human being.

Click here for the full 805x624 image.

Download the Windows executable here

bzr repo is here, if you swing that way: bzr branch http://nil.cjb.net/raumkrieg/ . The source is under the BSD license so basically do whatever you want with it. Requires Python 2.5, pyglet 1.1.1, pymunk 0.7.1 or above. Psyco is optional.

# ? Oct 23, 2008 22:40

OneEightHundred: Feb 28, 2008; Soon, we will be unstoppable!

TheDingo posted:

What's the general consensus on the Torque engine? I've done some work on my own engine before and found that I often got burnt out before I really reached an end product I was proud of.

Going off of things I've heard from someone who did contract work developing it, there are a LOT of quirks, cobbled-together stuff, and gaps in the content pipeline. It's certainly not bad for the price tag, but it's definitely not something that sounds like it qualifies as "good."

nihilocrat posted:

3D all-in-one game engines seem to be one of the weak spots of open source (also, music composition apps) compared to the commercial alternatives.

Mainly because open-source developers of those projects like to focus on things that are interesting develop rather than crucial to the development process. Good tools, for example, are one of the most important parts of a good 3D engine, but they're boring as gently caress to write so they're dumped to the bottom of the priority list.

quote:

There are a large number of tutorials/examples written for integrating OGRE3D with OpenAL, Bullet, ODE, a series of GUI packages, etc..

Ogre3D and Irrlicht are two of the better ones out there, I'd really recommend staying away from Bullet until they get their poo poo together though. It's one of those projects run by ivory-tower devs who really know their poo poo but think documentation is a luxury. ODE is starting to fall behind the curve while Bullet's trying to get ahead of it, but ODE has extraordinarily good documentation and Bullet has nearly none.

quote:

There are also Irrlicht, Crystal Space 3D, Sauerbraten, and probably some others which don't just concentrate on the 3d engine. Blender also has some sort of game engine built into it which I've never ever looked into (but I probably should!). Don't forget the Quake 3 engine, either, which is open source.

Irrlicht is proven in the field, is making a serious effort to tackle ALL aspects of creating a good game development PLATFORM seriously, and is probably the best choice overall.
Crystal Space 3D has been missing critical features and failing to evolve properly since its conception.
Sauerbraten is more of a proof-of-concept of what is ultimately a very unorthodox level design mentality, I'd say it's lacking in overall flexibility.
Blender Game Engine will make you lose your sanity because using it involves learning to use Blender.
Quake 3's got some difficulties due to its age and the gamecode is overoptimized to the point that it's frustrating to break the mold, but it's extremely cohesive and well-designed.
Panda3D I have not dealt with.

Also consider QFusion, which an upgraded Quake 2 with a lot of good architectural changes that have made it a suitable platform to develop off of. Its network performance is still kind of limp and getting the gamecode out of 10Hz is still annoying, but it's an easier launchpad than Quake 3, is greatly improved over stock Quake 2, and it's much more cohesive than most engine mods which basically involve haphazardly slapping visual upgrades on and ignoring everything else.

I hate to poo poo on most of the selection, but I've spent a lot of time on my own project patching up content pipeline and design holes because the open source projects are so lax on it. In general, they focus too much on the flashy stuff that people like to see in games and far too little on the content pipeline and cohesive architecture that is the entire reason game developers use middleware in the first place.

OneEightHundred fucked around with this message at 19:26 on Oct 24, 2008

# ? Oct 24, 2008 09:28

Bouquet: Jul 14, 2001

I played around briefly with Panda3D. I got scared off by the fact that there seemed to be one main developer and he stopped working on the project in May of 2008. It feels like it never quite crossed the open source threshold of long-term viability, which requires a large enough active team with full access to stuff that if one person disappears the project can keep going.

# ? Oct 24, 2008 18:20

nihilocrat: Jun 8, 2004; all the hep cats jam to "cat /dev/hda1 > /dev/audio"

Bouquet posted:

I played around briefly with Panda3D. I got scared off by the fact that there seemed to be one main developer and he stopped working on the project in May of 2008. It feels like it never quite crossed the open source threshold of long-term viability, which requires a large enough active team with full access to stuff that if one person disappears the project can keep going.

I'm also a little scared off by the fact that it doesn't seem very well engineered and the documentation is bad (like I said before)

One big question I have: I am just now getting around to figuring out how to do network programming for a game. Is it a necessity that my program follow a strict presentation/data seperation similar to the MVC model? If so, how would I implement it in an engine like Panda3D or Cocos2D, which have lots of tools for automatically performing operations over time ("Intervals" or "Actions", respectively) like 'move this node 10 units left over a period of one second' or 'make it fade to alpha=0 over a period of three seconds'. This strikes me as unifying presentation (these are functions which take scenegraph nodes as arguments and operate on them) with data (the 'real' properties of the objects change over time, and are time-sensitive). I don't really know how you could make a cleanly-networked game, including a headless server, and still use these.

# ? Oct 24, 2008 20:56

JohnyTex: Jan 10, 2005

Ok, so it's looking like they finally managed to make XNA games a one-click install:

http://creators.xna.com/en-US/xnags_islive

Haven't tried it myself yet, but if it really does what it says on the tin it's good news for everyone

# ? Oct 31, 2008 04:41

a slime: Apr 11, 2005

I started writing a 2D game using SDL/OpenGL and C++ about a month ago. I have never really done any game programming, and I was basically trying to pick it up entirely via Google. Reading through this thread, it seems like I'm probably doing a ton of poo poo in really stupid ways, as my problems are usually solved by Google linking me to a GameDev.net forum post

I have a lot of questions, but I'll start here: I'm trying to do collision detection. I'll have a lot of high speed objects flying around- after Googling for a while it seems like my best option is enhanced GJK. I haven't buckled down and read any papers yet, I wanted to ask here to make sure I wasn't doing something absolutely retarded. Is there a better alternative? I don't have to deal with rotations at all, I just need to 1) eliminate tunneling and 2) get the time of impact.

Does anyone have any experience implementing GJK in 2D? Will I be able to get it fast enough to handle a fairly busy environment on older machines?

# ? Nov 1, 2008 14:47

JohnyTex: Jan 10, 2005

not a dinosaur posted:

I have a lot of questions, but I'll start here: I'm trying to do collision detection. I'll have a lot of high speed objects flying around- after Googling for a while it seems like my best option is enhanced GJK. I haven't buckled down and read any papers yet, I wanted to ask here to make sure I wasn't doing something absolutely retarded. Is there a better alternative? I don't have to deal with rotations at all, I just need to 1) eliminate tunneling and 2) get the time of impact.

Could you elaborate a bit on your game / collision environment?

# ? Nov 1, 2008 16:47

a slime: Apr 11, 2005

JohnyTex posted:

Could you elaborate a bit on your game / collision environment?

Sure- it's a 2D shooter that is heavily influenced by Space Station 13, a multiplayer sandbox/mystery game. Right now, the idea is eight directional player movement with semi-overhead view (think SNES style, ie. Harvest Moon, Earthbound).

In regards to collision detection, I'm mostly worried about bullets and thrown objects tunneling due to their high speeds. Thrown objects colliding with each other, thrown objects colliding with bullets, that sort of thing.

Another question- I'm using very low-res sprites (16x24 right now)- when these are scaled appropriately for high resolutions (1280x800 in the following case), I see some distortion. Is there a standard way to avoid this kind of thing? Any ideas?

The rightmost pixels on the character's head are malformed- they are not square anymore. The "l" above his head is sometimes straight, and sometimes crooked like in this picture.

# ? Nov 1, 2008 17:16

Scaevolus: Apr 16, 2007

not a dinosaur posted:

The rightmost pixels on the character's head are malformed- they are not square anymore. The "l" above his head is sometimes straight, and sometimes crooked like in this picture.

It's easiest to just write your own scaling routine if you want true squares. Usually built-in scaling uses floating point, which can cause those sorts of artifacts.

Scaevolus fucked around with this message at 22:18 on Nov 1, 2008

# ? Nov 1, 2008 21:09

a slime: Apr 11, 2005

Scaevolus posted:

It's easiest to just write your own scaling routine if you want true squares. Usually built-in scaling uses floating point, which can cause those sorts of artifacts.

Thanks, I think I really wanted you to link me to the Wikipedia page on "Pixel art scaling algorithms"

edit: is it reasonable to only allow 1x, 2x, 3x scaling and so on? And if the user switches to fullscreen, simply choose the largest integer scaling factor that still fits the desired resolution?

a slime fucked around with this message at 22:37 on Nov 1, 2008

# ? Nov 1, 2008 22:16

JohnyTex: Jan 10, 2005

not a dinosaur posted:

Thanks, I think I really wanted you to link me to the Wikipedia page on "Pixel art scaling algorithms"

edit: is it reasonable to only allow 1x, 2x, 3x scaling and so on? And if the user switches to fullscreen, simply choose the largest integer scaling factor that still fits the desired resolution?

If you want to write your own scaling algorithm, nearest neighbour is the easiest to implement (I guess?), but that will only really give satisfactory results if the scale is a multiple of two.

Concerning the collision detection issue:
This answer might seem pretty unhelpful, but is tunneling really going to be that big of a problem? I wouldn't really be worried unless very small objects should be able to collide with each other, and even so I would probably opt for increasing the sizes of their collision boxes as a solution to the tunneling problem.

BTW, just out of curiousity, why did you choose to use C++ / SDL?

# ? Nov 2, 2008 04:18

a slime: Apr 11, 2005

JohnyTex posted:

If you want to write your own scaling algorithm, nearest neighbour is the easiest to implement (I guess?), but that will only really give satisfactory results if the scale is a multiple of two.

Concerning the collision detection issue:
This answer might seem pretty unhelpful, but is tunneling really going to be that big of a problem? I wouldn't really be worried unless very small objects should be able to collide with each other, and even so I would probably opt for increasing the sizes of their collision boxes as a solution to the tunneling problem.

BTW, just out of curiousity, why did you choose to use C++ / SDL?

I went ahead and did what I described before- scale up by the largest integer possible- now GL_NEAREST seems to do the right thing. Crisis averted.

I guess I just want to do collision detection in an extremely robust fashion so I can forget about it. Not to mention GJK sounds like fun... Just not fun enough to do for no reason. Hopefully someone can chime in with some insight.

C/C++ is what I've always worked in, and I like the idea of doing all this from the ground up. I tried messing around in Python a bit- pyglet for windowing and rabbyt for sprites- but there was just too much magic. Maybe I'll switch once I have the chance to write an engine myself, but I like details too much to not at least do it this way once. I went with SDL because portability details are NOT something I enjoy, and I was tired of hacking functionality into OpenGLUT- SDL did everything I wanted out of the box.

# ? Nov 2, 2008 05:46

Mithaldu: Sep 25, 2007; Let's cuddle.

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?

# ? Nov 2, 2008 12:37

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

Mithaldu: Sep 25, 2007; Let's cuddle.

Hubis posted:

How do you divide this?

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

Hubis posted:

Are you trying to find the set of rectangles of minimum count that cover the valid area?

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.

# ? Nov 3, 2008 14:22

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

Mithaldu: Sep 25, 2007; Let's cuddle.

The Hilbert thing could only help in finding big rectangles if i understand this right, yes? It doesn't seem to be particularly accurate about it though and i'd still need to use the algorithm that actually looks for rectangles to verify its results.

Quite interesting read though, so thanks.

# ? Nov 3, 2008 21:27

OneEightHundred: Feb 28, 2008; Soon, we will be unstoppable!

The easiest way would probably be just iterating over the grid, and as soon as you hit an unassigned block, scan out along a single axis as far as you can go, then try to extend it across the other axis until one of the scans fails.

If this is time-sensitive and needs to scale better, then cache the number of consecutive elements found on each scan.

# ? Nov 3, 2008 21:41

Mithaldu: Sep 25, 2007; Let's cuddle.

OneEightHundred posted:

If this is time-sensitive and needs to scale better, then cache the number of consecutive elements found on each scan.

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.

Mithaldu fucked around with this message at 22:49 on Nov 3, 2008

# ? Nov 3, 2008 22:42

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

OneEightHundred: Feb 28, 2008; Soon, we will be unstoppable!

Actually one related thing I'm trying to find: A better UV atlas algorithm, because q3map's stock one is quite inefficient. In this case the sections to atlas are all rectangular, so that should simplify things considerably.

# ? Nov 4, 2008 02:27

slovach: Oct 6, 2005; Lennie Fuckin' Briscoe

OneEightHundred posted:

Actually one related thing I'm trying to find: A better UV atlas algorithm, because q3map's stock one is quite inefficient. In this case the sections to atlas are all rectangular, so that should simplify things considerably.

Maybe Q3MAP2 would be of help? I don't know the technical details other than it's a huge upgrade in comparison to the old compiler. You can find the source of it around, I'm sure.

# ? Nov 4, 2008 08:35

OneEightHundred: Feb 28, 2008; Soon, we will be unstoppable!

slovach posted:

Maybe Q3MAP2 would be of help? I don't know the technical details other than it's a huge upgrade in comparison to the old compiler. You can find the source of it around, I'm sure.

q3map2 is just a naive loop over existing lightmap pages to see if it can drop the lightmap on any of them, and it finds locations by just looping over positions. I get the feeling that's less than ideal, especially considering it'll cause major state trashing if small surfaces added late (which is common with stairs) wind up getting spread over several lightmap pages. q3map2's lightmap allocation in general favors lightmap page reduction over state trashing, which is the opposite of what I want.

I've seen some algorithms that are based on inserting lightmaps aligned with the corners of existing ones, and there seem to be some that do something like attempting to drop in new atlases according to their dimensionality (i.e. lightmaps that are much wider than tall tend to wind up along the top edge), which Sauerbraten does for example, so I'm trying to look in to better specialized algorithms for this sort of thing.

OneEightHundred fucked around with this message at 09:32 on Nov 4, 2008

# ? Nov 4, 2008 09:30

Mithaldu: Sep 25, 2007; Let's cuddle.

Hubis posted:

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.

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

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.

# ? Nov 5, 2008 19:02

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

Kennedy: Aug 1, 2006; hard to breathe?

Edit : Spent the last 4 hours rewriting my code from scratch, and have my Pong bounce working perfect now. I was calling a launch() operation on the ball during the update - so obviously on every refresh the ball was being launched in the same direction, regardless of the reflection from the bounce. I've now called launch() in initialize to set a random direction, and now have ball.move(direction) in update; direction is changed by CheckWallCollisions

Kennedy fucked around with this message at 03:51 on Nov 7, 2008

# ? Nov 6, 2008 21:48

Mithaldu: Sep 25, 2007; Let's cuddle.

Hubis posted:

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

You'd be surprised. ;)

The highlighting isn't perfect, but this should be pretty readable once one knows that $x is a scalar, @a is an array and %a is an associative array (hash): http://code.google.com/p/dwarvis/source/browse/trunk/lifevis/Lifevis/QuadTree.pm?spec=svn241&r=241

Use would be like this:

code:

my $tree = Lifevis::QuadTree->new(
    -xmin   => 0,
    -xmax   => 15,
    -ymin   => 0,
    -ymax   => 15,
    -parent => undef,
    -pos    => undef
);

for ( <map_data> ) {
    $tree->fill($x,$y);
}

my $moo = $tree->get_rectangles;

It seems to work pretty well. If i give it input like so:

code:

  0   4   8   12 15
 00111000000000000
  1111000000000000
  1111000000000000
  1111000000000000
 40000000000000000
  0000000000000000
  0000000000000000
  0000000000000000
 80000000000000000
  0000000000000000
  0000000000000000
  0000000000000000
120000000000000000
  0000000000000000
  0000000000000000
150000000000000000

the result is: "0:3:2:3|2:3:0:1|0:1:1:1|1:1:0:0|"

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.

# ? Nov 7, 2008 17:02

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

Kleedrac: Jan 16, 2008; Mii, myself & I

I've finally got the bulk of my story ready and want to start designing my magnum opus. It shall be an old-school RPG in the vein of Final Fantasy VI (III on SNES.) The problem is I've never actually built a game engine before and I'm not sure where to dig in? I've started writing pseudo-code for what classes I think I'm going to need but where do I start writing? How do I design my own file formats (for saving map data, art/music assets, saves, etc)? I'm using Python and either Pygame or Pyglet (haven't decided yet ... I'm experienced in pygame but after reading the thread perhaps pyglet would be a better choice?) Where do I dig in? I understand that the tools would come after the engine but where to start on the engine? Any advice for class structures? Is there any documentation on game engine (specifically 2D RPG) theory out there that I can't seem to find? Looking for some help from you knowledgeable guys/gals here :v:

# ? Nov 13, 2008 23:02

Benji the Blade: Jun 22, 2004; Plate of shrimp.

Kleedrac posted:

Where do I dig in?

First thing is, put aside all your pseudo-code for classes you think you'll need.

Figure out what the most bare-bones thing you possibly make that might still be remotely useful is, like say, a window that displays a picture. Now make it. Then start improving it really small ways, one feature at a time, by say, making that picture move in response to keyboard input. As the project gets bigger, make sure to take a little time to clean up old code when it's slowing you down, but don't get bogged down in major overhauls. Build tools, either in the engine or separately, only when doing so will actually save you time. Repeat until your magnum opus is complete.

Basically, avoid working on speculation at all times. Make sure you're always working on stuff you need. Do this by taking baby steps and trying out what you've got.

For more detail: http://en.wikipedia.org/wiki/Iterative_and_incremental_development

# ? Nov 13, 2008 23:39

Kleedrac: Jan 16, 2008; Mii, myself & I

Benji the Blade posted:

First thing is, put aside all your pseudo-code for classes you think you'll need.

Figure out what the most bare-bones thing you possibly make that might still be remotely useful is, like say, a window that displays a picture. Now make it. Then start improving it really small ways, one feature at a time, by say, making that picture move in response to keyboard input. As the project gets bigger, make sure to take a little time to clean up old code when it's slowing you down, but don't get bogged down in major overhauls. Build tools, either in the engine or separately, only when doing so will actually save you time. Repeat until your magnum opus is complete.

Basically, avoid working on speculation at all times. Make sure you're always working on stuff you need. Do this by taking baby steps and trying out what you've got.

For more detail: http://en.wikipedia.org/wiki/Iterative_and_incremental_development

Thanks for your ideas

To clarify, however, there is method to my madness. Normally I take an extreme programming approach http://en.wikipedia.org/wiki/Extreme_Programming to things so this does make sense. In this case there are a few other factors which have steered me away from it. Firstly I would like to have this engine so doing a sequel or any other story I feel like writing (I used to run a lot of D&D campaigns but don't have the players these days) would be a cakewalk (especially if I implement some good tools.) Secondly in the extreme programming vein I will be working with a partner on this project. So breaking it up into classes ahead of time will allow us to work separately towards the over-arching goal. Beyond that writing the small code like drawing a sprite and having it respond to movement will be one minor part of this, I'll probably spend far more time on balance issues and tweaking the XP curve and other aspects of monsters, bosses, and player classes (yet another reason that needs to be its own class with inheritance for each and a tool to allow easy editing of the file format which will store it.) Again thank-you for your help, I hope this clears up my intent.

# ? Nov 14, 2008 00:20

Adbot: ADBOT LOVES YOU

# ? May 12, 2024 12:08

Star Warrior X: Jul 14, 2004

Kleedrac: Oh, experienced game-dev goons, I want to make a game, and I have this idea. Please, from your experience and expertise, do you have any advice, for me, a novice?

Benji the Blade: Yes, I would be happy to lend you my knowledge and advice. I think you may be headed down the wrong track, as I have seen many similar projects begin this way and fail without getting anywhere. I recommend you do use this alternate approach.

Kleedrac: Thank you for your kind and helpful ideas. However, in my ignorance, I have decided that the way I intended to do things is best, despite having asked for your input, acknowledging your greater experience and knowledge. Instead, I choose to spurn your advice, and I shall ignore it, despite your implied warnings about my now inevitable failure. I realize that because I approached you with the intent of ignoring your advice, even though I was ostensibly seeking it, that I was doomed from the start.

gently caress you, man.

# ? Nov 14, 2008 03:15

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

«‹›622 »