|
Gordon Cole posted:I'm trying to come up with an algorithm to solve a problem that I've never come across before. The situation is thus: You could use a linescan approach. Divide it into lines first, and then collect lines of equal height into rectangles.
|
#
?
Oct 25, 2010 11:41
|
|
|
|
| # ? May 13, 2024 04:27 |
|
|
wlievens: yeah, that was my first thought. If that approach winds up having a bunch of edge cases, you could more generally apply some kind of simulated annealing algorithm.
|
|
#
?
Oct 25, 2010 13:38
|
|
|
You could start by constructing a region quadtree over the grid, marking leaves as either selected or not-selected. The end result would be a structure looking somewhat like so: http://en.wikipedia.org/wiki/File:Quad_tree_bitmap.svg. Then you can just pick all of the selected leaves. If that's not optimal enough, you might be able to modify this whitespace cover algorithm to match your needs. That quadtree you constructed earlier should help to get this one to run fast even with a large number of "obstacles" (unselected tiles), I believe, though you might need to come up with a clever way to pick obstacles fairly to really make it worth it.
|
|
#
?
Oct 25, 2010 14:01
|
|
|
Thanks for all the suggestions. I think I'm leaning towards the quad tree approach. The line scan approach seems interesting, but as I'm understanding it, it sounds a bit more complicated to implement since lines can be discontinuous. A quad tree seems like it will work great though. Thanks!
|
|
#
?
Oct 25, 2010 21:35
|
|
|
I think I would just line scan over it in the horizontal and vertical directions, and encode the one that generated the least rectangles. However, there have been papers written about this, if you care.
|
|
#
?
Oct 26, 2010 02:50
|
|
|
Sweet, thanks for the link. That was exactly the kind of thing I was searching for, but I didn't know the proper term for the problem.
|
|
#
?
Oct 26, 2010 09:00
|
|
|
Anyone have any idea what kind of language developing something like Super Meat Boy would be best suited to? I've seen a lot of those kind of games recently and I'm keen to know what powers it.
|
|
#
?
Oct 26, 2010 14:32
|
|
|
How do you guys find the artists for your games?
|
|
#
?
Oct 26, 2010 15:30
|
|
|
Hanpan posted:Anyone have any idea what kind of language developing something like Super Meat Boy would be best suited to? I've seen a lot of those kind of games recently and I'm keen to know what powers it. I think SMB started out as a Flash game before it was remade for Xbox. Any of the major languages can do a 2D platformer, but Flash is probably faster and easier for that specific sort of game.
|
|
#
?
Oct 26, 2010 15:47
|
|
|
Yakattak posted:How do you guys find the artists for your games? Ah, the age old question for wannabe independent game developers  There are some posts on the XNA forums about this (like where to hunt for artists, etc.) but since you're a goon you probably just want to try stalking goon artists. Either way, if you're not paying they'll probably flake out, if you don't flake out first. Additionally, it's always a million times better to bring a lovely looking (but functional) prototype to the table when trying to find an artist.
|
|
#
?
Oct 26, 2010 16:17
|
|
|
haveblue posted:I think SMB started out as a Flash game before it was remade for Xbox. Any of the major languages can do a 2D platformer, but Flash is probably faster and easier for that specific sort of game. Yea the prototype was a Flash game from what I remember. I'm just wondering what they actually used for the final production because its really solid.
|
|
#
?
Oct 26, 2010 16:45
|
|
|
Hanpan posted:Yea the prototype was a Flash game from what I remember. I'm just wondering what they actually used for the final production because its really solid. I'm fairly sure it's just good ol' C++. I don't think a lot of other languages will run on the xbox, except for XNA, but that's mostly (or exclusively?) used on the indie channel.
|
|
#
?
Oct 26, 2010 16:47
|
|
|
Nev posted:except for XNA, but that's mostly (or exclusively?) used on the indie channel. Not exclusively, but nearly so.
|
|
#
?
Oct 26, 2010 16:53
|
|
|
The game is also for the Wii, so it's most likely written in C++. Well, I'm sure they embed some sort of scripting language like Lua and use that for many things. It's at least not C#/XNA.
|
|
#
?
Oct 26, 2010 16:58
|
|
|
Yakattak posted:How do you guys find the artists for your games? What are you looking for, exactly? 3D models, textures, 2D sprites? There are lots of sites like OpenGameArt (and not-so-kosher sites that have rips from console ROM's and PC games), that might be enough to get you started. Then you can offer to pay a goon cash to create some stuff for you, a lot of the stuff I see there is pretty good. The trouble will be finding someone who is good at making game-specific art.
|
|
#
?
Oct 26, 2010 17:40
|
|
|
I have a question that should be pretty simple - what's the best (or a good) way to make a color-configurable object in 3D, such that you can have ten of the same object with different colors and without ten duplicates of the model and without changing the vertex data between renders? For example, say I wanted to use a flag object with a fixed pattern but three user-configurable colors. I figure one way would be to split the object into three sub-objects and render them each with different colored lighting. Is there a better way than that?
|
|
#
?
Oct 26, 2010 18:55
|
|
|
roomforthetuna posted:I have a question that should be pretty simple - what's the best (or a good) way to make a color-configurable object in 3D, such that you can have ten of the same object with different colors and without ten duplicates of the model and without changing the vertex data between renders? More or less. You'd split up the base geometry into one class and the characteristics of each instance of the flag into a second, then instantiate three of the second that all refer back to the single base instance and have them call the base's render method after setting up their unique transformation and lighting.
|
|
#
?
Oct 26, 2010 19:14
|
|
|
Let's talk map file formats for a tile-based game for a second (either overhead or side-scroller) First thought is to make up some sort of binary file spec, with a header for misc stuff then x*y bytes for the map. Would it make more sense to use some sort of text file format? For some reason something like XML makes my toenails curl, but I can see it making sense. What's a good library to use to read/write formats like that? I'm trying to piece an editor together for maps, because right now I'm just making them in a text editor. code:
|
|
#
?
Oct 26, 2010 22:00
|
|
|
I always use a text format for the basic map data, followed by XML/JSON/YAML/whatever to note the position of entities and so on The library depends on the language. I use yaml-cpp for all my text file needs
|
|
#
?
Oct 26, 2010 22:07
|
|
|
Bob Morales posted:Let's talk map file formats for a tile-based game for a second (either overhead or side-scroller) There's no reason that you can't/shouldn't write an editor that works with the file format you have already, assuming the same rules are in effect (each thing that can be placed is one tile, etc.) It'd be a good starting point at least.
|
|
#
?
Oct 26, 2010 22:21
|
|
|
Ugg boots posted:There's no reason that you can't/shouldn't write an editor that works with the file format you have already, assuming the same rules are in effect (each thing that can be placed is one tile, etc.) It'd be a good starting point at least. I think I'm just having nightmares about doing text i/o in C
|
|
#
?
Oct 26, 2010 23:29
|
|
|
Why wouldn't a solution like OGMO work? The format is going to be different from what you have, but it shouldn't be too difficult to convert, it's really simple at its heart.
|
|
#
?
Oct 26, 2010 23:52
|
|
|
Bob Morales posted:I think I'm just having nightmares about doing text i/o in C Surely you have to do the exact same I/O in order to get the actual game to use these maps. I think there's also the Mappy editor, unless that doesn't exist/work anymore. I've always rolled my own tools and ended up with a crappy miasma of hotkeys and awkward half-right UI elements because I hate writing my own UI controls.
|
|
#
?
Oct 27, 2010 00:01
|
|
|
Bob Morales posted:I think I'm just having nightmares about doing text i/o in C You could always build a mapping tool that emitted C files that contain all the map data in array literals and so forth. 
|
|
#
?
Oct 27, 2010 01:36
|
|
|
Because I am a huge manslut, I will recommend the use of TilED. (http://www.mapeditor.org/) If you can avoid re-inventing the wheel and dodge not-invented-here syndrome, you'll save yourself tons and tons of time.
|
|
#
?
Oct 27, 2010 07:24
|
|
|
I personally use OGMO but it's not really the best, I tend to write a lot of small very specific editors for certain things in as3 with AIR to make up for the shortcomings. I think the key thing with 2D level editors is having the ability to define as much information and behaviour as you want, OGMO does that well for most stuff but could really do with a plugin system (or be open source which Matt is apparently planning on once the code is cleaned up a bit, i'd rather just have him clean it up publicly). Also I never understood why people dislike XML based file formats for things that aren't huge in file size, it's readable, there's a good implementation for every language and DOM really suits a lot of game entity data. I'm guessing a lot of people have bad experiences from Xerces or having to validate for software engineering/web purposes.
|
|
#
?
Oct 27, 2010 16:34
|
|
|
Seat Safety Switch posted:I've always rolled my own tools and ended up with a crappy miasma of hotkeys and awkward half-right UI elements because I hate writing my own UI controls. It's going to be my first 'real' Cocoa app (the editor) so in theory I should just be able to throw something together real quick and the hard stuff will be taken care of for me.
|
|
#
?
Oct 27, 2010 16:57
|
|
|
haveblue posted:More or less. You'd split up the base geometry into one class and the characteristics of each instance of the flag into a second, then instantiate three of the second that all refer back to the single base instance and have them call the base's render method after setting up their unique transformation and lighting. For things that are color-tinged rather than a solid color, you can avoid using an alpha channel by premultiplying and treating the colorization layer as additive.
|
|
#
?
Oct 27, 2010 17:04
|
|
|
OneEightHundred posted:Most games that do this have separate texture overlays for colorable parts.
|
|
#
?
Oct 27, 2010 17:55
|
|
|
You'd make the entire thing a "colorable part" and you have a separate texture for coloration. Like let's say you had a human model with a colorable shirt. You'd have two textures for them, a base which contains all colorable areas and the area corresponding to the shirt would be black. The second texture has everything black except the shirt area, which would be white, or shaded, or whatever. You'd render the whole object, send the coloration as a uniform instead, and render as basetexture+(shirtmasktexture*shirtcolor)
|
|
#
?
Oct 27, 2010 19:47
|
|
|
Still not sure I'm getting how this works - what if you have ten guys with indepenently colored shirts, pants and hats? Would this involve rendering with basetexture and three other textures for each object? And if so, is that really going to be quicker/better than rendering it as three or four objects with only one texture each? Also not getting how you'd do shirtmasktexture*shirtcolor - is shirtcolor being set as a variable in a shader or something? (So far I'm still using the old FVF so I'm not really sure what you can do with shaders.)
|
|
#
?
Oct 27, 2010 21:29
|
|
|
Gordon Cole posted:Thanks for all the suggestions. I think I'm leaning towards the quad tree approach. The line scan approach seems interesting, but as I'm understanding it, it sounds a bit more complicated to implement since lines can be discontinuous. I know you said it doesn't need to be optimal, but I would note that a quad-tree algorithm will be problematic for anything that doesn't lay on or close to the quad tree boundaries. A better approach would probably be something like an axis-aligned BSP, where you basically keep slicing in into two parts until you end up with a completely covered cell (which will be your rectangle). The optimization here will be in how you choose where to put your partition; however, the simplest case (always splitting in the middle) will be exactly as good as the quad-tree approach, so you've got room to improve there in the event of lopsided distributions inside each node.
|
|
#
?
Oct 28, 2010 00:00
|
|
|
roomforthetuna posted:Still not sure I'm getting how this works - what if you have ten guys with indepenently colored shirts, pants and hats? Would this involve rendering with basetexture and three other textures for each object? And if so, is that really going to be quicker/better than rendering it as three or four objects with only one texture each? quote:Also not getting how you'd do shirtmasktexture*shirtcolor - is shirtcolor being set as a variable in a shader or something? (So far I'm still using the old FVF so I'm not really sure what you can do with shaders.) Also FVF is obsolete as of D3D9, having been replaced by vertex declarations, which are better in every conceivable way.
|
|
#
?
Oct 28, 2010 00:25
|
|
|
OneEightHundred posted:Coloration masks are single-channel so you can stuff up to 4 of them in the same texture. quote:Also FVF is obsolete as of D3D9, having been replaced by vertex declarations, which are better in every conceivable way. Sorry if that sounds ungrateful, I do appreciate the advice and am certainly filing it away as a thing you can do with shaders that I didn't know about (especially sneakily slapping four 'grayscale' masks into one texture).
|
|
#
?
Oct 28, 2010 02:47
|
|
|
roomforthetuna posted:Yeah, I have three reasons for still using FVF - one, it's what I wrote the engine to use the second time I rewrote it, and it seems silly to rewrite it again if I don't desperately need to, two, my target platform is "somewhat outdated machines and up" Shaders are something worth learning BECAUSE they make things a lot easier, instead of trying to do stupid tricks with the state machine to produce effects you want, you just hammer out some shader code blurb which tells it to do EXACTLY what you want it to do in very no-bullshit fashion.
|
|
#
?
Oct 28, 2010 16:42
|
|
|
OneEightHundred posted:DX9 is a pretty reasonable minimum target right now, it hits things as low as the 915G and FX5200. Doing shaders in DX8 will drive you insane since it's low-level and inconsistent across vendors. Seconding this. You shouldn't even need to rewrite that much of your engine anyways, since you could just use shaders/FVF side by side. Heck, I'd implement support for shaders just to be able to quickly reload and debug graphic glitches. If I were you I would at least consider downloading some samples/tutorials with shaders to toy around with them and see what they can do for you.
|
|
#
?
Oct 28, 2010 17:55
|
|
|
Basically the instant you want bumpmapping, you'll quickly start seeing the advantages of shaders. Without them, you need goofy poo poo like directional cubemaps, you'll quickly run in to texture unit limits, and trying to combine multiple effects will combine all of the previous problems into endless frustration. Don't even get me started on how horrible it is trying to do bumpmapped reflection without shaders or in DX8 compared to how trivial it is with shaders. Regarding the FVF point in regard to hardware targets, there is very little reason to target anything below DX9 as a minimum. The 915G, which has been Intel's low-end shitpiece since Vista came out (2006) and has the horsepower of a GeForce 2, supports DX9. Nearly everything bad about DX8 was either resolved or given a non-bad alternative in DX9, and the non-bad alternative to FVF are vertex declarations. If you REALLY need to target below DX9, use OpenGL instead, the Direct3D API pre-9 is pretty brain-damaged. OneEightHundred fucked around with this message at 18:35 on Oct 28, 2010 |
|
#
?
Oct 28, 2010 18:19
|
|
|
OneEightHundred posted:If your target minimum is DX9, you should be using vertex declarations, not FVF. Eh, just checked my girlfriend's new-low-end laptop and it supports DX9 and puxel shader 3, so I guess it probably would be okay to stretch my low-end support up that far. That said, I'm very unlikely to need or want any of the really clever stuff for my project - it's pretty much comprised of 2D stuff (some of which is made of basic 3D to produce a "Flashback" sort of look). As such I barely even need texture mapping (except as used for sprites), and certainly bump mapping would be ridiculous in this context. Edit: But I should probably learn shaders anyway because my backburnered project will certainly want some of that prettier-looking stuff. roomforthetuna fucked around with this message at 18:52 on Oct 28, 2010 |
|
#
?
Oct 28, 2010 18:44
|
|
|
I'm pretty sure the FVF/declaration mapping requirement only applies when you're using fixed-function.
|
|
#
?
Oct 28, 2010 18:49
|
|
|
|
| # ? May 13, 2024 04:27 |
|
|
roomforthetuna posted:I was aiming for a minimum of "Direct3D 9 Drivers without Pixel Shader Version 3 Support" (as a piece of Microsoft documentation calls it), for which the requirements for using vertex declarations include that the declaration must map precisely to an FVF. Is this a model not worth supporting any more? (Again, this is what my previous was-high-end-at-the-time laptop was capable of.) We still target PS 2.0 graphics cards at work and while it has its limits, I can think of a myriad of cool effects I could do in a 2D game that would be trivial to implement using shaders and nightmarish to implement otherwise. I think if you just learn a little bit of what shaders are capable of and realize how easy they are to manipulate, you will suddenly have tons of ideas that you will want to squeeze into your game
|
|
#
?
Oct 28, 2010 21:24
|
|